하위 문제의 해를 이용하여 상위 문제의 해를 효율적으로 구하는 기법 '분할정복' 과의 차이 동적 계획법은 부분문제 사이에 연관성이 존재하고, 분할정복은 부분문제 사이에 연관성이 없다. 동적 계획법은 부분문제가 중복되고, 분할정복은 부분문제가 중복되지 않는다. 구현 방식 Top-Down 방식과 Bottom-Up 방식이 있는데, 각 방식이 압도적 우위를 가지는 장단점은 명확하지 않다. Top-Down 전체문제에서 가장 작은 부분문제까지 호출한 뒤, 가장 작은 부분문제부터 해결값을 기억(Memoization)하고 재활용하면서 전체문제를 해결하는 방식 재귀를 주로 사용함. -> 메모리 문제 주의 Bottom-up 가장 작은 부분문제부터 호출해가며 해결값을 기억(Tabulation)하고 재활용하면서 전체문제를 해..
https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 class Solution { public int solution(int n) { int[] dpArr = new int[n+1]; dpArr[0]=0; dpArr[1]=1; for(int i=2; i
https://school.programmers.co.kr/learn/courses/30/lessons/12924 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 class Solution { public int solution(int n) { int answer = 0; int tmp = 0; for(int i=1; i
https://school.programmers.co.kr/learn/courses/30/lessons/70129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 class Solution { public int[] solution(String s) { StringBuilder sb = new StringBuilder(); for(int i=0; i1){ transformCount++; for(int i=0; i=1){ if(tmp==1) { sb.insert(0,1); tmp=tmp/2; } else{ sb.insert(0,tmp%2); tmp=tm..
https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 import java.util.*; class Solution { boolean solution(String s) { Stack stack = new Stack(); for(int i=0; i
https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 /* 양쪽 배열에서 각각 가장 작은 값을 고르고 가장 큰값을 고르면 된다. 사실 수학적 증명은 완벽하진 않다. 그래도 맞는 것 같다. */ /* 배열 A는 오름차순, 배열 B는 내림차순으로 정렬한다. 첫 요소부터 순서대로 배열 A는 최솟값, 배열 B는 최댓값이다. 둘을 곱해서 더하면 된다. */ import java.util.*; class Solution { public int soluti..
