boj

[백준 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를 수행할 때마다 ..

[백준 2517] 달리기 (C++)

2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 세그먼트 트리 최대 50만명의 선수들의 실력이 1부터 10억까지의 범위를 가지고 주어진다. 선수들의 등수는 상대적이므로 실력을 10억까지 되는수로 가지고 있을 필요가 없다. 정렬을 사용해서 선수들의 실력을 1~N까지의 수로 조정해준다. 그리고 주어진 선수들을 한명씩 세그먼트 트리에 넣으면서 자신보다 앞서 있지만 자신보다 실력이 낮은 선수의 수를 구한다. 세그먼트 트리의 구간은 선수들의 실력이 된다. 각 노드의 값은 해당 실력에 속한 선수들의 수가 된다. 트..

[백준 5527] 전구 장식 (C++)

5527번: 전구 장식 서강대학교의 축제 기간에 상근이는 매년 AS관 복도에 화려한 장식을 꾸민다. 장식은 전구 N개로 이루어져 있고, 전구는 왼쪽에서 오른쪽으로 일렬로 배열되어 있다. 각 전구는 불이 켜있을 수 www.acmicpc.net 다이나믹 프로그래밍 가만히 머리로만 생각할 때는 잘 떠오르지 않다가 손으로 패턴이 될 만한것들을 적다보니까 풀 수 있었다. 가장 긴 증가하는 부분 수열 문제와 비슷한 느낌을 받았다. 증가하는 부분수열의 크기를 구할 때와 비슷하게 연속해서 나타나는 교대 패턴의 최대 길이를 구했다. 1번 예제 : 1 1 0 0 1 0 1 1 1 0 연속해서 나타나는 패턴의 길이는 1 2 4 1 2 이렇게 구할 수 있다. 나뉘는 구간은 그림에 나타난다 나뉘는 구간이 3개가 있다면 두번째 ..

[백준 17142] 연구소 3 (C++)

17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net BFS 삼성 SW 기출 BFS 시뮬레이션 문제! M은 최대 10개!! 바이러스도 최대 10개이므로 바이러스를 고를 수 있는 경우의 수는 최대 252개! -> 10C5 연구실의 최대 크기는 50x50 = 2500!! 252 * 2500 하면 약 60만개!! 0.25초 안에 해결하기 충분함! 바이러스를 고를 수 있는 경우의 수를 백트래킹을 통해서 구하고, 바이러스 M개를 고르면 고른 바이러스들을 가지고 bfs를 돌린다! 빈 칸에 도달한 경우에만 답을 갱신한다! -> 가장 마지..

[백준 17182] 우주 탐사선 (C++)

17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍, 비트마스킹 [백준 13308] 주유소 (C++) 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리 hyeo-noo.tistory.com 얼마 전 위 문제를 풀면서 다익스트라와 dp를 함께 쓰는 방법에 익숙해진 덕분에 풀 수 있었다 모든 행성이 서로 이..