Hoguz

하노이의 탑의 경우 이를 패턴 확인 및 동적으로 접근하고자 했다가 함정에 빠졌다.

단순 옮기는 횟수를 구하는 것은 위에 처럼 하면 쉽게 나오지만

문제에서 원하는 것은 바로 실제로 옮긴 방법이기에 재귀로 접근하였다.

하노이는 중앙으로 옮기는 경우, 중앙에서 끝으로 옮기는 경우로 보는 것과

제일 큰수를 끝으로 옮기는 경우, 제일큰수-1 까지를 중앙으로 옮기는 경우, 두가지를 모두 복합적으로 생각해야한다.

또한 숫자를 옮긴다는 것을 start, temp, end로 구분하여 재귀를 돌때 이것이 변하게끔 조정하는게 핵심이다.

이부분이 제일 어렵다, 생각해내는게.

예를 들어 n=3인 경우에 1은 처음에 세번째 탑으로 가고 2를 옮긴 뒤 두번째 탑으로 가고 3을 옮긴뒤 첫번째 탑으로 간 다음 제일 마지막에 세번째 탑을 가야한다.

이렇게 탑을 움직이는 것을 start, end를 통해 표현하고 그럴 파라미터로 조정하게끔 하는것, 그것이 핵심이다.

그렇기에 재귀로 들어갈때 start, temp, end가 서로 다르게 바뀐다.

레벨 3 멀리띄기 문제.

문제는 간단하다. 00이는 멀리띄기를 1칸 또는 2칸 할 수 있다.

자연수 n칸을 줄때 00이가 n까지 갈 수 있는 경우의 수를 구하라.

만약 4를 건네주면

1,1,1,1

1,2,1

2,1,1

1,12

2,2

로 총 5가지의 경우가 나온다

이런 문제는 당연히 DP로 접근을 해야하는데 지난번 풀었던 문제와는 살짝 다르다.

지난번 동전문제는 1,2,1 이나 2,1,1 이나 결국 같은 것으로 인식하지만 이 문제는 그렇지 않다.

하지만 지난번 거스름돈 문제를 풀면서 느낀점은 쪼개서 해결할 수 있다는 것이었고

이 문제 역시 쪼개서 풀도록 노력하였다.

이 문제를 1,2,3,4 의 숫자를 각각 경우의 수를 풀어쓰면 좀더 쉽게 이해 할 수 있다.

결국 4라는 숫자는 3에 1을 더한 경우와 2에 2를 더한 경우이기에

결국 4의 경우의 수는 3과 2의 경우의 수를 더한 것과 같고

이를 정리하게되면 피보나치 수열이 된다..

껄껄

레벨3, 거스름돈 문제,

문제는 매우 간단하다.

총 금액과 동전의 종류를 건네주고 이에 대한 경우의 수를 계산해낸다.

예를 들어 5원, [1,2,5] 가 들어오면

1 * 5, 1*1 + 2*2, 1*3+2*1, 5*1 로 총 4가지의 경우가 나온다.

이렇게 무언가가 쌓여야 하는 문제는 기본적으로 동적 프로그래밍으로 접근을 해야한다는 것을

알고는 있으나 여기서 더 나아가지 못했다.

이번 문제를 통해서 알수 있는것은 동적프로그래밍은 개념은 방법이 아니라 어떻게 테이블을 구성하냐는 점이다.

정리한 노트 이미지가 올라가질 않는다...

파일로 넣으니 올라가네

문제는 위와 같다.

단순히 보게 되면 이는 3진법을 물어보는 문제같다.

하지만 3진법과는 다르다.

기존 3진법과 다른 점은 나머지를 어떻게 표현하는가, 정확히 말하자면 나머지가 0인경우의 대처법이다.

기존의 진법들은 나머지를 0으로 함으로서 1의 자리가 0이 되게끔 하나 124는 나머지가 0인 경우 1의 자리를 3으로 고정시킨다.

위 처럼 같은 21을 나누어도 210, 144 이런 모양이 발생하는 이유는 나머지의 처리때문이다!!

레벨 1을 어서 다 끝내야겠다는 생각으로 붙은 문제인데..

효율성에서 무너졌다.

문제는 너무 간단해서 직접 칠수 있을 정도있다.

