백준

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

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

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

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

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

이 문제를 보면서 어떻게 풀어야 할지 고민하다가 알고리즘 분류를 보고 더 많이 헷갈렸다. 원래 문제를 풀 때 알고리즘 분류를 잘 보지 않으려고 하는데 이문제는 접근 자체가 너무 고민되어 보고 말았다.... 알고리즘 분류에 플로이드-와샬이 적혀있었는데 나는 기본적으로 플로이드-와샬 알고리즘도 다익스트라처럼 가중치가 있는 그래프의 최단경로가 있을 때 사용할 거라 생각했었는데 이 문제는 가중치가 없어서 어떻게 플로이드 와샬로 풀지 와닿지 않았다. 그래도 일단 플로이드-와샬 알고리즘의 기본 틀은 알고 있었기 때문에 그 틀에 맞추어 풀어보았다. 나의 아이디어는 아래와같다. 1. 2차원 배열에는 현재 행을 기준으로 열이 행보다 작으면 True (1)을 준다. 2. 플로이드-와샬알고리즘을 활용하여 비교대상 값(s)이..

이분탐색 문제이다. 이번문제는 이분탐색인걸 모르는채로 풀었는데 문제를 읽자마자 이거 이분탐색이잖아? 라는 생각이 들었다. 내가 그래도 연습을 하긴했구나 싶어서 뿌듯했다. 항상 느끼는 거지만 이분탐색문제는 어떤 값을 찾을 것인가? 그 값이 내가 원하는 값인지 어떻게 검증할 것인가가 가장 중요하고 어려운것 같다. 이 문제에서는 몇 센티미터로 잘랐을 때 원하는 갯수만큼 가장 길게 줄 수 있냐고 묻는 문제이다. 즉, 몇 센티미터인가를 우리가 찾는 값으로 이 값을 기준으로 자르면 몇개를 만들 수 있냐를 통해 검색을 해나갈 수 있다. 이를 코드로 나타내면, 이렇게 된다. 이전에 풀었던 이분탐색문제들보다는 쉬웠던 문제인것 같다.

이 문제는 https://congsoony.tistory.com/158 이 블로그를 참고하여 풀었습니다, 위 블로그에서 설명하는 것처럼 문자열 폭발이라는 문제를 먼저 풀고 이문제를 풀면 그나마 쉽게 접근할 수 있다. 이 문제는 앞에서부터 가면서 원하는 단어가 있으면 삭제하고, 뒤에서 부터 탐색하는 과정을 반복한다. 앞에서부터 탐색하는 과정은 문자열 폭발이라는 문제와 동일하다. 스택을 이용하여 끝 문자가 같으면 검사하고 삭제하는 과정을 반복하는 것이다. 뒤에서부터 탐색하는 과정 역시 스택과 비슷하게 큐를 이용하면 같은 로직으로 해결할 수 있다. 그리고 이를 투포인터를 활용하여 앞에서 진행, 뒤에서 진행 반복하며 모든 문자열을 검사할 때까지 반복했다. 정리하면 아래와 같이 된다. 1. 문자열의 시작을 lef..