Algorithm

[백준 1321] 군인 C++

1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 세그먼트 트리 10개월 만에 다시 풀어보는 세그먼트 트리문제이다. 우선 a ~ b 구간의 부대의 인원의 합을 하나의 노드로 잡고 세그먼트 트리를 만들었다. 특정 부대의 증원이나 감원을 할 때는 업데이트 쿼리를 만들어서 수행했다. ex) 2번 부대의 인원이 늘어났다면 1-5번, 1-3번, 2번 노드의 인원이 모두 같은 수 만큼 증가해야 한다. 마지막으로 군인을 배치하는 arrangement쿼리를 만들었다. 군인의 번호가 왼쪽 자식 노드의 최대 인원보..

[백준 1944] 복제 로봇 C++

1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 최소 스패닝 트리 - MST 현재 로봇이 복제를 거듭하며 열쇠를 찾으러 다니는 이동거리를 가장 작게 해야한다. 전체 이동거리를 가장 작게 해야하므로 다익스트라가 아니라 MST알고리즘을 사용해야 한다는걸 알았다. 입력을 받으면서 시작점과 모든 열쇠들은 정점이 되므로 정점 vector에 넣어준다. 정점들 간의 거리를 BFS를 통해 모두 구하고 간선의 정보를 저장한다. BFS 매번 돌면 자신을 제외하고 시작점을 포함한(M-1+1) M번 ..

[백준 2262] 토너먼트 만들기 C++

2262번: 토너먼트 만들기 월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러 www.acmicpc.net 그리디 랭킹이 높은 사람이 반드시 이기기 때문에 우승자는 항상 1번이다. 부전승이 여러번 있어도 상관없기 때문에 매번 가장 랭킹이 낮은 사람(번호가 높은 사람)만 경기를 하게 했다. 랭킹이 가장 낮은 사람(자신)의 양 옆 사람 중에서 자신과 랭크 차이가 적게 나는 사람과 경기를 치러야 한다. 랭크 차이가 많이 나는 사람과 경기를 치르게 되면 그 사람은 랭크차이가 많이 나는 만큼 경기를 더 많이 치러야 하기 때문이다. 경기를 더 많이 한다면 그만큼 최솟값과는 멀어질 수..

[백준 2211] 네트워크 복구 C++

2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 다익스트라 최소 스패닝 트리의 탈을 쓴 다익스트라 문제였다. 끊어진 그래프에서 최소 개수의 회선만을 복구해야 한다고 하길래 n-1개의 간선을 연결시켜서 모든 컴퓨터를 연결해 주는 MST 문제로 착각했다. 위 그래프에서 MST는 어떻게 될지 생각해보자 2-3, 2-4, 1-3 간선이 모여서 MST를 이룰 수 있다. 하지만 이 때 1 -> 2로가는 비용은 5가 되고, 1 -> 4로 가는 비용은 7이 된다. 각각 기존의 최단거리였던 4, 3..

[백준 1774] 우주신과의 교감 C++

1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 최소 스패닝 트리 Minimum Spanning Tree (MST) - Kruskal 크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기 모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다. 유니온 파인 hyeo-noo.tistory.com 통로의 개수 1000개 이미 연결이 되어있다고 입력받은 노드들끼리는 Union_Node를 수행한다. adj..

[백준 1602] 도망자 원숭이 C++

1602번: 도망자 원숭이 첫 번째 줄에는 도시의 개수 N (2 ≦ N ≦ 500) 과 도로의 개수 M (0 ≦ M ≦ 10,000), 그리고 질문의 개수 Q (0 ≦ Q ≦ 40,000) 가 주어진다. 그 다음 줄에, N개의 정수로 각 도시에서 멍멍이가 원숭이를 괴 www.acmicpc.net 플로이드-와샬 쿼리(Q)가 최대 4만개 들어온다. 출발도시와 도착도시가 주어졌을 때 플로이드 최단경로를 구하고, 경로상의 정점 중 멍멍이가 괴롭힐 수 있는 최대 시간을 구한다면 O(40000 * N^3) 으로 시간초과가 발생한다. 플로이드의 특징을 잘 생각해보자 경유하는 점은 보통 1 ~ N 번까지의 점을 순서대로 경유하도록 한다. 이는 그냥 편의를 위해서 사용하는 순서이고 경유점의 순서가 바뀌더라도 결국 A->..

[백준 20165] 인내의 도미노 장인 호석 C++

20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 구현, 시뮬레이션 도미노 넘어뜨리는 구현 : crash_domino() 참고 현재 넘어지고 있는 도미노 : last 곧 넘어질 수도 있는 도미노 : Map[nr][nc] 현재 넘어지는 도미노의 최대길이를 구한다. last = max(last, Map[nr][nc]) 만약 도미노가 있다면 넘어뜨린다. Map[nr][nc] = 0 nr과 nc를 현재 방향에 맞춰서 이동시킨다. 하나 넘어뜨렸으므로 현재 넘어지고 있는 도미노의 길이를 1 감소시킨다. 1 2..

[백준 16681] 등산 C++

16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 다익스트라 시작점은 항상 1이고 도착점은 항상 N이다. 시작점에서 도착점으로 가면서 높이가 점점 높아지는 최단거리 다익스트라를 수행한다. 도착점에서 시작점으로 가면서 높이가 점점 높아지는 최단거리 다익스트라를 수행한다. 임의의 가운데 정점을 잡고 해당 정점이 시작점과 도착점 모두와 연결되어있다면 위 2개의 다익스트라를 통해서 시작점과 연결된 최단거리는 자연스럽게 높이가 증가하는 최단거리가 구해지고, 임의의 정점에서 도착점으로 가는 최단거리는 높이가 감소하..

[백준 1890] 점프 C++

1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 다이나믹 프로그래밍 dfs top-down방식으로 2차원 cache를 적용한 풀이. Cache[r][c] = r, c에서 점프해서 N-1, N-1에 도달할 수 있는 경우의 수. long long 주의. N-1, N-1에 도달하면 1을 리턴. Map의 원소가 0이면 0을 바로 리턴. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ..

[백준 2573] 빙산 C++

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS 현재 맵의 빙산의 개수가 0이 될 때까지 반복문을 수행한다. 물과 접촉한 빙산의 높이를 줄여주는 BFS를 수행한다. 높이가 달라진 빙산들은 임시 맵과 큐에 따로 저장한다. 임시 맵의 정보를 기존 맵으로 복사한다. 임시 큐의 빙산 정보를 기존 큐의 빙산정보로 옮김과 동시에 높이가 달라진 빙산들이 서로 떨어졌는지 확인하는 BFS를 수행한다. 중간에 서로 떨어진 경우에는 현재 year를 출력하고 return 한다. 1 2 3 4 5 6 7 8 9 10 1..