[백준] 9095번: 1, 2, 3 더하기 [C++]
알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 【 풀이 】 DP, 동적 계획법으로 해결 가능한 문제이다. 이 문제의 경우는 11개의 수만 대상으로 하기에, 규칙만 제대로 찾아내면 시간제한 혹은 메모리 제한에 걸릴 일은 없다. 처음에는 1, 2, 3으로 나타낼 수 있는 모든 경우의 수를 구하면서 규칙을 알아내려 했지만, 5가 넘어가면서 직접 경우의 수를 계산하기에는 그 수가 너무 많아졌다. 그래서 예제에 있는 답안을 토대로 구해보았다. 정수 n이 주어졌을 때 n을 1, 2, 3의 합으로 나타내는..
[백준] 2606번: 바이러스 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 링크: https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 【 풀이 】 DFS(깊이 우선 탐색)이나 BFS(너비 우선 탐색)을 이용하여 간단히 해결할 수 있다. DFS가 조금 더 간단하게 구현 가능하기에 DFS를 이용하여 해결했다. 방문 여부를 나타내는 배열과 인접 리스트(각 점에 인접한 점들을 나타내는 배열)를 선언하고 인접 리스트 각 노드의 깊이를 우선으로 반복문으로..
[백준] 2579번: 계단 오르기 [C++]
알고리즘 분류: 다이나믹 프로그래밍문제 링크: https://www.acmicpc.net/problem/2579과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/2579" data-og-url="https://www.acmicpc.net/problem/2579" data-og-image="https://scrap.kakaocdn.net/dn/Yeqka/hySE3iyM6M/iCmFo2mdABuEOxkh7OCYSK/img.png?width=2834&height=1480&face=0_0_2834_1480,https://s..
[백준] 1463번: 1로 만들기 [C++]
알고리즘 분류: 다이내믹 프로그래밍 문제 링크: 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으로 모두 ..
[백준] 1003번: 피보나치 함수 [C++]
알고리즘 분류: 다이내믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 【 풀이 】 동적 계획법(DP, Dynamic Programming)을 이용하여 해결하는 문제이다. 동적 계획법은 한 문제를 여러 문제로 나누어서 각 문제는 단 한 번만 풀도록 각 답안을 매번 저장하는 알고리즘이다. 쉽게 말해서, 이 문제의 경우 피보나치 함수 호출 중에 이전에 호출했던 피보나치 수들은 다시 호출하지 않도록 따로 다른 테이블에 저장해 놓고 가져다 쓰는 것이다. 또한 이 문제는 0이 출력되는 횟수와 1이 출력되는 횟수의 규칙성을 찾..
[백준] 11399번: ATM [C++]
알고리즘 분류: 그리디 알고리즘, 정렬 문제 링크: 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..
