감사하며 살기

sw_1226 미로1DFS를 이용해서 미로의 길을 찾는 문제이다.입력버퍼DFS - 방문했던 곳은 다시 방문하지 않아도 된다.CODE입력버퍼cpu가 사용자의 입력을 그때그떄 처리하면 무리가 간다. 그래서 버퍼에 저장하고 있다가 사용자의 입력이 끝나면 데이터를 가져온다. 데이터를 가져오는 함수가 scanf, cin, getline 등 이다. 사용자가 입력을 하면 입력한 문자는 stdin이라는 버퍼에 저장된다. 그리고 '\n' 개행문자를 입력하면 사용자가 입력이 끝났다고 생각하고 scanf함수가 데이터를 cpu로 가져온다. 하지만 만약 scanf("%d", &number); 함수를 호출하면 버퍼에 저장된 '1234592\n' 중 '\n'을 제외한 1234592를 cpu로 가져오게된다 그렇게 되면 다음 줄에 한..

문제, 시뮬레이션

톱니바퀴문제를 이해한다.어떻게 풀지 계획을 세운다.처음에는 cache를 만들어 톱니바퀴의 n,s극의 다름을 저장하고 while문으로 톱니바퀴를 돌리려고 했다.계획을 수행해서 문제를 해결한다.먼저 명확하게 기능이 분리 가능한 turn 함수를 만든다.그리고 각 톱니바퀴의 n,s극을 비교한다. 결과를 cache에 저장한다. while문을 통해 turn 함수를 호출한다.결과를 if문을 통해 도출 #include #include #include using namespace std; ​ ​ char gear[5][8]; int turnChk[5]; ​ void turn(int gearNum, int direction) { int temp; switch (direction) { // 시계 방향 case 1: temp..

분할정복과 비슷하다. 문제를 작게 나눈 뒤 조각의 답을 계산하고, 이 답들로 부터 원래의 문제에 대한 답을 구한다.동적계획법은 이항계수를 통해 쉽게 알 수 있다. int bino(int n, int r) { if(r==0 || n==r) return 1; return bino(n-1, r-1) + bino(n-1, r); }하지만, 이는 중복으로 호출되는 함수가 많다. 캐시 배열을 만들어 각 입력에 대한 반환값을 저장해놨다가 함수가 호출될 때마다 이 배열에 접근해 값이 저장되었는지를 확인한 후 저장되어있다면 즉시 반환한다.메모이제이션 : 한번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법 int cache[30][30] // -1로 초기화 int bino2(int n, int r) { if (r==0 ..

문제:삼각형을 타고 내려가서 최대인 값을 구하여라 package 숫자삼각형_1932; //import java.lang.reflect.Array; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int input = sc.nextInt(); int max = 0; int dp[][] = new int[input + 1][]; int num[][] = new int[input + 1][]; // 동적할당 for (int i = 1; i < input + 1; i++) { for (int j ..

package 붕어빵판매하기_11052; //혜빈이가 붕어빵이 남아 있는데 남은 붕어빵을 세트로 묶어서 판다고한다 //가장 큰 수익을 남겨야하고 그 최대 수익을 출력하시오 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int iter = scan.nextInt(); int[] set = new int[iter+1]; int[] dp = new int[iter+1]; int max = 0; // 배열에 값을 각 세트의 가격을 저장한다. for(int i=1;i

완전탐색, 동적계획법 - 전체를 고려해서 최적해 구하기 탐욕법 - 그때 그때 최선을 찾는 경우 동적계획법보다 수행시간이 빠르다. 최적해를 구하기 힘들때, 적당히 괜찮은 답을 찾는 것.(임의의 답보다는 좋은 답을 구하는 용도) 근사해 구하는 문제 탐욕법 조합탐색 메타휴리스틱 알고리즘의 정당성을 증명하는 과정이 꼭 필요 예제 회의실 예약 회의실을 예약하는데, 최대로 예약할 수 있는 회의의 개수 구하기 알고리즘 정당성 증명 무식하게 풀 수 있을까? - 시간대로 나누었을 때 n이 30만 되어도 시간안에 문제 풀긴힘들다(2^30) 탐욕적 알고리즘의 구상 길이가 짧은 회의 선택(예외 발생) 빨리 끝나는 회의 선택 - 목록에 남은 회의중 가장 일찍 끝나는 회의를 선택 - 일찍끝나는 회의와 겹치는 회의를 다지운다. -..

처음에 생각과는 전혀 다른 방법으로 시도해야 할 때도 있다. 손으로 여러 간단한 입력, 예제 입력 등으로 직접 해결해 보는 것. 그리고 그것을 공식화 해서 답을 만드는 방법 출전 순서 정하기 프로코더들의 대회에서 결승전에 진출했다. 결승전은 각자 1:1을 해서 많이 승수가 많은 팀이 승리한다. 각 선수의 레이팅을 비교해서 더 높은 사람이 승리하고, 같다면 우리선수가 승리한다고 할때, 어떤순서대로 내보내야 승수를 최대화 할 수 있을까? 경기 1 2 3 4 5 6 러시아팀 3000 2700 2800 2200 2500 1900 한국 팀 2800 2750 2995 1800 2600 2000

처음에 생각과는 전혀 다른 방법으로 시도해야 할 때도 있다. 손으로 여러 간단한 입력, 예제 입력 등으로 직접 해결해 보는 것. 그리고 그것을 공식화 해서 답을 만드는 방법 실험 데이터 복구하기 진호가 데이터를 날려 먹어서 데이터를 위조하려고 힌다. 데이터의 조각을 입력하면 조각을 모두 포함하는 가장짧은 문자열을 반환 하는 문제. 입력 3

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. #include using namespace std; int main() { int input,i,j; int max,fin=0; cin >> input; int *num = new int[input]; int *dp = new int[input]; for (i = 0; i > num[i]; } //그러니까 이거는 먼저 1개를 고정해놓고 그 고정된수가 가장 크다고 가정하고 //처음부터 고정된수와..