Now Loading ...
-
-
dynamic programming
동적 계획법(Dynamic Programming)
WHAT IS?
하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 컨셉! 수열의 점화식 느낌 유남생? aka ‘기억하며 풀기’
WHY USE?
사실 DP는 일반적인 재귀법과 매우 유사함. 하지만 그 효율성은 말도 못하게 더 높다.
일반적인 재귀법은 보통 O(n^2)의 시간 복잡도를 나타내는 반면 DP는 O(f(n))의 시간 복잡도를 보인다.
위 그림처럼 재귀법을 사용한다면 불필요하게 한번 구했던 값 (=함수 호출 횟수)을 한번 더 구해야함.
이때 한번 구한 작은 문제의 결과 를 저장했다가 재사용 하면 굉장히 효율적이게 되겠죵?
이것이 바로 DP의 핵심 개념입니다!
WHAT CONDITIONS?
DP를 사용하기 위해서는 아래 2조건을 만족해야 합니다.
겹치는 부분 문제 (Overlapping Subproblems)
DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.
최적 부분 구조 (Optimal Substructure)
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다.
만약, A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다.
HOW USE?
아래 단계를 거쳐 문제를 해결할 수 있습니다.
DP로 풀 수 있는 문제인지 확인
문제의 변수 파악
변수 간 관계식 만들기(점화식)
메모하기(memoization or tabulation)
기저 상태 파악하기
구현하기
1. DP로 풀 수 있는 문제인지 확인
현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지를 판단
보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다.
2. 문제의 변수 파악
문제 내 변수의 개수를 알아내야 한다. ( = state를 결정한다.)
예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있다.
3. 변수 간 관계식(점화식) 만들기
변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일하므로 우리는 이를 관계식으로 만들어 낼 수 있고 그 관계식을 점화식이라고 한다!
예를 들어 피보나치 수열에서는 f(n) = f(n-1) + f(n-2)
4. 메모하기
변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장
보통 배열을 쓰며 변수의 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다.
5. 기저 상태 파악하기
가장 작은 문제의 상태를 알아야 한다.
피보나치 수열을 예시로 들면, f(0) = 0, f(1) = 1과 같은 방식
해당 기저 문제에 대해 파악 후 미리 배열 등에 저장해두면 된다.
6. 구현하기
2가지 방식으로 구현 가능함.
Bottom-Up (Tabulation 방식) - 반복문 사용
아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식
dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서
dp[n]까지 그 값을 전이시켜 재활용하는 방식
메모하기 부분에서 Memoization이라고 했는데 Bottom-up일 때는 Tabulation이라고 부른다.
Top-Down (Memoization 방식) - 재귀 사용
dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식
packge com.test;
public class Fibonacci{
// DP 를 사용 시 작은 문제의 결과값을 저장하는 배열
// Top-down, Bottom-up 별개로 생성하였음(큰 의미는 없음)
static int[] topDown_memo;
static int[] bottomup_table;
public static void main(String[] args){
int n = 30;
topDown_memo = new int[n+1];
bottomup_table = new int[n+1];
long startTime = System.currentTimeMillis();
System.out.println(naiveRecursion(n));
long endTime = System.currentTimeMillis();
System.out.println("일반 재귀 소요 시간 : " + (endTime - startTime));
System.out.println();
startTime = System.currentTimeMillis();
System.out.println(topDown(n));
endTime = System.currentTimeMillis();
System.out.println("Top-Down DP 소요 시간 : " + (endTime - startTime));
System.out.println();
startTime = System.currentTimeMillis();
System.out.println(bottomUp(n));
endTime = System.currentTimeMillis();
System.out.println("Bottom-Up DP 소요 시간 : " + (endTime - startTime));
}
// 단순 재귀를 통해 Fibonacci를 구하는 경우
// 동일한 계산을 반복하여 비효율적으로 처리가 수행됨
public static int naiveRecursion(int n){
if(n <= 1){
return n;
}
return naiveRecursion(n-1) + naiveRecursion(n-2);
}
// DP Top-Down을 사용해 Fibonacci를 구하는 경우
public static int topDown(int n){
// 기저 상태 도달 시, 0, 1로 초기화
if(n < 2) return topDown_memo[n] = n;
// 메모에 계산된 값이 있으면 바로 반환!
if(topDown_memo[n] > 0) return topDown_memo[n];
// 재귀를 사용하고 있음!
topDown_memo[n] = topDown(n-1) + topDown(n-2);
return topDown_memo[n];
}
// DP Bottom-Up을 사용해 Fibonacci를 구하는 경우
public static int bottomUp(int n){
// 기저 상태의 경우 사전에 미리 저장
bottomup_table[0] = 0; bottomup_table[1] = 1;
// 반복문을 사용하고 있음!
for(int i=2; i<=n; i++){
// Table을 채워나감!
bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2];
}
return bottomup_table[n];
}
}
/*
결과
832040
일반 재귀 소요 시간 : 9
832040
Top-Down DP 소요 시간 : 0
832040
Bottom-Up DP 소요 시간 : 0
*/
-
호출 스택과 실행 컨텍스트
JavaScript 주요 개념 시리즈 2, 4번째 키워드!
호출 스택 (실행 컨텍스트 스택)과 실행 컨텍스트에 대해 정리하겠습니다.
두 개념은 아주 긴밀한 관련이 있으니 함께 알아두시면 좋을 것 같습니다.
그럼 시작하겠습니다!
23. 실행 컨텍스트
23.1. 소스코드의 타입
ECMAScript 사양은 소스코드를 4가지 타입으로 구분함.
전역 코드, 함수 코드, eval 코드, 모듈 코드 4가지 타입의 소스코드는 실행 컨텍스트를 생성함.
타입에 따라 실행 컨텍스트를 생성하는 과정과 관리 내용이 다름.
23.2. 소스코드의 평가와 실행
실행에 앞서 평가 과정을 거침.
평가 과정에서 실행 컨텍스트를 생성하고 변수, 함수 등의 선언문만 먼저 실행하여 생성된 변수나 함수 식별자를 키로 실행 컨텍스트가 관리하는 스코프에 등록함.
선언문을 제외한 소스코드가 순차적으로 실행됨.(런타임)
실행에 필요한 정보, 즉 변수나 함수의 참조를 실행 컨텍스트가 관리하는 스코프에서 검색하여 취득함.
변수 값의 변경 등 소스코드의 실행 결과는 다시 실행 컨텍스트가 관리하는 스코프에 등록됨.
23.3.실행 컨텍스트의 역할
전역 코드 평가
선언문만 먼저 실행 -> 생성된 전역 변수와 전역 함수가 전역 스코프에 등록됨. -> 전역 변수, 전역 함수는 전역 객체의 프로퍼티와 메서드가 됨.
전역 코드 실행
전역 코드가 순차적으로 실행됨. -> 전역 변수에 값이 할당되고 함수가 호출됨. -> 함수가 호출되면 순차적으로 실행되던 전역 코드의 실행을 일시 중단하고 코드 실행 순서를 변경하여 함수 내부로 진입함.
함수 코드 평가
매개 변수와 지역 변수 선언문이 먼저 실행되고 생성된 매개변수와 지역 변수가 지역 스코프에 등록됨.
argument 객체가 생성되어 지역 스코프에 등록되고 this 바인딩도 결정됨.
함수 코드 실행
매개변수와 지역 변수에 값이 할당됨.
함수 코드 실행 과정이 종료되고 함수 호출 이전으로 되돌아가 전역 코드 실행을 계속 함.
코그가 실행되려면 스코프를 구분하여 식별자와 바인딩된 값이 관리되어야 함.
중첩 관계에 의해 스코프 체인을 형성하여 식별자를 검색할 수 있어야 하고, 전역 객체의 프로퍼티도 전역 변수처럼 검색 할 수 있어야함.
함수 호출이 종료되면 함수 호출 이전으로 되돌아가기 위해 현재 실행 중인 코드와 이전에 실행하던 코드를 구분하여 관리해야 함.
이를 위해 모든 코드는 실행 컨텍스트를 통해 실행되고 관리됨.
식별자와 스코프는 실행 컨텍스트의 렉시컬 환경으로 관리하고 코드 실행 순서는 실행 컨텍스트 스택으로 관리함.
23.4. 실행 컨텍스트 스택
생성된 실행 컨텍스트는 스택 자료구조로 관리됨. 이를 실행 컨텍스트 스택이라 함.
실행 컨텍스트 스택은 코드의 실행 순서를 관리함.
소스코드가 평가되면 실행 컨텍스트가 생성되고 실행 컨텍스트 스택의 최상위에 쌓임.
최상위에 존재하는 실행 컨텍스트는 언제나 현재 실행 중인 코드의 실행 컨텍스트이고 이를 실행 중인 실행 컨텍스트라고 함.
23.5. 렉시컬 환경
렉시컬 환경은 식별자와 식별자에 바인딩된 값, 그리고 상위 스코프에 대한 참조를 기록하는 자료구조로 실행 컨텍스트를 구성하는 컴포넌트 임.
실행 컨텍스트는 LexicalEnvironment 컴포넌트와 VariableEnvironment 컴포넌트로 구성됨.
렉시컬 환경은 환경 레코드와 외부 렉시컬 환경에 대한 참조 두 개의 컴포넌트로 구성됨.
환경 레코드 : 스코프에 포함된 식별자를 등록하고 등록된 식별자에 바인딩된 값을 관리하는 저장소
외부 렉시컬 환경에 대한 참조 : 상위 스코프를 가리킴. 스코프 체인을 구현함.
23.6. 실행 컨텍스트의 생성과 식별자 검색 과정
다음 코드를 참고하여 아래 설명을 이해하자!
var x = 1;
const y = 2;
function foo (a) {
var x = 3;
const y = 4;
function bar (b) {
const z = 5;
console.log(a+b+x+y+z);
}
bar(10);
}
foo(20);
23.6.1. 전역 객체 생성
전역 객체는 전역 코드가 평가되기 이전에 생성됨.
23.6.2. 전역 코드 평가
전역 실행 컨텍스트 생성
비어있는 전역 실행 컨텍스트를 생성하여 실행 컨텍스트 스택에 push 함.
전역 렉시컬 환경 생성
전역 렉시컬 환경을 생성하고 전역 실행 컨텍스트에 바인딩함.
렉시컬 환경은 환경 레코드와 외부 렉시컬 환경에 대한 참조로 구성됨.
전역 환경 레코드 생성
전역 환경 레코드는 전역 변수를 관리하는 전역 스코프, 전역 객체의 빌트인 전역 프로퍼티와 빌트인 전역 함수, 표준 빌트인 객체를 제공 함.
전역 환경 레코드는 객체 환경 레코드와 선언적 환경 레코드로 구성됨.
객체 환경 레코드는 var 전역 변수와 함수 선언문 정의 전역 함수, 빌트인 전역 프로퍼티와 빌트인 전역 함수, 표준 빌트인 객체를 관리하고 선언적 환경 레코드는 let, const 전역 변수를 관리함.
객체 환경 레코드 생성
객체 환경 레코드는 BindingObject라고 부르는 객체와 연결된 전역 객체 생성에서 생성된 전역 객체임.
전역 코드 평가 과정에서 var 전역 변수와 함수 선언문 정의 전역 함수는 객체 환경 레코드에 연결된 BindingObject를 통해 전역 객체의 프로퍼티와 메서드가 됨.
선언적 환경 레코드 생성
let, const 전역 변수는 선언적 환경 레코드에 등록되고 관리됨.
이들은 선언 단계와 초기화 단계가 분리되어 진행되어 변수 호이스팅이 발생하여도 런타임에 변수 선언문에 도달 전까지 일시적 사각지대에 빠지기 때문에 런타임에 변수 선언문에 도달 전까지 참조 불가함.
this 바인딩
전역 환경 레코드의 [[GlobalThisValue]] 내부 슬롯에 this(전역 객체)가 바인딩됨.
this 바인딩은 전역 환경 레코드와 함수 환경 레코드에만 존재함.
외부 렉시컬 환경에 대한 참조 결정
현재 평가 중인 소스코드를 포함하고 있는 외부 소스코드의 렉시컬 환경, 즉 상위 스코프를 가리킴.
전역 렉시컬 환경의 외부 렉시컬 환경에 대한 참조에는 null이 할당됨.
23.6.3. 전역 코드 실행
식별자 결정을 위해 식별자를 검색할 때는 실행 중인 실행 컨텍스트에서 식별자를 검색하기 시작함.
만약 실행 중인 컨텍스트의 렉시컬 환경에서 식별자를 검색할 수 없으면 외부 렉시컬 환경에 대한 참조가 가리키는 렉시컬 환경, 즉 상위 스코프로 이동하여 식별자를 검색함.(스코프 체인의 동작 원리)
23.6.4. foo 함수 코드 평가
함수 실행 컨텍스트 생성
함수 실행 컨텍스트는 함수 렉시컬 환경이 완성된 다음 실행 컨텍스트 스택에 Push됨.
함수 렉시컬 환경 생성
foo 함수 렉시컬 환경을 생성하고 foo 함수 실행 컨텍스트에 바인딩함.
함수 환경 레코드 생성
함수 환경 레코드는 매개변수, argument 객체, 함수 내부에서 선언한 지역 변수와 중첩 함수를 등록하고 관리함.
this 바인딩
함수 환경 레코드의 [[ThisValue]] 내부 슬롯에 this가 바인딩됨.
일반 함수로 호출된 foo 함수의 [[ThisValue]]에는 전역 객체가 바인딩됨.
외부 렉시컬 환경에 대한 참조 결정
외부 렉시컬 환경에 대한 참조에 foo 함수 정의가 평가된 시점에 실행 중인 실행 컨텍스트의 렉시컬 환경의 참조가 할당됨.
즉, 전역 렉시컬 환경의 참조가 할당됨.
JS 엔진은 함수 정의를 평가하여 함수 객체를 생성할 때 현재 실행 중인 실행 컨텍스트의 렉시컬 환경, 즉 함수의 상위 스코프를 함수 객체의 내부 슬롯 [[Environment]]에 정장함.
함수 렉시컬 환경의 외부 렉시컬 환경에 대한 참조에 할당된 것은 함수 객체의 내부 슬롯 [[Environment]]에 저장된 렉시컬 환경의 참조임.
23.6.5. foo 함수 코드 실행
스코프 체인을 돌며 식별자 결정 진행.
23.6.6. bar 함수 코드 평가
23.6.7. bar 함수 코드 실행
console 식별자 검색
console 식별자를 스코프 체인에서 검색함.
스코프 체인은 현재 실행 중인 컨텍스트의 렉시컬 환경에서 시작하여 외부 렉시컬 환경에 대한 참조로 이어지는 렉시컬 환경의 연속임.
console 식별자는 객체 환경 레코드의 BindingObject를 통해 전역 객체에서 찾을 수 있음.
log 메서드 검색
console 객체에서 log 메서드를 검색함.
표현식 a+b+x+y+z의 평가
식별자는 스코프 체인에서 검색.
console.log 메서드 호출
표현식 a+b+x+y+z가 평가 되어 생성한 값 42를 console.log 메서드에 전달하여 호출함.
23.6.8. bar 함수 코드 실행 종료
bar 함수 코드의 실행이 종료됨. -> 실행 컨텍스트 스택에서 bar 함수 실행 컨텍스트가 pop되어 제거됨. -> foo 함수 실행 컨텍스트가 실행 중인 실행 컨텍스트가 됨.
bar 함수 실행 컨텍스트가 제거되었다고 해서 bar 함수 렉시컬 환경까지 즉시 소멸하는 것은 아님.
만약 bar 함수 렉시컬 환경을 누군가 참조하고 있다면 bar 함수 렉시컬 환경은 소멸하지 않음.
23.6.9. foo 함수 코드 실행 종료
foo 함수 코드의 실행이 종료됨. -> 실행 컨텍스트 스택에서 foo 함수 실행 컨텍스트가 pop되어 제거됨. -> 전역 실행 컨텍스트가 실행 중인 실행 컨텍스트가 됨.
23.6.10. 전역 코드 실행 종료
전역 코드의 실행이 종료되고 전역 실행 컨텍스트도 실행 컨텍스트 스택에서 제거되어 실행 컨텍스트 스택에는 아무것도 남지 않음.
23.7. 실행 컨텍스트와 블록 레벨 스코프
선언적 환경 레코드를 갖는 렉시컬 환경을 새롭게 생성하여 기존의 전역 렉시컬 환경을 교체함.
이때 새롭게 생성된 코드 블록을 위한 렉시컬 환경의 외부 렉시컬 환경에 대한 참조는 코드 블록이 실행되기 전의 렉시컬 환경을 가리킴.
코드 블록의 실행이 종료되면 코드 블록이 실행되기 전의 렉시컬 환경으로 되돌아감.
for 문의 변수 선언문에 let 키워들 사용한 for 문은 코드 블록이 반복해서 실행될 때마다 코드 블록을 위한 렉시컬 환경을 생성함.
만약 for문 내에 함수가 있다면 이 함수의 상위 스코프는 for 문의 코드 블록이 생성한 렉시컬 환경이 됨.
이때 함수의 상위 스코프는 for 문의 코드 블록이 반복해서 실행될 때 마다 식별자(for문의 변수 등)의 값을 유지해야 함.
이를 위해 코드 블록이 반복 실행될 때마다 독립적인 렉시컬 환경을 생성하여 식별자의 값을 유지해야 함.(클로저)
이상 호출 스택과 실행 컨텍스트 정리였습니다.
-end-
-
-
Touch background to close
Welcome! This is ratel's Blog.
