boj

[백준 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..

[백준 3977] 축구 전술 C++

3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 강한 연결 요소 1. 문제 해결 아이디어 도미노 문제와 매우 비슷한 문제이다. 이 문장을 통해서 SCC임을 알 수 있다. 강한 연결 요소 (SCC) - 타잔 알고리즘 [백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으..

[백준 1504] 특정한 최단경로 C++

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 반드시 방문해야 하는 정점이 2개 주어진다. 예를 들어 1번 정점에서 4번 정점으로 가야하는데 2, 3번 정점을 반드시 거쳐야 한다고 하자 첫 번째로 1 -> 2 -> 3 -> 4 순으로 정점을 방문할 수 있다. 위 순서는 각 정점이 방문된 시점을 순서대로 나열한 것에 불과하다. 1에서 2, 2에서 3, 3에서 4로 가는 최단 거리를 구하기 위해서 중간에 다양한 정점을 방문할 수 있..

[백준 2213] 트리의 독립집합 C++

2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 트리 DP 1. 문제 해결 아이디어 [백준 1949] 우수 마을 C++ 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, hyeo-noo.tistory.com 위 문제와 표현하는 말만 다르지 결국 똑같이 서로 인접하지 않는 정점들의 가중치의 최댓값을 찾는 문제이다. 하지만..

[백준 2458] 키 순서 C++

2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 플로이드-와샬 1. 문제 해결 아이디어 자신보다 키가 큰 게 확실한 사람, 키가 작은 게 확실한 사람들의 수를 구하면 된다. 주어진 방향그래프에서 자신이 도달할 수 있는 정점들이 모두 자신보다 키가 큰 학생임을 알 수 있다. 자신보다 키가 작은 학생들도 알아야 하므로 입력이 주어질 때 역방향 그래프도 같이 저장한다. 역방향 그래프에서 자신이 도달할 수 있는 정점들이 모두 자신보다 키가 작은 학생임을 알 수 있다. 따라서 임의의 정점에서 다른 모든 정점으로 갈 수 ..