[데브코스] 7일차 TIL (백트래킹, 동적 계획법, 실행 컨텍스트)
공부
자바스크립트
javascript
데브코스
TIL
자료구조
알고리즘
2022-03-29

들어가며

오늘도 역시 알고리즘 공부를 했다. 프로그래머스의 연습 문제 두 문제를 풀었는데 한 문제도 제대로 못 풀었다. 아직은 어려운 문제를 풀기엔 내 실력이 많이 부족하다는 걸 느꼈다. (물론 실력이 좋다고 생각한 적은 없다ㅠ) 그래도 지금 개념을 익히고 문제 유형을 자주 보다보면 어느 순간 어려운 문제도 조금씩 풀 수 있을거라고 생각한다. 지금 상황에서 조급한건 하나도 도움이 되지 않는다는 걸 과거의 경험으로 알고 있다. 공부만 꾸준히 해보자.

백트래킹

모든 경우의 수를 탐색하는 알고리즘이다. 보통 DFS와 BFS를 사용하는데 DFS를 사용할 경우 자바스크립트의 재귀 성능이 좋지 않기 때문에 스택을 사용해 구현하는 것이 좋다. 탐색 과정에서 사이클이 생길 수 있다면 BFS를 사용하는 게 더 좋다.
백트래킹에서의 핵심은 가지치기라고 할 수 있다. 탐색하지 않아도 되는 곳은 미리 막아 효율을 높이는 방법이다.

백트래킹 실습

프로그래머스의 N-Queen 문제를 풀어보았다. 행, 열, 대각선으로 움직이는 퀸이 있는데 숫자 N이 주어졌을 때 N*N의 체스판에 N개의 퀸들을 서로 공격할 수 없는 위치에 놓는 방법의 수를 반환하는 문제이다.

내가 생각한 방법

  1. 먼저 (1, 1) 위치에 퀸을 둔다.
  2. 갈 수 없는 곳을 막고 다음에 둘 수 있는 위치에 다음 퀸을 둔다.
    • 갈 수 없는 곳 확인하는 방법: 퀸을 체스판에 놓을 때 배열을 하나 만들어 퀸의 좌표를 저장해둔다. 좌표들을 탐색할 때 배열에 있는 좌표들을 확인해 행, 열, 대각선이 겹치는지 확인한다. 행과 열은 같은 값을 가지고 있는지 확인할 수 있고, 대각선은 이미 놓인 퀸의 좌표와 새로운 퀸을 놓을 좌표의 행의 차이와 열의 차이가 같은지를 통해 비교할 수 있다.
  3. 다음으로 둘 수 잇는 곳에 퀸을 둔다.
  4. 더 이상 놓을 곳이 없는데 남은 퀸이 있다면 (1, 2) 위치에 첫 퀸을 두고 과정을 반복한다.

이런 생각을 가지고 코드로 옮겨보려고 했다. 어찌저찌 코드를 구현하고 결과를 확인했는데 한문제만 맞고 나머지는 다 틀리거나 시간초과가 났다.

정답과 비교

나는 모든 체스판을 탐색하면서 퀸을 놓을 수 있는 자리인지 놓인 퀸의 좌표가 담긴 배열을 순회하며 확인했다. 이렇게 되면 탐색 과정이 너무 오래 걸리기 때문에 시간초과가 나는 것이다. 해설에서는 배열을 사용하는 방식을 썼다. 1차원 배열을 선언하고 퀸의 좌표가 row=0 이고 col=0 일 때 아래와 같이 저장할 수 있다.

1  const arr = new Array(n);
2  arr[row] = col; // 배열의 0번째 인덱스에 0값 저장

이렇게 저장 했을 때의 장점은 어차피 퀸이 놓이면 같은 행과 열에는 다른 퀸을 둘 수 없다. 배열의 인덱스가 행의 역할을 하기 때문에 자연스럽게 한 행에 퀸이 하나만 들어갈 수 있다는 조건을 만족하는 것이다.

  • 정답 코드
1  function check(queen, row) {
2    for (let i = 0; i < row; i += 1) {
3      if (
4        queen[i] === queen[row] ||
5        Math.abs(row - i) === Math.abs(queen[i] - queen[row])
6      ) {
7        return false;
8      }
9    }
10    return true;
11  }
12  

