복습노트 복습노트

문제 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 섬의 개수 n이 주어지고 섬과 섬사이에 무게를 최대로 옮길수 있는 간선의 정보 m개가 주어집니다. 섬과 섬사이에 최대로 옮길 수 있는 무게보다 큰 무게를 옮길 수 없습니다. 그리고 특정섬 a, b 가 주어지면 a와 b사이에 한번에 최대로 옮길 수 있는 무게를 구하면 됩니다. 예를 들어 0번 섬에서 9번섬으로 갈 수 있는 최대 무게는 11입니다. 따라서 11이상인 무게는 항상 옮길 수 있고 11미만인..

문제 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 현재 위치 n이 주어지고 도착 지점 k가 주어지면 도착할때 까지 최단시간을 구하는 것입니다. 먼저 현재위치 n은 n+1로 가거나 n-1로 가거나 n*2로 갈 수 있습니다. 예를 들어 n = 5이고 k = 17이면 5 -> 10 -> 9 -> 18 -> 17 이므로 총 4초만에 최소시간으로 도달합니다. 단순히 문제를 봤을 때는 처음에는 dp를 생각하였습니다. 하지만 n이 움직일 수 있는 3가지 경우의 수에 대해서 따로따로 봐야하고 ..

문제 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 행렬의 크기 nm이 주어지면 1이면 벽이고 0이면 갈 수 있는 길입니다. 이때 벽을 한번 부수고 통과할 수 있다고 할때 최단거리를 구하는 문제입니다. 최단 거리이므로 BFS로 이용하면 됩니다. 원래 평소대로라면 bool visited[x][y] : arr[x][y]에 해당하는 부분을 방문하면 true로 바꿔주었지만 벽을 부수는 경우도 생각해줘야 하기때문에 방문기록이 총 3차원으로 생각할 수 있습니다. int dist[x][y][0]..

문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net Flood Fill Algorithm : 어떤 칸과 연결된 영역을 찾는 알고리즘 가로 M과 세로 N이 주어지고 배추의 위치 (M(가로), N(세로)) 이 주어 집니다. 다음과 같이 1끼리 인접한 부분(상하좌우)이 몇개인지 출력하는 문제입니다. 위의 그림에서는 5개입니다. 주어지는 위치가 처음에 가로, 세로가 주어지므로 행렬로 생각할 때 주의해야합니다. M은 행이 아닙니다. 열입니다. N은 열이 아닙니다. 행입니다. 즉 행열이 반대로 주어지는 겁니다. 저는 처음에 이것을..

문제 12895번: 화려한 마을 첫 번째 줄에 N, T, Q (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 30, 1 ≤ Q ≤ 100,000)이 공백을 구분으로 주어진다. 각각 천나라에 존재하는 집의 개수, 사용할 색의 개수, 작업의 개수를 의미한다. 두 번째 줄부터 작 www.acmicpc.net n, m, k가 주어지면 n은 집의 개수, m은 사용할 색의 개수, k는 작업의 개수를 의미합니다. 작업은 C와 Q가 있는데 C는 C a b c 의 형태로 주어지면 [a, b]구간에 있는 모든 집을 c로 색칠한다는 의미입니다. Q는 Q a b 의 형태로 주어지면 [a, b] 구간에 있는 모든 집의 색의 가짓수를 출력한다는 의미입니다. 작업이 Q a b 일때 [a, b]에 있는 모든 집에 존재하는 색의 가짓수..

문제 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 저번에 풀었던 구간합 구하기 1 와 유사한 문제입니다. 차이점이라면 구간을 update하는 부분이 구간 모두에 정수 d를 더해준다는 것입니다. 이번에는 신촌 겨울캠프에서 배운 Lazy Segment Tree를 이용해서 풀었습니다. const ll n_ = 4 * 1e6 + 100; ll tree[n_], lazy[n_], A[n_]; 주어진 수를 받을 배열 A A를 Segment tree로 바..

문제 3033번: 가장 긴 문자열 첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다. www.acmicpc.net 길이가 L인 문자열이 주어지면 해당 문자열 안에서 2번이상 등장하는부분문자열 중에서 가장 긴 문자열의 길이를 출력하는 문제입니다. 예를 들어 길이가 11인 문자열 "sabcabcfabc" 이 주어지면 2번이상 등장하는 부분문자열 중에서 가장 긴문자열은 "abc" 이므로 부분문자열 중에서 가장 긴 문자열의 길이는 3입니다. 단순히 naive한 풀이를 생각해보면 한 문자씩 반복문을 돌아보며 확인하므로 최대 O(N^2)의 시간복잡도를 가질 수 있습니다. 길이가 k인 문자열이 2번이상 등장했다면, k-1 인 문자열도 2..

문제 16900번: 이름 정하기 첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문자열이 s가 주어지면 해당 문자열을 최소 k번 부분문자열로 들어가게 이름을 정하고 이름의 길이를 출력하면 되는 문제입니다. 예를 들어 s = ada 이고 k = 3 일때 이름의 최소길이는 adadada 총 7 입니다. KMP알고리즘의 fail 배열을 이용하여 해결하였습니다. 접두사와 접미사가 같으면 중복으로 처리해서 이름을 최소로 할 수 있기 때문입니다. 위의 예시를 보면 ada가 총 3번 부분문자열로 들어가야합니다. ada의 fail 배열은 {0, 0, 1} 입니다. 즉 맨 마지막..