백준
1.[백준] 2243 - 사탕상자 (Python)
사탕에는 1에서 1,000,000까지 맛이 있다. 그렇다면 길이가 1,000,000인 길이를 갖는 리스트로 구현이 가능하다. 인덱스는 사탕의 맛이 되고, 값은 사탕의 개수가 될 것이다.하지만 이렇게만 구현하면 순위로 사탕을 빼는 것이 매우 비효율적인 연산이 된다. 매번
2.[백준] 3015 - 오아시스 재결합 (Python)
앞에서부터 한 명씩 차례대로 줄을 선다고 생각하면 스택을 사용할 수 있다. 서로 볼 수 있어야 하므로, 모든 사람들은 오직 앞쪽만 본다고 가정해도 무리가 없다. 스택은 항상 키의 내림차순으로 정렬되어 있다.키가 작은 사람이 줄을 서면 스택에 넣는다.키가 큰 사람이 줄을
3.[백준] 5719 - 거의 최단 경로 (Python)
문제 해결의 기본적인 아이디어는 먼저 최단거리를 구한 후, 그래프에 최단 경로에 포함되는 경로를 모두 지운 뒤 한번 더 최단거리를 구하는 것이다. 최단 경로에 포함되는 경로를 찾으려면 어떻게 해야 할까? 먼저, 다익스트라 알고리즘을 사용해서 최단 경로의 길이를 구했다고
4.[백준] 7578 - 공장 (Python)
케이블이 교차하기 위한 조건은 무엇일까?. A열 기계를 모두 배치한 상황에서 B열 기계를 하나씩 배치하는 상황을 가정하겠다.n번째 B열 기계와 연결되는 A열 기계의 위치(인덱스)를 loc\[n] 라고 하자. 기존에 배치된 기계 m에 대해서 loc\[n] < loc
5.[백준] 13141 - Iginition (Python)
불이 전파되는 방식을 어떻게 구현해야 할까?불의 속도는 1이므로 불이 다른 정점으로 전파되는 시간은 정점 사이의 최단거리와 같다.모든 발화점을 비교해서 그래프가 전부 타는 최소시간을 구해야 하므로 플로이드 워셜 알고리즘을 사용해 모든 정점 사이에서 불이 전파되는 속도를
6.[백준] 14517 - 팰린드롬 개수 구하기 (Python)
부분수열 중 팰린드롬을 구해야 하므로 구간으로 접근해 보자. 구간 \[l-r] 에 대해서 구간 내의 모든 팰린드롬의 개수를 DP(l, r)라 하자. 그렇다면 기본적으로 DP(l, r) = DP(l+1, r) + DP(l, r-1)로 점화식을 세워볼 수 있다.이러면 무엇
7.[백준] 14942 - 개미 (Python)
개미집은 1번이 루트인 트리로 구조화할 수 있다.모든 개미들이 에너지를 다 쓰기 전까지 루트로 올라가도록 구현해야 한다.가장 간단하게 구현할 수 있는 것은 부모 노드로 한칸씩 올라가는 방식이다. 하지만 이렇게 되면 시간복잡도가 O(N^2)이 되기 때문에 비효율적이다.
8.[백준] 15678 - 연세워터파크 (Python)
문제의 조건을 보면, 아무 지점에서 시작해서 나오고 싶을 때 나오는 것이 가능하다. 그렇다면, 나오는 지점에 초점을 두고 동적 계획법을 적용해 보자.시작점과 도착점을 반대로 바꿔도 점수에는 변화가 없으므로 항상 왼쪽에서 시작해 오른쪽에서 탈출한다고 가정해도 문제가 없다
9.[백준] 16287 - Parcel (Python)
4개를 모두 골라서 w가 맞는지 비교하는 것은 지나치게 큰 비용을 요구한다. 2개씩 골라서 합을 구해 비교하는 방식을 사용해야 한다.(i < j < k < l) 이며 a\[i]+a\[j]+a\[k]+a\[l] = W 을 만족하는 i, j, k, l을
10.[백준] 17401 - 일하는 세포 (Python)
혈관 지도를 행렬로 표현해보자. 이때, 적혈구는 모든 거점에서 출발하므로 초기 상태는 길이가 $n$ 인 단위행렬과 같다.$\\begin{pmatrix}1&0&0\\0&1&0\\0&0&1 \\end{pmatrix}$ $\\times$ $\\begin{pmatrix}0&
11.[백준] 1014 - 컨닝 (Python)
두 가지 해결방법이 있다. 첫번째는 비스마스킹을 이용한 동적 계획법이다.모든 학생이 앞의 행 왼쪽부터 순서대로 앉는다고 가정한다.각각의 학생이 앉을지 결정하는 시점에는 앞쪽 대각선과 왼쪽 자리만 체크하면 된다.이 경우, 가능한 학생들의 배치가 오직 바로 앞의 배치에 종
12.[백준] 13977 - 이항 계수와 쿼리 (Python)
구하고 싶은 값은 (n! / (n-k)!k!) MOD P 가 된다.n! 을 매번 구하는 것은 비효율적이므로 모든 경우의 팩토리얼 값을 미리 계산해 놓는다.모듈러 연산에서 나눗셈은 곱셈 역원으로 바꾸어야 하므로 페르마의 소정리를 이용하면 (n-k)!k!^-1 MOD P
13.[백준] 3176 - 도로 네트워크 (Python)
도시가 $N$개 존재하고 도로가 $N-1$개 존재하므로 트리 형태인 것을 알 수 있다. 따라서 경로를 찾기 위해서는 최소 공통 조상 알고리즘을 사용하고, 빠르게 찾기 위해 희소 배열을 사용한다.이 문제에서는 경로 상에서 가장 짧은 도로와 가장 긴 도로를 찾아내야 하므로
14.[백준] 3653 - 영화 수집 (Python)
DVD를 꺼내서 본 후에 가장 위에 놓는 배열을 구현하는 것은 어렵지 않다. 하지만 단순한 배열로 구현하면 각 DVD의 위에 놓인 영화의 개수를 찾는 것이 비효율적인 연산이 될 것이다.따라서 구간의 DVD개수를 빠르게 구할 수 있는 세그먼트 트리를 사용해야 한다. 이
15.[백준] 11266 - 단절점 (Python)
주어지는 그래프를 루트에서 시작해 중복 없이 재귀적으로 순회한다고 생각해보자. 이때 각 노드에 진입하는 순서에 따라 번호를 부여한다.한 노드를 기준으로 했을 때, 특정 자식이 도달가능한 진입순서의 최솟값이 해당 노드의 진입순서보다 앞선다면 해당 자식으로 통하는 다른 경