[백준] 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 함수를 이용하여 해결했다. 풀이 과정은 다음과 같다. 우선 원본 좌표를 저장한 벡터와 원본 좌표를 복사..
[백준] 1016번: 제곱 ㄴㄴ 수 [C++]
알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체 문제 링크: https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 【 풀이 】 에라토스테네스의 체를 활용하여 해결하는 문제이다. 처음엔 2부터 하나씩 제곱해 가면서 4, 9, 16, 25, 36.. 등의 제곱수들로 나누어 떨어지는 지를 체크해서 하나씩 제거해 가는 아이디어를 떠올렸다. 하지만 가능한 min 값이 0부터 1,000,000,000,000, 즉 1조나 된다. ..
