알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 링크: https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 【 풀이 】 DFS(깊이 우선 탐색)이나 BFS(너비 우선 탐색)을 이용하여 간단히 해결할 수 있다. DFS가 조금 더 간단하게 구현 가능하기에 DFS를 이용하여 해결했다. 방문 여부를 나타내는 배열과 인접 리스트(각 점에 인접한 점들을 나타내는 배열)를 선언하고 인접 리스트 각 노드의 깊이를 우선으로 반복문으로..
알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 【 풀이 】 이 문제 역시 동적계획법(DP)을 이용하여 해결하는 문제이다. 또한 문제의 규칙성을 찾는 것이 굉장히 중요하다. 우선, 본인은 계단의 수가 5일 때까지 계단을 오르는 모든 경우의 수를 구해보았다. 계단의 점수를 저장해놓은 배열 stair과 경우의 수에 따라 계단의 점수를 더한 것 중 최댓값을 저장하는 배열 score를 선언한다. 계단의 수는 5개라고..
알고리즘 분류: 다이내믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 【 풀이 】 동적 계획법(DP, Dynamic Programming)을 이용하여 해결하는 문제이다. 그리고 이 문제 역시 여러 경우의 수를 생각하며 규칙성을 찾는 것이 중요한데, 이 규칙을 찾는 것이 어려웠던 것 같다. 우선 index를 피연산수, 값을 연산 횟수로 배열을 선언한 다음 1~10까지의 수를 검사하며 규칙을 찾아나갔는데, 규칙은 대충 다음과 같이 나왔었다. 2와 3으로 모두 나누어 떨어지지 않는 수: 1 + dp[index - 1] 2와 3으로 모두 ..
알고리즘 분류: 다이내믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 【 풀이 】 동적 계획법(DP, Dynamic Programming)을 이용하여 해결하는 문제이다. 동적 계획법은 한 문제를 여러 문제로 나누어서 각 문제는 단 한 번만 풀도록 각 답안을 매번 저장하는 알고리즘이다. 쉽게 말해서, 이 문제의 경우 피보나치 함수 호출 중에 이전에 호출했던 피보나치 수들은 다시 호출하지 않도록 따로 다른 테이블에 저장해 놓고 가져다 쓰는 것이다. 또한 이 문제는 0이 출력되는 횟수와 1이 출력되는 횟수의 규칙성을 찾..
알고리즘 분류: 그리디 알고리즘, 정렬 문제 링크: https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 【 풀이 】 그리디 기초 문제 중 하나이다. 이 문제의 경우에는 정렬했을 때의 각 요소의 값이 최적의 경우가 되기 때문에 먼저 정렬을 해주고 계산을 해주는 것이 중요하다. 【 코드 】 #include #include using namespace std; int main(void) { int human[1001]; int n; int sum=0; cin >> n; for (in..
알고리즘 분류: 그리디 알고리즘 문제 링크: https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 【 풀이 】 그리디 알고리즘을 활용하는 그리디 기초 문제이다. 동전 거스름돈은 항상 가장 큰 금액의 동전부터 거슬러 주는 것이 최적해이기 때문에 n개의 동전들을 배열에 저장해 주고 배열의 맨 뒤에서부터 계산해 주면 된다. 【 코드 】 #include using namespace std; i..