코딩뚠뚠

풀이일시 : 2020-08-19 ​ 문제 : N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. ​ 입력: 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. ex) 3 2 //3번이 2번보다 앞 1 3..

풀이일시 : 2020-08-09 ​ 문제 : 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자. ​ 입력 : 첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다. ​ 출력 : 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. ​ 풀이 : 다이나믹프로그래밍 DP를 이용한다 dbstndi6316.tistory.com/35?category=953970 [개념정리] DP 동적프로그래밍 Dynamic Programing, DP, 동적프로그래밍, 동적계획법 으로 중요한 알고리즘 중 하나이다. ​ DP란 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 방식은 분할정복과 같으나 분할정복은 계산한 부 dbstndi6316.tistory.com 가장 ..

풀이일시 : 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..