programmers. 순위 어려운 문제였습니다. 저도 어제 조금 생각하다가 방향이 잘 안잡혀서 답안을 봤는데 더 모르겠더라구요. 그래서 오늘 다시 도전해봤는데 오늘은 이 방법이 맞을지 안 맞을지 모르지만 일단 해보자는 생각으로 도전을 했습니다. 결국 답은 틀렸지만 시도한 가치가 있었습니다. 왜냐하면 마지막에 답을 산출하는 과정만 틀렸을 뿐 그 전에 데이터를 가공하는 과정은 의미가 있었거든요. 그럼 처음에 제가 시도한 방법부터 설명해보겠습니다. 답안에는 '플로이드-워셜'알고리즘으로 푸는 방법으로 풀려있습니다. 하지만 저는 bfs를 n번 도는 방법을 통해 데이터를 가공하였습니다(실제 답안에도 이렇게 2가지로 풀 수 있다고 가이드되어 있습니다). bfs를 n번 도는 이유는 다음과 같습니다. 만..
programmers. 가장 먼 노드 그래프 문제이지만 bfs의 개념을 알면 쉽게 풀 수 있는 문제였습니다. 다만 기초적인 bfs에서 조금 더 나아가 length를 따로 표시해줘야한다는 점에서 좀 더 추가적으로 구현해야 합니다. 왜냐하면 length가 몇이냐에 따라서 answer값이 계속 갱신되어야 하기 때문입니다. 기본적인 아이디어는 bfs로 풀면서 최단 거리를 찾아나갑니다. 그리고 Queue에서 Node(해당 노드의 수, length 상태값을 가짐)를 꺼낼 때 count하고 있는 length의 값과 같으면(같은 길이의 노드일때) answer을 증가시키고, count하고 있는 length가 아니면(더 큰 길이의 노드일때) answer = 1 로 초기화시킵니다. class Solution { public..
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] = 오른쪽만 버릴 때 처음보았을 때 이게 ..