13  function search(queen, row) {
14    const n = queen.length;
15    let count = 0;
16  

17    if (n === row) {
18      return 1;
19    }
20  

21    for (let col = 0; col < n; col += 1) {
22      // 유효한 위치인지 검사해서 맞다면
23      queen[row] = col;
24      if (check(queen, row)) {
25        count += search(queen, row + 1);
26      }
27      // 다음 행으로
28      // 아니라면 다음 열로
29    }
30    return count;
31  }
32  

33  function solution(n) {
34    return search(
35      Array.from({ length: n }, () => 0),
36      0
37    );
38  }

재귀를 사용한 풀이 방법이다. 코드를 보고도 잘 이해가 되지 않았는데 아래 그림이 많이 도움이 됐다. N=4 일 때, 정답의 갯수를 찾는 과정을 시각적으로 나타낸 것이다.

n-queen

동적 계획법

해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식이다. 특정 알고리즘이 아닌 문제 해결 방식을 의미한다. Dynamic Programming(DP) 라고도 하는데 사실 전혀 Dynamic 하지 않고 Programming과도 관련이 없다고 한다. 동적 계획법은 메모리를 사용하는 대신 빠른 성능을 가지고 있다.

동적 계획법에는 두 가지 방법론이 있는데 메모이제이션(Memoization)과 타뷸레이션(Tarbulation)이다.

  • 메모이제이션: 하향식 접근법이다. 작은 문제들의 결과는 항상 같으며 메모리에 이미 해결한 문제의 답을 저장했다가 꺼내쓰는 방법을 의미한다.
  • 타뷸레이션: 상향식 접근법이다. 필요한 값들을 미리 게산해두고 필요할 때 사용한다. 이 과정은 성능 향상에 많은 도움을 주지만 코딩테스트에서는 보통 메모이제이션을 사용한다.

동적 계획법을 사용할 수 있는 예로 피보나치 수열을 들 수 있다. 피보나치 수열의 첫번째 값은 1이고 두번째 값도 1이다. 그럼 세번째 값은 무엇일까? 첫번째 값과 두번째 값을 더한 값인 2가 세번째 값이 된다. 이를 식으로 나타내면 f(n) = f(n-1) + f(n-2) 이다. 피보나치 수열을 먼저 재귀 함수를 사용해 출력해보자.

1  function fibo(index) {
2    if (index === 1 || index === 2) return 1;
3    return fibo(index - 1) + fibo(index - 2);
4  }

엄청 간단하다. 입력으로 받은 인덱스에 해당하는 피보나치 수열의 값을 반환하는 함수이다. 재귀를 사용하면 식이 간단하게 표현된다는 장점이 있다. 그러나 재귀 함수를 사용하면 값을 구하는 과정에서 중복으로 계산이 이루어지는 단점이 있다. 이때 동적 계획법을 사용할 수 있다.

1  const dp = [];
2  function fibo(index, dp) {
3    if (index === 1 || index === 2) {
4      dp[index] = 1;
5      return 1;
6    }
7    if (dp[index] !== undefined) {
8      return dp[index];
9    }
10    dp[index] = fibo(index - 1, dp) + fibo(index - 2, dp);
11    return dp[index];
12  }

각 과정에서 계산한 값을 배열에 저장하고, 나중에 같은 값이 필요할 때 꺼내서 사용할 수 있다. 인덱스 값이 작을때는 재귀 함수로만 풀어도 충분히 원하는 값을 얻을 수 있다. 그러나 인덱스가 커질수록 재귀 함수만 사용했을 때는 시간이 오래 걸리기 때문에 동적 계획법을 사용하는 것이 좋다.

그렇다면 동적 계획법을 사용하기 위해 어떻게 문제에 접근해야 할까?

  • 가장 작은 문제를 정의할 수 있는지
  • 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는지

위의 두 가지를 만족한다면 동적 계획법을 사용할 수 있는 문제이다. 값을 저장하기 위해 공간을 사용하기 때문에 간혹 메모리를 너무 사용해서 해결하지 못하는 경우가 있다. 그러나 코딩테스트에서는 잘 안나온다고 한다.

동적 계획법 실습

프로그래머스의 단어 퍼즐 문제를 풀어보았다. 이 문제는 무려 프로그래머스 레벨 4 문제다. 여러개의 문자열이 담긴 배열(각 문자열의 개수는 무한대라고 가정)과 단어가 주어졌을 때, 문자열을 최소로 사용해 주어진 단어를 만드는 문제이다. 항상 그래왔지만 개념을 이해하고 문제를 풀면 완전 다른 세상이 펼쳐진다. 이 문제는 정답을 보고도 아직까지 완전히 이해하지 못하고 있다. 최대한 빨리 이해하고 다시 정리하는 게 좋을 것 같다.

