1. 문제 2. 접근 방법 이분 탐색으로 해결할 수 있는 적당한 난이도의 문제... 라고는 하나 접근 방법이 잘 떠오르지 않아 애를 먹었던 문제이다. 이 문제는 브루트 포스적인 방법으로 접근하면, O(N * log N) 이라 시간 초과로 풀 수 없다. 그러므로 효율적인 계산 방법을 생각해야 하는데, 아래와 같이 구할 수 있음을 알게 되었다. 우선, N =5 일 때, 즉 5 X 5 배열을 통해서 계산을 생각해보자. 그리고 여기에서 k = 11 일 때, 즉 B[11] 을 찾는 경우를 생각해보자. 우리가 찾는 11번째의 숫자를 S 이라고 한다면, 다음과 같이 접근해야 한다. "전체 숫자 중에서, S보다 작거나 같은 숫자의 개수가 11개보다 작으면 안된다!" → 만약 그렇다면, 찾는 숫자의 범위를 큰 쪽으로 옮..

1. 문제 2. 접근 방법 이분 탐색의 종류인 Parametric Search 를 이용한 문제이다. 이 문제는 다음과 같은 과정으로 접근해야 한다. (1) 공유기 사이의 최소 거리가 될 수 있는 값은, 1 이다. (2) 공유기 사이의 최대 거리가 될 수 있는 값은, (마지막 공유기의 위치 - 첫 번째 공유기의 위치) 이다. (3) 중간값은 (1)과 (2)에서 구한 값의 중간값이다. (4) 중간값이 가능한 값인지 검사한다. (5) 만약, 중간값이 가능한 값이라면 → 범위를 큰 쪽으로 줄인다. (6) 만약, 중간값이 불가능한 값이라면 → 범위를 작은 쪽으로 줄인다. 여기에서 중간값이 가능한 값인지는 다음과 같이 구할 수 있다. 전체 공유기를 대상으로, 자신의 공유기의 위치에서 이전에 놓았던 공유기의 위치를 ..

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) 비주얼 스튜디오라면, 다음과 같이 '설..