1. 문제 2. 접근 방법 이분 탐색 알고리즘으로 접근하되, 찾고자 하는 숫자가 시작하는 지점, 끝나는 지점을 찾아야 한다. 즉, 변형된 이분 탐색 알고리즘이라고 생각하면 된다. 찾고자 하는 숫자 이상의 값이 처음으로 시작하는 지점은 Lower Bound 라 하고, 찾고자 하는 숫자 초과의 값이 처음으로 시작하는 지점은 Upper Bound 라고 한다. 우리의 목표는 Lower Bound와 Upper Bound를 구하고, 두 지점의 차이만큼을 구해 가지고 있는 카드의 숫자를 구하는 것이다. 입력이 6, 3, 2, 10, 10, 10, -10, -10, 7, 3 이라고 했을 때, 우선 이분 탐색을 위해 정렬시킨다. 그럼 -10, -10, 2, 3, 3, 6, 7, 10, 10, 10 과 같이 정렬된다. 여..

1. 문제 2. 접근 방법 '알고리즘' 하면 빠질 수 없는 문제, '다이나믹 프로그래밍' 하면 빠질 수 없는 문제! 그 유명한 배낭 문제 (Knapsack Problem) 되시겠다. 나는 이 문제를 처음 접했을 때, 그러니까 대학교 3학년 시절에는 당연하게도 모든 경우의 수를 대입하는 무식한 방법을 택할 수 밖에 없었다. 그도 그럴 것이, 당시에는 DP의 개념도 몰랐었을 뿐더러 마땅한 해결책이 떠오르지 않았기 때문이다. 이렇게 문제를 풀었을 때는 각 물건 당 넣을지 안넣을지의 경우가 가능하므로, O(2^n) 이라는 어마어마한 시간 복잡도가 나오게 된다. 만약 물건이 100개라면 2의 100승이니까... 얼마나 무자비한 계산인지는 상상에 맡기겠다. 자! 그렇다면 본격적으로 다이나믹 프로그래밍의 개념을 적용..

1. 문제 2. 접근 방법 다이나믹 프로그래밍 문제이다. 이틀에 걸쳐 다양한 접근 방법을 생각해보았으나, 결국 내 능력의 한계로 풀지 못해서 답을 봐야만 했다. 나에게 좌절감을 안겨준 문제이자, 동시에 자극을 준 문제이기도 하다. (더 열심히 해야겠다!) 어쨌든... 접근 방법은 다음과 같다. 위와 같이, 비교 대상인 두 문자를 각각 행과 열로 가지는 배열을 생성한다. 여기에서는 각 시작 문자 앞에 '0' 을 추가하여 0번 행과 열은 모두 0의 값을 가지게 한다. (계산을 위함) 그 후, Z의 순서로 계산을 해나가면 되는데, i행 j열의 계산 방법은 다음과 같다. (1) 행과 열의 문자가 일치할 경우 = 좌 대각선 위의 값 + 1 → 문자가 일치하므로, 이전까지의 LCS에 1을 더하기 위함이다. 즉, 이..

1. 문제 현상 비주얼 스튜디오 혹은 웹 IDE로 문제를 푸는데 배열의 크기를 int arr[1000][1000] 같이 할당했을 때, 에러가 나면서 종료되는 경우가 있었을 것이다. 참고로 이러한 에러가 발생할 때 뜨는 팝업은 다음과 같다. 2. 해결 방법 에러에 대한 해결법을 검색해보았는데, 의외로 굉장히 간단한 문제였다. 지역 변수로 배열을 선언하면 힙 영역에 할당되고, 전역 변수는 스택에 할당된다고 한다. 그런데 힙 영역에 할당되는 Default 크기가 매우 작기 때문에 이러한 에러가 발생하는 것이다. 그러므로 다음과 같은 2가지의 해결 방법이 가능하다. 1) 배열을 전역 변수로 설정하기 가장 간단한 해결 방법이고, 문제 풀이 과정이라면 추천하는 방법이다. 2) 비주얼 스튜디오라면, 다음과 같이 '설..

1. 문제 2. 문제 풀이 다이나믹 프로그래밍 (DP) 문제이다. 현재의 상태를 저장시켜서 이를 지속적으로 활용하는 다이나믹 프로그래밍의 특성에 맞춰, 다음과 같은 문제 풀이 접근 방법을 활용하였다. '각각의 계단에 대해서, 이전 계단을 선택하는 경우와, 이전의 이전 계단을 선택하는 경우를 계산해나간다.' 즉, 각 계단에 대해서 다음의 알고리즘을 반복하는 것이다. (1) 이전 계단을 선택하는 경우, 이전 계단의 상태 중에서 '이전 계단을 선택하지 않았던 상태'를 선택할 수 있다. -> 이전 계단 중에서, '이전 계단을 선택했던 경우'를 선택하면 연속해서 세 계단을 오른 경우이므로 선택 불가 (2) 이전의 이전 계단을 선택하는 경우, 이전의 이전 상태 중 더 큰 값을 선택한다. -> 이전의 이전 계단의 경..

1. 문제 2. 문제 풀이 다이나믹 프로그래밍(DP)의 대표적인 유형 중 하나인 LIS 문제이다. 현재의 상태를 지속적으로 저장시켜서 문제를 푸는 DP의 특성을 이용하여 문제에 접근한다. 나의 경우에는 다음과 같은 방법을 고안했다. 각 값들에 대해서, 그 값까지 만들어지는 LIS를 지속적으로 저장시켜 나간다. 이 때, 현재의 LIS를 구하는 방법은 다음과 같다. '자신보다 작은 이전의 Value들에 대해서, 그때까지의 LIS가 가장 큰 값에 1을 더한다.' 즉, 각 LIS 값은 다음과 같은 조건으로 구한다. (1) 현재 LIS 값보다 이전의 값들에 대해서 (2) 현재 자신의 Value보다 작은 값들에 대해서 (3) LIS 값이 가장 큰 값을 구한 후, 그 값에 1을 더한 값으로 구한다. (4) 만약 조건..