실행 컨텍스트

실행 컨텍스트란 실행할 코드에 제공할 환경 정보들을 모아 놓은 객체이다. 하나의 실행 컨텍스트를 구성할 수 있는 방법으로 전역공간, eval() 함수, 함수, es6부터는 블록이 있다. 이 중에서 eval() 함수는 사용하지 말라고 한다. 자세히는 모르지만 속도 문제와 보안 문제 때문인 것 같다.
eval 함수를 절대 사용하지 말 것!

자바스크립트 코드는 실행될 때 전역 컨텍스트가 콜 스택에 쌓인다. 그 후 함수나 블록을 만나면 관련 실행 컨텍스트를 생성한 후 콜 스택에 담는다. 실행 컨텍스트의 객체에는 VariableEnvironment, LexicalEnvironment, ThisBinding 정보가 저장되어 있다. 실행 컨텍스트를 생성할 때 VariableEnvironment 에 정보를 담고 이를 그대로 복사해 LexicalEnvironment 를 만든다. 그 이후는 LexicalEnvironment 를 활용한다. VariableEnvironment 와 LexicalEnvironment 내부에는 environmentRecord 와 outerEnvironmentReference 로 구성되어 있다. environmentRecord 는 현재 실행 컨텍스트와 관련된 코드의 식별자를 저장한다. 함수의 매개변수 식별자, 함수, var로 선언된 변수의 식별자 등을 수집하는데 이 과정에서 호이스팅이 발생한다.

호이스팅이란? 변수가 끌어올려지는듯한 효과를 의미한다. environmentRecord 에 의해 아직 변수가 선언되지 않았더라도 자바스크립트 엔진은 이미 현재 실행 컨텍스트에서의 변수 목록을 알고 있다. 그렇기 때문에 변수가 선언되지 않았지만 변수에 접근이 가능하다. 아직 값의 할당은 일어나지 않았기 때문에 undefined가 출력된다. 함수 선언문 또한 호이스팅 된다.

호이스팅이 일어날 때 var 와 let, const 의 동작이 다르다. 호이스팅이 발생하는 것은 똑같지만 var 는 선언과 초기화가 한번에 일어나기 때문에 undefined 값에 접근 가능하고, let 과 const 는 선언과 초기화가 따로 일어나기 때문에 아직 메모리에 공간이 할당되지 않아 선언이 될 때까지 오류가 발생한다. 이를 TDZ(Temporal Dead Zone) 이라고 한다.

outerEnvironmentReference 는 함수(또는 블록)이 선언될 당시의 LexicalEnvironment 를 참조한다. 이를 이용해 현재 실행 컨텍스트에서 호출한 변수가 현재 실행 컨텍스트에 없다면 외부의 LexicalEnvironment 에 접근해 식별자를 찾는다.

정리

개념은 쉽고 문제는 어렵다. 그래도 괜찮다. 한번 듣고 바로 문제 풀 수 있으면 그게 말이 안되는거다. 아직 프로그래머스 자바스크립트 2단계 문제도 13문제나 남았다. 일단 이거 먼저 차근차근 풀면서 실력을 더 길러야겠다.
글로 개념을 정리하면서 좋은 점은, 어디서 들어봤거나 애매하게 알고 있었던 것도 좀 더 명확하게 알 수 있다는 점인 것 같다. 어제부터 계속 함수형 프로그래밍 강의 듣기로 계획하고 안들었다. 진짜 내일은 함수형 프로그래밍 강의 들어야겠다.

참고자료

백트래킹 https://ddmix.blogspot.com/2015/06/cppalgo-29-greedy-backtracking.html
동적 계획법 https://hongjw1938.tistory.com/47
피보나치 수열 메모이제이션 https://velog.io/@minjae-mj/Memoization-%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98-feat.-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4
eval 절대 사용하지 말것 https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/eval#eval%EC%9D%84%20%EC%A0%88%EB%8C%80%20%EC%82%AC%EC%9A%A9%ED%95%98%EC%A7%80%20%EB%A7%90%20%EA%B2%83!
코어 자바스크립트 책

Loading script...
copyright 2021-2022. Jeongki.dev