코후닝

알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 【 풀이 】 DP 문제이다. 다른 문제들과 마찬가지로 처음부터 경우의 수를 따져가며 규칙성을 찾는 것이 중요하다. 결론적으로는 이 문제는 피보나치수열의 형태를 보인다. N[1] = 1 N[2] = 2 N[3] = 3 N[4] = 5 N[5] = 8, N[6] = 13, N[7] = 21, N[8] = 34, N[9] = 55 즉 N[n] = N[n-2] + N[n-1]...

알고리즘 분류: 수학, 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 【 풀이 】 동적계획법으로 해결 가능한 문제이다. 다른 DP 문제들과 마찬가지로 규칙을 찾아 점화식을 도출해 내는 것이 중요하다. 역시 규칙을 찾을 때까지 나열해보고 분석하면 된다. 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12 P[1] = 1 P[2] = 1 P[3] = 1 P[4] = P[1] + P[2] = 2 P[5] = P[2..

알고리즘 분류: 수학, 자료 구조, 조합론, 해시를 사용한 집합과 맵 문제 링크: https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 【 풀이 】 조합에 대한 수학적 사고력과 이를 해시맵으로 해결하는 능력을 묻는 문제이다. 조합(Combination)에 대해서 깊게 생각해 봤지만, 간단한 아이디어 하나로 풀 수 있는 문제였다. 같은 종류의 의상을 2개 이상..

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

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 링크: https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 【 풀이 】 DFS(깊이 우선 탐색)이나 BFS(너비 우선 탐색)을 이용하여 간단히 해결할 수 있다. DFS가 조금 더 간단하게 구현 가능하기에 DFS를 이용하여 해결했다. 방문 여부를 나타내는 배열과 인접 리스트(각 점에 인접한 점들을 나타내는 배열)를 선언하고 인접 리스트 각 노드의 깊이를 우선으로 반복문으로..

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