알고리즘

프로그래머스 징검다리 건너기 1. 문제 카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다. 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다. 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그다음 디딤돌로 한 번에 여러 칸을 건너뛸 수 있습니다. 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다. "니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 ..

이 문제를 봤을 때, 플로이드 와샬로 풀 수 있을까 고민했지만 tc의 개수가 5개, N의 크기가 500인 것을 보고 플로이드와 샬을 포기하고, 음의 가중치라는 점에서 벨만 포드 알고리즘을 시도했다. 벨만 포드 알고리즘이 익숙지 않아 많이 헤맸던 문제이지만, 이 문제 덕에 벨만 포드 알고리즘을 한번 더 정리할 수 있었다. 벨만 포드 알고리즘은 다익스트라와 같이 최단 경로 문제를 푸는 알고리즘이지만, 차이점은 변과 변 사이에서 음의 가중치를 가질 수 있다는 점이고 바로 이 점이 훨씬 더 빠른 다익스트라보다 벨만 포드 알고리즘을 사용하는 이유이다. 왜 다익스트라는 음의 가중치를 가지지 못할까? 음의 가중치가 있는 경우 음의 순환(계속 가중치가 최솟값으로 갱신되는 경우)이 있다. 다익스트라는 가중치의 합을 최솟..

이 문제는 문제 제목에서부터 MST 문제라는 것을 알려주고 있다. 당연히 나는 MST 알고리즘 중 내가 알고 있는 Prim알고리즘을 통해 풀었고, 아쉽게도 시간 통과를 하지 못하였다. 잘 모르는 크루스칼 알고리즘을 공부해봐야 하나 생각하며 백준 질문게시판을 둘러보았는데, 프림과 힙을 사용해서 풀었다는 사람들이 많아서 조금 충격을 받았다. 나의 다른 MST 풀이를 보면 알겠지만 나는 프림 알고리즘은 세 가지 구조를 가지고 문제를 해결한다. 1. 현재 내가 갈 수 있는 곳 중 최소 비용으로 갈 수 있는 곳을 찾는다 2. 최소로 갈 수 있는 곳을 등록한다. 3. 새로 등록한 곳에서 또 더 갈 수 있는 곳을 찾는다. 이렇게 할 때, 힙을 어디서 사용하지라는 아이디어가 쉽게 떠오르지 않았다. 하지만, 결국 프림 ..

이 문제는 백준 키순서에 내가 적어놓은 예시와 거의 유사한 문제였다. 문제집 커리큘럼에 따라 한 문제를 풀기 위해서는 선행되어야 하는 문제(진입 차수)가 있고, 이 문제는 그 순서대로 문제를 풀 때 어떤 순서대로 풀어야 할지를 묻는 문제이다. 여기서 하나의 추가조건이 있는데 가능하다면 쉬운 문제 (인덱스가 작은 문제)를 먼저 풀어야 한다. 나는 이 부분에서 조금 헷갈렸는데 이 문제가 원하는 것은 2번 문제(선행 문제가 1인 문제)와 3번 문제(선행 문제가 없는 문제)가 있다면 1-2-3 순서로 문제를 풀어야 한다. 즉, 선행 문제가 있다 하더라도 문제의 난이도는 인덱스가 결정한다. 위상 정렬과 문제만 이해했다면, 쉽게 풀 수 있을 것이다. 우리에게는 자동으로 인덱스를 정렬해주는 힙이라는 무기가 있기 때문..

줄 세우기 문제이다. 백준의 키순서와 비슷하다는 느낌이었지만 백준의 키순서 문제는 자신의 순서를 정확히 알 수 있는 사람의 수를 묻는 문제였고, 순서를 정렬(정확하지 않는 사람은 임의로)한다는 점에서 차이가 있었다. 이 차이에 의하여 키순서문제는 플로이드 와샬이나 dfs를 통해 푸는 문제가 되었고, 이 문제는 위상 정렬을 통해 푸는 문제가 되었다. 위상 정렬은 진입 차수가 낮은 노드들 순으로 정렬할 때 활용하는 알고리즘이며 일상생활에서도 우리가 흔히 쓰고 있는 알고리즘이다. 대표적으로 대학교의 수강커리큘럼을 볼 때 우리가 무의식적으로 많이 사용하고 있는데 어떤 한 과목을 듣기 위해서 선수과목이 있고, 그 과목의 또 선수과목이 있다. 우리는 이를 보기 쉽게 하기 위해 선수과목의 수준이 낮은 것부터 정렬하여..

이 문제는 문제에서 어피 치과 과녁을 쏜 이후에 라이언이 과녁을 쏘는데 문제에 규칙에 따라서 라이언이 최대 점수차로 이기게 과녁을 쏠려면 어떻게 점수를 얻어야 할지 구하는 문제이다. 이 문제를 보면서 어떻게 구현할지 고민을 했는데 나에게 힌트가 됐던 점은 점수가 1에서 10까지 있다는 것과 오직 점수 얻는 방식이 상대편(어피치) 보다 많이 그 점수를 맞췄을 때 딱 그 점수만 얻는다는 점이다. 예를 들면 어피치가 10점 3발, 라이언이 10점 4발을 맞춘다면 점수는 라이언만 10점을 얻게된다는 점이다. 즉, 10개의 점수판 중에서 1점을 획득한다/ 못한다, 2점을 획득한다 / 못한다 이런 식으로 경우의 수가 2의 10 제곱으로 완전 탐색을 할 수 있다는 점이 나에게 힌트였다. 나는 위의 아이디어를 바탕으로..

이 문제는 한 마을에서 다른 마을로 이동할 때 비용(시간)이 주어질 때 다른 마을까지의 비용이 주어진 K보다 작은 마을의 개수를 구하는 문제이다. 가장 먼저 다익스트라가 떠올랐고 실제로 다익스트라 알고리즘을 통해 문제를 풀었다. 한가지 특이점은 보통 다익스트라는 목적지까지의 최소비용을 구할 때 많이 사용해온 알고리즘이지만 이 문제는 특별한 목적지가 존재하지 않다. 그렇기 때문에 나는 이 문제에서 heap 자료구조를 사용하지 않았다. 최소비용으로 갈 수 있는 경우에만 enqueue를 하면서 그래프 탐색을 하다가 더 이상 최소비용으로 갈 수 있는 도시가 없을 때 종료하도록 코드를 만들었다. (지금 생각해보니 heap을 사용하여 현재까지 비용이 K가 넘어가면 중지하는 식으로 구현해도 될 것 같다.) 정리하자면..

이 문제를 요약하자면 출발점에서 목적지까지 최단거리를 제외한 그다음 최단거리를 이용한다면 소요되는 비용을 묻는 문제이다. 이 문제를 풀기위한 나의 아이디어는 다익스트라로 우선 최단거리를 구한 후 그 결과를 활용하여 최단거리를 추적하고, 그 최단거리를 삭제한 후에 다시 다익스트라를 이용하여 최단거리를 구하는 것이다. 이를 정리하자면 아래와 같다. 1. 다익스트라를 통해 최단거리를 갈 때 비용을 기록 2. BFS를 활용해서 최단 루트 추적 -> 다익스트라를 기록한 배열을 활용하여 추적함 3. 다익스트라를 다시 하여 최소 비용 구하기 문제를 풀면서 생각한 엣지케이스는 최단거리가 여러 개일 수도 있다는 점이었기 때문에 최단거리를 추적할 때 이를 고려하여 최단 루트를 추적하였다. 이를 코드로 나타내면 아래와같다...