숫자를 주면 1부터 그 숫자까지의 범위 안에서 소수를 찾아라 

예를 들어 10을 주면 2,3,5,7이 소수이므로 4를 리턴 하면 된다.

여기서 잠깐 든 생각이, 배수들 중 잘 나오는수? 를 생각해보면

2, 3, 5, 7, 이렇게 말고는 없다고 판단 = > 두번째 for문의 범위를 2,3,5,7로 한정 지었다

O(N)으로 줄었지만 정답이 아예 아니다.

왜냐면 1~10이 커버칠 수 있는 제곱의 범위, 즉 120까지는 가능하나 121부터, 11, 13 등을 약수로 갖는 세자리 숫자가 등장하기 때문.

그렇다고 얘네를 모두 넣어줄 수도 없기에 결국은 일반화된 식을 찾아야만 한다.

자연수 n 개로 이루어진 집합 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

제한사항

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

우선 이 문제를 직관이 아닌 수학적 접근을 통해 증명한 승완이에게 박수를 보낸다...

(차후에 증명을 정리하면 추가해야지..)

이 문제 역시 예산 처럼, 제약조건이 있는 상황에서 최대값을 뽑는 문제이다.

예를 들어 변수가 3개라 할때 x + y + z  = N , xyz = ? 식의 구성이라 라그랑주로 접근할수도 있다(!!!!)

물론 난 그렇게 못한다..

직관적으로 접근해보면 어떤 경우에 가장 클까?

곱한 값이 가장 크려면, 가장 큰 애들끼리 곱하면 된다.

즉, 9를 두개의 수로 나누어서 곱한다고 할때, 제일 큰 수가 나오게 나누면 된다

이 얘기는 9의 평균 값, 4.5 * 4.5로 하면 가장 큰 값이 나온다는 뜻이다.

만약 9을 3개의 수로 나누어서 구해야 한다고 하면 당연히 3, 3, 3이 제일 크다.

(이러한 직관적 접근을 승완이는 수학적으로 접근하여 증명하였다!!!... 라그랑주 or 산술평균과 기하평균을 통해서...)

그렇기 때문에 평균에 가장 근접한 숫자들을 구해서 곱하면 된다.

물론 이렇게만 생각하면 한가지 큰 실수가 발생한다.

(나는 여기서 몫을 구하고 남은 나머지를 그냥 다른 하나의 값에 모두 더했다. 그리고 틀렸따...)

11을 3개의 숫자로 구성한다고 생각해보자.

1) 11을 3으로 나누면 3이 나온다.

2) 3, 3, 3의 총 3개의 숫자와 2가 남는다.

3) 남은 2를 3개중 아무거나에 더하면 3, 3, 5가 된다

4) 정답이 아니다.

왜 3,3,5는 정답이 아닐까? 

(정답은 3,4,4 이다.)

11을 다시 3으로 나눠보자, 자연수가 아닌 실수까지.

그러면 3.6... 이 나온다.

즉 가장 큰 값은 3.6 * 3.6 * 3.6이고 결국 우리가 구하는 값은 이에 가장 가까워야한다.

3, 3, 5

3, 4, 4,

이 두개의 수중 누가 더 3.6, 3.6, 3.6에 가까울까?

후자이다...

나는 위에까지 생각을 못했다...

이러한 사실을 알도 코드를 수정해봤지만 시간초과가 뜬다.. 슬프다

프로그래머스 레벨2와 섬머 코딩 문제.

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원해 줄 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

• d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
• d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
• budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.
• 물품을 구매해 줄 수 있는 부서 개수의 최댓값을 return 하세요.

부서 // 예산 // 결과값

1,3,2,5,4 // 9 // 3

2,2,3,3 // 10 // 4

문제가 상당히 길고, 거창하지만?? 생각보다 간단하게 접근하여 풀었다.

문제의 핵심은 어떤 부서인가가 아닌 최대의 부서 갯수를 구하는 것이기에 최대 갯수에 집중을 하면 된다.

그렇기에 가장 작은 값(가장 작은 예산)을 하나씩 없애고, 이 예산을 더하면서 주어진 값보다 커지는 순간의 갯수를 계산하면 된다.

즉 1 + 2 + 3 + 4 에서, 4가 되는 순간 9 보다 예산이 오바 되므로 4를 제외한 1,2,3부서, 총 3개가 최대 부서의 갯수라 할 수 있다.

