JavaScript

스코프(scope)

프로그래밍을 하면 변수를 저장하고 변수를 다시 사용하기 마련이다. 그러기 위해서는 특정 규칙이 필요한데 이러한 규칙을 스코프라 한다.

자바스크립트는 컴파일러 언어이며 소스코드가 실행 되기 전에 컴파일레이션단계를 거치게된다. 이는 3단계로 이루어져 있는데

1. 토크나이징/렉싱
2. 파싱
3. 코드생성

var a = 2라는 코드를 실행한다고 하면

1. var a을 만나면 스코프 내에 a라는 변수가 있는지 체크하고 없으면 var a를 선언한다.
2. a = 2를 만나면 스코프 내에 a라고 선언된 변수가 있는지 체크하고 있으면 대입하고 없으면 에러를 던진다.

중첩 스코프

스코프는 확인자 이름으로 변수를 찾기 위한 규칙의 집합이다. 그러나 대개 고려해야할 스코프는 여러 개이다.

하나의 블록이나 함수는 다른 블록이나 함수 안에 중첩될 수 있으므로 스코프도 다른 스코프 안에 중첩될 수 있다.

그리고 현재 스코프에서 대상 변수를 찾지 못하면 글로벌 스코프라 부르는 가장 바깥 스코프에 도달 할 때까지 계속해서 바깥 스코프로 이동한다. (이를 스코프 체인이라한다.)

algorithm

LCS알고리즘

lcs알고리즘은 최대 공통 부분 수열 알고리즘으로 2개의 배열에서 서로 공통적으로 가지는 부분수열을 찾는 알고리즘이다.

이 알고리즘은 2가지 버전으로 나눌 수 있는데 연속된 부분수열과 비연속부분수열로 나눌 수 있다.

1. 연속된 부분수열

   ABDCDE, CCDCDE라는 두 배열이 있다고 생각하자.

   A, C는 서로 다르기 때문에 0이다. 그럼 일단 같지 않은 부분을 다 0으로 채우자. 왜냐하면 우리는 연속된 최대 부분 수열을 알고 싶기 때문에 같지 않으면 무조건 배열의 길이는 0으로 간주하여도 무방하다.

   X	0	A	B	D	C	D	E
   0	0	0	0	0	0	0	0
   C	0	0	0	0		0	0
   C	0	0	0	0		0	0
   D	0	0	0		0		0
   C	0	0	0	0		0	0
   D	0	0	0		0		0
   E	0	0	0	0	0	0

   그럼 이제 겹치는 부분을 생각해보자. 만약 첫번째 배열의 3번째와 두번째 배열의 2번째가 똑같다고 생각하면 여기의 값은 어떻게 정하는게 맞을까?

   여기서 우리가 생각해야될 부분은 현재 위치가 처음으로 똑같은 위치인지 연속된 위치인지에 대한 인지가 필요하다. 그럼 몇번째 2차 배열의 몇번째 인덱스를 확인해야 할까?

   정답은 첫번째 배열의 2번째와 두번째 배열의 1번째가 같은지 확인하면 된다. 이는 dp를 이용해서 연속된 배열의 값을 누적해 나갈 수 있다.

   X	0	A	B	D	C	D	E
   0	0	0	0	0	0	0	0
   C	0	0	0	0	1	0	0
   C	0	0	0	0	1	0	0
   D	0	0	0	1	0	2	0
   C	0	0	0	0	1	0	0
   D	0	0	0	0	0	2	0
   E	0	0	0	0	0	0	3

   결론은 가장 긴 배열의 길이는 3이 되고 이 배열의 값도 6,6 => 5,5 => 4,4 이런식 이기 때문에 쉽게 추적 가능하다.

   코드

   str1, str2 = 'ABDCDE', 'CCDCDE'
   
   dp = [[0 for _ in range(len(str1)+1)] for _ in range(len(str2)+1)]
   
   for i in range(1, len(str2)+1):
     for j in range(1, len(str1)+1):
       if str1[i-1] == str2[j-1]:
         dp[i][j] = dp[i-1][j-1] + 1

   다음과 같이 2차 배열을 만들 수 있다.

2. 비 연속 부분 수열

   비 연속 부분 수열은 조금 다르다. 바로 표로 보여 주도록 하겠다.

   X	0	A	B	D	C	D	E
   0	0	0	0	0	0	0	0
   C	0	0	0	0	1	1	1
   C	0	0	0	0	1	1	1
   D	0	0	0	1	1	2	2
   C
   D
   E

   ABDC와 C의 부분 수열의 갯수는 1개이며 이는 ABDCD가 되어도 ABDCDE되어도 최소 1개는 가지게됨을 알 수 있다.

   그래서 표를 마저 채우면

   X	0	A	B	D	C	D	E
   0	0	0	0	0	0	0	0
   C	0	0	0	0	1	1	1
   C	0	0	0	0	1	1	1
   D	0	0	0	1	1	2	2
   C	0	0	0	1	2	2	2
   D	0	0	0	1	2	3	3
   E	0	0	0	1	2	3	4

   이런 식으로 된다. 코드로 짜면

   str1, str2 = 'ABDCDE', 'CCDCDE'
   
   dp = [[0 for _ in range(len(str1)+1)] for _ in range(len(str2)+1)]
   
   for i in range(1, len(str2)+1):
     for j in range(1, len(str1)+1):
       if str1[i-1] == str2[j-1]:
         dp[i][j] = dp[i-1][j-1] + 1
       else:
         dp[i][j] = max(dp[i-1][j], dp[i][j-1])    ## 첫번째 혹은 두번째 배열이 하나 작을때 최장 부분수열의 길이 중 긴것을 차용하면 된다.

   여기서 최장 배열의 값을 찾기 위해서는 일단 두 배열의 길이를 N, M이라 하면

   1. N, M 에서 dp[N-1][M-1] + 1 == dp[N][M]인지 확인
      1. 맞으면 str1[N-1]은 배열의 값이므로 푸쉬 후 N-1, M-1로 이동
      2. 아니면 N-1, M or N, M-1로 이동 어디로 가던 상관없음.
   2. dp[i][j]가 0일때 까지 1번 반복하면 된다.