백준

[Algorithm][BFS] 백준 13549 - 숨바꼭질 3

알고리즘 분류 BFS (너비 우선 탐색) 시간 복잡도 \( O(V + E) \) 문제 링크 https://www.acmicpc.net/problem/13549 해당 문제는 대표적인 BFS 문제입니다. 현재 위치 N에서 목적지 K까지 가는데 가장 최소 시간을 구해야 합니다. 이처럼 탐색을 하는 데 있어 최소 시간을 구하는 문제는 DFS보다는 BFS를 이용해야 시간 초과가 나지 않습니다. BFS의 핵심은 "해당 지점에서 갈 수 있는 곳을 다시 Queue에 넣는다" 입니다. 이때 중복되는 지점을 계속해서 탐색을 한다면 시간 초과가 발생하기 때문에 꼭 잘 체크해서 Queue에 넣어줘야 합니다. BFS 문제는 많이 풀다 보면 비슷한 템플릿이 있다는 것을 알게 됩니다. 템플릿은 보통 아래와 같습니다. 입력 변수들 ..

[Algorithm][부분 합] 백준 11659 - 구간 합 구하기 4

알고리즘 분류 부분 합 시간 복잡도 \( O(n) \) 문제 링크 https://www.acmicpc.net/problem/11659 해당 문제는 부분 합 알고리즘의 가장 기본적인 문제입니다. 부분 합 알고리즘의 핵심은 "처음부터 \( i \)번째까지 원소의 합을 미리 구해놓자"입니다. 그래서 특정 구간의 합을 \( O(1) \)의 시간으로 알아낼 수 있습니다. 단순하게 for문을 이용하여 특정 구간의 합을 구하는 시간은 \( O(n) \)이지만 구간의 합들 중 가장 크거나 작은 값을 알려면 모든 구간의 합을 알아야 합니다. 그래서 결국 시간 복잡도는 \( O(n^2) \)가 됩니다. 이런 문제의 경우 \( N \)의 값은 10만 이상의 값이므로 \( O(n^2) \)의 시간 복잡도에서는 당연히 시간 초..

[Algorithm][위상 정렬] 백준 2252 - 줄 세우기

알고리즘 분류 위상 정렬 시간 복잡도 \( O(V + E) \) 문제 링크 https://www.acmicpc.net/problem/2252 선행되어야 할 인덱스들이 주어지면서 가능한 순서를 답으로 제출하는 위상 정렬의 문제입니다. 입력으로써 특정 인덱스 2개가 주어지면 첫 번째 숫자와 두 번째 숫자는 꼭 지켜야 할 순서입니다. 테스트 케이스 2번을 예시로 든다면 아래 그림처럼 4가 2를 가리키고 3이 1을 기리 키는 구조가 됩니다. 이 두 관계를 제외하고는 각 숫자들은 서로 연관되지 않습니다. 위상 정렬의 핵심은 "간선이 없는 노드를 처리하자" 입니다. 여기서 간선이 없는 노드의 뜻은 "가리킴을 당하지 않는 노드"입니다. 그래서 저의 풀이는 Queue를 사용했고 처리하는 과정에서 간선이 없는 노드가 생..