같은 원리로 좀더 간단히, 슬라이싱을 이용하려면

1. 리스트 sort

2. 슬라이싱을 통한 더하기(lst[:d] )

등으로 간단히 구현할 수 있다.

피보나치 수열은 재귀식으로 너무 유명하다

f(0) = 0

f(1) = 1

f(n) = f(n-1) + f(n-2)

인데, 이걸 재귀식으로 하여 돌리면 실제론 무진장 오래 걸린다.

기본적으로 함수가 실행되면 stack으로 쭉쭉 위에 쌓이기 때문에 좀만 큰 숫자를 넣으면 동작이 안될것이다.

이럴땐 간단히 동적프로그래밍을 통해서 구현할 수 있다.

동적프로그래밍의 핵심은 기억해놓는것, 저 멀리 있는거를 나중에 가져오는게 아니니까 미리미리..

파이썬 코드로 하면 이러하다

a = 0;

b = 1;

for i in range num:

a, b = b, a+b;

return b

우리가 필요로 한건 앞에 두개의 숫자만 필요로 하니까 주구장창 두개만...사용.

동적프로그래밍 개념을 알아도 실제로 적용하는 것은 매우 힘들다. 후

문제가 상당히 길다.

문제 설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.

마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.

앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.

이전에 등장했던 단어는 사용할 수 없습니다.

한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.

2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.

3번 사람이 자신의 첫 번째 차례에 know를 말합니다.

1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.

