그냥혀유 그냥혀유

데이터를 동적으로 할당하는 linkedList에 대해서 알아보기 전에 간단하게 그 컨셉에 대해 구현해보았다. #include #include typedef struct _node{ int data; struct _node* next; }node; int main(){ node* head =NULL; node* tail =NULL; node* cur =NULL; node* newnode = NULL; int readData; //데이터 읽기 while(1){ printf("자연수를 입력 하시오 종료하려면 0 입력"); scanf("%d",&readData); if(readDatadata =readData; newnode->next = NULL; if(head==NULL){ head=newnode; } el..

전에 풀었던 1,2,3 더하기 업그레이드 버전이다. 같은 수를 중복하지않은 1,2,3 더하기를 만들면된다. 여기서 중복, 감소, 증가라는 단어를 살펴보면 1,1,2,3,4,3,2,1 -> 수를 바로 옆과 비교해서 두개씩 끊어서 생각해보면 된다. 1,1중복 -> 1,2중복x 증가 -> 2,3증가 ->3,4증가->4,3감소 계속 양 옆을 비교하는 것이다. 이제 문제로 돌아가보자. 문제에서는 중복되는 경우의 수를 제거하고 1,2,3을 사용해서 숫자를 만드는 경우의 수를 찾고 싶다. 예시 처럼 4를 만들고자 한다면, 3+1, 1+3,1+2+1의 꼴로 만드는 것이다. 먼저 그냥 1,2,3 더하기 처럼 생각해보자 N이라는 숫자를 만드는 경우의 수는 다음과 같다. N = N-1 +1 N-2 +2 각각 마지막 수까지 ..

구매하려는 카드 N이 주어졌을 때, 카드 N개를 갖기 위해 지불해야하는 금액의 최댓값을 구하는 문제이다. 먼저 문제를 분석해보자. 민규는 카드를 어떻게 구매할 수 있을까? 각 카드팩의 가격이 카드의 갯수와 함께 주어졌다. 카드 1개 p[1] = M원 카드 두개 p[2] = K원 .. 민규가 N개의 카드를 구매한다면, N-1개가 들어있는 카드팩을 구매하고 p[1]개를 구매해서 N개 N-2개가 들어있는 카드팩을 구매하고 p[2]개를 구매해서 N개 0개가 들어있는 카드팩을 구매하고 p[N]개를 구매해서 N개를 구매하는 경우의 수로 나누어 생각해 볼 수 있을 것이다. 우리는 이 중에서 가장 비싸게 카드를 구매하는 방법을 찾으면 된다. 따라서 점화식은 D[n] = MAX(p[i] + D[n-i])일 것이다. 구하..

2*n타일링 문제에서 채울 수 있는 타일 2*2가 추가 된 것이다. 이제 2*2 타일은 2*1과 1*2와 2*2타일로 채울 수 있다. 3가지 타일로 다른 2*n타일로 마찬가지로 n-1타일에 2*1타일 추가 n-2타일에 1*2위아래 추가 n-2타일에 2*2타일 추가의 경우의 수로 2*n타일을 채우는 경우의 수를 생각할 수 있으니 점화식은 D[n] = D[n-1]+D[n-2]+D[n-2]이다. 상태:N , 종료조건 : 0일때는 0 1일때 1개 2일때 3개 return import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static int[] d; public static void main(Stri..

2*N 사이즈의 사각형을 2*1 타일 혹은 1*2타일로 채우는 방법의 경우의 수를 찾는 문제이다. - 먼저 상태와 종료조건을 생각해보자. => 상태 N , 종료조건 : ? 변하지 않는 것: 각 2*N의 타일을 채우는 경우의 수 가령 2*2타일을 채운다면, 2*1 옆으로 두개 1*2위아래로 두개씩 채울 수 있는 경우의 수 2가지 등 2*N의 타일을 채우는 경우의 수를 찾는 과정에서 생기는 2*N-1 ....2*1을 채우는 경우의 수는 변하지 않을 것이다. 이제 큰 문제를 작은 문제로 쪼개서 생각해보자. 2*N타일을 채우는 과정에서 2*n-1 ..2*n-2.. 2*n-3의 타일들을 채우는 경우의 수가 변하지 않는다면, 이를 활용할 수 있을 것이다. 2*N-1타일에서 2*1타일 하나가 추가된 모양이 2*N타일..

정수 N을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제이다. -먼저 상태와 가장 작은문제를 종료하기 위한 조건을 생각해보자: 상태: N ,종료조건: ? (종료조건 ->더 이상 재귀호출하지않고 이전 호출로 return 시작) 점화식을 만들면서 종료조건을 생각해보자. 문제를 해결하면서 변하지 않는 값 -> 각 수를 만드는 경우의 수 가령 1 => 1개, 2 = 1+1, 2 두개 , 3 = 1+1+1, 1+2, 2+1, 3 4개 등등의 경우의 수는 다른 N을 구하는 과정에서 나오더라도 변하지 않을 것이다. 점화식 N이라는 숫자를 만들기 위해 1,2,3만을 이용해야한다면, N = N-1 +1 = N-2 +2 = N-3 +3 꼴 일 것이다. 예제의 4를 보면 4 = 1+3, 2+2 등으로 표현할 수 있는..

정수 N이 주어졌을 때, 세가지 방법의 연산으로 1로만드는 최소 방법의 수를 구하는 문제이다. 먼저 상태와 가장 작은문제를 종료하기 위한 조건은 직관적이다 --> 상태 :N , 종료조건 N ==1 이제 문제를 풀기위한 점화식을 생각해보자. 먼저, 큰 문제 D[N]을 작은 문제로 쪼개서 생각해보자. (D[N] => N을 만드는 가장 최소의 경우의 수 return) **계산하는 과정에서 변하지 않는것 -> 각 수를 최소방법으로 1로만드는 경우의 수 ex D[2] : 2 ->1 (/2) ,D[3] :3 -> 1 (/3) , D[4] : 4 -> 2 -> 1 (/2) **기억해야할 것 : 각 단계에서 1로만드는 최소의 경우의 수 그렇다면 D[N]을 최소의 경우로 1로만드는 조건은 N을 -> N/3 or N/2 ..

- 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. - 큰 문제를 작은 문제로 쪼개는 알고리즘은 다이나믹 프로그래밍과 분할정복이 있다. 두 알고리즘의 차이는 문제를 작은 문제로 만들었을 때, 분할정복과 다르게 dp는 중복이 가능하다는 점이다. (따라서 중복을 잘 다뤄야한다.) - 문제가 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다. 1. overlapping Subproblem (겹치는 작은 문제) 2. optimal substructure (최적부분구조) - 1번 속성에 의해 문제를 큰 문제와 작은 문제로 쪼갤 수 있어야하고, 큰 문제와 작은 문제는 같은 방식으로 풀 수 있어야한다. - 2번 속성에 의해 문제의 정답을 작은 문제의 정답에서 구할 수 있다. -> 최적부분구조를 만..