Programming/알고리즘 문제
-
[c++] 백준 2133번 - 타일 채우기Programming/알고리즘 문제 2020. 11. 15. 10:50
#백준 2133번 URL 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 이번에는 3*N 크기의 벽을 2*1, 1*2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 마찬가지로 다이나믹 프로그래밍을 이용하여 문제를 해결해보자. n=1일 경우, 타일을 채울 수 있는 경우의 수가 0이다. 즉, d[1] = 0. n=2일 경우, 아래와 같이 3가지의 방법이 있다. 즉, d[2] = 3이다. n=3일 경우는 3*1의 타일이 세개가 연달아 나타나는 모양이므로 d[3]=0이다. n=4일 경우는 n=2일 경우에 3*2 타일을 배치하는 경우이므로 d[4] = 3*d[2]의 경우의 수가 있다고 할 수 있다. 또한, n=6일 경우 d..
-
[c++] 백준 11726번 - 2*n 타일링Programming/알고리즘 문제 2020. 11. 7. 21:56
# 백준 11726번 URL 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 다이나믹 프로그래밍 문제의 기본이라고 할 수 있는 '타일링' 문제이다. 기본적으로 다이나믹 프로그래밍에서는 규칙성을 찾아서 점화식을 찾는게 관건이라고 할 수 있다. 먼저, 수많은 타일이 이미 쌓여있고 1만큼 추가한다고 가정해보자! 위와 같은 경우, 이미 이전에 d(n-1)가짓 수로 타일을 배치한 상태에서 1가지의 방법으로 밖에 타일을 놓지 못한다. 두번째로, 2만큼 타일을 추가한다고 생각해보자. 이렇게 타일을 쌓는 방식은 앞서 고려했던 경우와 같으므로 고려..
-
[c++] 백준 10989번 - 수 정렬하기 3Programming/알고리즘 문제 2020. 11. 7. 01:49
# 백준 10989번 URL 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 숫자를 N개 만큼 입력 받는다. (각 숫자는 10000보다 작거나 같은 자연수) 이 문제는 속도가 O(nlog)이 나오는 퀵 정렬, 병합정렬, 힙정렬을 사용하게 되면 메모리 초과가 나오게 된다. 입력값이 10000보다 작다는 조건이 있으므로 여기서는 계수정렬을 사용한다. (계수정렬은 O(n)의 시간복잡도를 가진다) 또한 c++의 입력, 출력 방식인 cout, cin을 사용하게 되면 시간초과가 일어나므로 여기서는 printf()와 scanf()를 사용하였..
-
[c++] 백준 1431번 - 시리얼 번호Programming/알고리즘 문제 2020. 11. 7. 00:59
# 백준 1431번 URL 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 문자열의 수 N을 먼저 입력하고, N만큼 문자열을 입력한다. 1. 길이가 짧은 것 2. 길이가 같다면, 각 자리의 합이 작은것(숫자만 더할 것) 3. 각 자리의 합 또한 같다면 사전 순으로.. 위의 세가지 조건을 만족시켜 c++ STL의 sort를 사용하여 정렬한다. sort의 세번째 인자에는 compare 함수가 들어가며, compare 외에도 각 자리의 숫자의 합을 반환하는 integer_sum이라는 함수를 따로 구현하였다..
-
[c++] 백준 1181번 - 단어 정렬Programming/알고리즘 문제 2020. 11. 7. 00:24
# 백준 1181번 URL 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 1. 길이가 짧은 것 2. 길이가 같을 경우 사전 순으로 입력할 문자열의 수 N을 먼저 입력하고, N가지의 문자열을 입력한다. 그리고 각 N개의 문자열을 위의 두 가지 조건을 만족시켜 출력하는 문제였다. 문제 풀이는 간단하다. C++ STL에서 지원하는 sort를 사용하는 대신 세번째 인수로 bool 형식의 compare라는 함수를 사용하면 된다. compare라는 함수는 길이가 string.length() 함수를 사용하여 길이가 ..