(계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항

끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.

words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.

단어의 길이는 2 이상 50 이하입니다.

모든 단어는 알파벳 소문자로만 이루어져 있습니다.

끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.

정답은 [ 번호, 차례 ] 형태로 return 해주세요.

만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

입출력 예

n  words  result

3  [tank, kick, know, wheel, land, dream, mother, robot, tank]  [3,3]

5  [hello, observe, effect, take, either, recognize, encourage, ensure, establish, hang, gather, refer, reference, estimate, executive]  [0,0]

2  [hello, one, even, never, now, world, draw]  [1,3]

입출력 예 설명

입출력 예 #1

3명의 사람이 끝말잇기에 참여하고 있습니다.

1번 사람 : tank, wheel, mother

2번 사람 : kick, land, robot

3번 사람 : know, dream, tank

와 같은 순서로 말을 하게 되며, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한 tank와 같으므로 3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다.

입출력 예 #2

5명의 사람이 끝말잇기에 참여하고 있습니다.

1번 사람 : hello, recognize, gather

2번 사람 : observe, encourage, refer

3번 사람 : effect, ensure, reference

4번 사람 : take, establish, estimate

5번 사람 : either, hang, executive

와 같은 순서로 말을 하게 되며, 이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. 따라서 [0, 0]을 return하면 됩니다.

입출력 예 #3

2명의 사람이 끝말잇기에 참여하고 있습니다.

1번 사람 : hello, even, now, draw

2번 사람 : one, never, world

와 같은 순서로 말을 하게 되며, 1번 사람이 자신의 세 번째 차례에 'r'로 시작하는 단어 대신, n으로 시작하는 now를 말했기 때문에 이때 처음 탈락자가 나오게 됩니다.

문제가 이정도 이다.

근데 막상 읽어보면 엄청 복잡한 문제는 아니다.

기초 로직을 생각하자면

첫 단어가 나오고 그 단어의 끝 글자와 다음 단어의 첫글자를 비교,

다를 경우 return하고

같을 경우 나온 단어(첫단어)를 빈 리스트에서 더한다.

그리고 다음 단어는 방금 더해진 리스트 내에서 유무를 확인하고 있으면 return, 없으면 위로 다시 진행.

만약 return이 안되고 다 돈다면 다 맞는 경우이니 return 0,0

알고리즘 자체는 어렵지 않다. 다만 결과값을 내는 방법에 대해 좀더 고민 중이다.

# 6월 18일 수정

결과값을 내는 방법 자체는 매우 쉽다.

몇번의 예시를 돌려보면 된다.

중요한 것은 결과값을 내기 위한 인덱스를 어떻게 지정하는가 이다.

처음에 내가 문제를 풀때는 인덱스를 0부터 시작하게 했다.

이렇게 할 경우 문제가 i번째에 걸리 수도 있고 또는 i+1번째에 걸릴 수도 있고, 이렇게 서로 다른 경우가 발생하다 보니

이 다른 경우를 해결 하기 위해 코드가 길어지고, 또 다른 경우가 발생하기도 했따.

(4번의 경우가 실패했따.. 아직도 이유는 모르겠지만 뭔가 틀렸겠찌)

그렇기에 코드를 간략히 하고 정확성을 높이기 위해 1부터 시작하고, 대신에 비교를 i-1로 하였다.

코드가 훨씬 간략해졌다. 기존에 서로 다른 경우에 따라서 나누기를 다르게 할 필요도 없고..

무엇보다 안되는 경우가 없다. ㅎㅎㅎㅎ

'''땅따먹기 게임을 하려고 합니다. 

땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 

모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 

각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 

같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.'''

# 땅따먹기 역시 동적 프로그래밍으로 풀었따.

내 힘으로 풀어서 너무 기분이 좋구나.. 좀 시행착오도 많긴했따.

문제는 이러하다

[[1,2,3,5],

[5,6,7,8],

[4,3,2,1]];

위와 같은 배열이 있을 때 열이 중복 안되게 하여 최대 값을 구하는 것이다.

이런 경우 5 + 7 + 4 = 16이 제일 큰 경우가 된다.

위에서 언급 했듯이 이는 다익스트라 알고리즘과 매우 유사하다.(최소냐 최대냐의 차이일뿐)

최대값을 비교하고 이를 업데이트 하는 동적프로그래밍 개념을 다시금 사용하였다.

처음에 이 문제를 접근하려 했을때는 동적프로그래밍을 염두 했음에도 불구하고 row, column을 제어하려고 노력하였다.

그리고 가장 잘못 생각했떤게, 한번에 max를 찾으려고 했다는 것이다.

무슨 의미냐면 1부터 시작할 경우, 6,7,8에 1을 더한 값을 구한 후 바로 3,2,1 에 이를 계산 하려고 했다.

모든 경우의 수를 다 생각을 해서 해야했기에 이는 최소 O(N^3) 의 시간 복잡도가 필요했을것이다

하지만 다익스트라를 보면

다익스트라는 한번에 마지막 노드까지 전진하지 않는다. 시작 노드에서 다음노드로, 또 해당노드의 값을 계산 하고 이를 업데이트 하고 넘어간다. 

그렇기에 이 문제에서도 1번으로 6,7,8을 계산 한 후, 2번으로 다시 계산하고 값을 비교하고 업데이트 하는 식으로 하면 된다.

로직은 다음과 같다.

1. 처음 시작은 0번 로우의 원소들이다.

2. 2번 로우의 원소들과 비교한다

- 여기서 비교는 1번)(오리지널 원소)와 2번)(시작 노드 + 오리지날 원소 값)을 비교해서 1번)이 작으면 그 값을 2번으로 바꿔준다.

- 비교해야하는 주체가 필요하므로 나는 복제 테이블을 하나 만들어서 오리지널 원소는 복제테이블에서 뽑아오고 업데이트는 다른 리스트를 해주었다.

3. 반복.

1번에서 시작하면

[[1,2,3,5],

[5,6,7,8],

   7,8,9 가 되고 모두 오리지널 보다 크므로 값이 바뀐다. 

[4,3,2,1]];

바뀐후

[[1,2,3,5],

[5,7,8,9],

[4,3,2,1]];

이제 2번에서 시작한다.

[[1,2,3,5],

[5,7,8,9],

7,   9, 10 2번 + 2번째 원소들의 합이 오리지널보다 더 크다. 업데이트 하자.

[4,3,2,1]];

[[1,2,3,5],

[7,7,9,10], 7은 2번과 같은 인덱스이므로 문제의 규칙에 따라서 적용되지 않았다.

[4,3,2,1]];

다음은 3번이다.

[[1,2,3,5],

[7,7,9,10],

8, 9,  , 11 역시 모두 큰 값이므로 업데이트 해준다

[4,3,2,1]];

이렇게 반복을 하면 된다.

코드 상에서 row를 움직이기 위해 변수를 하나 선정한후 while로 돌렸다.

이게 최선의 코드는 아니나 효율성에서도 큰 문제 없이 돌아갔다.