Today's Dev Notes(2019-01-27) programmers. 징검다리 많은 사람이 풀지 않는 문제답게 어렵네요. 어떻게 접근해야할지 몰라 모범답안을 참고하였습니다. 전혀 생각해보지 않은 방법이라 신선하기도 하면서 다음에 또 이렇게 풀 수 있을까 생각하면 확신이 들지 않네요. 문제에서 구해야하는 것은 '제거해야할 바위 수가 주어질 때 각 경우의 수에서 각 바위 사이 거리 중 가장 짧은 거리를 구하고 그 중 가장 큰 값'을 구하는 문제였습니다. 모범답안에서 제안하는 문제풀이 방식은 다른 각도에서 생각해보기를 권합니다. '가장 짧을 거리 c일 때 제거해야 할 바위 수 R(c)'로 말이죠. 그렇기 때문에 비교할 때 가장 짧은 거리라고 설정한 값보다 작을 때는 제거해야할 바위수가 +1 증가됩니다...
programmers. 입국심사 이분탐색 문제의 유형이 비슷해서 이 문제를 접근하는데 크게 어렵지 않았습니다. 물론 아마 프로그래머스 내 이분탐색 부류에 있지 않았다면 이렇게 접근하는데 좀 더 시간이 걸렸을지도 모르겠네요. 기본적인 해법은 mid값일 때 얼마만큼의 사람이 통과되었는지를 구하고 이를 바탕으로 low와 high를 조절하는 것입니다. 그런데 이 문제를 풀면서 가장 어려웠던 것은 type이 int가 아닐수도 있다는 점입니다. 즉, 다시 말하면 최악의 상황의 경우 문제에서는 int가 주어졌지만 int가 넘어가는 값이 최악의 상황(=high)이 될 수가 있다는 것입니다. 예를들어 심사관 1명 밖에 없고 1명을 검사하는데 1,000,000,000분이 필요한데 1,000,000,000명이 기다리고 있는..
programmers. 서울에서 경산까지 이 또한 동적문제인데요. 이 전 문제에서 동적계획문제에 대한 감을 잡았다고 생각했는데 생각보다 쉽지 않더라구요. 이전에도 말씀드렸듯이 동적문제에서는 dp배열을 어떻게 정의하느냐가 가장 중요합니다. 저는 처음에 이렇게 가정했습니다. dp[i][j] : 도보로 i번째, 자전거로 j번째 이동했을 때 최대 모금액 그럴듯하죠. 이전에도 이런식으로 문제를 풀었으니까요. 그런데 이게 제대로 작동할까요? 아닐 것 같습니다. 이전 카드문제에서는 left, right 배열이 각각 따로 주어져서 '왼쪽에서 i번째, 오른쪽에서 j번째'가 가능했습니다. 하지만 이번의 경우는 조금 다릅니다. 왜냐하면 하나의 일련의 구간에 대해 도보와 자전거 중 하나를 골라서 타야하기 때문이..
programmers. 카드 게임 문제의 갈피를 잡지 못해 다른 사람의 코드를 참고하였습니다. 동적계획문제 라는 것이 그 느낌을 알기전엔 참 어떻게 해결해야 할지 알기가 힘든 것 같아요. 그래도 이번 문제를 통해 또 다시 쪼금(?!) 감을 잡을 수 있었습니다. 동적계획에서 dp배열을 만들때는 그것을 어떻게 정의하는지가 중요합니다. 이 문제 같은 경우 이와같이 정의할 수 있죠. dp[i][j] = 왼쪽 i번째, 오른쪽 j번째일 때 최대값을 가진다 위와 같이 정의한다면 문제의 상황은 다음과 같이 해석할 수 있을 것입니다. dp[i - 1][j - 1] = 양쪽 모두 버릴 때 dp[i - 1][j] = 왼쪽만 버릴 때 dp[i][j - 1] + right[j - 1] = 오른쪽만 버릴 때 처음보았을 때 이게 ..
programmers. 도둑질 동적계획법 문제는 정말 동적계획법답게 풀지 않으면 시간 초과나 메모리 초과가 발생하는데 이 때문에 많은 고생을 했습니다. 처음엔 머리에 떠오르는대로 재귀로 풀었는데요. 모든 경우의 수를 다 돌다보니 역시나 시간초과부터 발생하더라구요. 그리고 이후엔 학교에서 배운대로 배낭문제나 최소 잔돈개수 문제처럼 표를 떠올리며 구현하였습니다. 여기서 정확성 테스트에서 시간 초과는 극복할 수 있었지만 효율성 테스트에서 시간 초과 및 메모리 초과가 발생하여 이 또한 통과하지 못하였습니다. 우선 메모리초과가 발생한 이유는 array[length][length] 로 만들었기 때문인데요. 다른 사람의 코드를 참고하면서 굳이 저렇게 배열을 모두 만들지 않더라도 해결할 수 있음을 알게되었습니다. 두 ..
programmers. 단속카메라 또 탐욕법이라 생각하니 자연스럽게 큰 것을 먼저 처리해야 한다는 생각이 들었고 이번 문제의 경우 길이가 가장 크거나 작은 순으로 하여 각각의 경우 체크하도록 문제를 풀었습니다. 구체적으로 먼저 길이로 정렬을 하였고, 해당 길이 내에서 for문을 돌면서 어느 지점에 단속카메라를 설치하였을 때 가장 겹치는 지점을 찾았고, 그 겹치는 지점에 속하는 구간을 빼내면서 결국 카메라가 몇 개가 필요한 것인지 찾아나갔습니다. 이렇게 하였을 때 정확성에는 문제가 없었지만 역시나 복잡도 때문에 시간초과가 발생하였습니다. 결국 다른 방법을 찾아야했습니다. 결국 길이가 중요한 것이 아니었습니다. 진입점과 진출점만 알면 위와 같은 복잡도 없이 쉽게 풀 수 있거든요. 우선 객체를 하나 만들었는데..
