코후닝

알고리즘 분류: 다이내믹 프로그래밍 문제 링크: 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..

알고리즘 분류: 자료 구조, 문자열, 정렬, 해시를 사용한 집합과 맵 문제 링크: https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 【 풀이 】 반복자를 생성하고 map의 멤버 함수 중 하나인 find로 key 값을 저장한다. map.find(key)는 찾고자 하는 값이 없으면 map.end()를 반환하기 때문에, 이를 이용해 개수와 key의 value를 1씩 증가시킨다. 그 후 map을 순회하면서, value값이 1인 key를 출력해 주면 된..

알고리즘 분류: 자료 구조, 큐 문제 링크: https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 【 풀이 】 2023.04.09 - [백준 [BAEKJOON]] - [백준] 10845번: 큐 [C++] [백준] 10845번: 큐 [C++] 알고리즘 분류: 자료 구조, 큐 문제 링크: https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,..