코딩뚠뚠

풀이일시 : 2020-11-15 ​ 문제 : 알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자. K A K T X E A S Y R W U Z B Q P 이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다. X X X X X X X X 반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다. 이와 같은 문자판과 K..

풀이일시 : 2020-10-15 ​ 문제 : 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. ​ ​ 입력 : 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. ex) 3 4 7 10 ​ ​ 출력 : 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. ex) 7 44 274 ​ ​ 풀이 : DP문제의 기본문제이다. 다이나믹프로그래밍 문제는 ..

풀이일시 : 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-08 ​ 다이나믹프로그래밍 : 하나의 문제는 단 한번만 풀도록 하는 알고리즘으로 효율성을 개선하는 알고리즘이다. 가정1 - 큰 문제를 작은 문제로 나눌 수 있다. 가정2 - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 작동한다. 이미 계산한 결과는 배열에 저장함으로써 나중에 꺼내서 쓰기만 하면 되게끔 한다. ​ 문제 : dp로 피보나치 구현 풀이 : #include int d[100] = { 0, }; //배열 선언 및 전체 0으로초기화 int fibonacci(int x) { if (x == 1) return 1; //1과 2는 피보나치에서 뭘 더해서 나오는 수가 아니기때문에 거른다 if (x == 2) return 1; if (d[x] != 0){ return..