늘 겸손하게

DP 문제를 처음으로 스스로 풀었네요 문제 풀이 모든 경우를 다 구하려면 시간 초과가 나오므로 dynamic programming으로 풀어야 한다. 1. 합이 최대가 되는 경로에 있는 수의 합을 출력해야 하고, 위에서 아래로 내려갈 때 더 큰 숫자가 있는 방향으로 나아가야 하므로 두 개의 숫자를 비교한 후 더 값이 큰 숫자를 반환하는 함수를 만들어두자. 2. 삼각형의 맨 위에서 아래로 내려가는데, 더 큰 수가 있는 방향으로 내려가고 더 큰 수를 합하면서 맨 아래까지 내려가야 한다. -> 이 과정에서 지금까지 합한 값을 기록해야 하고 다음 값을 계산할 때 기록한 값을 사용한다. 3. edge case 주의 : 맨 오른쪽 정수는 바로 윗줄의 맨 오른쪽, 맨 왼쪽 정수는 바로 윗줄의 맨 왼쪽만 선택 가능하다...

큐를 이용하라고 했지만 일차 배열로도 충분히 풀 수 있는 문제이다. 문제 풀이 1. 길이가 n인 배열을 준비하고 1부터 n까지 저장한다 2. 선형으로 배열의 원소를 하나씩 참조한다. 3. 검색하면서 0이 아닌 원소가 있다면 counter값을 1 증가시킨다 4. counter값이 k와 동일해지면 해당 인덱스의 원소 값 출력, 해당 인덱스 값 0으로 변환 5. 배열에 0이 아닌 숫자가 더 이상 남아있지 않을때까지 반복한다 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #inclu..

두 수의 합 투 포인터 기법으로 x 값에 해당하는 (ai , aj ) 쌍을 찾는 문제 문제 풀이 1. 서로 다른 n개의 자연수를 입력받아 배열에 저장한다. 2. 배열을 정렬시킨다. 3. 2개의 변수를 준비하여 한 개의 변수(lp)에는 배열의 첫 번째 인덱스 값을 저장하고 다른 한 개의 변수(rp)에는 배열의 마지막 인덱스값을 저장한다. 4. 정답 개수를 저장할 변수를 준비한다. ( ans ) 4. 배열[lp] + 배열[rp] 값이 x 값보다 작으면 lp++ 5. 배열[lp] + 배열[rp] 값이 x값보다 크면 rp-- 6. 배열[lp] + 배열[rp] 값이 x값과 동일하면 ans++ , rp--; 7. lp < rp일때 동안 반복 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..

출처 : https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 문제를 풀기 위해, 문제를 여러 개의 하위 문제 (subproblem)으로 나누어 푼 다음, 그것을 결합하여 최종 목적에 도달하는 것 하위 문제의 해결방법을 찾았는데 같은 하위 문제가 계속해서 나올 경우 계산 횟수를 줄일 수 있다. 출처 : https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182 이름은 다이내믹 프로그래밍이지만 전혀 다이나믹하지도 않고 프로그래밍이라기보다는 테이블을 만드는 기법입니다. 대표적인 동적 프로그래밍으로 ..