코딩뚠뚠

풀이일시 : 2020-08-09 ​ 문제 : 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. ​ 입력 : 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. ​ 출력 : 첫째 줄에 경우의 수를 출력한다. ​ 풀이 : 가장 마지막에 오는 타일을 생각했을 때 나타나는 경우의 수는 세 가지이다. (그 이전 갯수는 N-2개) 또한 4개이상일 때부터 2의 배수가 될때마다는 고유한 모양이 2개씩 나타난다. D[i] = 3*D[i-2] + (2*D[i-4] + 2*D[i-6] + 2*D[i-8] + .... + 2*D[0]) 아래는 DP에 대한 포스팅이다. 이의 알고리즘으로 풀이했다. dbstndi6316.tistory.com/35?category=953970 [개념정리] DP 동적프로그..

풀이일시 : 2020-08-09 ​ 문제 : 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. ​ 입력: 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) ​ 출력: 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. ​ 풀이 : 점화식을 만들어보자 가장 마지막에 오는 타일을 생각해봤을 때 가능 한 경우의 수를 생각해본다면 1. 1x2 타일 (그 앞엔 N-1개) 2. 2x1 타일 (그 앞엔 N-2개) 3. 2x2 타일 (그 앞엔 N-2개) 점화식 D[i]=D[i-1]+2*D[i-2] 를 도출해 낼 수 있다. DP에 대한 포스팅이다. 점화식을 쓰는것은 이 알고리즘을 사용한것이다. dbstndi6316.tist..

풀이일시 : 2020-08-09 ​ 문제 : 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. ​ 입력: 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) ​ 출력: 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. ​ 풀이 : 2*n 크기의 직사각형을 1*2, 2*1 타일로 채우는 방법의 수를 구하는 프로그램 작성한다. 가장 마지막에 오는 타일을 기준으로 생각해보았을때 가능한 경우는 오직 두가지이다. -> 1*2 (그전까지는 N-1개) or 2*1 2*1 배치 (그전까지는 N-2개) #include using namespace std; int d[1001]; int dp(int x) { if (x == 1..

풀이 일시 : 2020-08-04 ​ 문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. ​ 입력: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. ex) 10 5 2 3 1 4 2 3 5 1 7 ​ 출력: 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. ex) 1 1 2 2 3 3 4 5 5 7 ​ 풀이 : N이 1000만 이하이기때문에 무조건 O(N)을 요구한다. 대부분의 알고리즘으로는 풀지못하므로 계수정렬로 풀어야 한다. #include using namespace std; int n,m; int a[10001]; /..

#include #include #include using namespace std; int n; vector v; int getSum(string a) { int n = a.length(); int sum = 0; for (int i = 0; i < n; i++) { if (a[i] - '0' = 0) { //string 중 숫자만 구분해서 더한다. sum += a[i] - '0'; } } return sum; } bool compare(string a, string b) { if (a.length() != b.length()) //첫번째 고려사항 길이가 짧은것이 먼저온다. return a.length() < b.length(); else { //두번째 고려사항 길이가 같다면 합이 작은게 먼저온다. i..

풀이 일시 : 2020-08-04 ​ 문제 : 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 1. 길이가 짧은 것부터 2. 길이가 같으면 사전 순으로 ​ 입력: 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. ex) 13 but i wont hesitate no more no more it cannot wait im yours ​ 출력: 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. ex) i im it no but more wait won..

풀이일시 : 2020-07-30 ​ 문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. ​ 입력 : 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. ex) 5 5 4 3 2 1 ​ 출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. ex) 1 2 3 4 5 ​ 풀이 : 수의 개수가 100만 이하라는 것에 주목하자. -> O(N^2) 의 시간복잡도를 가지는 정렬 알고리즘을 사용하게되면 100만 * 100만 = 1조 까지 나올 수 있다. 하지만 시간제한이 1초이기 때문에 대략 이정도의 시..

풀이 일시 : 2020-07-30 ​ 문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. ​ 입력 : 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. ex) 5 5 2 3 4 1 ​ 출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. ex ) 1 2 3 4 5 ​ 풀이 : N을 먼저 입력 받고 N개의 숫자를 입력받아 배열에 입력해준다. 이후 원하는 sort 알고리즘으로 sort 후 출력한다. 시간복잡도 O(N^2) #include #define MAX 1001 int a[MAX]; int main(..