[백준] 1697번: 숨바꼭질 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 【 풀이 】 1차원 배열에서의 BFS 로 해결할 수 있는 문제이다. 수빈이의 현재 점(N) 부터 BFS 를 해서 +1, -1, *2를 했을 때 나오는 위치들을 모두 방문처리 해주고 그 위치에 도달했을 때의 시간을 따로 기록해주면 된다. 【 코드 】 #include #include using name..
[백준] 1932번: 정수 삼각형 [C++]
알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 【 풀이 】 삼각형의 규칙을 구하면 된다. 2차원 배열 dp에 입력 받고, 각 칸까지 선택된 수의 합을 각 칸에 다시 저장한 2차원 배열을 dp라고 하자. dp[1][1] = dp[1][1] dp[2][1] = dp[1][1] + dp[2][1], dp[2][2] = dp[1][1] + dp[2][2] 이다. 3번째 층부터, 가운데의 수들은 양쪽 대각선에 저장된 숫자 중 가장 큰 값과 더해져야 한다. 즉, dp[3][1]..
[백준] 14940번: 쉬운 최단거리 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 【 풀이 】 모든 정점들을 방문하면서, 각 정점마다 목표 지점까지의 거리를 다른 배열에 기록해 주면 되는 문제이다. BFS를 이용하여 쉽게 해결할 수 있다. 단, 목표 지점을 기준으로 BFS 를 시작해야 원하는 답을 얻을 수 있다. 왜냐하면 목표 지점에서부터 거리가 0으로 시작하기..
[백준] 1931번: 회의실 배정 [C++]
알고리즘 분류: 그리디 알고리즘, 정렬 문제 링크: https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 【 풀이 】 시작 시간과 끝나는 시간 사이에 겹치는 회의 시간이 없이 사용 가능한 최대 회의 개수를 구하는 문제이다. 이는 곧 겹치지 않고 가장 최소인 회의시간들만 구하면 된다는 것인데, 입력으로 주어진 회의시간들을 시작 시간을 기준으로 정렬해야 한다. 그리고 시작 시간이 같다면, 같은 것끼리는 종료 시간을 기준으로 또 정렬한다. 또 한가지 주의해야할 점은 시작하자마자 끝나는 회의인데, 얘네들은 여러개 나와도 모두 카운트해주어야 한다. 자세한 풀이는 다음과 같다..
[백준] 11724번: 연결 요소의 개수 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 【 풀이 】 서로 연결되어 있는 정점의 그룹이 몇 개인지를 구하는 문제이다. 정점이 서로 연결되어 있는지만 확인하면 되므로, 비교적 구현하기 쉬운 DFS 로 문제를 해결했다. DFS 함수를 호출할 때 연결되어 있는 곳은 이미 다 방문처리가 되므로, 반복문으..
[백준] 18870번: 좌표 압축 [C++]
알고리즘 분류: 정렬, 값/좌표 압축 문제 링크: https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 【 풀이 】 범위 내의 중복된 값을 뒤로 보내주는 unique 함수와, 이진 탐색 기반으로, 찾으려는 값보다 크거나 같은 숫자가 몇 번째 인덱스에서 처음 나오는지를 알려주는 lower_bound 함수를 이용하여 해결했다. 풀이 과정은 다음과 같다. 우선 원본 좌표를 저장한 벡터와 원본 좌표를 복사..
