justgo_developer

[추상화] 추상화란? 어떤 영역에서 필요로 하는 속성이나 행동을 추출하는 작업 구체적인 사물들의 공통적인 특징을 파악해서 이를 하나의 개념으로 다루는 수단 예시) switch(자동차 종류) case 아우디: break; case 벤츠: break; default: breka; 이러한 경우 BMW 차가 추가 된다면 BMW에 대한 case문을 추가해야한다. switch(자동차 종류) case 아우디: break; case 벤츠: break; case BMW : break; default: breka; 하지만 추상화의 개념을 이용한다면 아래와 같이 코드를 작성할 수 있다. 추상화 개념인 Car 클래스를 사용한다. 따라서 이 코드는 자동차가 추가되더라도 변경될 필요가 없다. 물론 실제 changeEngineOi..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111import java.util.*; public class Main { static int N; static int L; static int[][] map; static boolean[][] visit; static int cnt; public static void main(String[] args) { Sc..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113import java.util.*; public class Main { static int N; static int[][] S; static int min ; public static void main(String[] args) { Scanner sc = new Scanner(System.in); ..

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.util.*;public class Main { static int N; static int[] number; static int[] op = new int[4]; static int min = Integer.MAX_VALUE; static int max = Integer.MIN_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); number = ne..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263import java.util.*; public class Main { static int N; static int M; static int[] arr; static int[] temp; static boolean[] visit; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); arr = new int[9]; temp = new int[N]; v..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import java.util.*; public class Main { static int N; static int M; static int[] arr; static int[] temp; static boolean[] visit; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); arr = new int[9]; temp = new int[N]; visit = new boolean..

knapsack problem- n개의 아이템과 배낭- 각각의 아이템은 무게 Wi와 Vi를 가짐- 배낭의 용량 W- 목적 : 배낭의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합예Greedy - 가격이 높은 것부터 선택- 무게가 가벼운 것부터 선택- 단위 무게당 가격이 높은것부터 선택->불가능 순환식bottom-up

LCS(Longest Common Subsequence) 순환식 항상 순환식은 base케이스로 수렴하는지 확인해야한다. 동적계획법

동적계획법1. 일반적으로 최적화문제(최소값,최대값) 혹은 카운팅 문제에 적용됨2. 주어진 문제에 대한 순환식을 정의한다.3. 순환힉을 memoization 혹은 bottom-up 방식으로 푼다. - subproblem들을 풀어서 원래 문제를 푸는 방식, 그런 의미에서 분할정복법과 공통성이 있음- 분할정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않음- 즉 서로 overlapping하는 subproblem들을 해결함으로써 원래 문제를 해결 분할정복법동적계획법 Optimal Substructure- 어떤 문제의 최적해가 그것의 subproblem들의 최적해로부터 효율적으로 구해질 수 있을 때 그 문제는 optimal substructure를 가진다고 말한다.- 분할정복법/탐욕..

행렬 경로 문제 - 정수들이 저장된 n x n 행렬의 좌상단에서 우하단까지 이동한다.단 오른쪽이나 아래쪽 방향으로만 이동할 수 있다.- 방문한 칸에 있는 정수들의 합이 최소화되도록 하라. Recursive algo. int mat(int i, int j){if (i==1 && j==1)return m[i][j];else if(i==1)return mat(1,j-1) + m[i][j];else if(j==1)return mat(i-1,1) + m[i][j];elsereturn Math.min(mat(i-1,j) , mat(i,j-1) ) + m[i][j]; } => 비효율적 Memoization:계산된 결과값을 캐시에 저장int mat(int i, int j){if(L[i][j] != -1)return L..