Social Developer

어제보다 한 걸음 더

Algorithms

블로그에 같은 문제를 2번씩 올리는 사람이 나말고 또 있을까..? 분명 풀어서 풀이 업로드까지 해놓았는데, 거의 정확히 1년이 된 오늘 다시 푸는데 엄청 애를 먹었다. 단순한 문제 풀이가 아니라, DP를 활용함에 있어 중요한 부분인듯 싶어 고민했던 부분을 다시 기록하려 한다. 문제를 보자마자 처음 든 생각은 1이 될 때까지 입력값을 if 문으로 1번 연산(3으로 나눔) 먼저, 다음은 2번 연산(2로 나눔), 두 연산 모두 안되는 경우 3번 연산(-1)으로 처리하면서 과정을 count하면 될 거라고 생각했다. 역시 이렇게 간단할 리가 없다. 예제 입력 2처럼 10 -> 9 -> 3 -> 1 로 먼저 3번 연산을 하는 경우가 최솟값을 반환하는 경우가 있기 때문이다. 여기까지 보고 나서 바로 든 해결 방법은 ..

2021. 3. 7.

Algorithms

이전 1753번 최단경로 문제와 같이 최단경로 유형의 문제다. 다만 이번에는 버스 노선이 edge인데 음수 범위를 포함하기 때문에, 벨만 포드 알고리즘을 사용해 최단경로를 구해주어야 한다. 이번 문제에서 유의해야 할 점은 최단 경로를 나타내는 dist 배열을 int가 아닌 long으로 설정해줘야 한다는 점이다. 이 점을 캐치하지 못하고 출력초과 결과를 받아 오래 헤맸다. (이 문제에서 출력초과는 사실상 음수사이클 판정을 하지 못한 것) 간선 weight의 범위가 -10,000 < C < 10,000이고, 노드의 수가 최대 500임에도 dist 배열을 long으로 설정해줘야 하는 이유는 경로의 weight를 계산하는 과정에서 음의 사이클이 존재하는 경우 알고리즘 내부 반복문을 한 번 돌 때마다 최악의 경우..

2021. 3. 4.

Algorithms

제목부터 최단경로다. 최단경로와 관련된 알고리즘으로는 대표적으로 1) 다익스트라, 2) 벨만포드 , 3) 플로이드 워셜 알고리즘이 있음을 알고 각각의 특징에 대해서도 익혀두는 것이 좋다. 이 문제는 먼저 간선의 범위가 자연수이고, 시작점이 하나로 주어지므로 Dijkstra 알고리즘을 적용하는 것이 좋다. 물론 벨만포드나 플로이드 워셜 알고리즘으로도 최단 경로를 구할 수는 있겠지만 각 알고리즘의 시간복잡도를 이 문제에 적용해보면 벨만포드는 O(E log V), 플로이드 워셜 O(N^3)이므로 시간 제한에 걸리게 된다. 다익스트라 알고리즘을 적용하면 크게 어렵지 않게 풀어낼 수 있는데, 구체적인 구현 방법에 대해 잘 기억하는 것이 중요할 수 있겠다. (최단 경로인데 간선의 가중치가 10 이하 자연수이므로, ..

2021. 3. 4.