Algorithm

[백준 17472] 다리 만들기 2 (C++)

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net BFS, 최소 스패닝 트리 BFS를 통해서 각 칸마다 섬의 번호를 지정해서 섬을 구분한다. 모든 섬과 섬 사이의 거리를 구한다. 서로 이어지지 않은 섬은 거리를 INF로 한다. 여기까지 사전작업을 마쳤으면 모든 섬을 연결하는 최소 거리를 구하면 된다. 모든 노드를 연결하는 최단거리를 구하는 알고리즘은 최소 스패닝 트리임을 알 수 있다. 2번 과정에서 얻은 섬 간의 거리는 양방향이었으므로 중복되는 구간은 제외하고 새로운 벡터에 넣어준다. 거리를..

동적 계획법 메모이제이션 패턴 (C++)

동적 계획법.. 다이나믹 프로그래밍과 같은 말이다. 동적 계획법은 개념 자체는 쉬워서 알고리즘의 기본 난이도는 낮은 편이다. 하지만 메모이제이션을 몸에 익히고 문제를 보고 동적계획법을 떠올리며 어떤 정보를 메모이제이션할지 바로 찾아내는 내공을 가지려면 엄청난 노력이 필요하다고 생각한다. 다른 알고리즘과는 비교가 안될정도로 많이. 이 책에는 약 25개 정도의 큼직한 알고리즘 파트가 1000페이지 조금 넘게 기술되어있다. 그 중에서 동적계획법은 160페이지 가량 되는데 비중이 정말 크다고 볼 수 있다. 쉬우면 너무 쉽지만 어려우면 말이 안나올정도로 어려운 동적계획법의 가장 기본이 되는 탑다운 메모이제이션 패턴을 알아보자. 패턴 코드 // 전부 -1로 초기화 int cache[2500][2500]; int F..

[백준 1395] 스위치 (C++)

1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 세그먼트 트리 오랜만의 백준 풀이다. 어저께 하루 종일 고민하면서 구현했고 방금 구현을 마무리해서 AC를 받았다. 처음엔 3653 영화 수집 문제를 풀려고 했는데 아무리 생각해도 푸는 방법이 생각이 안 나서 런하고 만난 문제가 이번 문제다. 도망쳐서 만났기 때문에 한번 더 도망칠 수가 없었다.. 전에 풀었던 구간합구하기2 문제랑 느낌이 비슷해서 레이지 세그먼트 트리로 감을 잡았다. [백준 10999] 구간 합 구하기 2 (..

[백준 15559] 내 선물을 받아줘 (C++)

15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 www.acmicpc.net 강한 연결 요소 임의의 칸에서 출발해서 다시 자신의 칸으로 되돌아 올 수 있으면 해당 루트의 아무 지점에 선물을 놓아도 선물을 가져갈 수 있다. 따라서 각 칸의 scc번호를 구한다. scc번호를 구하고 scc그래프를 만드는데 역방향으로 만드는게 중요하다. 하나의 SCC집합 내부에선 어떤 칸에 놓던지 선물을 가져갈 수 있는 성질을 활용하면 된다. SCC의 outdegree가 0이면 해당 SCC에서 다른 SCC로 갈 수 없다..

[백준 10217] KCM Travel (C++)

10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍 [백준 17182] 우주 탐사선 (C++) 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 hyeo-noo.tistory.com 위 문제와 비슷한 다익스트라+DP문제였다. (주유소_13308 도 비슷하다) 하지만 이번 KCM문제는 최단 시간을 ..

[백준 20056] 마법사 상어와 파이어볼 (C++)

20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 시뮬레이션, 구현 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다. 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다. 파이어볼은 4개의 파이어볼로 나누어진다. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋..

[백준 4354] 문자열 제곱 (C++)

4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net KMP 예를 들어 문자열 abcab가 있다고 하자 kmp알고리즘을 사용해서 주어지는 문자열마다 접두사 실패 table을 만들어 준다. -> {0, 0, 0, 1, 2} table의 마지막 수는 마지막으로 접두사와 중복되는 문자열의 길이를 의미한다. -> 2 (ab 중복) 현재 문자열(text)의 크기에서 마지막으로 중복되는 접두사의 길이를 빼준다. -> 5 - 2 = 3 위 값은 중요하다. 무엇을 의미하는 걸까? 값 '3'은 ..

[백준 17835] 면접보는 승범이네 (C++)

17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 다익스트라 각각의 도시에서 면접장을 가기위한 다익스트라를 매번 돌려선 안된다. 가상의 도시를 하나 잡고 면접장으로 가는 거리를 0으로 두고 우선순위 큐에 넣어준다. 그리고 면접장에서 시작해 모든 도시로 가는 최단거리를 구한다. 이때 주의할 점은 입력을 받을 때 역방향으로 입력 받아야 한다는 점이다. a -> b가 4 b -> a가 2 이고 면접장이 a라고 하자. b도시에서 면접장을 가는 최소 비용은 2가 되지..

[백준 2234] 성곽 (C++)

2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트마스킹, BFS [백준 16946] 벽 부수고 이동하기 4 (C++) 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 hyeo-noo.tistory.com 위 문제와 아주 비슷한 방법을 적용해서 풀었다. 차이점은 N과 M의 크기가 현재 문제에서는 50, 50이 최대라서 O(N^2 * M^2)이 가..

[백준 16946] 벽 부수고 이동하기 4 (C++)

16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net BFS 우선 bfs를 수행하면서 연속해서 비어있는 칸의 묶음마다 집합의 번호를 매겨주고 집합의 번호에 따라서 집합의 크기를 저장했다. setMap[][] 배열에는 해당 칸의 집합의 번호를 넣어준다. setcount 변수는 bfs를 수행하는 횟수만큼 집합이 생길 것이므로 bfs가 끝날 때마다 1씩 더해줘서 집합의 번호를 가지고 있는다. setnums[] 배열에는 집합의 번호에 따른 집합의 크기를 저장한다. 집합의 크기는 bfs를 수행할 때마다 ..