programmers. 배달 문제를 정리하는데 좀 시간이 걸렸던 문제였습니다. 일단 이런 문제에서는 각 노드간의 연결관계를 정리하는 자료구조가 필요합니다. 그 자료 구조에는 다음과 같은 내용이 담겨야 합니다. 각 노드는 다른 어떤 노드와 연결이 되어있는가? 각 다른 노드와의 연결시 가중치가 얼마나 되는가? 보통은 위와 같은 조건에서 끝나지만 이 문제에서 다른 점이 있다면 각 노드를 선의 중복이 있을 수 있다는 것입니다. 물론 문제에서 구하고자 하는 것이 가장 많은 마을을 돌아야 하니까 중복이 있더라도 가중치 작은걸로 초반에 걸러주면 될겁니다. 이 연결관계만 정리되어 있다면 순회를 해야하는데 저는 dfs로 풀었습니다. dfs가 적절하다고 생각했던 이유는 한번 시행시 끝을 보는 것이 문제 푸는데 단순하다고 ..
baekjoon1110. 더하기 사이클 오늘은 좀 쉬운 문제를 풀어보았습니다. 백준의 '단계별로 문제풀기' 라는 코너에 특정 영역에 딱 하나 1를 풀지 않아 '완료' 표시되지 않은 것이 눈에 좀 걸려서요. 이와 같은 문제를 풀다보면 String으로 문제를 푸는 것이 좋을까, Int로 문제를 푸는 것이 더 좋을까 생각하곤 하는데요. 저 같은 경우 이번 문제에서 String으로 풀었습니다. 그런데 다 풀고나니 이 문제는 Int로 해도 괜찮겠더라구요. 그 이유는 다음과 같습니다. 여기에서 속도는 큰 문제되지 않았지만 int를 String으로 바꾸고 하는 과정에서 성능에서 불리한 점이 분명 있습니다. 새로운 숫자를 만드는 방식이 기존 수의 가장 오른쪽 수와 각 자리의 수를 더한 수의 가장 오른쪽 수 합치는 것이..
Today's Algorithm(2019-03-18) baekjoon1932. 정수 삼각형 이전에 프로그래머스에서 풀어봤던 문제인데요. 그때 제가 다른 사람의 풀이를 참고해서 풀었던 것으로 기억해서 다시 한번 풀어보게 되었습니다. 이 문제에서 핵심은 '최대값을 어떻게 구할까'인데요. 전에 풀었을 때 재귀로 풀었다가 시간초과가 발생한 기억이 있습니다. 이에 대한 해법은 '다이나믹 프로그래밍'입니다. 쉽게 말하면 그 전까지 값들을 모두 메모해두었다가 다음 계산할 때 사용하는 것입니다. 그럼 어떤 것을 메모할까요? 삼각형을 유심히 보면 제일 앞, 제일 뒤를 제외한 그 사이 숫자는 바로 윗줄의 왼쪽 또는 오른쪽에서 오는 수를 받게 됩니다. 이때 최대값을 받기 위해선 둘 중 큰 수를 받아야겠죠. 그것을 착안하면 ..
Today's Algorithm(2019-03-17) baekjoon1931. 회의실배정 처음 이 문제를 이해할 때 잘못 이해한 부분이 있었는데요. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 문제를 푸는데 이것이 가르키는 의미는 다음과 같습니다. 4시에 시작해서 4시에 끝나는 것도 하나의 회의의 개수로 취급한다 단, 3 5 가 있고 4 4가 있을 때 3 5을 취급하려면 4 4는 무시해야한다. 즉, 회의가 한번 시작하면 중단할 수 없기 때문에 안된다는 것입니다. 그렇지만 3 4가 있고 4 4가 있을 때는 2개의 회의를 취급하겠죠!! 문제에서 주어진 예시에서 1 4와 5 7과 같이 1씩 간..
Today's Algorithm(2019-03-15) baekjoon2293. 동전1 이제 정말 제대로 된 다이나믹 프로그래밍 문제를 만나는 것 같습니다. 다이나믹 프로그램에서는 기록을 해두고 그것을 이용하여 푸는 것이 중요한데요. 중요한건 '어떤 것을 기록하느냐'입니다. 그건 문제에 따라 다릅니다. 이 문제의 경우 '경우의 수'가 구하는 것인데요. 그럼 기록하는 것도 경우의 수를 기록해놓고 그 전에 구해놓은 경우의 수를 재활용하는 방법을 생각해야합니다. 위 그림에서 [해결전략]에 하나의 표가 보일 것인데요. 저게 기록해두는 배열입니다. 이 문제는 이런 전략으로 기록할 것입니다. d [i] [j] : i 번째까지 코인들로 j라는 수를 만들어 내는 경우의 수 ex) 위 경우 A(0) = 1 로 3을 만드는..
Today's Algorithm(2019-03-14) baekjoon11047. 동전0 이 문제는 탐욕법의 문제의 첫걸음에 해당하는 문제인데요. 정말 탐욕법스럽게만 풀면됩니다. 그럼 탐욕법이란 뭘까요? 탐욕법은 뒤까지 모두 고려하지 않고 각 단계에서 최선의 선택을 하는 방법입니다. 이 문제에서 탐욕법스럽게 푸는 방법은 잔돈에서 낼 수 있는 가장 큰 단위의 동전부터 내는 것입니다. 즉 4400원이 있다면 낼 수 있는 가장 큰 범위인 1000원 단위부터 낸다는 것입니다(1, 5, 10, 50, 100, 500, 1000, 5000 단위 가정)그럼 모든 잔돈 문제가 이렇게 단순하게 접근 가능할까요? 그건 아닙니다. 왜냐하면 동전 단위에 따라 이렇게 풀 수 없는 경우가 있기 때문입니다. 예를들어 1060원의 잔..
