연관관계는 ATT와 편향의 합으로 설명할 수 있다.

따라서 편향이 0이면, 연관관계는 오롯이 인과관계라고 볼 수 있다. 즉, 실험군과 대조군에서 처치 외의 나머지 조건이 동일하다면 연관관계는 인과관계가 된다. 적어도 실험군과 대조군의 잠재적 결과에 대한 기댓값이 같다는 걸 말한다.

이때 처치와 결과 사이의 독립성을 얘기하는 게 아니라, 잠재적 결과가 처치와 독립적이라는 점이 중요하다. 즉, 실험 대상이 처치를 받았더라면 관측되었을 결과가 실제로 처치 받았을지 여부와는 무관하다는 뜻이다.

독립성 가정 → 실험군과 대조군이 비교 가능하다.

$(Y_0, Y_1) \perp T$ 는 실험군과 대조군의 결과 차이를 유발한 요인이 바로 처치라는 걸 의미한다.

$E[Y_0|T=0] = E[Y_0|T=1] = E[Y_0]$

위 식처럼, 독립성 가정을 만족하면 실험군과 대조군의 평균을 비교하여 간단히 ATE를 구할 수 있다.

$E[Y_1|T=1] - E[Y_1|T=0] = E[Y_1-Y_0] = ATE$

그럼 어떻게 독립적인 상태로 만들 것인가?

처치 T를 무작위로 배정하면 실험군과 대조군이 비교 가능해지는 그럴듯한 상황을 만들어볼 수 있다. 처치는 피험자의 10-1% 이하에게만 배정해도 된다. 중요한 건 처치 배정 매커니즘이 무작위여야 한다는 것! 무작위로 처치를 배정하면 실험군과 대조군의 기댓값은 거의 비교 가능해진다. 두 그룹 간의 유일한 차이는 처치밖에 없으므로, 두 그룹의 결과 차이는 해당 처치에 따른 것으로 볼 수 있다. 이렇듯 기본적으로 랜덤화는 처치와 잠재적 결과를 독립적으로 만든다. '무작위 통제 실험(RCT, Randomized control trial)'를 활용할 수 있다.

AB 테스트 사례

이메일을 받은 고객이 얼마나 많이 전환(Conversion)되는가?

단순히 생각해보면 $E[Conversion|Email=1] > E[Conversion | Email = 0]$ 이런 결과가 나올 가능성이 크다. 즉, 이메일을 받은 고객이 더 많이 전환됐다고 할 수 있다. 그러나 모종의 이유로 애초에 전환 가능성이 높다고 생각한 고객한테만 이메일을 보냈을 수도 있다.

$E[Conversion_0|Email=1] > E[Conversion_0 | Email = 0]$

위 식을 보면, 실제로 이메일을 받은 고객은 설령 이메일을 받지 않았더라도 다른 고객보다 더 많이 전환될 수 있다는 것이다. 따라서 편향 때문에 단순한 비교로는 이메일의 실제 인과효과를 추정할 수 없다.

이 문제를 해결하기 위해서는 이메일을 받은 고객과 받지 않은 고객을 비교 가능하도록, 즉 $E[Y_0|T=1] = E[Y0|T=0]$ ($(Y_0, Y_1) \perp T$)으로 만들어야 한다. 이메일을 무작위로 보내면 비교 가능한 상황을 만들 수 있다. 이렇게 하면 이메일을 받은 고객과 받지 않은 고객의 전환율은 평균적으로 동일해진다.

무작위 배정이 잘 됐는지 확인하기 위해서 실험군과 대조군이 처치 받기 전에 동일한지 확인해본다. 성별, 나이 등의 특성이 그 그룹 간에 균형을 이루는지 확인해보는 것이다.

두 그룹이 비슷한지 평가하는 방법은 정규화 차이를 계산하면 된다.

$\frac{\hat{\mu_{tr}}- \hat{\mu_{co}}}{\sqrt{\hat{\sigma_{tr}^2} + \hat{\sigma_{co}^2}/2}}$

통계적 유의성 파악

RCT는 인과관계를 식별할 때 유용하나, 이러한 효과가 우연에 따른 것이 아니라고 확신할 만한지, 통계적으로 유의한지 검정하는 과정이 필요하다. 추정에 대한 불학실성을 나타내기 위해 표준오차를 계산하여 신뢰구간을 구하거나 가설검정을 진행한다. 귀무가설은 $H_0 : Conversion_{no \ email} = Conversion_{short \ email}$ 로 설정하고 t검정을 진행하면 된다.

실험 설계 관점에서 적절한 표본 크기를 결정하고자 할 때, $SE_\triangle = \sqrt{SE_1^2 + SE_2^2}$ 에서 실험군과 대조군의 분산이 같다고 가정할 수 있으니, $SE_\triangle = \sqrt{2SE^2} = \sqrt{2\sigma^2/n} = \sigma\sqrt{2/n}$ 으로 적절한 n을 계산할 수 있다. 80%의 검정력과 95%의 신뢰도를 원할 때 표본 크기는 $n = 2*2.8^2\sigma^2$ 이다.

정의 및 특징

두 개의 시계열 데이터에서 한 변수(한 시계열)의 과거데이터와 다른 한 변수(시계열)의 과거데이터의 결합으로 그 변수(처음 시계열)를 선형 예측(Linear regression)을 했을 때 다른 한 변수의 과거데이터로만 선형예측 한 것이 통계적으로 유의미하고 예측에 도움을 줬다면 그것을 그래인저 인과가 있다고 말한다.

즉, 동일한 시간축의 범위를 가진 두 데이터가 있을 때 한 데이터를 다른 한쪽의 데이터의 특정한 시간간격에 대해서 선형회귀를 할 수 있다면 그래인저 인과가 있다고 한다.

시간이 지남에 따라 진화하는 변수 X가 자신의 과거 값과 X의 과거 값에 기반한 Y의 값에 대한 예측이 Y의 과거 값에만 기반한 Y의 예측보다 더 나은 경우, 진화하는 또 다른 변수 Y를 그랜저 유발한다고 말한다.

: '닭이 먼저냐 달걀이 먼저냐' 문제를 해결할 때 사용

추론불가한 문제: "닭이 먼저인가 달걀이 먼저인가?" (인과관계) 추론가능한 문제: "닭과 달걀의 생성순서 별 서로의 영향력은 어떤가?" (Granger 인과관계) : 원인과 인과 관계를 규명하는 어렵기 때문에 상대적으로 두 요인 중 먼저 영향을 미치는 변수를 알아보고자 할 때 사용

• 귀무가설(Null Hypothesis, 𝐻0H0): 한 변수가 다른 변수를 예측하는데 도움이 되지 않는다

• 대립가설(Alternative Hypothesis, 𝐻1H1): 한 변수가 다른 변수를 예측하는데 도움이 된다

• 선형 인과관계 검증 방식으로, 모형 설정의 오류가 존재할 수 있음.

• 비선형 Granger 모형도 존재함.

• 그랜저 인과관계 검정은 한 시계열이 다른 시계열을 예측하는 데 유용한지 여부를 판단하기 위한 통계적 가설 검정.

• 그랜저 인과관계는 ‘시간적 관련성’으로 더 잘 설명되기 때문에 ‘인과관계’라는 용어만 사용하는 것은 잘못된 명칭이라고 함. 그랜저 인과관계는 X가 Y를 유발하는지 여부를 테스트하는 대신, X가 Y를 예측하는지 여부를 테스트함.

• 시계열 X는 일반적으로 X의 후행 값에 대한 일련의 t-검정 및 F-검정(Y의 후행 값도 포함)을 통해 해당 X 값이 Y의 미래 값에 대해 통계적으로 유의미한 정보를 제공한다는 것을 보여줄 수 있는 경우 Y를 그랜저 원인으로 간주.

• A라는 사건이 B라는 사건 이전에 일어났다면 A가 B의 원인이라고 파악할 수 있지만, 반드시 B가 A를 유발시켰다고 할 수는 없음 → Post hoc fallacy

  • 과거의 사건은 현재의 사건을 유발할 수 있지만, 미래의 사건은 현재의 사건을 유발할 수는 없다는 것임.
  • 이러한 논리에 근거하여 인과관계를 파악하는 것이 Granger 인과관계 검정이라고 함.

• Granger 인과관계 검정은 전통적인 F-통계량을 이용한 비교적 단순한 검정방법임.

  • Granger의 정의에 의하면 y를 예측할 때 y의 과거값과 함께 x의 과거값도 함께 사용하는 것이 y의 과거값만으로 예측하는 것보다 정확하면 x로부터 y로의 인과방향이 존재한다고 간주함.
  • 마찬가지로 x의 예측이 자신의 과거값에 의존하는 것보다 y의 과거값이 포함됨으로써 x의 과거값만으로 예측하는 것보다 정확하면 y로부터 x로의 인과방향이 존재한다고 간주함.
  • 만일 이러한 인과관계가 두 방향으로 모두 성립되면 x와 y는 상호의존적인 관계로 쌍방의 인과방향이 존재하는 것으로 간주함.

• H0(귀무가설) : 한 변수가 다른 변수를 예측하는 데 도움이 되지 않는다.

• 그랜저 인과관계 검정에 대한 모형은 아래 두개의 회귀모형

  $$ y_t = \sum_{i=1 \to p} + \alpha_i x_{i-i} + \sum_{j=1 \to p}\beta_j y_{t-j} + \varepsilon_{1t} $$

  $$ x_t = \sum_{i=1 \to n} + Y_i X_{i-i} + \sum_{j=1 \to p} \delta_j y_{t-j} + \varepsilon_{2t} $$

  • x가 y에 영향을 미치지 않는다는 귀무가설을 검정하기 위하여 y를 y의 과거값과 x의 과거값에 대한 회귀식을 추정함. 그리고 y를 y의 과거값에 대해서만 회귀식을 추정함. 여기서 오차항 $\varepsilon_t$는 상호독립적이고 iid임.

인과관계를 확인하기 위한 통계적인 방법인 Granger causality 는 일반적으로 사람들이 생각하는 원인을 바로 찾고 관련이 있는지를 알려주는 인과관계를 말하는 것은 아니다. 사람들이 생각하는 인과는 매우 추상적이고 포괄적이기 때문에 이런 것을 과학적인 방법으로 알아내는 것은 매우 어렵다. 그럼에도 시도할 수 있는 단순하고 잘 알려진 방법중, Granger causality가 있다.

Granger 인과의 요점과 방식은 매우 간단하고 쉽지만 알고리즘의 깊은 이해는 여러가지 골치아픈 문제가 엮여 있다. 그레인저 인과관계가 모든 인과문제나 해석문제를 해결해주는 것은 아니며, 결과를 해석함에 있어 분석가의 지식, 경험, 논리가 필요하다.

예를 들어 A와 B라는 데이터가 모두 1일 단위로 집계된 데이터고 265일분의 데이터라고 가정할 때 A와 A의 시점으로부터 각각 5일 후의 데이터가 선형회귀가 된다면, A는 ?????

오해석에 대한 유의

이름이 인과관계라고 되어 있는데 사람들이 흔히 생각하는 인과와는 다르게 생각해야 하므로 이 검정의 결과를 확대해석하거나 오해석하는 것을 매우 경계해야 한다.

달걀의 개체수 증가가 미래의 닭의 개체수 증가에 인과영향이 있다는 사실이 밝혀졌다고 해서 반드시 닭의 수의 요인은 달걀의 개체수다라고 확신해서 말하는 것은 무리가 있다. 단순히 달걀의 생산량을 증가시키면 닭의 수가 늘어나게 된다고 확대해석을 하기 때문이다. 그래서 그레인저 인과관계는 줄여서 인과관계라고 하지 않고, ‘그레인저 인과관계’라고 명시하는 경우가 많다.

그것은 그레인저 인과관계가 일반적으로 인과관계를 말하는 것이 아니며 사람들이 생각하는 추상적인 인과관계를 명확히 밝혀낼 것이라는 기대감을 주지 않기 위함이다.

그래인저 인과관계는 상관관계(Correlation)처럼 결과를 해석할 때 논리적으로 결함이 없는지 여러번 고찰하고 해석할 때 매우 주의해야 한다.

Input Parameter

두 개의 시계열 변수가 필요하며 시차(lag)를 파라미터로 넣어줘야 한다.

시차는 2개의 시계열 데이트 세트 A와 B에 대해 테스트할 때 A가 B의 몇 번째 뒤의 시점까지 영향을 주는지를 확인하기 위함이다.

이 시차값은 직접설정함. 적당한 값을 찾기는 매우 어려우므로 여러 시차를 반복해서 실험해 봐야 함. 경험적 판단으로 적절한 구간을 실행해보고 논리적으로 적당한 값으로 사용해야 함. 만약 적절한 Lags를 찾기 아렵다면 알려진 몇가지 방법을 활용한다.

이 방법은 입력한 시차에 해당하는 것만 사용해 선형회귀를 수행하는 게 아니라, 시차(lags)가 N으로 주어진다면 1부터 N까지의 지연에 해당하는 모든 데이터를 전부 사용한다. 즉 N시차만 영향을 주는지가 아니라 N시차까지 영향력이 있는가를 보는 것이다.

전제조건

1. 정상성(Stationary)

   테스트하려는 두 변수가 모두 정상성을 만족해야 한다. 정상성을 만족하지 않으면 오해석할 여지가 많은 결과가 나온다. 대부분의 시계열 데이터가 정상성을 바로 만족하지 않기 때문에 정상성을 만족하도록 변형을 시도한다.

   정상성이 없는 시계열 데이터를 정상성 있는 데이터로 만들기 위해서는 일반적으로 차분과 로그 변환을 많이 한다. 특히 증감률은 절대값이 심하게 크지 않는 한 로그 차분에 근사하는 수치이다.

2. 테스트 방향(Direction)

   테스트하려는 두 개의 변수 A와 B가 있을 때 양방향으로 총 2회의 검정세트로 수행하는 것이 일반적이며 결과에 따라 해석이 달라지는 어려움이 있다.

   • A → B / B → A

     즉, 그래인저 인과 테스트를 두 번 하는 게 일반적인데 논리적으로 확실하게 한쪽 방향이 성립하지 않다고 확신하면 한 쪽은 하지 않아도 된다.

     두 번의 테스트를 통해서 A가 B에 인과 영향을 주는지 테스트하고 B가 A에 인과 영향을 주는지 테스트하게 된다. 이 결과의 조합을 통해서 4가지 경우의 결과가 나온다.

   1. A가 B에 인과영향을 준다. B는 A에 인과영향을 주지 않는다.

   2. B가 A에 인과영향을 준다. A는 B에 인과영향을 주지 않는다.

   3. A가 B에 인과영향을 준다. 그리고 B도 A에 인과영향을 준다.

   4. A가 B에 인과영향을 주지 않는다. 그리고 B도 A에 인과영향을 주지 않는다.

      이것을 다시 논리적으로 해석해야 한다. 위에서 해석이 곤란한 것은 4번째이다. 이 해석이 곤란한 이유는 뒤에 기술할 것이다.

자세한 설명

A lags + B lags로 B의 데이터를 선형회귀한 것의 예측력 > B lags로만 B의 데이터를 선형회귀한 것의 예측력

다음 결과에 대한 조건이 통계적으로 유의미하면 A가 B에 대해 Granger Causality하다고 표현하며, 이는 인과관계가 있을 여지가 있다고 볼 수 있다. (하지만 명확하게 인과관계가 있다는 의미가 아니므로 주의!)

귀무가설 : “Granger Causality를 따르지 않는다”

p-value가 0.05 이하로 나오면 귀무가설을 기각한다.

결과 해석

앞서 시차(lag)가 정해진 경우에는 경우의 수를 보면 총 4개의 결과가 나올 수 있다.

1. 변수A → 변수B = Granger Causality 성립 변수B → 변수A = Granger Causality 성립하지 않음

   이 경우는 변수A가 변수B에 선행한다고 볼 수 있다. 즉 변수A가 변수A의 인과요인이 될 가능성이 높다.

2. 변수A → 변수B = Granger Causality 성립하지 않음 변수B → 변수A = Granger Causality 성립

   이 경우는 변수B가 변수A에 선행한다고 볼 수 있다. 즉 변수B가 변수A의 인과요인이 될 가능성이 높다.

3. 변수A → 변수B = Granger Causality 성립 변수B → 변수A = Granger Causality 성립

   쌍방으로 Granger Causality가 성립하는 경우로 이 경우는 제3의 외부변수(Exogenous Variable)가 영향을 공통으로 주었을 가능성이 높다. 이 경우 제3의 외부변수를 알아내던가 포기하던가 해야 한다. VAR모형(사실 Granger Causality도 VAR모형중 하나이다)을 사용해야 할 수 있다.

4. 변수A → 변수B = Granger Causality 성립하지 않음 변수B → 변수A = Granger Causality 성립하지 않음

   두 변수가 서로 인과영향을 주지 않는다고 볼 수도 있지만 단언하지는 못한다. ARIMA모형으로 추가 확인이 가능한 것으로 알려져 있다. 주의 할 점은 위의 결과가 입력값으로 주는 시차에 따라서 달라질 수 있으므로 시차에 따른 해석을 달리해야 하는 문제가 있다. 즉, 해석에 있어서 사람의 경험과 판단이 개입되어야 한다.

소스 코드

from statsmodels.tsa.stattools import grangercausalitytests

df['kakao_ac'].diff()
sample_outs = grangercausalitytests(df[['kakao_ac','kakao_v']], maxlag=4)
print(sample_outs)

출처: https://songseungwon.tistory.com/133

Reference

• https://en.wikipedia.org/wiki/Granger_causalit
• http://www.scholarpedia.org/article/Granger_causality
• http://elearning.kocw.net/contents4/document/lec/2013/Konkuk/Leegiseong/10.pdf
• https://www.aptech.com/blog/introduction-to-granger-causality/
• https://www.jstor.org/stable/1912791
• https://intothedata.com/02.scholar_category/timeseries_analysis/granger_causality/
• https://playinpap.github.io/granger-causality-test/
• https://datascientistforai.github.io/DataScienceStudy/TimeSeriesData/4_Algorithms_TS_NonLinear.html
• 그래인저 인과관계 - Granger Causality :: 인투더데이터 데이터과학 위키 Datascience Wiki

🔗 백준 12933 오리 (실버3) 문제 바로가기

오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.

영선이의 방에는 오리가 있는데, 문제를 너무 열심히 풀다가 몇 마리의 오리가 있는지 까먹었다.

갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.

녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는 두 오리가 울었다고 볼 수 있다.

영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다.

출력

영선이 방에 있을 수 있는 오리의 최소 수를 구하는 프로그램을 작성하시오. 녹음한 소리가 올바르지 않은 경우에는 -1을 출력한다.

시도 1

문제점

• numpy는 표준 라이브러리가 아니기 때문에 백준에서 쓸 수 없다. 런타임에러가 뜬다.
• qqqqqqqqqquack 를 입력했을 때 -1 가 나와야 하는데 그 처리를 안 해줬다.

import numpy as np

def find_index(duck, q):
  return [i for i in range(len(duck)) if duck[i]==q]

def howmanyducks(quack):
  duck_m = [find_index(quack, i) for i in "quack"]

  # 정상인지 확인
  tran_duck_m = np.transpose(duck_m).tolist()
  for i in range(len(tran_duck_m)):
    if tran_duck_m[i] != sorted(tran_duck_m[i]):
      return -1

  # 정상이면 몇 마린지 확인
  count_duck = [list(tran_duck_m[0])]
  for i in range(1, len(tran_duck_m)):
    if tran_duck_m[i][0] > min([i[-1] for i in count_duck]):
      count_duck[[i[-1] for i in count_duck].index(min([i[-1] for i in count_duck]))].extend(tran_duck_m[i])
    else:
      count_duck.append(tran_duck_m[i])

  return len(count_duck)

print(howmanyducks(input()))

transpose를 하기 위해 numpy가 아닌 map()과 zip(*list)를 이용해 아래처럼 tran_duck_m 를 바꿨다.

tran_duck_m = list(map(list, zip(*duck_m)))

근데 문제점은

[[0, 5], [1, 6], [2, 7], [3], [4]] 와 같이 빈칸이 존재하는(직사각행렬이 아닌) duck_m 을 transpose 하면, tran_duck_m = [[0, 1, 2, 3, 4]] 이렇게 나와버린다. 그래서 먼저 q, u, a, c, k 각 개수가 똑같지 않을 때 먼저 쳐내여야 한다. 아래처럼 코드를 수정했다.

# 정상인지 확인
  if len(set([len(i) for i in duck_m])) != 1:
    return -1
  tran_duck_m = list(map(list, zip(*duck_m)))
  for i in range(len(tran_duck_m)):
    if tran_duck_m[i] != sorted(tran_duck_m[i]):
      return -1

정답 코드

def find_index(duck, q):
  return [i for i in range(len(duck)) if duck[i]==q]

def howmanyducks(quack):
  duck_m = [find_index(quack, i) for i in "quack"]

  # 정상인지 확인
  if len(set([len(i) for i in duck_m])) != 1:
    return -1
  tran_duck_m = list(map(list, zip(*duck_m)))
  for i in range(len(tran_duck_m)):
    if tran_duck_m[i] != sorted(tran_duck_m[i]):
      return -1

  # 정상이면 몇 마린지 확인
  count_duck = [list(tran_duck_m[0])]
  for i in range(1, len(tran_duck_m)):
    if tran_duck_m[i][0] > min([i[-1] for i in count_duck]):
      count_duck[[i[-1] for i in count_duck].index(min([i[-1] for i in count_duck]))].extend(tran_duck_m[i])
    else:
      count_duck.append(tran_duck_m[i])

  return len(count_duck)

print(howmanyducks(input()))

풀이

처음부터 find_index 라는 함수를 쓰는데, 이는 q, u, a, c, k 각 문자가 몇 번째 인덱스에 나타나는지 보기 위해 사용한다.

예를들어 “quackqua” 를 입력받으면, duck_m = [[0, 5], [1, 6], [2, 7], [3], [4]] 가 된다. 즉 q는 0번, 5번 인덱스에 / u는 1번, 6번 인덱스 / a는 2번, 7번 인덱스 / u는 3번 인덱스 / a는 4번 인덱스에 등장한다는 의미를 가졌다.

정상적인 울음소리가 아니면 -1 을 리턴해야 한다. 일단 정상인지부터 확인하자.

1. 먼저 각 문자가 동일한 횟수로 등장했는지 확인한다. if len(set([len(i) for i in duck_m])) != 1 에서는 q, u, a, c, k 가 각각 등장한 횟수가 동일한지를 확인한다. 위 “quackqua” 예시에서 각 q는 2번, u는 1번만 등장한다. 이런 경우를 쳐낸다.

2. 만약 각 문자가 동일하게 등장한 경우, 문자의 순서가 올바른지 확인해야 한다. “quackqauckquack” 에서 중간에 u랑 a랑 순서가 바뀌어 있다. 이렇듯 quack 의 순서가 맞아야 한다는 뜻이다.

   각 문자가 동일하게 등장하면 duck_m 은 직사각형 매트릭스가 된다. 이때는 tranpose를 취할 수 있다. 이것의 의미하는 건, 위의 “quackqauckquack” 예시의 tran_duck_m 은 [[0, 1, 2, 3, 4], [5, 7, 6, 8, 9], [10, 11, 12, 13, 14]] 처럼 나온다. 각 요소들이 정렬되어 있어야 하는데 중간에 5, 7, 6 와 같이 정렬되지 않았다. quack 의 순서가 맞지 않다는 의미다.

이렇게 정상적이 아닌 경우를 쳐냈으면, 정상이 몇 마린지 확인해야 한다.

“quqacukqauackck” 이 예시의 답은 2 인데, 이 예시의 tran_duck_m은 아래와 같다. [[0, 1, 3, 4, 6], [2, 5, 8, 11, 12], [7, 9, 10, 13, 14]]

첫번째 [0, 1, 3, 4, 6] 각 숫자는 q, u, a, c, k가 등장한 인덱스이다. 6번 인덱스에 k로 잘 끝났다.

두번째 [2, 5, 8, 11, 12] 에서 q는 2번 인덱스에서 시작한다. 그럼 첫 번째의 울음소리와 연결되지 않는다.(=첫번째 오리와 다른 오리다.)

세번째 [7, 9, 10, 13, 14] 는 첫 번째 오리 소리가 6번째 인덱스에서 끝났으니 이 오리와 연결될 수 있다. 즉, 첫 번째 오리는 [0, 1, 3, 4, 6, 7, 9, 10, 13, 14] 이렇게 울었다는 뜻이다.

이렇게 인덱스 순서가 이어질 수 있으면 같은 오리로 보는 것이다. 이를 구현하면 아래와 같다.

# 정상이면 몇 마린지 확인
count_duck = [list(tran_duck_m[0])] # 일단 첫 번째 울음소리만 담긴 리스트
for i in range(1, len(tran_duck_m)): # 다른 울음소리 하나씩 보면서 
  if tran_duck_m[i][0] > min([i[-1] for i in count_duck]): # count_duck 울음소리 중에 연결할 수 있는 게 있으면 
    count_duck[[i[-1] for i in count_duck].index(min([i[-1] for i in count_duck]))].extend(tran_duck_m[i]) # 연결하고
  else: # 연결 못 하면 
    count_duck.append(tran_duck_m[i]) #count_duck에 새로운 오리의 울음소리로 추가한다.

따라서 count_duck의 길이를 리턴하면 된다.

인과추론은 상관관계로부터 인과관계를 추론하고 언제, 그리고 왜 서로 다른지 이해하는 과학이다. 목적은 바로 현실을 이해하는 것이다.

예를 들어 회사에서 어떤 마케팅이 매출 증가로 이어지는지 알고 싶어한다고 하자. 그것을 알아야 그 마케팅으로서 수익을 늘릴 수 있기 때문이다. 일반적으로 원인과 결과의 관계를 알아야만 원인에 개입하여 원하는 결과를 가져올 수 있다. 이렇게 인과추론을 산업에 적용하면 의사결정 과학의 한 분야가 된다.

상관관계(Correlation)는 인과관계(Cauality)가 아니다

위 사진은 아이스크림 판매량과 상어의 사고횟수를 나타내는 그래프다. 둘은 상관관계는 있으나 인과관계는 없다. 그저 여름에 덥기 때문에 아이스크림을 많이 사먹는 거고, 해변에서 수영을 자주 하다보니 상어에 노출되는 경우가 많은 것뿐이다. 이렇듯 상관관계와 인과관계를 구분할 줄 알아야 한다.

• 상관관계 : 두 개의 수치나 확률변수가 같이 움직이는 것, 즉 통계적 변수가 다른 통계적 변수와 함께 공변(covariance)하는 관계를 말한다. ML모델의 예측을 목적으로 사용된다.
• 인과관계 : 한 변수의 변화가 다른 변수의 변화를 일으키는 것, 즉 선행하는 한 변수가 후행하는 다른 변수의 원인이 되고 있다고 믿어지는 관계를 말한다. ‘원인 설명’이 목적이다.

인과추론의 기본 지식

이제 인과추론에서 사용되는 기본 용어들과 개념을 알아보자.

가격할인이 판매량에 미치는 영향을 알고 싶다고 해보자. 가격할인이 판매량에 영향을 미친다면, 이는 인과관계에 관한 문제이다. 즉, 가격을 할인했을 때가 그렇지 않았을 때보다 얼마나 더 많이 판매했을지를 알고 싶은 거다.

할인여부(is_on_sale)가 주간 판매량(weekly_amount_sold)에 미치는 효과를 알아보자

$T_i$ : 실험 대상 i의 처치 여부

$Y_i$ : 실험 대상 i의 결과

$$ T_i=\left{\begin{array}{l} 1: \text { 실험 대상 } i \text { 가 처치 받은 경우 } \ 0: \text { 실험 대상 } i \text { 가 처치 받지 않은 경우} \end{array}\right. $$

• 처치(treatment) : 효과에 대한 개입(intervention)을 나타내는 용어, 이 예시에서는 ‘가격할인(is_on_sale)’을 말함
• 결과(outcome) : 영향을 주려는 변수, 여기서는 주간 판매량(weekly_amout_sold)

위는 처치(is_on_sale)에 따른 결과(weekly_amount_sold)를 그래프로 나타낸 것이다. 이것만 보면 할인한 경우 판매량이 더 많았음을 알 수 있다.

인과추론의 근본적 문제

인과추론에는 근본적인 문제가 있는데, 동일한 실험 대상이 ‘처치’를 받은 상태와 받지 않은 상태를 동시에 관측할 수 없다는 점이다.

위의 예시를 조금 더 깊이 생각해보면, 연관관계를 인과관계로 착각하고 있었음을 알 수 있다. 판매량이 많게 나타난 이유는 상품을 많이 판매하는 대기업들이 더 공격적으로 가격을 낮출 여유가 있기 때문일 수 있다. 또, 시기에 따라 다른 원인이 발생할 수 있다.

즉, 동일한 실험 대상인 회사가 할인이 진행되는 상황과 그렇지 않은 상황을 동시에 관측할 수 있어야만 가격할인이 판매량에 미치는 효과를 확신할 수 있다는 것이다.

이런 문제들에 대한 대안을 앞으로 하나씩 알아보자.

인과모델

인과모델을 표시하는 공식 표기법을 알아보자. 인과모델에서는 화살표를 써서 인과관계의 비가역성을 표시한다.

$$ T \leftarrow f_t(u_t) \ Y \leftarrow f_y(T, u_y) $$

첫 번째 식은 모델링 하지 않는 변수 집합인 외부변수($u_t$)가 함수 $f_t$를 통해 처치변수 $T$를 유발하는 원인이 됨을 설명한다.

두 번째 식은 처치변수 $T$와 다른 변수 집합 $u_y$가 함수 $f_y$를 통해 결과 $Y$를 유발함을 의미한다.

이 식에서 알 수 있는 것은 모델링하지 않기로 선택한 변수라 하다더라도 결과에 영향을 미친다는 것이다. 우리 예시에서 보자면, 판매량은 처치($T$)에 해당하는 할인 여부 뿐만 아니라 특정되지 않은 요인인 $u$에 의해 발생한다는 것이다. 변수 $u$의 목적은 모델에 포함된 변수로는 아직 설명되지 않은 변수의 모든 변동을 설명하는 것이다. 이러한 변수를 내생변수(endogenous variable)라고 한다.

더 많은 변수를 사용해 모델링하려면 $u$에서 변수를 꺼내서 인과모델에 명시적으로 포함시키면 된다. 예를 들어 대기업이 더 많이 할인을 할 수 있기 때문이라는 근거에서 BusinessSize를 명시적으로 포함시키는 거다. 그럼 아래와 같이 모델링 할 수 있다.

$$ BusinessSize \leftarrow f_s(u_s) \ IsOnSalse \leftarrow s_t(BusinessSize, u_t) \ AmountSold \leftarrow f_y(IsOnSalse, BusinessSize, u_y) $$

(1) 추가 내생변수(BusinessSize)를 포함하기 위해, 먼저 그 변수가 어떻게 생성되었는지 나타내는 수식

(2) BusinessSize를 모델 외부벼수로 다루지 않도록 $u_t$에서 꺼내고, IsOnSalse가 BusinessSize와 외부변수들인 $u_t$에 의해 발생함을 나타냄

(3) 판매량에는 할인여부(IsOnSalse)와 BusinessSize와, 그 외의 외부변수들이 원인으로 작용함을 나타냄

개입(Intervention)

아주 간단한 인과모델에서 모든 실험 대상이 처치 $t_o$를 받도록 하는 상황을 가정해보자. 이렇게 하면 $T$에 대한 자연적 원인을 제거하여 상수로 대체할 수 있다.

$$ T \leftarrow t_o \ Y \leftarrow f_y(T, u_y) $$

처치를 $t_o$로 설정한다면 결과 $Y$에 어떤 일이 일어날까?

인과추론에서는 개입을 $do(.)$ 연산자를 활용해 나타낸다. $T$에 개입해서 어떤 일이 일어날지를 추론하고 싶다면 $do(T = t_o)$로 표현할 수 있다.

$do(.)$ 연산자로 보는 연관관계와 인과관계의 차이

$$ E[AmountSold|IsOnSales = 1] \ E[AmountSold|do(IsOnSalse =1)] $$

실제로 가격을 할인한 회사의 판매량 기댓값은 $E[AmountSold|IsOnSales = 1]$ 로 표현할 수 있고,

가격을 할인하도록 개입한 경우의 판매량 기댓값은 $E[AmountSold|do(IsOnSalse =1)]$ 로 표현한다. 모든 회사가 가격을 할인하도록 통제했을 때 어떤 일이 발생했을지를 나타낸다.

중요한 것은 이 두 개의 조건부 기댓값이 다르다는 점이다.

$do(.)$ 연산자는 관측된 데이터에서 항상 얻을 수 없은 인과 추정량(causal quantity, causal effect estimand) 을 정의하는 데 사용한다. 이 예제에서 보면 모든 기업이 가격할인이 강요되지 않았기 때문에 모든 회사의 $do(IsOnSales = 1)$인 상황을 관측할 수 없다. 즉, $do(.)$ 연산자는 구하려는 인과 추정량을 분명하게 표현하는 데 사용할 수 있는 이론적 개념으로 사용된다. 대부분의 인과추론은 인과 추정량에 대한 이론적 표현에서 직접 관측할 수 없는 부분을 제거하기 위한 일련의 과정으로, 이를 식별(identification)이라고 부른다.

개별 처치효과(Individual Treatment Effect, ITE)

$do(.)$ 연산자를 사용하면 실험 대상 i에 처치가 결과에 미치는 영향인 개별 처치효과(Individual Treatment Effect, ITE)를 표현할 수 있다. 아래처럼 두 개입의 차이로 나타낸다.

$$ \tau_i = Y_i|do(T=t_1) - Y_i|do(T=t_0) $$

예시를 적용해보면 아래처럼 쓸 수 있다.

$$ \tau_i = AmountSold_i|do(IsOnSales=1) - AmountSold_i|do(IsOnSales=0) $$

그런데! 앞서 말했듯 인과추론의 근본적인 문제, 앞 식의 두 항 중 하나의 항에 대해서만 관측이 가능하다는 것이다. 그래서 이론적인 식이라고 보면 된다.

잠재적 결과(Potential Outcome)

• 사실적 결과(Factual Outcome) : 관측할 수 있는 한 가지 잠재적 겨과
• 반사실적 결과(Conterfactual Outcome) : 관측할 수 없는 다른 한 가지 결과

→ 예를 들어, 실험 대상 i가 처치를 받았다면, 사실적 결과인 $Y_{1i}$를 관측할 수 있으나 반사실적 결과인 $Y_{0i}$는 알 수 없는 것이다.

그래서 잠재적 결과를 아래처럼 나타낼 수 있다. 이는 ‘처치가 t인 상태일 때, 실험 대상 i의 결과는 Y가 될 것이다’를 의미한다.

$$ Y_{ti} = Y_i|do(T_i=t) \ Y_{ti} = Y(t)_i $$

잠재적 결과에 따라 회사 i의 인과효과를 정의할 수도 있다.

$$ \tau_i = Y_{1i} - Y_{0i} $$

일치성과 SUTVA

앞서 본 식에는 두 가지 가정이 있다.

1. 일치성(Consisency)이 있어야 한다.

즉, $T_i = t$ 일 때 $Y_i(t) = Y$ 여야 한다는 것이다. $T$ 로 지정된 처치 외에 숨겨진 다른 처치가 존재하지 않음을 의미한다. 예를 들어 할인쿠폰(처치)을 여러 번 시도했다면, 일치성 가정을 위배하는 것이다. 또 처치가 잘못 정의된 경우에도 일치성 가정이 위배될 수 있다. 예를 들어 재무 설계사의 도움이 개인 자산에 어떤 영향을 미치는지 파악하려고 하는데, 여기서 ‘도움’이 일회성 상담인지, 정기적 조언인지가 다를 수 있는데 이를 하나로 묶어버리면 일치성 가정에 위배되는 것이다. ** 2. 상호 간섭 없음(No interference) 또는 SUTVA(Stable Unit of Treatment Value Assumption)이다.**

하나의 실험 대상에 대한 효과가 다른 실험 대상에 영향을 주지 않아야 한다는 것이다. 파급효과(spillovers effect)나 네트워크 효과가 있는 경우 이런 가정을 위배할 수 있다. 예를 들어 백신이 전염성 질환에 미치는 영향을 알고 싶은 경우, 한 사람에게 백신을 접종하면 보통 그 주위 사람들의 질병 확률이 낮아진다. 이렇게 가정을 위배하는 경우, 일반적으로 처치효과가 실제보다 작다고 결론내리게 된다. 파급 효과가 발생하면 대조군도 처치의 영향을 받으므로, 파급 효과가 없을 때보다 실험군과 대조군 간의 차이가 작아지기 때문이다.

인과 추정량

이렇게 인과추론의 근본적인 한계가 무엇인지 알게 되었다. 그러나 추정량을 통해 이 문제를 어느정도 해결해볼 수 있다. ATE라는 것인데, 이를 세 가지 방식으로 정의해 볼 수 있다.

평균 처치효과(Average Treatment Effect, ATE)

평균 처치효과(ATE)는 처치 $T$가 평균적으로 미치는 영향을 나타낸다. 앞서 본 인과추론의 근본적 문제 때문에 하나의 실험 대상의 효과는 알기 어려나, 기댓값은 알 수 있는 것이다.

1. $ATE = E[\tau_i]$
2. $ATE = E[Y_{1i}-Y_{0i}]$
3. $ATE = E[Y|do(T=1)] - E[Y|do(T=0]$

가격할인이 판매량에 미치는 평균 영향을 아래와 같이 쓸 수 있다.

$ATE = E[AmountSold_{1i}-AmountSold_{0i}]$

실험군에 대한 평균 처치효과(Average Treatment Effect on the Treated, ATT)

$ATT = E[Y_{1i}-Y_{0i}|T=1]$

이는 처치 받은 대상에 대한 처치효과이다. ATT는 처치 받은 대상을 조건으로 하므로, $Y_{0i}$는 항상 관측되지 않지만, 이론적으로는 잘 정의될 수 있다. (무슨 말이지??)

가격을 할인한 회사가 어떻게 판매량을 늘렸는지 보자.

$ATT = E[AmountSold_{1i}-AmountSold_{0i}|IsOnSales=1]$

조건부 평균 처치효과(Conditional Average Treatment Effect, CATE)

$$ CATE = E[Y_{1i}-Y_{0i}|X=x] $$

변수 X로 정의된 그룹에서의 처치효과를 의미한다. 예를 들어 50세 이상과 그보다 젊은 고객에게 광고가 미치는 영향을 비교하는 데 쓸 수 있다. 이렇듯 어떤 유형의 실험 대상이 개입에 더 잘 반응하는지를 봐서 개인화에 유용하다.

크리스마스 주간의 할인 여부가 미치는 영향은 아래처럼 나타낼 수 있다.

$CATE = E[AmountSold_{1i}-AmountSold_{0i}|weeksToXmas=0]$

인과 추정량 예시

다음 표는 잠재적 결과를 알고 있다고 가정하고 작성한 표이다. 다음 표를 기준으로 ATE, ATT, CATE를 구하는 예시를 보자.

만약 AmountSold0과 AmountSold1를 모두 알 수 있다면 모든 인과 추정량을 쉽게 구할 수 있다.

ATE는 마지막 열(te)의 평균이다. 65의 의미는 가격 할인으로 판매량이 65개가 증가함을 의미한다.

$$ ATE = (20+20+100+50+0+200)/6 = 65 $$

ATT는 $T=1$일 때 마지막 열의 평균이다. 즉, 가격을 할인한 회사는 가격할인에 따른 판매량이 83.33개가 증가했다.

$$ ATT = (50+0+200)/3 = 83.33 $$

크리스마스 1주일 전이라는 조건부 평균효과는 회사 3번과 6번 효과의 평균이다.

$$ CATE(x=1) = (100+200)/2 = 150 $$

크리스마스 주에 대한 평균 처치효과(CATE)는 다음과 같이 구한다.

$$ CATE(x=0) = (20+20+50+0)/4 = 22.5 $$

즉, 크리스마스 주간에 가격을 할인하면 평균 22.5개의 판매량이 증가하고, 크리스마스 1주일 전에 할인했을 때는 평균 150개가 증가하는 것이다. 따라서 가격을 일찍 할인한 매장이 나중에 할인한 매장보다 더 많은 이득을 보았다고 할 수 있다.

현실 세계에서는 다음 표처럼 알 수 없는 값이 많다. 잠재적 결과중 하나만을 볼 수 있으므로, 개별 처치효과를 파악할 수 없다.

처치를 받은 회사와 그렇지 않은 회사의 평균을 비교하는 것은 연관관계를 인과관계로 착각하는 중대한 오류를 범하는 것이다. 이제 연관관계가 인과관계가 아닌 이유를 이해해보자.

편향(bias)

편향(Bias)는 인과관계와 연관관계를 다르게 만드는 요소이다.

ATE를 추정하려면 실험군이 처치 받지 않았을 경우인 $E[Y_0|T=1]$와 대조군이 처치 받았을 경우인 $E[Y_1|T=0]$을 추정해야 한다. 즉, $E[Y_t]$를 찾을 때 $E[Y|T=t]$를 추정하게 된다. 두 값이 일치하지 않는다면, 처치 t를 받은 실험 대상의 평균 결과인 $E[Y|T=t]$는 추정하고 싶은 $E[Y_t]$의 편향 추정량이 된다.

편향의 수식적 이해

표본평균이 추정하려는 잠재적 결과의 평균과 다를 수 있는 이유를 앞서 살펴봤다. 이제는 평균의 차이가 ATE와 같지 않은 이유를 살펴보자.

예제에서 처치와 결과 간의 연관관계는 $E[Y|T=1]-E[Y|T=0]$ 으로 측정된다. 이는 할인을 진행한 회사의 평균 판매량과 할인하지 않은 회사의 평균 판매량을 뺸 값이다.

반면, 인과관계는 $EY_1-Y_0$ 으로 측정할 수 있다.

이 두 식이 왜 다른지 살펴보자.

위 식으로 알 수 있다시피, 연관관계는 실험군에 대한 처치효과(ATT)에 편향을 더한 값이다. 편향은 처치와 관계 없이 실험군과 대조군이 어떻게 다른지에 따라 주어지고, 이는 $Y_0$의 차이로 표현된다.

이런 일이 왜 발생할까?

바로 교란(Confounding)때문이다. ‘관측할 수 없는 많은 요소가 처치와 함께 변화하므로 편향이 발생한다’고 생각하면 된다. 실험군과 대조군은 단순히 할인 여부뿐만 아니라 회사규모, 위치, 경영 방식 등의 다른 여러 요소가 다르다. 때문에 가격할인으로 인해 판매량이 얼마나 증가하는지 알기 위해서는 할인한 회사와 그렇지 않은 회사가 평균적으로 비슷해야 한다. 이것을 ‘실험군과 대조군이 교환가능(Exchangeable)하다’고 표현한다.

인과효과 식별

실험군과 대조군이 서로 교환 가능하다면, 주어진 데이터만으로도 인과관계를 표현하는 일이 아주 간단해진다는 의미다. 즉, 가격을 할인한 회사와 그렇지 않은 회사가 서로 비슷하다면(교환 가능하다면), 두 그룹 간의 판매량 차이는 오직 가격할인 때문이라고 볼 수 있다는 것이다. 수식으로 살펴보면 다음과 같다.

그러나 현실에서는 하나의 잠재적 결과만 관측할 수 있으므로, 인과 추정량을 관측할 수 없다. 하지만, 관측 가능한 다른 수치를 찾아서 이를 관심있는 인과 추정량을 찾는 데 활용할 수 있다. 관측 가능한 데이터에서 인과 추정량을 찾아내는 방법을 ‘식별 과정’이라고 한다.

독립성 가정

교환 가능성은 인과추론의 핵심 가정이다.

$(Y_0, Y_1) \bot T$ 와 같이 잠재적 결과와 처치가 독립적이라고 가정한다. 독립성 가정은 $E[Y_0|T]=E[Y_0]$, 즉 처치가 잠재적 결과에 관한 어떠한 정보도 제공하지 않음을 의미한다. 어

랜덤화와 식별

독립성 가정으로 연관관계를 인과관계로 같게 만드는 방법을 알아보자. 인과추론 문제는 보통 다음과 같이 두 단계로 나뉜다.

1. 식별(identification) : 관측 가능한 데이터로 인과 추정량을 표현하는 방법을 알아내는 단계
2. 추정(estimation) : 실제로 데이터를 사용하여 식별한 인과 추정량을 추정하는 단계

처치를 무작위로(Randomize) 배정할 수 있다고 가정하자. 실험 대상에 처치가 무작위로 이루어진다면 잠재적 결과는 물론이고 어떤 변수와도 독립적이 된다. 이렇듯, 랜덤화는 독립성 가정을 만족시키도록 한다.

$$ IsOnSalse \leftarrow rand(t) \ AmountSold \leftarrow f_y(IsOnSales, u_y) $$

이게 인과적 식별 작업의 핵심이다. 즉, 인과적 식별은 편향을 제거하고 실험군과 대조군을 비교할 수 있게 만드는 방법을 찾아서 눈에 보이는 모든 차이를 처치에 따른 효과로 돌리는 과정이다. 여기서 식별은 데이터 생성 과정을 알거나 기꺼이 가정할 수 있는 경우에만 가능하다. 즉, 일반적으로 처치가 어떻게 배정되었는지를 알 수 있을 때 식별이 가능하다.

다음 장에서는 랜덤화추출(Randomization)를 통해 인과추론의 추론 부분을 알아보도록 하자!

Reference

• 책 : 실무로 통하는 인과추론
• 인과관계 vs. 상관관계 - Granger causality - The Pabii Research

1️⃣ 소프트웨어 마에스트로란?

🔗 소프트웨어 마에스트로 사이트

SW인재를 발굴/육성하는 2010년부터 시작한 정부지원 사업입니다. 창의·도전형 프로젝트 기획·개발과 SW분야 최고 전문가들의 집중 멘토링 및 심화교육을 통해 최고급 인재로 성장할 수 있습니다.

연수생 특전

(15기 기준, 기수마다 다르다고 함)

• 장학금 : 예비 연수기간(4-5월)은 세전 30만원씩, 본 연수기간(6-11월)은 100만원씩 지급

• 기기 지원비 : 1회 한정으로 150만원, 본체, 노트북, 아이패드 등 구매 가능
• 프로젝트 개발비
• 특허/창업지원
• 교육 및 개발공간 제공 등...

지원 과정

자기소개서 > 코테 1차 > 코테 2차 -> 면접 으로 이루어진다.

2️⃣ 자기소개서

전기수 14기까지는 자소서 문항이 많았는데, 이번 15기에는 딱 필수문항 2개 + 선택문항 1개로 이루어졌다.

1번 : (*필수) [자기소개] SW분야의 전문성을 키우기 위해 몰입했던 경험과 도전이 무엇인지, 또한 이러한 성장과정을 통해 얻은 배움은 무엇인지를 서술하여 주시기 바랍니다. (최소 400자, 최대 1000자 입력가능)

• 데이터분석을 공부하며, 방법론의 원리가 무엇인지 꼼꼼히 파악하고 적용하는 것의 중요성을 알게 된 사건과 그 해결과정, 그리고 그 경험들이 성장의 원동력이 되었다는 것
• 교내 데이터분석·AI 동아리의 회장으로서 배운 것들, SW분야에서 필요한 소프트 스킬을 어떻게 키워왔는지 등

2번 : (*필수) [연수계획서] SW마에스트로 과정 참여를 통해 어떠한 프로젝트를 수행하고 싶은가요? 해당 프로젝트를 수행하기 위한 계획과 이루고자 하는 목표가 무엇인지 구체적으로 서술하여 주시기 바랍니다. (최소 400자, 최대 1000자 입력가능)

• 실제 경험에서부터 불편함을 느꼈던 부분을 해결하고자 하는 프로젝트 아이디어 설명
• 2번에서 '내가 아이디어가 많다!'는 걸 보여주려고 했다. 그래서 과거에 어떤 아이디어를 생각했었고, 결국 그게 배포까지 가지 못 한 사건들에 대해 이야기했다.
• 그리고 그 아이디어를 실현시키고 싶다는 목표와, 수행하기 위한 계획을 간단하게 적었다.

3번 : (선택) [기타] SW대회 수상 등 증빙이 가능한 경우 서술하여 주시기 바랍니다. (대회명 / 수상내역 / 수상일자 / 수여기관 / 증빙서(첨부파일):해당자는 이전단계->서류첨부->"기타 증빙서류"에 증명서 반드시 첨부)

• 위에 나와있는 형식으로만 써야 한다.

💭 생각/느낀 점

처음에 썼던 자소서가 진짜 너무너무 형편없었다. 같이 준비한 언니오빠 덕분에 여러 번의 퇴고 끝에 괜찮은 자소서가 나온 것 같다. '습니다' 체로 써야 하는데 처음에는 '했다.'이렇게 썼고, 두괄식으로 써야 하는데 서두를 너무 길게 쓴다거나 하는 문제가 많았다. 이런 문제점을 언니오빠 덕분에 많이 고칠 수 있었다. 하고 싶은 말은 많지만 최대 1000자 라서 말을 좀 더 간결하게 쓸 필요가 있다. 언니오빠한테 조언을 얻으면서 고치기도 했고, 은근 챗지피티가 잘 요약해줘서 지피티도 활용했다. 자소서에서 면접까지 그냥 정말 '내 이야기를 하자!'라는 마인드로 준비했다. 실제로 경험했던 것만 썼다. 특히 내가 보여주고 싶은 나의 모습을 키워드 두 가지로 고민했다. 그리고 그 키워드가 느껴지도록 자소서를 작성했다. '빠른 학습력(언제나 성장하고 발전하는 마인드)' 과 '아이디어(가치있는 것을 만들고 싶다는 마음)' 를 키워드로 그에 맞는 일화를 작성했다.

3️⃣ 코딩테스트

코테 준비 과정

준비 기간 : 1월 20일 시작 - 2월 24일(1차 코테)까지 (약 한 달)

• 매일 (일요일 제외)
  • 하루에 한 문제 풀어서 인증(인증은 제출 날짜 보이게)
  • 일정있는 날은 전 날에 푼 문제로 인증
• 일요일
  • 오후 3시에 줌(또는 디스코드) 키고 2시간 동안 5문제 풀기
  • 알고리즘 4문제 (실버 2문제, 골드 2문제) + sql 1문제
  • 문제는 돌아가면서 준비하기
• 벌칙
  • 지각 가장 많은 사람이 하이디라오 사기ㅎㅎ
• 서류 제출 7일전
  • 자소서 공유해서 피드백 해주기
• 코테 직전
  • 시간 제한두고 푸는거 횟수 늘리기

코테 공부하기 전 수준? 일단 백준은 거의 안 풀었어서 브론즈.. 그리고 프로그래머스 알고리즘 고득점 Kit 1/5도 안 푼 상태 SQL은 프로그래머스 SQL Kit 한 절반 정도 풀어봤던 상태 알고리즘은 DP, 분할정복, 다익스트라, 크루스칼 등 기본적인? 것은 알고 있었지만 실제 문제풀이 능력은 거의 없었음. 기억도 잘 안 나서 다시 복습하면서 공부할 필요가 있었다.

코테 스터디 하면서? 약 1주 반만에 백준 브론즈🥉에서 골드🏅를 달성했다! 이때는 하루종일 코테만 공부한 것 같다.

그 외 소프트웨어 마에스트로를 준비하는 오픈채팅 톡방이 존재한다! 그 톡방에 들어가서 이런저런 정보를 얻을 수 있으니 들어가는 걸 추천한다.

💭 생각/느낀 점

코테 스터디 할 때 가장 즐거웠다 ㅎㅎ 꼭꼭 스터디 하는 걸 추천한다. 같이 시간 맞춰 풀고, 문제 푼 사람이 해설해 주는 방식으로 진행했다. 혼자 준비했다면 당연 힘들었을텐데 서로 응원해주고, 북돋아주는 사람들이 옆에 있어서 그렇게 힘들지 않게 준비했던 것 같다. 그리고 모두 매일 코테 풀어서 하이디라오는 같이 사 먹으러 갔다! 역시 다들 맛잘알이다~ 같이 준비한 사람들이 너무너무 소중했다. 진심으로 서로가 잘 되길 응원해주는 게 느껴져서랄까. 소중한 인연들이다. to 노인정 멤버 👵👴

SQL 공부방법?

• 1차 코테 전

  • 프로그래머스 SQL Kit 문제풀이 1회 + 1차 복습

• 2차 코테 전

  • HackerRank 문제풀이 1회
  • 프로그래머스 풀이 눈으로 훑기
  • 익숙하지 않은 함수/개념 위주로 봄 : 비트연산, Recursive, set, Partition by, row_number, CTE 등..
  • 2차 문제에서 HackerRank에서 나온 row_number 함수를 사용했다. 이 함수는 프로그래머스에 딱히 나올 일이 없는 함수다. 운 좋게 이 함수를 2차 코테 하루 전에 공부해서 다행이다.. 꼭 HackerRank도 푸는 걸 추천!
  • SolveSQL 이라는 사이트도 있는데 이건 한 두 문제만 풀었었다.

• 아래 함수/개념 정도는 꼭 알고 있어야 한다. FROM절/WHERE절 서브쿼리 DISTINCT() like % COALESCE() IFNULL() DATE_FROMAT() CASE WHEN then ELSE LEFT() SUBSTR() JOIN UNION LIMIT TIMESTAMPDIFF() DISTINCT set REGEXP DATEDIFF RECURSIVE RIGHT() HAVING TRUNCATE() MID() ROUND() AVG() CONCAT() LPAD() RPAD() FLOOR() REPEAT REPLACE PARTITION BY RANK DENSE_RANK ROW_NUMBER CTE

• [노션] SQL 풀이 정리 : SQL 문제 풀면서 정리한 내용인데 도움될 것 같아서 공유합니당

알고리즘 공부방법?

• 대략 120개의 문제를 풀었다.
• [노션] 알고리즘 문제풀이 : 매일 푼 문제 모아서 정리해둠
• 코테 스터디가 가장 도움이 많이 됐다! 실전연습을 매주 했던 게 도움이 많이 된 것 같다.

코테 환경

• 프로그래머스 (온라인)
• 웹캠으로 내 얼굴 찍고, 핸드폰 카메라로 측면 찍음
• 독립된, 혼자 있는 공간에서 봐야 함
• 백준과 달리 시간 제한이 10초 정도로 널널한 편! 어떻게든 구현해내면 된다. 근데 나중에 면접에서 시간복잡도를 개선할 방법이 없었냐 물어볼 수도? 근데 일단 코테에서는 풀어내는 게 더 중요하겠죵
• 프로그래머스처럼 예제 입출력 제공해줌
• 영어로 된 언어 레퍼런스를 제공해줌
  • 나는 코테 2번 둘 다 레퍼런스 사이트를 이용했다. command+F로 필요한 모듈을 검색해서 썼다.

1차 코테(2월 24일 토요일)

• SQL
  • 너무 쉬웠다!
• 알고리즘 1 : 단순 구현
  • 쉬움
• 알고리즘 2 : 단순 구현
  • 그림이 보였을 때 어려운 건가..? 했는데 문제 읽어보니 쉬운 문제였다
• 알고리즘 3 : 아 귀찮아 구현
  • 일단 글이 길어서 여기서 당황했을 사람이 많았을 듯.
  • 근데 예제 입출력이랑 같이 보면서 읽어보면서 단순한 규칙을 찾음.
  • 파이썬 딕셔너리형(해시)를 사용함.
• 알고리즘 4 : 아 뭐지 구현
  • 배열, 또는 우선순위 큐? 들어보니 다양한 풀이가 가능할 것 같다. 그냥 부르트 포스도 가능했을 듯. 또 규칙을 찾아서 푼 사람도 있다고 함.
  • 문제에서 주어진 조건을 만족하는 것 중에 나오는 경우의 수끼리 비교하는 부르트 포스로 풀려고 했는데 별로 안 남은 시간에 당황해서 결국 못 풀었다.

알고리즘 3번까지 브론즈 - 실버 하위문제 정도 되는 것 같다. 다들 전반적으로 다 쉬웠다고 말하는 코테였던 것 같다.

1차 코테 응시 인원? 프로그래머스 화면 상에 이름(번호)가 떴는데, 그 번호가 대략 3000을 넘었다는 말이 많다. 아마 그 번호가 이름 순 응시번호가 아니였을까 하는 생각.. 그리고 2차때는 그 번호가 없어졌다. 정확한 응시인원은 모르지만 3,000명은 넘었을 것 같다는 게 나의 추측

1차 코테 합격선? 아래는 소마 15기 준비 카톡방에서 1차 코테 몇 개 풀었는지 투표한 결과 대략 4솔부터 안정적인 1차 코테 합격선이었던 것 같다. 3솔도 있다고 한다. 이 부분은 소마에서 알려주지 않기 때문에 그저 예상할 뿐이다. 본인이 4솔이라고 생각해도 문제의 히든 케이스에서 틀릴 수도 있다.

1차 합격 결과는 3/28 수요일에 나왔다.

2차 코테(3월 2일 토요일)

• SQL
  • 1차 SQL이 너무 쉬웠어서 그런지.. 이를 갈았나보다..
  • SET, CTE, ROW_NUMBER 사용했다.
  • 하루 전에 HackerRank에서 본 ROW_NUMBER 덕분에 운 좋게 풀었다.
  • 이 방법을 사용하지 않고 푸는 방법도 있다. 대신 그럼 좀 힘들어짐.. 다행히 함수를 알고 있어서 풀이시간은 20분 내외였다.
• 알고리즘 1 : 구현, 그리디
  • 아니 첫 알고리즘 문제부터 1차 코테의 알고리즘 3번 문제보다 오래 걸렸던 것 같다. 1차에 비해 갑자기 어려워지니까 당황했던 것 같다.
  • 반복문/While문 정도 쓰면 될 듯
• 알고리즘 2 : DP
  • 3차원 DP로 푸는 문제였다.
  • 3차원 DP문제를 푼 적이 별로 없어서 풀이 과정이 떠오르지 않았다.
  • 대충 2차원 DP로 나와있는 예시 케이스만 맞추도록 코드를 짰다.. 틀림!
• 알고리즘 3 : 분할정복
  • 못 풂. 문제 보자마자 분할정복 떠올랐지만, 분할정복 문제를 많이 안 풀어봐서 포기함.
• 알고리즘 4 : 빡구현?
  • 풀이 과정을 잘 모르겠다. 찾아본 정보에 의하면 DP, 비트연산라는 말이 있다.

2차 코테 난이도? 사람들 후기에 따르면 꽤나 어려운 코테였던 것 같다.

2차 코테 결과? SQL 1, 알고리즘 1번 풀었고, 결과는 합격!

2차 코테 느낀 점 아마 SQL 문제 푼 덕분에 2차 코테도 합격하지 않았을까 싶다. SQL 푼 사람이 많이 없었던 것 같다. 그리고 딱 느낀 점은 '아, 수련이 부족했다..!' DP나 분할정복 문제를 덜 풀어봤다. 너무 BFS/DFS 문제만 많이 풀었던 것 같다. 다양한 문제를 풀어봤어야 했다.

2차 코테 합격선? 2차 합격자 컷은 대략 1.5솔 정도 되는 듯. 2솔부터 안정적인 합격선이었던 것 같다.

💭 생각/느낀 점 처음 쳐 본 실제 코딩 테스트인 것 치고 잘 했다고 생각한다. 윗집이 이사와서 거의 매일 오후에 못 질하는 소리가 들렸고, 1/2차 코테 때도 좀 심하게 소리가 컸다. 특히 2차 때는 드릴 소리가 아주 컸다. 그래도 신경 안 쓰고 꽤나 침착하게 풀었다. 그런 소리나 외부의 자극에 민감하게 반응하지 않고 풀었던 점이 만족스럽다. 또, 주의했던 것이 한 문제에만 너무 몰두해 있지 않는 것! 뭐 하나 꽂히면 시간 가는 줄 모르고 풀어서 쉬운 문제를 못 풀고 끝났던 경험이 있어서 모든 문제를 읽고 생각해보자고 생각했다. 가장 크게 얻어간 건, 어떻게 코테 준비/공부를 해야 하는지를 알게 됐다는 거다.

4️⃣ 면접

3월 6일(수) 2시 발표인데 1:56에 메일이 먼저 왔다.. 아무생각 없이 봤는데 면접 보러 오라고 했다!!

면접 준비 과정

톡방에 아래처럼 많은 면접 스터디 모집글이 올라온다. 나는 우리학교 면접 스터디 1회 + 동네 면접 스터디 3회를 진행했다.

서로 포트폴리오 피드백, 3분 발표 피드백 등을 진행했고, 나올 만한 공통 질문/개인 질문에 대해 계속 서로 질문하고 답하는 시간을 가졌다. 정말 도움이 많이 됐었다! 면접 스터디를 하면서 어떻게 보완할지를 많이 알게 됐다.

💭 생각/느낀 점 올해부터 일기를 쓰고 있는데 그렇게 쓰는 과정과 더불어 면접 스터디를 하면서는 말하는 과정을 통해 내 생각을 확실하게 굳히고 전달하는 연습을 한 것 같다. 결과적으로 그게 면접에서 정말 도움이 많이 되었다고 생각한다. 예를 들어 예상 질문에 '팀원이 탈주하면 어떻게 대처할 것인지', '“MZ세대 개발자들은 워라밸을 중시한다"라는 말에 대해 어떻게 생각하는가?', '1년 뒤 혹은 5년 뒤의 예상하는 본인의 모습' 등 자기 자신에 대해 잘 알아야 하는 질문에 대해 비교적 쉽게 답을 생각해볼 수 있다.

포트폴리오 면접 합격 발표날로부터 4-5일 정도 포트폴리오를 만들 시간을 준다. 포트폴리오는 노션으로 제출한다. 노션 템플릿을 제공해주나, 그 템플릿을 꼭 따르지 않고 디자인을 변경해도 된다. 나는 거의 새로 만들었다.

• 상 받은 게 많아서 각 상을 받은 프로젝트마다 설명을 적었다. 한 줄 요약, 배우고 느낀 점을 적었다. 창업 경진대회에서 상 받은 것도 추가했다.
• 대학 성적 상장, 이공계 장학금 받은 것도 따로 빼서 넣었다. 딱히 플러스 요인이 되진 않겠지만, 그동안 뭐 했니? 왜 배포 경험이 없니? 에 대한 답이 좀 될 것 같았고, 어느정도 성실성을 보여줄 수 있지 않을까란 생각으로 넣었다.
• 기술 스택을 안 썼다. 그동안 데이터분석/AI 만 주로 해왔기 때문에 따로 프레임워크를 적을 게 없었다. 대신 이에 대해 물어보면 어떤 답을 해야 할지 준비했다.
• 3분 발표안에 모든 것을 얘기하지 못 한다. 그러나 면접관께서 다른 부분을 읽을 수 있기 때문에 좀 많다 싶을 정도로 작성한 게 많았다.

면접 날

면접은 aT센터 3, 4층에서 진행됐다.

정장 입으신 분들이 꽤 계셨다. 면접자 분들이라는 걸 바로 알 수 있었다.

면접장에 도착하면 스태프 분께서 친절하게 안내해주신다. '0분과 0번' 이라고 써 있는 목걸이와 교통비 3만원, 소마 브로셔를 주신다. 그리고 내 번호가 써 있는 대기실 의자에 앉아 있으면 된다. 옆에 앉으신 분께 인사드리려고 했는데 앞에 바로 스탭 분께서 지키고 계시고 조용한 분위기라 가만히 있었다.

그리고 아래 사진 왼쪽에 있는 기지개 펴는 포즈처럼 두 팔을 들어 올렸다ㅎㅋ 이게 실제로 테스토스테론 수치를 높여 자신감을 높여준다는 연구 결과가 있다고 한다. 효과가 있는 건지, 떨리지 않았다.

앞에 계신 스탭 분께서 친절히 안내사항을 말씀해주셨다. 그리고 떨지 말라고 격려의 말도 해주셨다!

면접관 N명, 면접자 (5-6)명으로 면접이 진행된다. 그러나 우리 5분과에서는 4명만 왔고, 4분과에서는 3명만 오셨다. 다른 분과는 알 수 없었다. 톡방 보니까 이렇게 빠진 경우는 많지는 않은 것 같다. 대부분 5-6명 모두 오신 것 같다. 대략 320명 내외의 사람이 면접을 본 것 같다.

그렇게 면접장에 들어가니 5분의 인상 좋으신 면접관 분들이 계셨다. 스탭 한 분께서도 같이 들어간다. 분과마다 동일한 면접관분들이신 것 같다. 3일동안 진행되는 면접일정이고, 그 외 시간에는 우리 자소서랑 포폴, 블로그를 보셨을 테니까 아무래도 굉장히 피곤하셨던 것 같다. 면접관 분들 책상에 커피와 에너지 드링크가..

바로 번호대로 각자 3분씩 포트폴리오 발표를 진행한다. 각자 알아서 3분 스톱워치를 누르고 시작하면 된다. 근데 내 순서에서 분명히 스톱워치에서 삑- 소리가 들려서 발표를 시작했는데 끝날 때쯤 보니 안 눌러져 있었다. 그래도 다행히 스탭 분께서 따로 시간을 재고 계셨고, 3분을 넘지 않았다고 하셨다. 타이머로 PT발표 연습을 많이 해봤기 때문에 3분을 넘지 않았을 거라는 것을 알고 있었다. 아무튼 죄송하다 말씀드리고 자리에 앉았다.

다른 분들이 발표할 때 고개를 돌려서 열심히 봤다. 이런 팀 면접시에는 다른 사람의 말을 경청할 필요가 있다. '다른 분들 발표중에 인상 깊었던 게 있었다면, 어떤 건지 말해달라'는 질문도 나올 수 있다.

압박면접일수도 있겠다는 생각을 하고 갔다. 그러나 우리 분과에서 뵌 면접관 분들께서 모두 정말 인상이 너무 좋으셨고, 따뜻한 분들이셨다. 처음에는 농담을 던져서 분위기를 풀어주시기도 하셨다. 그래서 진짜 하나도 안 떨고 얘기할 수 있었다.

기술질문은 두 가지가 나왔는데 AI관련 최신 기술인 어떤 개념에 대한 질문, 그리고 블로그에 한 2년 전에 써둔 내용을 질문하셨다. AI 질문은 잘 대답했지만 2년 전에 써둔 내용에 대해서는 진짜 기억이 안 나서 솔직하게 2년 전이라 기억이 잘 안 나지만, 이러이러한 내용이었던 것 같습니다 하며 얼버무렸다.

우리 분과에서 딱히 기술질문은 많이 나오지 않았다. 인성 질문이 대부분이었다. 평소 내가 내 자신을 어떻게 생각하는지 그 가치관이 좀 확실한 사람이라면 대답하기 쉬운 질문들이었다.

면접 팁

소마 사이트에 나온 면접 평가내용은 아래와 같다. 제출서류, 코딩테스트 작성코드, 포트폴리오 발표를 통해 활동계획, 참여의지, 협업능력, SW지식수준 및 학습역량, 논리적 사고력, 인성 및 발전가능성 등 평가

딱 위 평가내용에 맞는 질문을 하셨다. 돈만 받고 참여를 안 할 사람인지, 중간에 취업이 되어서 중도하차하지는 않을지 등.. 정말로 1년동안 소마에 열심히 할 사람인지를 우선적으로 확인하는 것 같다.

준비해 가야 할 사항을 아래와 같다. 아래 내용에 대해서는 어떻게 변주되어 질문이 나올지는 모르지만, 이 부분은 확실하게 생각을 해야 한다. (아래는 실제 받은 질문과 동일하지 않지만, 면접 준비하면서 고민했던 부분들이다.)

• 내가 강조하고 싶은 나의 장점이 무엇인지?
  • 웹/앱 개발 경험이 부족했던 나는 다른 부분에 있어 장점을 강조할 필요가 있었다.
• 그전에 다른 도메인을 하던 사람이라면, 왜 갑자기 소마에 지원하게 되었는지 그 이유를 확실하게 해야 한다.
• 소마에 들어와서 진짜 하고 싶은 게 뭔지? 취업? 창업? 어떤 걸 얻어가고 싶어?(활동계획/참여의지)
  • 꼭 소마여서 내가 얻을 수 있는 것, 또 꼭 소마가 나를 뽑아야 하는 이유를 확실하게 사례/근거와 함께 준비해두자.
  • 또 소마를 하고 나서 내가 어떤 사람이 되어 있을지를 생각해보자.
• 팀 활동에 문제 없는 사람인가, 문제를 해결한 경험 (협업능력)
  • 다양하게 변주되어 나올 수 있는 질문이다.
  • 본인이 리더의 성향인지, 팀원의 성향인지 잘 생각해보자. 리더의 성향이라면, 리더로서 어떤 경험이 있는지를 정리해두는 게 필요하다. 반대로 팀원의 성향도 마찬가지로 사례를 준비해두자.
  • 경험과 사례가 중요하다. 미리 생각해놔야 한다. 나는 이러이러한 사람이다 얘기하고 그거에 대해 경험과 사례로 근거를 설명해야 한다.
• 평소 어떻게 SW지식을 습득하는지? (학습역량)
  • 남들과 다른 학습 방법이 있는지 생각해보자.
• 본인이 하고 싶다고 쓴 프로젝트에 대해 구체적으로 생각해보자 (활동계획, SW지식 수준, 논리적 사고력)
  • 하고 싶다고 쓴 프로젝트가 왜 필요한지
  • 기존에 그런 프로젝트/서비스가 없었는지
  • 없었다면 왜 없었을지, 있다면 차별점이 있는지
  • 그 프로젝트를 수행하기 위해 어떤 기술이 필요할지 등
• 당연한 거지만 본인이 쓴 프로젝트에 대해서는 기술적인 부분에서 준비를 열심히 해가야 한다. 특히, 꼭 그 기술을 거기에 쓴 이유가 있을까 생각해보자.(SW지식 수준, 논리적 사고력)
• 코딩테스트 작성코드를 보신다. 그리고 실시간으로 어떻게 풀었는지를 아시는 것 같다. 여기에서 공격이 들어올 수 있다. 아래는 예상질문과 내가 생각한 답변이다. 코딩테스트에 관한 질문은 우리 면접장에서는 하나도 안 나왔지만 이런 질문이 들어왔을 때 방어할 수 있는 나만의 답을 생각해두자. 당황하지 않는 것이 중요하다.

합격

3/22 금요일 1:55에 합격 메일이 왔다! 👏 14기까지만 해도 연수기간에 탈주하는 사람들까지 고려해서 기존 선발인원의 10%가량 더 뽑았다고 하는데 이번 15기에서는 딱 200명만 뽑았다. 그리고 예비번호를 받은 사람이 있다고 한다. 이럴수가.. 더 빡세졌다.

아무튼 이렇게 합격하게 돼서 넘나 감사하다! 열심히 해야징 자소서, 코테부터 포트폴리오, 면접까지 이 모든 과정에서 참 배운 게 많다. 그러니 고민하는 분들이 있다면 꼭꼭 지원하시길!

마코프 결정과정(MDP, Markov Decision Process) 은 마르코프 보상과정(MRP, Markov Reward Process)에 행동(A: Action)과 정책($\pi$: Policy)이 추가된 개념이다.

• MRP의 목적 : 에피소드나 환경전체의 가치를 계산

  • 에이전트는 타임스텝에 따라 상태전이확률(P)에 영향을 받으며 자연스럽게 이동한다.

• MDP의 목적 : 환경의 가치를 극대화 하는 정책을 결정하는 것

  • MDP에서는 에이전트(Agent)라는 새로운 개념이 등장한다. MDP에서는 에이전트가 취한 행동과 상태 전이 확률의 영향을 동시에 받아 환경의 상태가 바뀐다.
  • MDP에서 에이전트는 정책($\pi$)에 따라 행동(A)을 하며 상태(S)는 에이전트가 취한 행동과 상태전이확률(P)에 따라 바뀌게 된다.

• MDP의 구성요소

  • $S$ : 상태(State)의 집합

  • $P$ : 상태 전이 매트릭스 $P^a_{ss'} = P[S_{t+1} = s' | S_t = s, A_t = a]$ 시간 $t$에서 상태가 $s$ 였을 때 $a$ 행동을 할 경우 시간 $t+1$ 에서 상태가 $s'$ 일 조건부 확률

  • $R$ : 보상함수 $R_s^a = E[R_{t+1}| S_t = s, A_t = a]$ 간 $t$에서 상태가 $s$ 였을 때 $a$ 행동을 할 경우 시간 $t+1$ 에서 받는 보상의 기댓값

  • $\gamma$ : 감가율

  • $A$ : 행동(Action)의 집합

  • $\pi$ : 정책 함수

MDP는 MRP의 상태전이매트릭스와 보상함수에 ‘행동’이라는 조건이 더 추가됐다. MDP에는 행동(A)이 추가됐기 때문에 상태 전이 매트릭스와 보상함수 또한 행동을 함께 생각해줘야 한다. MDP에서 취할 수 있는 행동의 개수는 상태와 마찬가지로 유한하다.

MDP에서 정책이란? $\pi = P[A_t = a | S_t = s]$

MDP에서 정책이란 행동을 선택하는 확률이다. 따라서 정책에서 따라 행동한다는 것은 확률이 높은 행동을 할 가능성이 크다는 의미이다.

MDP에서 에이전트는 항상 정해진 길을 따라가진 않는다. 언제나 의외성이 존재한다. 이는 이후 나올 탐험(Explopration)과 연관이 있다.

위를 보면 정책의 확률과 그쪽으로 이동할 확률을 곱해줘서 다 더한다. 에이전트는 s2로 가는 a1과 s3로 가는 a2중 하나를 고를 수 있다. 에이전트가 정책에 따라 a1을 선택했다고 하더라도 반드시 s2로 이동하지 않는다. 바로 상태전이 확률에 영향을 받기 때문이다.

상태전이확률은 에이전트의 의지와 전혀 상관없는 환경에서 자연적으로 발생하는 환경이다. 따라서 정책에 대한 확률과 상태전이확률을 각각 곱해서 더해야 한다.

MRP나 MDP나 s1에서 s2로 이동할 확률은 동일하다. 그러나 MDP는 정책이라는 새로운 요소가 추가된 것이고 이 덕분에 새로운 기능을 추가할 수 있다.

MDP에서 에이전트의 행동은 오로지 정책에 의해 결정되며, 정책은 시간에 따라 변하지 않는다. MDP도 마코프 속성을 가정하므로 현재상태에만 영향을 받는다.

• 정책을 고려한 상태 전이 매트릭스와 보상 함수 $$ P_{ss'}^\pi = \sum_{a \in A} \pi(a|s)P_{ss'}^a $$

  $$ R_s^\pi = \sum_{a \in A}\pi(a|s)R_s^a $$

정책도 매트릭스 형태의 조건부 확률이다. MDP에서 상태가 변한다는 것은 원래 가지고 있던 상태 전이 매트릭스와 정책의 영향을 동시에 받는다는 것이다.

따라서 행동에 따른 정책과 상태전이확률의 기댓값을 구함으로써 정책을 고려한 상태전이매트릭스를 구할 수 있다.

정책을 고려한 보상함수 또한 상태전이매트릭스와 동일하게 정책과 각 행동별 보상 함수의 기댓값을 통해 나타낸다.

MRP와 MDP의 상태 가치 함수

• MRP의 상태가치함수

  $$ v(s) = E[R_{t+1} + \gamma v(S_{t+1}) | S_t = s] \ = R_{t+1} + \gamma E[v(S_{t+1})|R_t = s] \ = R_{t+1} + \gamma \sum_{s' \in S}p_{ss'}v(s') $$

• MDP의 상태가치함수

  $$ v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi(S_{t+1})|S_t = s] \ = \sum_{a \in A} \pi(a|s)(R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_\pi (s')) \ = \sum_{a \in A}\pi(a|s)R_s^a + \gamma\sum_{a \in A}\pi(a|s)\sum_{s' \in S}P_{ss'}^a v_\pi(s') $$

MRP와 MDP의 상태 가치 함수는 같다!

$$ v(s) = v_\pi(s) $$

두 값은 같지만, MDP에서 상태 가치 함수를 구할 때는 정책이라는 요소를 하나 더 고려한 것뿐이다.

MDP 행동 가치 함수(Q 함수)

MDP의 목적은 환경의 가치를 극대화하는 정책을 결정하는 것이다. 그리고 정책은 행동을 결정하는 확률이다.

상태 가치 함수는 상태를 중심으로 가치를 평가했다. 정책을 평가하기 위해서는 ‘행동’을 중심으로 평가해야 한다. 이것이 바로 행동 가치 함수(Q : Action Value Function, Q함수)이다.

1번은 상태가치함수를 다시 기술한 것이다. 행동가치함수에서는 행동을 미리 선택했기 때문에 기댓값을 구할 필요가 없다. 따라서 1-1과 1-2 부분을 빼고 수식을 3번과 같이 기술할 수 있다.

$\pi(s',a')$ 부분이 추가된 것은 다음 상태에서의 보상을 정확히 계산하기 위해서는 정책과 상태 전이 확률 매트릭스를 곱해줘야 하기 때문이다.

Q함수는 선택할 수 있는 여러 행동 중 하나를 선택했을 때의 가치를 계산한다.

행동 가치 함수 $$q_\pi (s,a)$$는 내가 선택한 행동의 가치를 계산하는 함수이고, 상태 가치 함수 $$v_\pi(s)$$는 특정 상태의 가치를 계산하는 함수이다.

1. MDP에서 하나의 상태에서 다른 상태로 이동하기 위해서는 상태 전이 매트릭스와 함께 행동을 선택할 확률인 정책을 함께 고려한다. 따라서 행동 가치 함수를 사용해서 상태 가치 함수를 구하기 위해서는 정책에 대한 기댓값을 구한다.

2. 행동 가치 함수는 어떤 행동을 했을 때 그 가치가 어떻게 되는지 계산한 것이다. 가치는 현 상태에서 즉시 받을 수 있는 보상 + 미래에 받을 수 있는 보상으로 계산한다. 미래 보상은 행동을 했을 때 이동한 상태에 따라 달라진다.

   $P_{ss'}^a$ → 상태 전이 매트릭스에서 모든 행동을 고려하는 것이 아니라 하나의 행동만을 고려한다.

MDP는 가치를 극대화 하는 것이 목표이다. 가치를 기반으로 정책을 평가해서 가치를 최대화하는 정책(최적 정책 : Optimal Policy)를 찾는 것이 최종적인 목적이며, 이것이 강화학습의 기초적인 개념이다.

MDP 최적 가치 함수

이제 MDP의 최종목적을 달성하기 위해 최적 가치 함수(Optimal Value Function)에 대해 알아보자.

최적 가치 함수는 아래처럼 최적상태 가치함수와 최적행동 가치함수로 나눌 수 있다.

$$ v^*(s) = max_\pi v_\pi(s) $$

$$ q^*(s,a) = max_\pi q_\pi(s,a) $$

1. 최적 상태 가치함수 : 여러 정책을 따르는 상태가치함수가 있을 때 가치를 최대로 하는 정책을 따르는 상태 가치 함수를 말한다.
2. 최적 행동 가치 함수 : 다양한 정책을 따르는 행동 가치 함수 중에서 가치를 최대로 하는 정책을 따르는 행동 가치 함수를 말한다.

MDP에서 최적 행동 가치 함수를 안다는 것은 가장 효율적인 행동을 선택할 수 있는 정책을 안다는 것과 같다. 따라서 최적 행동 가치 함수를 찾아내면 MDP 문제를 해결할 수 있다.

• 최적정책의 특성

  • $\pi^* : \pi^* \ge \pi, \forall pi$

  • $v_{\pi^}(s) = v^(s)$

  • $q_{\pi^}(s) = q^(s)$

• 최적 정책을 나타내는 방법
  어떤 행동 a가 최적 행동 가치 함수의 최댓값을 반환하게 만드는 행동이라면 그 행동에 대한 정책은 1이 되고, 그렇지 않으면 0이 된다. 이때 정책은 행동을 선택할 수 있는 확률이므로 상태 s에서의 정책은 확률이 1로 설정된 행동을 반드시 선택하게 된다.

강화학습(RL, Reinforcement Learning) : 적절히 설계된 보상 체계를 활용해 에이전트가 긍정적인 행동을 할 수 있도록 에이전트 행동을 제어하는 정책을 찾아내는 최적화 기법

에이전트(Agent)는 정책(Policy)에 따라 어떤 환경 (Environment)에서 특정 행동(Action)을 한다. 그러한 행동에 따라 환경의 상태(State)가 바뀌고 상태가 긍정적으로 바뀌 었는지 부정적으로 바뀌었는지에 따라 보상(Reward)을 받는다.

• 강화학습 구성요소

행동, 상태의 종류가 적은 경우에는 계산을 통해 최적의 정책을 찾을 수 있으나 상태의 종류가 많아질수록 최적의 정책을 찾는 계산 증가 → 인공신경망 활용

환경과 에피소드

환경과 에피소드라는 말이 계속 나온다. 환경(Environment)은 아래 그림처럼 각 노드(상태)와 엣지로 이루어진 전체를 의미하고, 에피소드(Episode)는 S > R1 > R3 > F 처럼 일련의 연속된 상테의 변화를 의미한다.

확률과 확률과정

• 확률적(stochastic)이다? = 무작위적 (random)이다!

📌 경영과학2에서 마코프 체인, 마코프 프로세스에 대해 자세하게 배운다. 마코프 프로세스를 넘어 대기행렬이론까지 배우는데 이 내용은 추후 블로그에 정리할 예정이다.

확률 과정(Stochastic Process)

시간의 흐름에 따라 확률적(무작위적)으로 움직이는 상태를 말한다.

$\left{ X_t \right}$ 로 집합으로 표현한다. X는 랜덤변수, t는 시간이다.

이런 확률 과정이라는 개념을 만들어 수학적으로 현상을 표현하면 프로그래밍을 통해 쉽게 문제 해결이 가능해진다.

마코프 속성(Markov Property)

마코프 속성은 확률과정의 특수한 형태로, memoryless, 즉 과거에 일어났던 일들과 무관하게 현재의 상황만이 미래의 상황에 영향을 미친다는 것을 의미한다.

이렇게 과거의 일을 무시하고 현재만을 고려하면 문제를 풀기 훨씬 수월해진다. 마코프 속성을 조건부 확률로 나타내면 아래와 같다. St는 t시점에서의 상태를 의미한다.

$P[S_{t+1}|S_t] = P[S_{t+1}|S_1, ..., S_t]$

마코프 연쇄(Markov Chain)

마코프 체인(Markov Chain)은 마코프 속성을 지닌 시스템의 시간에 다른 상태 변화를 나타낸다. 즉, 과거와 현재 상태가 주어졌을 때, 미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정되는 환경을 말한다.

• 시간이 이산적일 때 → Markov Chain 이라고 하며

• 시간이 연속적일 때 → Markov Process 라고 한다.

마르코프 보상 과정(MRP, Makov Reward Process)

MRP : 마코프 연쇄에 보상(Reward)과 시간에 따른 보상의 감가율인 감마($\gamma$)가 추가된 개념

마코프 연쇄 : 상태에 전이확률만 주어짐 → 상태변화가 얼마나 가치있는지는 알 수 X ↔ MRP는 상태변화의 가치까지 계산!

구성 : 상태집합($S$), 상태 전이 매트릭스($P$), 보상함수($R$), 감가율($\gamma$)

• 상태집합($S$) MRP에서는 상태는 유한!

• 상태 전이 매트릭스($P$) $P_{ss'} = P[S_{t+1} = s'|S_t = s]$

• 보상함수($R$) $R_s = E[R_{t+1}|S_t =s]$ : 시간 t에서 상태가 s일 때, 시간 t+1에서 받을 수 있는 보상의 기댓값 보상함수(Reward Function)는 확률의 기댓값 형태로 표현할 수 있다. 상태 $s$가 $t+1$에서 가질 수 있는 상태가 2개($S2, S3$)이고 각각으로 갈 확률이 $p1, p2$이며, 각 상태변화에 따른 보상이 $r1, r2$ 일 때 보상함수는 아래와 같다. $R_{s1} = p1\times r_1 + p_2 \times r_2$ : 확률을 곱해 기댓값 형태로 나타냈다. 상태 $s1$의 보상은 t+1에서 계산된다.

• 감가율 ($\gamma$, 할인율) $\gamma \in [0, 1]$

  MRP의 목적은 가치를 계산하는 것인데, 이 가치는 보상함수를 사용해 하나의 에피소드 혹은 전체 환경의 가치를 한꺼번에 모두 계산한다. 그리고 그 가치는 현재가치로 환산되어야 한다. 여러 번의 타임스텝 후에 얻게 되는 현재가치를 환산하는데, 여기에 감가율을 사용하는 것이다. 이자율을 생각해보면 된다.

  감가율이 0이면 미래의 보상을 전혀 고려하지 않는 것이고, 감가율이 1이면 현재와 미래의 가치를 동일하게 보는 것이다.

여기에서 반환값($G$: return)이라는 개념이 등장한다. 반환값은 타임스텝 t에서 계산한 누적 보상의 합계이다. 반환값은 주로 전체 환경이 아닌 에피소드 단위로 계산하는데, 에피소드의 효율성이나 가치를 반환값을 통해 평가하며, 이 반환값을 극대화할 수 있도록 환경을 설계하는 것이 MRP의 목적중 하나다.

• 반환값

$$ G_t = R_{t+1} + rR_{t+2} + r^2R_{t+3} ... = \sum_{k=0}^\infin r^kR_{t+k+1} $$

여기에서 특이한 점은 상태전이확률을 고려하지 않는다는 점이다. 반환값은 하나의 선택된 경로(에피소드)에 대한 전체적인 보상을 계산하는 방법이기 때문이다. (= 이미 경로가 결정된 상태에서 계산하는 게 반환값. 확률은 필요 없다.)

• 반환값 계산 예시 감가율을 0.5로 설정. 3타임스텝에 목적지에 도달하는 에피소드는 모두 3가지. 각 노드마다 보상이 정해져 있고, 이 보상값에 타임스텝이 진행됨에 따라 감가율을 계속 곱해줌.

• 상태가치함수(v : State Value Function) 반환값(G)으로 에피소드 하나에 대한 가치를 측정할 수 있었다면, 상태가치함수는 환경 전체에 대한 가치를 측정한다. 상태전이확률을 같이 고려한다는 점이 반환값과 다른 점이다.

  	측정 대상	특징	감가율 r	상태 전이 확률 P
  반환값 G	에피소드	합계	사용	미사용
  상태 가치 함수 v	전체 환경	기댓값	사용	사용

MRP 상태 가치 함수

1. 타임스텝 t가 상태 s에 있을 때의 반환값의 기댓값으로 정의한다.
   • 아래 그림과 식을 보면 이해하기 쉽다.
     

2. 반환값을 구하는 식을 그대로 집어넣는다.
3. 다음 타임스텝의 반환값을 감가율($$\gamma$$)로 묶는다.
4. 이것을 다음 타임스텝의 반환값으로 대치한다.
5. 마지막 수식은 반환값 대신에 상태가치함수를 집어넣은 것이다. 반환값을 상태가치 함수로 대체할 수 있는 이유는 반환값에 대한 기대값을 구하면 상태 가치함수를 구하는 것과 같기 때문이다.
6. 상수를 기댓값에서 빼줌
7. 기댓값을 수열의 합과 다음 상태에서의 상태 가치 함수로 나타낸 것. 이것을 벨만 방정식이라 부른다.

벨만 방정식(Bellman Equation)

벨만 방정식(Bellman Equation)는 MRP의 상태 가치 함수를 일반화하여 프로그래밍이 가능한 형태로 만든 것이다. 강화학습에서는 프로그래밍으로 가치를 구하기 위해 이 방정식을 많이 사용한다.

• 벨만 방정식 : 현재 상태의 가치함수와 다음 상태의 가치함수 사이의 관계 $v(s) = R_{t+1} + \gamma \sum_{s' \in S} P_{ss'} v(s')$

벨만 방정식은 일반적으로 기댓값을 시그마 기호를 사용한 수열의 합으로 표현하며 현재상태와 다음상태의 관계로 나타낸다.

위와 같은 상황에서 벨만 방정식을 그대로 적용해 직접 가치를 계산하는 것은 쉬운 일이 아니다. 벨만 방정식을 사용하는 이유는 프로그래밍을 통해 문제를 해결하기 위함이다.

간단한 네트워크로 구성된 라우팅 문제의 경우 순차적으로 반환값을 구해 상태가치함수를 계산할 수 있다.

위상정렬(Topological Sorting)이란 아래처럼 사이클이 없는 유향그래프를 일열로 나열하는 문제이다. 각 노드가 생산과정에서 하나의 Task라고 보면, e를 하기 위해서는 b와 d가 선행되어야 하고, b를 하기 위해서는 a가 선행되어야 한다. 이런 순서를 정해주는 거라고 보면 된다. 아래처럼 위상정렬의 결과는 여러 개일 수 있다.

• 입력 조건 싸이클이 없는 유향 그래프

• DAG(Directed Acyclic Graph) 라고 한다.

• 위상정렬(Toplogical Sorting) 특징 모든 정점을 일렬로 나열하되, 정점x와 정점 y로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치해야 한다. 일반적으로 임의의 유향그래프에 대해 복수의 위장정렬 해가 존재한다.

1️⃣ 위상정렬 알고리즘 1

수도코드

topologicalSort1(G)
{
    for 1 to n {
        진입간선이 없는 정점 u를 선택한다;
        A[i] <- u;
        정점 u와, u의 진출간선을 모두 제거한다;

    }
    // 이 시점에서 배열 A[1..n]에 정점들이 위상정렬 되어 있다. 
}

• 위 수도코드를 보면서 그린 예시다. 진입간선이 없는 정점 u을 찾고, A에 넣은 다음, 그 u에서 나가는 화살표를 지워나간다.

파이썬 구현

def topologicalSort1(G):
  A = []
  k = len(G)
  while len(A) != k:
    to_list = []
    for i in G.values():
      to_list += i

    # 진입간선이 없는 정점 리스트
    u_list = set(G.keys()) - set(to_list)
    if len(u_list) == 0:
      return A

    for i in u_list:
      A.append(i)
      del G[i]
  return A

# 입력예시 1
adj_list = {0: [2, 3], 1: [3, 4], 2: [3, 5], 3: [5], 4: [5], 5: []}
# 입력예시 2
test_G = {'a': ['b', 'c'], 'b': ['d'], 'c':['d', 'e'], 'd':['f'], 'e':['f'], 'f':[]}

topologicalSort1(adj_list) # [0, 1, 2, 4, 3, 5]
topologicalSort1(test_G) # ['a', 'c', 'b', 'e', 'd', 'f']

2️⃣ 위상정렬 알고리즘2

수도코드

topologicalSort2(G)
{
    for each v in V:
        visited[v] <- NO;
    for each v in V:
        if (visited[v] = NO) then DFS-TS(v);
}

DFS-TS(v)
{
    visited[v] <- YES;
    for each x in L(v) // L(v) : v의 인접 리스트
        if (visited[x] = NO) then DFS-TS(x);
    연결 리스트 R의 맨 뒤에 정점 v를 삽입한다;
}

파이썬 코드

def topologicalSort2(G):
  R =[]
  visited = {i:False for i in G.keys()}
  for v in visited:
    if visited[v] == False:
      DFS_TS(v, G, visited, R)
  return R

def DFS_TS(v, G, visited, R):
  visited[v] = True
  for x in G[v]:
    if visited[x] == False:
      DFS_TS(x, G, visited, R)
  R.insert(0, v)

# 입력예시 1
adj_list = {0: [2, 3], 1: [3, 4], 2: [3, 5], 3: [5], 4: [5], 5: []}
# 입력예시 2
test_G = {'a': ['b', 'c'], 'b': ['d'], 'c':['d', 'e'], 'd':['f'], 'e':['f'], 'f':[]}

print(topologicalSort2(adj_list)) # [1, 4, 0, 2, 3, 5]
print(topologicalSort2(test_G)) # ['a', 'c', 'e', 'b', 'd', 'f']

3️⃣ DAG 에서 최단경로 구하기

싸이클이 없는 유향그래프인 DAG에서 최단경로(Shortest Path)를 구할 때, 위상정렬을 사용한다. DAG는 r이라는 출발노드에서 다른 모든 노드까지 각각 최소거리를 구한다. 아래 수도코드를 보자.

수도코드

DAG_shortestPath(G,r) // G: 그래프, r: 출발노드
{
    for each u in V:
        d_u <- inf;
    d_r <- 0;
    G의 정점들을 위상정렬한다;
    for each u in V: // 위상정렬 순서로
        for each v in L(u): // L(u): 정점 u로부터 연결된 정점들의 집합
            if (d_u + w_{u,v} < d_v) then d_v <- d_u _ w_{u,v};
}

• 가중치가 있는 DAG를 우선 위상정렬을 한다. 일단은 다른 노드까지의 거리를 inf로 설정한다. 아래 예제에서는 노드 b를 시작노드로 설정했기 때문에 본인으로 가는 거리는 0으로 설정한다.
• 그리고 위상정렬된 순서대로 반복문을 돌린다. 각 노드 안에 써 있는 숫자는 그 iteration에 시작노드에서 해당 노드까지 가는 거리를 나타낸다. iteration이 반복되면서 이게 업데이트된다.

파이썬 코드

import math

def DAG_shortestPath(G, r):
  d = {i:math.inf for i in G.keys()}
  d[r] = 0
  for u in topologicalSort2(G):
    for v in G[u]:
      if d[u] + G[u][v] < d[v]:
        d[v] = d[u] + G[u][v]
  return d

# 연결리스트
G = {'a':{'b':6, 'd':1}, 
     'b':{'d':7, 'f':5, 'c':3}, 
     'c':{'e':4}, 
     'd':{'e':-2, 'f':1}, 
     'e':{'f':-3},
     'f':{}}

DAG_shortestPath(G, 'b') # {'a': inf, 'b': 0, 'c': 3, 'd': 7, 'e': 5, 'f': 2}

내가 좋아하는 조승연, 장동선 두 분이 나와서 치킨게임, 죄수의 딜레마 등을 재밌게 설명하는 영상이 나왔다. 이걸 보고 게임이론을 공부하면 더 재밌다 :) 🔗 유투브 영상 : 🕹️뇌과학게임으로 보는 큰 성과를 이뤄내는 사람들의 특징

게임이론이란?

게임이론이란, 두 명 이상의 참가자가 이해관계가 상충하는 상황에서 각자 자신의 이익을 최대화하기 위해 어떤 전략을 택해야 할지 연구하는 학문이다.

제갈량과 조조의 전쟁게임 조조는 적벽대전 패배 후 퇴각하는 중이다. 넓고 대피하기 쉽지만 오래걸리는 '대로', 그리고 좁고 이동이 불편하지만 빠른 '소로' 중 어디로 대피할지 고민중이다. 제갈량도 둘 중 한 곳에만 복병을 배치할 수 있고, 어디에 배치할지 고민중이다. 이 결과는 내가 선택하는 전략뿐만 아니라 상대방에 선택하는 전략에 따라 결정된다. 조조는 소로에서 연기가 나자, 제갈량이 소로에 사람이 있는척 연기를 피우고 사실은 대로에 복병을 배치했을 거라 생각하고 소로로 퇴각하게 된다. 그러나 제갈량은 그 상황까지 예측하고 사실은 소로에 복병을 배치한다.

게임의 종류

게임은 3가지의 기준으로 나눌 수 있다.

1. 2인 게임 vs 다인 게임

• 2인 게임(two-person game) : 참가자가 2명
• 다인 게임(n-person game) : 참가자가 3명 이상

2. 영화게임 vs 비영화게임

• 영화게임(zero-sum game) : 참가자의 게임 결과의 합이 0이 됨 (누가 100을 잃으면, 누군 100을 잃음) ex. 노사협상
• 비영화게임(non zero-sum game) : 게임 결과의 합이 0이 되지 않는 게임 ex. 광고전략

3. 협력게임 vs 비협력게임

• 협력게임(cooperative game) : 게임 시작 전, 참가자들이 완전히 구속력있는 협약을 맺고 진행하는 게임
• 비협력게임(non-cooperative game) : 협약없이 서로 자신의 이익을 극대화하기 위해 최선의 전략을 찾으려는 게임

2인 영화게임 (two-person zero-sum game)

2인 영화게임에는 (1) 경기자 1의 전략, (2) 경기자 2의 전략, (3) 이득표(성과표, payoff table)가 필요하다. 이걸 보통 테이블로 표현하는데 이 테이블 안의 숫자는 경기자 1이 얻는 payoff이다. 'zero-sum'게임이기 때문에 경기자2는 경기자1이 받는 payoff에 - 를 취한 값이 된다.

2인 영화게임에는 아래와 같은 가정이 필요하다.

1. 두 경기자는 모두 이성적이다. 2. 두 경기자는 각각 상대방에 대한 동정심 없이 오직 자기의 이익만을 추구하여 전략을 선택한다.

이 가정으로, 자신의 몫을 지키기 위해 자기 방어적인 Maximin 전략을 사용하게 된다. Maximize min 이라고 보면 되는데, 내가 가질 수 있는 이익 중 최소값(하한)이 가장 커질 수 있게 Maximize 하는 전략이다.

열등전략 vs 우위전략

열등전략(dominated strategy)과 우위전략(dominant strategy)은 각각 Strictly, Weakly로 나뉜다.

• Strictly 열등전략(Strictly Dominated Strategy) 상대방이 어떤 전략을 선택하든 상관없이 전략 A가 전략 B보다 불리하면, "전략 A는 전략 B에 대해 Strictly 열등전략이다" 라고 표현한다.

  $$u(a, i) < u(b, i) \ for \ all$$ 상대전략 i

• Weakly 열등전략(Weakly Dominated Strategy) 최소 하나의 상대전략에서는 불리하고, 나머지에서는 불리하거나 동일한 이득을 주면 , "전략 A는 전략 B에 대해 Weakly 열등전략이다" 라고 표현한다.

  ( $$u(a, i) \le u(b, i) \ for \ all$$ 상대전략 i ) & ( $$u(a, i) < u(b, i) \ for \ some$$ 상대전략 i )

우위전략(dominant strategy) 도 마찬가지로 Strictly, Weakly로 나뉜다. 이성적인 경기자는 (Strictly or Weakly) 열등전략을 사용하지 않는다.

예제) 정치인 선거유세일정 문제

선거에서 두 정치인 1과 2가 대결하는 중이다. 앞으로의 유세기간은 2일이고, 두 정치인 모두 남은 2일 동안 도시 갑과 을에서 유세할 것을 계획중이다. 두 후보는 상대방의 일정은 알지 못 한다. 최선의 유세전략을 세우려고 한다. 각 정치인은 세 가지 전략을 가지고 있다.

• 전략 1 : 각 도시에서 하루씩 유세

• 전략 2 : 도시 갑에서 2일 유세

• 전략 2 : 도시 을에서 2일 유세

  • 이 전략을 세웠을 때 이득표는 아래와 같다.

  • 이 상황에서 정치인 2의 경우에는 열등전략이 존재하지 않는다. 하나의 전략이 확실히 불리한 게 없다. 그러나 정치인 1의 경우, 전략 3을 사용했을때 전략 1, 2를 사용했을 때보다 Strictly 열등하다. 따라서 정치인1은 전략 3을 사용하지 않는다. 그리고 정치인 2도 정치인1이 전략3을 안 쓸 거라는 걸 알고 있다.

  • 이 이득표는 정치인1의 입장이기 때문에, 정치인2의 입장에서는 숫자가 클수록 안 좋은 거다. 정치인 2가 전략 3을 쓰면 전략1,2에 대해 Strictly 열등전략이 되기 때문에 정치인2는 전략 3을 쓰지 않을 것이다.

  • 이번에 정치인 1 입장에서 전략 2는 전략 1에 대해 Weakly 열등전략이다. 따라서 전략 2를 버린다.

  • 정치인 2 입장에서는 전략 2가 전략 1에 대해 Strictly 열등전략이 된다.따라서 전략 2를 버린다.

  • 결국에 두 정치인은 모두 전략 1을 선택하게 된다. 정치인 1은 1의 이득을, 정치인 2는 -1의 이득을 얻게 된다.

  • 그리고 여기에서 정치인 1이 얻는 이득을 게임값 이라고 한다. 게임값이 0이 아니므로 정치인 1에게 유리한, 불공정한 게임이다.

최대최소기준, 최소최대기준 적용

위에서 푼 문제를 좀 더 쉽게 풀 수 있다. 최대최소(Maxi min), 최소최대(Mini max)를 적용하면 된다. 정치인 1 입장에서 먼저 보자. 파란색 부분의 min을 보면된다. 전략1을 썼을 때 가능한 이익은 1,2,4이고 그 중 정치인 2가 이성적이라면 정치인1의 이익을 가장 작게 만드는 1이 선택되게 할 것이다. 마찬가지로 정치인 1이 전략 2를 썼을 때 1, 0, 5 이익 중 0, 전략 3을 썼을 때 0, 1, -1 이익 중 -1의 이익을 얻게 될 것이다. 이 세 개의 전략을 썼을 때 각 1, 0, -1의 이익을 얻게 될 것이고 정치인 1은 그 중에서 이익이 가장 큰 1을 선택하게 된다. 그래서 이 과정을 Maxi min 이라고 하는데, 하한을 가장 크게 만드는 전략을 선택하는 것이다. 그때의 값을 lower value라고 부르고 $$\underline{v}$$ 으로 표현한다.

이제 정치인 2 입장에서 보자. 정치인 2가 전략 1을 선택했을 때, 정치인 1은 최대의 이익을 얻으려고 할 것이므로 그때 발생하는 이익은 1이다. 전략 2를 선택했을 때는 2, 전략 3을 선택했을 때는 5의 이익이 있다. 그러나 이 이익은 정치인 1의 입장에서의 이익이기 때문에 정치인 2는 이 중(1, 2, 5)에서 가장 작은 이익을 선택할 것이고 결국 1이 선택된다. 그래서 이 과정을 Mini max라고 하며, 상한을 가장 작게 만드는 전략을 선택하는 것이다. 그리고 이때의 값을 upper value라고 부르고 $$\bar{v}$$ 으로 표현한다.

전략 중 꼭 하나만 실행하는 '순수전략' 에서는 균형해가 존재하는 경우와 균형해가 존재하지 않는 경우로 나뉜다.

(1) 순수전략에 의해 균형해가 존재하는 경우 위와 같은 경우, 정치인 1과 2 모두 전략 1을 취하는 게 서로에게 이성적인 결과이다. 위 예시 처럼 $$\underline{v} = \bar{v}$$ 이 성립하는 경우에 이 점을 '안장점(saddle point)'라고 한다. 안장점이 존재하는 경우, 어떤 경기자든 전략을 바꾸면 더 안 좋은 상황이 되기 때문에 현 전략을 고수하려고 한다. 이러한 해를 '균형해(안정해)' 라고 한다.

(2) 순수전략에 의해 균형해가 존재하지 않는 경우 하나의 전략만을 선택하는 '순수전략'의 경우에는 균형해가 존재하지 않을 수 있다. 아래 예시를 보자. $$\underline{v}(-2) \ne \bar{v}(2)$$ 으로 안장점이 존재하지 않는다. 경기자 2는 경기자 1이 전략 1을 선택하면 전략 2를 사용하는 게 유리해서 전략 2로 변경할 것이다. 그러면 또, 경기자 1은 전략 2가 유리해서 전략 2로 변경한다. 그럼 경기자 2는 전략 3을 선택할 거고, 그럼 경기자 1은 전략 1을 선택할 것이다. 이렇게 과정이 순환될 수 있다. 이런 상황을 불안정한 해(unstable solution) 이라고 한다.

한 경기자의 전략이 예측가능하면 상대방이 이러한 정보를 이용해 자기 입장을 좋게 하려고 한다. 따라서 상대방의 전략을 예측하지 못하도록 '혼합전략' 을 사용한다. 혼합전략은 전략을 딱 하나만 선택하는 게 아니라 여러 전략을 확률적으로 선택하는 것이다.

혼합전략 -> 균형해가 존재

혼합전략이란? 전략집합에 확률분포를 할당하고 확률분포에 따라 전략을 무작위한 방법으로 선택하는 것이다.

최소최대정리(Minimax Theorem) 혼합전략이 허용될 경우 최소최대기준에 의해 최적이 되는 한 쌍의 혼합전략은 $$\underline{v} = \bar{v} = v$$(게임값) 을 갖는 균형해를 갖는다. 따라서 어느 쪽도 일방적으로 전략을 바꿈으로써 자신의 입장을 좋게 할 수 없다.

최적 혼합전략 구하기 최적 혼합전략을 구하는 방법은 두 가지 방법이 있다. (1) 선형계획법에 의한 해법 -> 어떠한 2인 영화게임에도 적용 가능 (2) 그래프에 의한 해법 -> 어느 한 경기자의 전략이 두개 뿐일 경우 적용 가능

여기에선 (2) 그래프에 의한 해법을 알아보자.

그래프 해법으로 최적 혼합전략 구하기

아래처럼 순수전략에서는 균형해가 존재하지 않는 문제를 혼합전략에서 그래프 해법으로 풀어보자.

• 경기자 1이 전략 1을 선택할 확률 : $$x_1$$
• 경기자 1이 전략 2을 선택할 확률 : $$x_2 = (1-x_1)$$

경기자 2의 선택이 전략 1이냐, 2이냐, 3이냐에 따라 경기자 1이 얻는 이익은 $$5-5x_1$$, $$4-6x_1$$, $$-3+5x_1$$ 이다. 경기자 1은 이 값의 최솟값을 maximize 하고 싶다. 따라서 아래처럼 그래프를 그려 최소값이 max가 되는 지점을 찾으면 된다.

• 경기자 1의 혼합전략 : $$(x_1, x_2 ) = (\frac{7}{11}, \frac{4}{11})$$
• 게임값 : $$\frac{2}{11}$$

아래는 경기자 2의 입장에서 본 것이다.

이번엔 경기자 2의 입장에서 아래 문제를 풀어 보자. 전략 1은 위에서 본 것처럼 열등전략이므로 사용하지 않는다. 따라서 전략 2와 3만 고려한다. 풀이는 위와 비슷하다. 이렇게 게임값을 구하면 위에서 구한 값과 똑같은 걸 알 수 있다.

이렇게 2인 영화게임에서의 순수전략일 때의 문제와 혼합전략으로 푸는 방법을 알아봤다.

다음에는 2인 영화게임의 혼합전략을 선형계획법으로 구하는 방법과 왜 게임이 쌍대문제인지, 2인 비영화 게임(non zero-sum game), 내쉬균형점, 치킨게임을 알아보자!

• [메타 휴리스틱] 1. 타부서치
• [메타 휴리스틱] 2. 시뮬레이티드 어닐링
• [메타 휴리스틱] 3. 유전자 알고리즘

다음 글은 경영과학에서 배우는 내용을 정리함.

0️⃣ 유전자 알고리즘이란?

유전자 알고리즘도 시뮬레이티드 어닐링처럼 자연의 현상을 모방한 방법이다. 시뮬레이티드 어닐링은 물리적 담금질이라는 자연 현상에서 아이디어를 가져왔고, 유전자 알고리즘은 다윈의 진화이론에 영향을 받았다.

진화이론 생물 종 중에서 환경에 적응해서 개별적인 변이가 일어난 개체가 다음 세대에 더 생존(적자생존, survival of fittest)한다. 자손은 부모로부터 염색체(chromosomes)을 물려 받고, 이 염색체 내의 유전자(genes)는 자손의 특성을 결정한다. 부모로부터 좋은 형질을 물려받은 자손이 더 많이 생존하고, 부모가 되었을 때 다음 세대에게 그 형질을 물려준다. 또한, 가끔이지만 돌연변이(mutation)가 발생하여 형질이 랜덤하게 변화된다. 대부분의 돌연변이는 단점이 많지만, 일부는 개선된 형질을 가지고 있다.

이런 생물학적 아이디어를 최적화 문제에 적용한 것이 유전자 알고리즘이다. 타부서치, 시뮬레이티드 어닐링은 초기해 하나를 사용해 변화시켰다면, 유전자 알고리즘은 여러 해인 해 집단, 여기에서는 '모집단(population)'을 사용한다.

✔️ 용어 정리

• 모집단(population) : 실행 가능한 해들의 집합
• 세대(generation) : 유전자 알고리즘의 반복횟수
• 개체 : 해
• 적합도(fitness) : 목적함수 값
• 부모 : 랜덤하게 선택된 개체 중, 2개를 선택해 한 쌍의 부모로 만듦
• 번식 : 부모의 형질이 랜덤하게 섞인 2개의 자식 태어남
• 유산(miscarriage) : 번식과 돌연변이로 실행 불가능한 해가 발생한 경우. -> 번식에 실패하면 성공할 때까지 번식해야 한다.
• 염색체 : 해를 표현하기 위한 것으로, 유전자 알고리즘은 보통 문자열로 표현.
• 부호화 : 해를 염색체로 표현하는 것을 의미함
• 동일교배 : 두 자식이 생성되는 방식이 같은 경우를 의미함

✔️ 유전자 알고리즘 과정

a. 초기화 : 모집단을 랜덤하게 만든다. 적합도를 평가한다.

b. 반복단계 : 부모는 적합도가 큰 개체를 랜덤하게 선택;
            부모의 형질이 랜덤하게 섞인 2개의 자식이 태어남;
            유산되면 번식이 성공할 때까지 번식해야 함.
            새로운 세대의 모집단의 크기를 유지하기 위해 이전 모집단 + 자식집단에서 적합도 좋은 일부를 선택하여 다음세대의 모집단을 구한다.

c. 종료단계 : 정해진 반복횟수나 CPU시간이 지나면 종료;
            또는 정해진 반복횟수동안 목적함수의 개선이 없는 경우;
            정해진 반복횟수동안 실행가능한 영역으로 이동할 수 없는 경우;
            => 지금까지 찾은 해 중 가장 좋은 해 출력

✔️ 유전자 알고리즘에서 명확히 할 것

1. 부호화 : 문제의 해를 염색체로 어떻게 표현할 것인가? (중요!)
2. 모집단의 크기는 몇 개로 할지?
3. 현재 모집단에서 부모가 될 개체 쌍을 어떻게 선택할 것인지? (랜덤하게 할 수 있지만, 좋은 적합도의 개체를 선택)
4. 교배 : 부모의 형질을 어떻게 자식에게 전할 것인지?
5. 돌연변이 : 어떻게 자식의 형질에 돌연변이를 발생시킬 것인지?
6. 어떤 종료 조건 쓸 것인지?

1️⃣ 유전자알고리즘 예제

유전자 알고리즘으로 비선형계획문제와 외판원 문제를 풀어보자.

✔️ 비선형계획문제와 외판원 문제에 사용할 파라미터

1. 부호화 : 문제마다 다르다. (해인 염색체를 어떻게 표현?)
2. 모집단의 크기 : 10개 (대규모 문제일 때는 이것보다 더 커야 함)
3. 적합도가 큰 5개 중 랜덤하게 4개 선택, 적합도 낮은 5개 중 랜덤하게 2개 선택 (총 6개 선택)
4. 교배 : 부모의 형질 전달 방법으로 문제마다 다름
5. 돌연변이 비율 : 자식에서 돌연변이가 발생할 확률 0.1 (대규모 문제일 때에는 이보다 작은 값 사용함)
6. 5번의 반복횟수 동안 목적함수 값의 변화가 없으면 종료

✔️ 1. 비선형계획문제

아래 비선형 문제를 풀어보자.

$$Maximize \ f(x) = 12x^5 - 975x^4 + 28,000x^3 - 345,000x^2 + 1,800,000x$$ $$subject \ to \ 0 \le x \le 31. \ x \ is \ integer$$

부호화

유전자 알고리즘은 보통 문자열(염색체)로 해를 표현한다. 여기에서는 정수를 이진화 하여 표현한다. x가 최대 31이니, 이를 이진화 하면 11111이 된다. 따라서 자릿수는 5개로 설정하고 이진화한다.

교배

교배는 부모의 유전자를 비교해 일치하면 형질을 자식에게 넘겨주고, 다른 경우에는 랜덤하게 넘겨준다. 즉, 부모가 정수 3과 10이라고 해보자. 그럼 같은 자릿수에 둘 다 0이면 자식도 0, 둘 다 1이면 1을 물려준다. 이때, 자식은 꼭 두 개체여야 한다. (개체 수 유지를 위해)

# 부모 개체
p1 =  3 = 00011 
p2 = 10 = 01010

# 자식 개체
c1 = 0_01_ 
c2 = 0_01_

그리고 빈칸은 0과 1중 랜덤하게 채워 넣는다. 여기에서는 아래와 같이 결정됐다고 하자.

# 자식 개체
c1 = 01011  => 11
c2 = 00010  => 2

돌연변이

이렇게 자식을 만들고, 확률적으로 돌연변이를 준다. 여기에서는 자식의 유전자 10개에 대해 각각 0.1의 확률로 랜덤하게 형질을 바꾼다. c2의 세 번째 값이 0->1로 바뀌었다.

# 자식 개체
c1 = 01011  => 11
c2 = 00110  => 6

이런 과정으로 작성하면 아래와 같다.

• 이렇게 만들어진 자식 6개체, 원래 있던 부모 10개체 중, 적합도가 좋은 10개의 개체를 다음 세대의 모집단으로 선정한다.

연속형 변수의 이진화 위처럼 정수조건이 없고, 실수일 때는 어떻게 할까? 실수도 이진화가 가능하다.

✔️ 2. 외판원 문제

외판원 문제란? => 여기 클릭

부호화

방문하는 도시를 순서대로 적은 문자열(염색체)로 해를 표현한다.

p1 = 1-2-3-4-5-6-7-1
p2 = 1-2-4-6-5-7-3-1

교배

c1과 c2는 어떻게 만들 수 있을까? 아래와 같은 방법으로 만들어낼 수 있다.

• 우선 시작 도시는 1, 그리고 1과 연결된 도시인 2,7,3번 도시 중 랜덤하게 선택한다
  • 2 선택 -> c1 : 1-2
• 이제 2와 연결된 도시중에 아직 방문하지 않은 3,4번 도시 중 랜덤하게 선택
  • 4 선택 -> c1 : 1-2-4
• 4와 연결된 도시 중 아직 방문하지 않은 3,5,6중 선택
  • 3 선택 -> c1 : 1-2-4-3
• 3과 연결된 도시를 선택해야 하는데, p1에서 연결된 도시가 없음. 3-4를 하위경로역순을 통해 뒤집고, 5를 후보로 선택함. p2에서는 후보로 7 선택
  • 5 선택 -> c1 : 1-2-4-3-5
• 5와 연결된 도시 중 아직 방문하지 않은 6,7 중 선택
  • 6 선택 -> c1 : 1-2-4-3-5-6
• 남은 도시는 7, 마지막으로 1이랑 연결
  • 자식 -> c1 : 1-2-4-3-5-6-7-1

돌연변이

0.1의 확률로 돌연변이를 만든다. 이 문제에서는 돌연변이를 아래와 같이 만든다.

후보도시 중, 랜덤하게 하나를 선택하는데 이때 0.1의 확률로 선택된 도시를 제외하고 다시 랜덤하게 남은 도시 중 하나를 선택한다.

위 예제에서는, 처음에 1과 연결된 도시 2,7,3번 중 하나를 랜덤하게 고르게 되는데 이때 2가 선택됐다. 0.1의 확률로 돌연변이가 일어났다고 하면, 선택된 2를 제외하고 7,3번 중에서 하나를 랜덤하게 생성하게 된다.

번식 요약

위 과정을 요약하면 아래와 같다.

1. 초기화 출발도시 1 선정 2. 다음 도시 후보 선택 각 부모에서 출발도시와 연결된 도시를 후보로 선택. 출발도시와 연결된 도시가 없는 경우 하위경로역순을 통해 연결할 도시 선택 3. 다음 도시 선택 2에서 얻은 후보 도시 중 랜덤하게 하나 선택 4. 돌연변이 검사 랜덤수를 발생하여 돌연변이 확률보다 작으면 3에서 선택한 도시 거절. 2에서 얻은 나머지 후보 도시 중 하나를 랜덤하게 선택 5. 계속 현재 도시에 연결할 수 있는 후보도시를 찾아 경로를 완성. 즉, 모든 경로가 완성될 때까지 2-4번 반복 6. 완성 실행불가능한 경로이거나 더 이상 도시를 연결할 수 없을 때에는 1단계부터 다시 수행하여 실행가능한 경로를 찾는다.

0️⃣ 시뮬레이티드 어닐링

메타 휴리스틱은 대부분 자연현상을 관찰하여 만든 것이 많다. 시뮬레이티드 어닐링도 마찬가지로 '어닐링(Annealing)'을 모방했다. 어닐링은 어떤 물체의 열을 높여 분자의 자유도를 높였다가 열을 서서히 낮추면 분자 상태가 더욱 단단해지는 것을 이용한다.

문제에서는 현재해의 온도를 높여, 현재해 주변,

이전 게시글에서 소개한 '타부서치'는 가장 높은 언덕을 찾는 시간보다 각각의 언덕을 오르는 데에 시간을 많이 소모한다. 그러다보니 지역최적해에 너무 매몰되어 있을 수가 있다.

반면 시뮬레이티드 어닐링은 가장 높은 언덕(전역최적해)을 찾는 데에 중점을 둔다. 그러다보니 이웃해를 선택하는 방법이 타부서치랑 다르다.

✔️ 용어 정리

• $$Z_c$$ : 현재해(current solution)의 목적함수 값
• $$Z_n$$ : 후보해(next solution)의 목적함수 값
• $$T$$ : 온도로, 현재해보다 개선되지 않았지만, 후보해로 선택할 정도를 나타내는 파라미터.
  • T가 높으면, $$Z_n < Z_c$$ 이더라도(후보해가 안 좋더라도), 후보해쪽으로 가능성이 높다.

✔️ 이동선택규칙(move selection rule)

후보해를 선택하는 규칙이다. 현재해에 인접한 이웃해 중, 다음해가 될 후보해($$Z_n$$)를 랜덤하게 선택한다.

• 최대화(Maximize) 문제인 경우

  • $$Z_n \ge Z_c$$ 이면, 후보해를 다음해로 선택

  • $$Z_n < Z_c$$ 이면, 아래와 같은 확률로 다음해를 선택 $$prob{acceptance} = e^x \ (where \ x= \frac{Z_n-Z_c}{T})$$ $$Z_n << Z_c$$이면 즉, 후보해인 Zn이 현재해보다 많이 작으면 확률은 거의 0이 되어 선택되지 않는다. 반면에 차이가 작다면, 확률은 거의 1이 된다.

  • 최소화(Minimize) 문제인 경우

    • 위와 완전히 반대로, Zn과 Zc의 위치를 바꾸면 됨

• 여기에서 $$T$$(온도)가 크다는 것은, $$Z_n-Z_c$$가 동일할 때 다음해로 선택될 확률이 더 커진다는 것이다.

✔️ 이동선택규칙의 특징

• 위 식을 보면, 약간 낮은 아래쪽 언덕으로 이동하는 것은 허용하나, 가파른 아래쪽 언덕으로 움직이는 확률은 작다.
• T값은 상대적으로 큰 값으로 시작한다. 처음에 후보해 선택 확률을 크게 하여 많은 곳을 탐색할 수 있도록 하기 위함이다.
• 탐색과정에서 T를 점점 감소시킨다. 그럼 후보해 선택 확률이 줄어들어 위쪽으로 올라가게 된다.
• T값에 따라 반복횟수가 결정되므로, 알고리즘 성능에 많은 영향을 준다.
• 사전실험으로 파라미터를 선택한다. 문제마다 T의 상태에 따라 결과가 달라진다.

✔️ 시뮬레이티드 어닐링 알고리즘 과정

a. 초기화 : 실행가능한 초기해 선정

b. 반복단계 : 이동선택규칙을 이용하여 다음해를 선택한다. 
            단, 현재해에 이웃해가 없을 경우 알고리즘을 종료.

c. 온도표 확인 : 현재의 온도 T에서 정해진 반복횟수만큼 알고리즘을 수행.
              온도표에서 다음 T값으로 감소시키고 다시 반복횟수만큼 알고리즘 수행

d. 종료단계 : 온도표에서 T값이 가장 낮아지거나, 더이상 현재해에 인접한 이웃해를 선택할 수 없으면 종료
            지금까지 찾은 해 중 가장 좋은 해를 출력

✔️ 시뮬레이티드 어닐링에서 명확히 해야 할 것

1. 초기해를 어떻게 선택할 것인가?
2. 현재해에 인접한 이웃해 구조를 어떻게 정의할 것인가?
3. 현재해에 인접한 이웃해 중에서 다음의 초기해로 사용할 후보해를 선택하는 이동선택규칙의 랜덤성은 어떻게 할 것인가?
4. 적절한 온도표는 무엇인가?

1️⃣ 시뮬레이티드 어닐링 예제

✔️ 1. 외판원 문제

1. 초기해 랜덤으로 발생시킬 수 있음 1-2-3-4-5-6-7-1

2. 이웃해 구조 하위경로역순 Neighborhood 1-2-6-5-4-3-7-1

3. 인접한 이웃해의 랜덤 선택 하위경로의 처음과 끝을 나타내는 구간을 선택해야 한다. 이 처음과 끝을 랜덤하게 선택

4. 온도표 5개의 T값에 대해 다섯 번의 반복 수행. 현재해의 목적함수 값이 Zc일 때, T1 = 0.2Zc, T2 = 0.5T1, T3 = 0.5T2, T4 = 0.5T3, T5= 0.5T4 로 정의 여기에서 T1 = 0.2Zc는 일반적으로 |Zn - Zc|보다 T1값을 더 크게 하기 위한 식이다. 이렇게 최초 온도값인 T1 값을 크게 줘서 자유도를 높게 한다. 대규모 문제를 풀 때에는 각각의 T에서 더 많은 반복횟수를 사용하고, 온도표에서 T를 천천히 감소시킨다.

Iteration 1

Step1 하위경로역순의 시작 값을 랜덤하게 선택

• 1-2-3-4-5-6-7-1 에서 시작값으로 선택될 수 있는 건 2,3,4,5,6 중 하나. 이 중 동일한 확률로 랜덤하게 하나를 선택한다.
• 여기에서 3이 선택됐다고 가정한다.

Step2 하위경로역순의 끝 값을 랜덤하게 선택

• 시작 값(3) 뒤에 있는 숫자중(4,5,6,7) 하나를 랜덤하게 고른다.
• 여기에서는 4가 선택됐다고 하자.
• 그럼 3-4 사이 역순 경로인 1-2-4-3-5-6-7-1이 후보해가 된다.

Step3 Zn 과 Zc 비교, 다음해 선택

• Zc(현재) : 1-2-3-4-5-6-7-1 경로일 때, Zc = 69
• Zn(다음) : 1-2-4-3-5-6-7-1 경로일 때, Zn = 65
• Zn < Zc 이므로, 목적함수가 더 좋아졌다. 이 후보해는 자동적으로 다음해로 선택된다!

Iteration 2

Step1-2-3 하위경로역순 선택후, Zn 비교

• 1-2-4-3-5-6-7-1 에서 3-5-6 부분이 선택됐다고 했을 때, 후보해는 1-2-4-6-5-3-7-1가 된다.
• 이때 Zn = 64로, Zn(64) < Zc(65)이므로 목적함수가 더 좋아졌다. 이 후보해를 다음해로 선택한다.

Iteration 3 목적함수가 나빠졌을 때

Step1-2-3 하위경로역순 선택후, Zn 비교

• 1-2-4-6-5-3-7-1 에서 3-7 부분이 선택됐다고 했을 때, 후보해는 1-2-4-6-5-7-3-1가 된다.
• 이때 Zn = 66로, Zn(66) > Zc(65)이므로 목적함수가 더 나빠졌다.
• 목적함수가 나빠졌을 때는 확률적으로 그쪽으로 갈 것인지를 정한다.
  • T1 = 13.8
  • Prob{acceptance} = $$e^\frac{Zc-Zn}{T1}=e^\frac{-2}{13.8} = 0.865$$ 의 확률로 이 해를 선택한다.

• 이런식으로 목적함수가 나빠진 경우, 확률적으로 선택하게 된다. T는 목적함수가 나빠지지 않더라도 iteration마다 하나씩 소모하게 된다.

✔️ 2. 비선형계획 문제

아래 비선형계획 문제를 시뮬레이티드 어닐링으로 풀어보자. $$L_1 = 0$$(하한), $$U_1 = 31$$(상한)으로 설정하고 시작한다.

1. 초기해 $$x_j = (L_j+U_j)/2$$ 으로 설정한다. 여기에서는 x = 15.5 이다.

2. 이웃해 구조 실행가능해 모두를 인접한 이웃해로 설정한다.

3. 인접한 이웃해의 랜덤 선택 표준편차와 현재해의 갱신은 아래와 같다. $$\sigma_j = \frac{U_j-L_j}{\sigma}, for \ j = 1,..., n$$ $$reset \ x_j = x_j + N(0, \sigma), for \ j = 1,..., n$$ 만약 실행불가능해가 나오면 이 과정을 반복한다.

4. 온도표 : 5개의 T값에 대해 다섯 번의 반복 수행. 현재해의 목적함수 값이 Zc일 때, T1 = 0.2Zc, T2 = 0.5T1, T3 = 0.5T2, T4 = 0.5T3, T5 = 0.5T4로 정의 여기서 $$\sigma = (U-L)/6$$으로 한 이유는 U와 L의 중간 값으로 xj가 있을 때, 새로운 값은 현재값의 표준편차 3 안에 있기 때문.

Iteration 1

• 초기값인 x = 15.5 부터 시작. Zc = f(15.5) = 3,741,121 이고 T1 = 0.2Zc = 784,224 $$\sigma = (U-L)/6 = (31-0)/6 = 5.167$$

• 이제 N(0, 5.167)에서 랜덤으로 발생시킨다.

  1. [0,1]에서 난수를 생성한다. 예를 들어 0.0735가 생성되었다고 하자.
  2. N(0,1)에서 $$P(X \leq y) = 0.0735$$ 인 $$y=-1.45$$
  3. N(0, 5.167) 에서 $$P(X \leq y) = 0.0735$$ 인 $$y' = 5.167 \times (-1.45) = -7.5$$
  4. x = 15.5 + N(0, 5.167) = 15.5 - 7.5 = 8
     • Zn = f(8) = 3,055,616 < Zc (목적함수 값 나빠짐)
     • prob{acceptance} = $$e^\frac{Zn-Zc}{T} = e^-0.916 =0.40$$ 의 확률로 다음해로 선택한다.

✔️ 3. 수도쿠(Sudoku) 문제

비용 정의 $$\sum_{i=1}^9 (r_i + c_i)$$ 로 정의한다.

• $$r_i$$ 는 행 i에서 겹치는 숫자 쌍의 수
• $$c_i$$ 는 열 i에서 겹치는 숫자 쌍의 수

1. 초기해 각 블록에 숫자가 겹치지 않도록 랜덤하게 생성한다.

2. 이웃해 구조 블록 내에서 고정되지 않은 숫자 2개의 위치를 바꿔서 만들 수 있는 해

3. 인접한 이웃해의 랜덤 선택 블록 내에서 고정되지 않은 숫자 2를 랜덤하게 선택

4. 온도표 각 T값에 대해 빈칸 수만큼 반복을 수행 T1 = 가능해 200개의 비용의 표준편차, $$T_{i+1} = 0.99T_i \ i = 1,2,3,..$$

이 영상에서 파이썬 코드로 구현하는 것도 나온다.Simulated Annealing Explained By Solving Sudoku - Artificial Intelligence 유투브

• [메타 휴리스틱] 1. 타부서치
• [메타 휴리스틱] 2. 시뮬레이티드 어닐링
• [메타 휴리스틱] 3. 유전자 알고리즘

다음 글은 경영과학에서 배우는 내용을 정리함.

0️⃣ 메타휴리스틱이란?

선형계획법, 동적계획법, 정수계획법, 비선형계획법은 최적해를 구하는 알고리즘에 집중한다. 그러나 최적해는 구하는 시간이 오래 걸리는 단점이 있다. 그래서 최적해를 포기하는 대신, 빠른 시간 내에 최적해와 가까운 해를 찾고자 했고, 이러한 접근법을 메타휴리스틱(Metahueristics)이라고 한다.

보통 휴리스틱은 문제의 특성에 맞춰 설계되므로 문제마다 매두 다르다. 이 중 메타휴리스틱은 특정 문제 집단에 범용으로 적용할 수 있는 일반적인 휴리스틱을 말한다.

• 실행 가능한 영역에서 탐색을 강화

• 지역최적해에서 탈출할 수 있는 전략 & 지역 개선 방법 사이의 상호작용 조율

• 자주 사용되는 메타 휴리스틱 방법
  • Genetic Algorithm(GA)
  • Tabu Search(TS)
  • Ant Colony Optimization(ACO)
  • Partical Swarm Optimization(PSO)
  • Simulated Annealing(SA)

1️⃣ 지역탐색방법 👀

지역탐색방법(Local Search Procedure)이란, 현재해 x의 이웃해(neighborhood) 중에서 가장 좋은 해로 이동하는 방법이다.

• 가능해 집합 S가 연속 집합인 경우에 현재해 x의 이웃해 집합을 N(x)라고 하자.

• N(x)는 중심이 x이고 반지름이 $$\epsilon$$ 인 구 $$B_\epsilon(x)$$와 S의 교집합에서 x를 뺸 집합이다.
• 가능해 집합 S가 이산 집합인 경우, 문제마다 N(x)를 정의하는 방법이 다르다.

<< Minimize 문제일 때 >>

a. 초기화 단계 : 초기해 x 선정
b. 반복 단계 : Local Search -> N(x)에서 제일 좋은 해 x'를 선택
c. 종료 단계 : Z(x) <= Z(x') 이면 x를 출력하고 종료. 그렇지 않으면 x=x'로 두고 반복단계 수행

✔️ 🧳 🧭 🧑‍💼 외판원 문제

외판원 문제(Travelling Salesman Problem, TSP)는 외판원이 도시1을 출발해서 다른 도시를 각각 한 번씩만 방문하고 다시 도시1로 돌아오는 경로를 결정하는 문제이다.

목적 경로의 거리나 시간을 최소화하고 싶을 때

응용 택배배송 경로, 회로 기판 구멍 뚫는 문제

가능해 표현 1부터 n까지의 숫자로 이루어진 순열(단, 1이 항상 맨 앞과 끝에 있음)

가능해 수 도시의 개수가 n개일 때, (n-1)!/2 개이다. (모든 경우가 가능해이진 않다. 경로가 없을 수도 있으니까.)

• 아래와 같은 경로가 있다고 하자!

하위경로 역순 Neighborhood N(x) 현재해에서 이웃해는 어떻게 설정할까? 하위경로역순으로 이를 설정한다. 현재해의 방문할 도시에서 일부 구간의 순서를 거꾸로 해서 만들 수 있는 해의 집합을 의미한다.

하위경로역순의 시작점과 끝점을 랜덤하게 선택한다. 만약 1-2-3-4-5-6-7-1 에서 2-3-4-5 가 선택됐다면, 1-5-4-3-2-6-7-1 이렇게 그 부분을 뒤집으면 된다.

아래는 3-4 가 선택되었을 때다.

✔️ 하위경로역순 알고리즘

하위경로역순 Neighborhood를 이용한 Local Search 알고리즘이 어떻게 작동하는지 보자.

a. 초기화 : 초기해는 무작위로 실행가능한 경로를 선정한다.

b. 반복단계
    1. 전체 경로의 역순을 제외하고, 가능한 모든 하위 경로 역순을 수행한다.
    2. 거리가 가장 많이 감소한 경로를 새로운 해로 사용한다. (동률인 경우에는 임의로 선택)

c. 하위 경로 역순으로 더 이상 개선이 없으면 종료하고, 그 때의 해를 출력

위 상황을 보면, Local Search로 해를 찾게 되면 더 좋은 해가 주변에 없으므로 종료하게 된다. 이 해는 지역최적해이고, 전역최적해는 아니다.

2️⃣ 타부서치

Local Search의 단점 : 지역최적해에 수렴해서 전역최적해를 못 찾는다. 이런 문제를 해결하기 위해 타부서치는 후보해가 현재해보다 목적함수보다 나쁘더라도 그 쪽으로 이동하는 것을 허용한다.

대신 같은 지역최적해를 순환할 수 있다는 단점을 막기 위해서 그쪽으로의 해 이동을 일시적으로 제한한다. 이렇게 갈 수 없는 이동을 타부 이동(Tabu move)라고 한다. Tabu는 독일어로 '금기'를 뜻한다. 그리고 이 타부 이동을 기억하는 공간을 T = Tabu list 라고 한다. 최근 탐색한 해를 타부 목록에 기록하는데, 이런 기억공간을 사용하는 것이 인공지능의 기본이 된다. Short Term Memory, Long Term Memory 이런 것이 타부리스트다.

✔️ 타부서치 알고리즘 과정

<<Minimize 문제>>

a. 초기화 : 초기해 x 선정. x* = x, Z* = Z(x)

b. 반복단계 
   1. Local Search : N(x)에서 타부상태가 아닌 제일 좋은 해 x'를 선택
   2. IF x'의 타부 이동이 타부목록 T에 포함되면;
      2-1. IF z(x') < z* 이면(목적함수가 개선되면);
           x'의 타부이동을 타부목록 T에 추가하고 x=x'
   3. Else ; x'의 타부이동을 타부목록 T에 추가하고 x=x'
   4. IF z(x) < z*이면; x* = x, z* = z(x)

c. 종료단계 : 정해진 횟수나 시간이 지나거나 or 특정 조건 만족하면 종료
            => 종료할 때까지 가장 좋은 해 출력

✔️ 타부서치 알고리즘에서 명확히 할 것

1. 어떤 Local Search를 사용할 것인가?
2. 이웃해 구조를 어떻게 정의할 것인가?
3. 타부 목록에 기록하는 타부 이동을 어떤 형태로 표현할 것인가?
   • 위 TSP예시 : [Tabu List] = (2-3), (4-7) 호를 끊을 수 없다.
4. 각 반복마다 어떤 타부 이동을 타부목록에 추가시킬 것인가?
   • 위 TSP예시 : 추가하는 두 호를 다음에 제거하는 호로 사용X
5. 타부목록의 최대 크기는 얼마로 유지할 것인가? 타부목록은 FIFO(First In First Out)으로 유지한다.
6. 종료조건은 어떻게 할 것인가?

3️⃣ 타부서치 예제

✔️ 1. 제약있는 최소걸침나무 예제

최소걸침나무 문제는 Greedy 알고리즘으로 O(nlogn)안에 풀린다.

• 최소걸침나무 문제에 다음과 같은 제약사항이 추가된 문제를 제약이 있는 최소걸침나무 문제라고 한다.
  • 제약1 : 호AD 는 호DE가 추가된 후에만 추가될 수 있다.
  • 제약2 : 호 AB, AD, CD 중 많아야 하나만 추가될 수 있다.
• 제약이 있는 최소걸침나무 문제는 Greedy 알고리즘으로 풀 수 없다.
• 제약을 어길 때 목적함수에 패널티를 부과한다.
  • 제약 1을 어길 때 : 패널티 100
  • 제약 2를 어길 때 : 호 AB, AD, CD 중 두 개가 포함되면 패널티 100, 3개가 포함되면 패널티 200

타부서치

1. Local Search 각 반복마다 타부상태에 있지 않다면, 현재해에서 이웃한 제일 좋은 해를 선택한다.

2. 이웃해 구조 호 하나를 추가시켜서 만들고, 이때 생긴 사이클에 포함된 호 하나를 제거해서 만들 수 있다. -> 이렇게 만든 해를 '이웃걸침나무해'

3. 타부이동의 형태 타부 목록에 있는 호는 사이클에 포함되더라도 제거하는 게 금지

4. 타부 이동의 추가 반복마다 걸침나무에 새롭게 추가되는 호를 타부 목록에 추가 (새롭게 추가된 호를 다음 Step에서 바로 제거하면 안 됨! 그럼 그 전 상태로 돌아가는 거니까! => 타부목록에 추가)

5. 타부 목록의 크기 2개 => 너무 많으면 해가 변경이 안 됨! (= 좋은 해 출력X)

6. 종료조건 3번 연속 현재 최적해를 갱신하지 못하면 종료

초기해는 제약이 없는 최소걸침나무 문제의 최적해를 사용

• 초기해 상태에서 모든 이웃해의 cost를 구한다. 호 DE가 추가되었다 할 때, 이를 Tabu list에 추가한다.

• 마찬가지로 또 가능한 모든 이웃해를 구하는데, AD가 추가되고 DE가 삭제하는 경우는 위의 상황으로 다시 되돌아가는 Tabu Move이므로 고려하지 않는다.

• CD가 추가되고 DE가 삭제되는 상황일 때는 cost를 작성해주는데,

  • 1) 전 상태로 돌아가지 않고,
  • 2) 목적함수가 더 좋아지는 경우, 두 경우중 하나를 만족하면 cost를 작성한다.

• 아래처럼 타부리스트에 있더라도 목적함수값이 개선되는 경우가 있음. 이런 경우에는 타부리스트 무시

✔️ 2. 외판원 예제

Local Search 각 반복마다 타부상태에 있지 않다면, 현재해에서 이웃한 제일 좋은 해를 선택한다.

이웃해 구조 하위경로역순 Neighborhoods

타부이동의 형태 타부 목록에 있는 호는 앞으로 하위경로역순에서 제거 금지

타부이동의 추가 하위경로역순할 때 새롭게 추가된 두 호는 타부목록에도 추가

타부이동의 크기 4 (각 반복마다 2개의 호가 추가되므로 최소걸침나무문제의 타부목록 크기보다 2배)

종료조건 3번 연속 현재 최적해를 갱신하지 못하면 종료

이번 글에서는 최단경로 알고리즘 중 BFS로 최단경로 만드는 방법과 Dijkstra 알고리즘을 이해하고, 수도코드를 살펴보고자 한다. 파이썬 코드는 다음번 글에서!!

• 최단경로란? 두 노드 사이 경로 중 가장 거리가 짧은 경로

• 그래프의 특성에 따라 최단 거리 알고리즘이 다르다
  • 방향이 있는지, 가중치는 있는지, 사이클이 있는지, 음수 엣지가 있는지 등, 그래프의 특성에 따라 사용되는 최단 거리 알고리즘이 다르다.

• 최단 경로 알고리즘

  • BFS

    • 비 가중치 그래프에서만 사용 가능

  • Dijkstra(다익스트라) 알고리즘

    • 가중치 그래프에서도 사용 가능

1️⃣ BFS

그래프 탐색을 하기 위한 BFS를 조금만 변경하면 최단 경로 알고리즘으로 만들 수 있다.

BFS 개념은 여기에서 확인 가능!

BFS에서 각 노드는 그 노드를 방문한 적 있는지 없는지 표시한다. 이를 visited 라는 변수로 표현해줬다. 최단 경로 알고리즘에서는 predecessor라는 변수를 추가해준다. predecessor는 '~이전의 것'을 의미하는데, 특정 노드에 오기 직전의 노드를 의미한다.

아래 그림처럼, B와 C로 오기 직전의 노드는 A이다. 따라서 왼쪽 표처럼 표시해줄 수 있다.

BFS알고리즘에 따라 Predecessor 표가 어떻게 채워지는지 하나씩 살펴보자. BFS는 뒤로 들어가고, 앞으로 나가는 큐를 사용한다.

• 우선 시작 노드인 A를 방문표시하고, predecessor는 None으로 표시한다. 이후에 큐에 넣어준다.

• 큐에서 A를 뽑고, A와 인접한 노드인 B를 큐에 넣어준다. B의 predecessor는 A가 된다. 마찬가지로 C도 큐에 넣고, predecessor는 A로 지정한다.

• 이제 큐에 앞에 있는 B를 뽑고 B와 인접한 노드이며, 아직 방문하지 않은 D를 큐의 뒤쪽으로 넣어준다. predecessor는 B로 표시한다. 또, 큐 앞에 있는 C를 뽑고, 아직 방문하지 않은 E를 큐에 추가, F를 추가, predecessor는 C로 설정한다.

• 큐에서 E, F를 꺼내고, 둘 다 인접한 노드 중 방문하지 않은 노드가 없으므로 BFS가 종료된다.

이제 어떻게 최단경로를 알 수 있을까? A에서 F까지의 최단 경로를 구한다고 해보자. F에서부터 A까지 거꾸로 올라가면 되는데, A의 predecessor는 C, C의 predecessor는 A로, A까지 온다. 즉, 이 순서를 거꾸로 하면, A -> C -> F가 최단 경로이다. 이렇게 거꾸로 찾아가는 것을 Backtracking이라고 한다.

BFS 수도코드 이를 일반화해서 정리하면 다음과 같다.

시작 노드를 방문 표시 후, 큐에 넣는다.
큐에 아무 노드가 없을 떄까지:
    큐 가장 앞 노드를 꺼낸다.
    꺼낸 노드에 인접한 노드들을 모두 보면서:
        처음 방문한 노드면:
            방문한 노드 표시를 해준다.
            predecessor 변수를 큐에서 꺼낸 노드로 설정
            큐에 넣어준다.

Backtracking 수도코드

현재 노드를 경로에 추가한다.
현재 노드의 predecessor로 간다.
predecessor가 없을 때까지 위 단계를 반복

코드잇 BFS 최단 경로용으로 바꾸기

from collections import deque
from subway_graph import *

# 코드를 추가하세요
def bfs(graph, start_node):
    """최단 경로용 bfs 함수"""
    queue = deque()  # 빈 큐 생성

    # 모든 노드를 방문하지 않은 노드로 표시, 모든 predecessor는 None으로 초기화
    for station_node in graph.values():
        station_node.visited = False
        station_node.predecessor = None

    # 시작점 노드를 방문 표시한 후 큐에 넣어준다
    start_node.visited = True
    queue.append(start_node)

    while queue:  # 큐에 노드가 있을 때까지
        current_station = queue.popleft()  # 큐의 가장 앞 데이터를 갖고 온다
        for neighbor in current_station.adjacent_stations:  # 인접한 노드를 돌면서
            if not neighbor.visited:  # 방문하지 않은 노드면
                neighbor.visited = True  # 방문 표시를 하고
                queue.append(neighbor)  # 큐에 넣는다
                neighbor.predecessor = current_station


def back_track(destination_node):
    """최단 경로를 찾기 위한 back tracking 함수"""
    res_str = destination_node.station_name  # 리턴할 결과 문자열
    while destination_node.predecessor != None:
        res_str = destination_node.predecessor.station_name + " " +  res_str
        destination_node = destination_node.predecessor
    return res_str.strip()

stations = create_station_graph("./new_stations.txt")  # stations.txt 파일로 그래프를 만든다

bfs(stations, stations["을지로3가"])  # 지하철 그래프에서 을지로3가역을 시작 노드로 bfs 실행
print(back_track(stations["강동구청"]))  # 을지로3가에서 강동구청역까지 최단 경로 출력

BFS로 찾은 경로가 최단 경로가 되는 이유?

• 방문하는 순서를 보면, 처음으로 방문하는 B와 C는 시작점에서 거리가 1인 노드들이다.
• 이후에 방문하는 노드들 D, E, F는 시작점에서 거리가 2인 노드들이다.
• 마찬가지로 다음으로 방문하는 G와 H는 시작점에서 거리가 3인 노드들이다.
• 이런 순서로 방문하기 때문에, F를 방문하는 순간에 거리가 1인 노드들은 이미 다 방문했고, 거리가 2인 노드들을 방문한다는 것을 안다. F를 처음 방문한 순간이 F를 가장 빠르게 찾은 순간이 된다. 그래서 이때, F까지의 predecessor를 통해 최단경로를 찾을 수 있다.

2️⃣ Dijkstra 알고리즘

가중치 그래프의 최단 경로를 구하기 위한 알고리즘이다. 다익스트라 알고리즘을 사용하기 위해서는 그래프 노드에 아래 3가지 변수를 저장해야 한다.

• distance : 시작점에서 이 노드까지의 거리를 저장한다. 노드까지 오는 여러 경로가 있으므로, 이 값이 업데이트된다. 따라서 특정 노드까지의 '최단 거리 예상치'라고 할 수 있다.
• predecessor : 현재까지의 최단 경로에서 바로 직전의 노드를 저장한다. 위와 마찬가지로 업데이트된다.
• complete : 노드까지의 최단 경로를 찾았다고 표시하는 변수다. 처음에 모두 False로 설정하고, 확실한 최단경로를 찾으면 True로 표시한다.

다익스트라 알고리즘에서는 노드를 하나씩 방문한다. 노드들을 방문하면서 해당 노드의 distance, predecessor 변수들을 업데이트해주는데, 이것을 relaxation이라고 한다. A에서 B로 방문할 때, B의 변수를 업데이트 해주는 걸 '엣지(A, B)를 relax 한다'고 표현한다.

이제 다익스트라 알고리즘을 하나씩 살펴보자. 먼저 predecessor는 None, distance는 무한대로 초기화한다. 아직 방문한 노드들도 없기 때문에 complete도 False로 초기화한다.

• 우선 시작노드인 A의 distance는 0, predecessor는 None으로 둔다. 그리고 A의 엣지들을 보는데, 이때 연결된 엣지의 노드가 complete된 노드면 건너뛴다. 아직 complete된 노드가 없으므로, 엣지(A, B)와 (A, C)를 다 relax해주면 된다. B의 distance는 4, predecessor는 A로 설정한다. C의 distance를 1로 바꾸어주고, predecessor는 A로 설정한다. 이제 A의 complete 변수를 True로 설정한다.

• 다음은 complete되지 않은 노드 중 distance가 가장 작은 노드를 고른다. distance가 1인 C를 고르면 된다. 위에서 했던 것과 같이 C의 엣지를 모두 relax해준다. (C, B)와 (C, D)를 relax해준다. 이제 C를 complete표시해준다.

• 다음으로 complete되지 않고 distance가 가장 작은 D 노드에 대해 진행한다.

• 그 다음은 B노드,

• 마지막으로 E노드까지 돌면 끝이다.

• 이렇게 마지막까지 돌면, 각 노드의 distance와 predecessor가 확정된다. 최단거리를 알고 싶으면, distance를 보면되고, 경로를 알고 싶으면 predecessor를 써서 Backtracking 을 사용하면 된다.

Dijkstra 알고리즘 수도코드 이를 일반화해서 정리하면 다음과 같다.

시작점의 distance를 0으로, predecessor를 None으로
모든 노드가 complete 일 때까지:
    complete하지 않은 노드 중 distance가 가장 작은 노드 선택
    이 노드에 인접한 노드 중 complete하지 않은 노드를 돌면서 :
        각 엣지를 relax한다.
    현재 노드를 complete처리한다.

MST(Minimum Spanning Tree)는 최소신장트리 또는 최소 비용 걸침 나무라고 하는데, 그래프의 신장트리들 중 간선의 합이 최소인 신장트리를 의미한다.

1. 입력조건 '무향 연결 그래프'여야 한다.

• 무향 : 방향이 없는 경우
• 연결 : 그래프가 나뉘어 있지 않음. 모든 정점 간에 경로가 존재함.

2. 신장트리 = 걸침나무

• 트리
  • 싸이클이 없는 연결 그래프를 말한다.
  • n개의 정점(node)을 가진 트리는 항상 n-1개의 간선(edge)을 갖는다.
• 신장트리(걸침나무, Spanning Tree)
  • 그래프의 정점들과 간선들로만 구성된 트리이다. 아래처럼 여러 개의 신장트리를 만들 수 있고, 그 중 노드를 잇는 가중치를 가장 작게 만드는 신장트리를 Minimum Spanning Tree라고 한다.

1️⃣ Prim Algorithm

✔️ Prim 수도코드와 이해

Prim의 수도코드 먼저 Prim 알고리즘의 수도코드를 보자.

Prim(G, r)
{
  S <- {}
  정점 r을 방문했다고 표시하고 집합 S에 포함시킨다.
  while (S != V){
      S에서 V-S를 연결하는 간선들 중 최소길이의 간선(x, y)를 찾는다;
    정점 y를 방문했다고 표시하고, 집합 S에 포함시킨다;
    }
}

Prim의 이해

• 위 수도코드와 아래 연결그래프를 보며 이해해보자.
  • G는 그래프, r은 시작노드 A, V는 전체 노드이다.
  • S = {A}이고, V-S는 아직 방문하지 않은 노드들이다. S에서 V-S를 연결하는 간선은 A-B, A-D, A-C이고 그 중 최소길이인 A-B를 찾았다.
  • B를 방문집합 S에 포함시킨다. S = {A, B}
  • 또 S에서 V-S를 연결하는 간선인 A-C, A-D, B-E 중 최소길이인 A-D를 찾았다. D를 방문집합 S에 포함시킨다. S = {A, B, D}
  • S == V가 될때까지 반복

Prim의 특징

• Rrim 알고리즘은 그리디(greedy) 알고리즘의 일종이다.
• 그리디 알고리즘은 순간순간의 최적만 찾기 때문에 전역 최적해를 보장하지 않는다. 그러나 그리디 알고리즘 중 Prim은 전역최적해를 보장하는 드문 예시이다.
• 수행시간 : $$O(|E|log|V|)$$이다. log인 이유는 최소간선을 찾을 때 정렬을 쓰는데 이때 heap정렬을 쓰면 log|V|가 된다.

✔️ Prim 구현(python)

입력 위 사진과 동일한 가중치가 존재하는 그래프는 아래처럼 dictionary 안에 dictionary 형태로 표현할 수 있다.

mywgraph = { "A" : {"B":8,  "C":11, "D":9},
      "B" : {"A":11, "E":10},
      "C" : {"A":11, "D":13, "F":8},
      "D" : {"A":9,  "C":13, "E":5, "G":12},
      "E" : {"B":10, "D":5},
      "F" : {"C":8,  "G":7},
      "G" : {"D":12, "F":7}
      }

Prim 구현(Python)

def Prim(G, r) :
  conn = [] # 간선이 추가된 순서
  S = [r] # 방문한 노드 리스트
  while len(S) != len(G):
    xmin, ymin, min_value = find_min_edge(S, G) # 최소 간선 찾기
    S.append(ymin) 
    conn.append([xmin, ymin, min_value])
  return conn

def find_min_edge(S,G): # 최소 간선 찾기
  edges = []
  for x in S:
    for y in G[x]:
      if y not in S:
        edges.append([x, y, G[x][y]])
  xmin, ymin, min_value = min(edges, key = lambda x:x[-1])

  return xmin, ymin, min_value

Prim(mywgraph, "A")
"""
[['A', 'B', 8],
 ['A', 'D', 9],
 ['D', 'E', 5],
 ['A', 'C', 11],
 ['C', 'F', 8],
 ['F', 'G', 7]]
 """

2️⃣ Kruskal Algorithm

✔️ Kruskal 수도코드와 이해

Kruskal의 수도코드

Kruskal(G)
{
  T <- {}; // T는 신장트리
  단 하나의 정점만으로 이루어진 n개의 집합을 S로 초기화 한다;
  모든 간선을 가중치가 작은 순으로 정렬한다;
  while (T의 간선수 < n-1){
    최소비용 간선 (u, v)를 제거한다;
    정점 u와 정점 v가 서로 다른 집합에 속하면{
      두 집합을 하나로 합친다;
      T <- T + {(u, v)};}
  }
}

Kruskal의 이해

• Kruskal 작동예시
• 계층적 클러스터링과 방식이 유사하다. 최소간선을 찾아 같은 집합으로 묶고 그 다음 최소간선을 묶고..를 반복하는데 이때 사이클이 생기면 안되므로 서로 다른 집합에 속할 때만 묶어준다.

✔️ Kruskal 구현(python)

입력 위와 동일

Kruskal 구현(python)

def Kruskal(G):
  T = []
  S = [set(x) for x in G.keys()]
  print("S=", S)
  E = sort_edges(G)
  while len(T) < len(G)-1:
    edge, value = E.popitem() # 작은 맨 뒤 삭제
    u, v = list(edge)
    if any(u in subset and v in subset for subset in S) == False: # 정점 u와 v가 서로 다른 집합에 속하면
      # u가 있는 집합과 v가 있는 집합 합치기
      merged_set = set()
      for s in S:
          if u in s:
              merged_set.update(s)
          elif v in s:
              merged_set.update(s)

      S = [merged_set] + [s for s in S if u not in s and v not in s]

      print("S=", S)
      T.append([set(edge), value])
  return T

def sort_edges(G): 
  E = {}
  for k1,v1 in G.items():
    for k2,v2 in v1.items():
      E[frozenset([k1,k2])] = v2
  E = {k: v for k, v in sorted(E.items(), key=lambda item: item[1], reverse=True)}
  return E # {frozenset({'C', 'D'}): 13, frozenset({'D', 'G'}): 12, frozenset({'B', 'A'}): 11, frozenset({'C', 'A'}): 11, frozenset({'E', 'B'}): 10, frozenset({'A', 'D'}): 9, frozenset({'F', 'C'}): 8, frozenset({'F', 'G'}): 7, frozenset({'E', 'D'}): 5}


print(Kruskal(mywgraph))
"""
S= [{'A'}, {'B'}, {'C'}, {'D'}, {'E'}, {'F'}, {'G'}]
S= [{'E', 'D'}, {'A'}, {'B'}, {'C'}, {'F'}, {'G'}]
S= [{'F', 'G'}, {'E', 'D'}, {'A'}, {'B'}, {'C'}]
S= [{'F', 'C', 'G'}, {'E', 'D'}, {'A'}, {'B'}]
S= [{'E', 'A', 'D'}, {'F', 'C', 'G'}, {'B'}]
S= [{'E', 'B', 'A', 'D'}, {'F', 'C', 'G'}]
S= [{'E', 'C', 'A', 'F', 'B', 'D', 'G'}]
[[{'E', 'D'}, 5], [{'F', 'G'}, 7], [{'F', 'C'}, 8], [{'A', 'D'}, 9], [{'E', 'B'}, 10], [{'C', 'A'}, 11]]
"""

frozenset을 쓰는 이유? 아래처럼 key는 간선, value는 가중치로 표현하는 dictionary를 만들고 싶다.

di = {{'D', 'E'} = 2,
      {'D', 'A'} = 3}

근데 아래처럼 set을 key로 쓰게 되면 오류가 난다.

di = {}
di[{'D', 'E'}] = 2
di
# TypeError: unhashable type: 'set'

그래서 frozenset을 key로 쓰는 것이다.

di = {}
di[frozenset(['D', 'E'])] = 2
di # {frozenset({'D', 'E'}): 2}

✔️ 그래프의 종류와 표현

그래프는 가중치가 있는지, 방향이 있는지에 따라 다르게 표현한다.

• 가중치 여부에 따라
  • 가충치 그래프
  • 가중치가 없는 그래프
• 방향 여부에 따라
  • 유향 그래프
  • 무향 그래프

각 그래프를 '인접행렬'로는 어떻게 표현하는지 보자

• 무향 그래프
  • 인접행렬은 대칭행렬

• 가중치가 있는 무향 그래프
  • 인접행렬은 대칭행렬, 가중치가 표현되어 있다.

• 유향 그래프
  • 인접행렬은 비대칭행렬
  • 세로가 From, 가로가 To

• 가중치가 있는 유향 그래프
  • 인접행렬은 비대칭행렬, 가중치가 표현

✔️ 인접행렬, 인접리스트

그래프를 표현하는 데에는 두 가지 방법이 있다. 위처럼 행렬로 표현할 수도 있고 인접리스트로도 표현할 수 있다.

인접행렬(Adjacency Matrix)

노드의 개수가 N 일때, NxN 행렬로 표현한다.

matrix = [[0, 1, 1],
          [1, 0, 0],
          [1, 0, 1]]

if ((i,j) exists)
    A[i][j] = W_ij
else if (i==j) A[i][j] = 0
else A[i][j] = infinity # i,j 간 에지가 존재하지 않는 경우

인접리스트(Adjacency List)

• 각 정점에 인접한 정점들을 연결 리스트로 표현한다. 정점이 n개인 그래프라면 n개의 연결리스트로 구성한다. 각 연결리스트마다 포인터 변수가 리스트의 처음 노드를 가리키며 연결리스트가 없는 경우, 즉 차수가 0인 경우 포인터 변수의 값은 null이 된다.
  • 

    # 1번 예시
    ad_list = {0: {1,2}, 
      1: {0}, 
             2: {0,1}, 
             3: {0}}
    # value를 set이 아니라 [] 리스트로 표현해도 된다.

1️⃣ DFS

DFS와 BFS의 개념은 여기에서 확인할 수 있다.

✔️ 인접리스트에서의 DFS

위 트리를 표현하는 인접리스트는 아래와 같다. 입력

mytree = { "v" : {"u", "w", "x"},
            "u" : {"q", "t"},
            "w" : {},
            "x" : {},
            "q" : {"r", "s"},
            "t" : {},
            "r" : {},
            "s" : {}
          }

# 인접리스트 입력방식에서 DFS구현하기
def DFS(G):               # 깊이우선탐색 알고리즘
  visited = []
  for v in G.keys():
    if v not in visited:
      aDFS(G, v, visited)
  return visited

def aDFS(G, v, visited):  # 깊이우선탐색 알고리즘
  visited.append(v)
  for x in G[v]:
    if x not in visited:
      aDFS(G, x, visited)

print("DFS:", DFS(mytree)) # DFS: ['v', 'w', 'u', 'q', 's', 'r', 't', 'x'] (value를 set으로 설정해서 이 순서는 다르게 나올 수 있음.)

✔️ 인접행렬에서의 DFS

인접행렬은 아래럼 만들 수 있다. 입력

N1 = {0:'q', 1:'r', 2:'s', 3:'t', 4:'u', 5:'v', 6:'w', 7:'x'}
A1 = [[0,1,1,0,0,0,0,0],
      [0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0],
      [1,0,0,1,0,0,0,0],
      [0,0,0,0,1,0,1,1],
      [0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0]]
G1 = (N1, A1)

# 인접행렬 입력방식에서 DFS구현하기
def DFS_tbl(G, v):               # 깊이우선탐색 알고리즘 (v부터 시작하게 세팅)
  visited = []
  stack = [v]

  while stack: # stack이 비어있지 않으면,
    node = stack.pop()
    if node not in visited:
      aDFS_tbl(G, node, visited)
  return visited

def aDFS_tbl(G, v, visited):  # 깊이우선탐색 알고리즘
  visited.append(v)
  for i in range(len(G[1])):
    if i not in visited and G[1][v][i] == 1:
      aDFS_tbl(G, i, visited)

def idx_to_key(list, N):
  keys =[]
  for i in list:
    keys.append(N[i])
  return keys

idxs = DFS_tbl(G1, 5)
print(idxs, idx_to_key(idxs, N1)) # [5, 4, 0, 1, 2, 3, 6, 7] ['v', 'u', 'q', 'r', 's', 't', 'w', 'x']

2️⃣ BFS

✔️ 인접리스트에서의 BFS

# 인접리스트 입력방식에서 BFS구현하기 Ver.1
def BFS(G, s):
  visited = []
  queue = [s]

  while queue: # 큐가 비어있지 않으면,
    node = queue.pop(0)
    if node not in visited:
      visited.append(node)
      queue.extend(G[node])
  return visited


print(BFS(mytree, "v")) # ['v', 'w', 'u', 'x', 'q', 't', 's', 'r']

# 인접리스트 입력방식에서 BFS구현하기 Ver.2
import queue

def BFS(G, s):
  visited = [s]
  q = queue.Queue()
  q.put(s)
  while not q.empty(): # 큐가 비어있지 않으면,
    node = q.get()
    for v in G[node]:
      if v not in visited:
       visited.append(v)
       q.put(v)
  return visited


print(BFS(mytree, "v"))

✔️ 인접행렬에서의 BFS

from collections import deque
def BFS_tbl(G, s):
  visited = []                    # s에 방문 표시
  queue = [s]
  while queue:
    node = queue.pop(0)
    if node not in visited:
      visited.append(node)
      for i in range(len(G[1])):
        if G[1][node][i] == 1 and G[1][node][i] not in visited:
          queue.append(i)
  return visited

def idx_to_key(list, N):
  keys =[]
  for i in list:
    keys.append(N[i])
  return keys

idxs = BFS_tbl(G1, 5)
print(idxs, idx_to_key(idxs, N1)) # [5, 4, 6, 7, 0, 3, 1, 2] ['v', 'u', 'w', 'x', 'q', 't', 'r', 's']

Reference

• [파이썬(python) 자료구조] 그래프 (Graph)
• 파이썬 인접행렬과 인접리스트 사용하기
• [Python] 그래프 (인접 행렬, 인접 리스트) + DFS/BFS를 배우기 앞서 알아야 할 개념들 (탐색 알고리즘, 자료구조)
• dfs와 bfs를 구현하는 여러가지 방법 in python

1️⃣ 조약돌 문제

1) 재귀적 해법

# 1. weight 계산하기
import copy

A = [[6,-8,11], [7,10,12],[12,14,7],[-5, 9, 4],[5, 7, 8],[3, 13, -2],[11, 8, 9],[3, 5, 4]]
A2 = [[6,-8,11], [7,10,12],[12,14,7],[-5, 9, 4],[5, 7, 8],[3, 13, -2],[11, 8, 9],[3, 5, 4],
      [6,-8,11], [7,10,12],[12,14,7],[-5, 9, 4],[5, 7, 8],[3, 13, -2],[11, 8, 9],[3, 5, 4]]

def append_weight(A):
#   w = A
#   w = A.copy()
  w = copy.deepcopy(A)
  for i in range(len(w)):
    w[i].append(w[i][0] + w[i][2])
  return w

w = append_weight(A)

def pebbleSum():
  n = len(w)
  m = [pebble(n-1,0), pebble(n-1,1), pebble(n-1,2), pebble(n-1,3)]
  return max(m)

def pebble(i, p):
  """i 번째 열에서 패턴 p(0,1,2,3)번을 선택하는 경우"""
  if i == 0:
    return w[0][p]
  else:
    M = -100
    for q in range(4):
      if compatible(p, q) == True:
        tmp = pebble(i-1, q)
        if tmp > M:
          M = tmp
  return M + w[i][p]

def compatible(p,q):
  if (p == 3 and q == 0) or (p == 3 and q == 2) or (p==q):
    return False
  return True

start_time = time.time()
w = append_weight(A)
print(pebbleSum())
print("\n %.4f sec." % (time.time() - start_time))

2) DP : Bottom-Up(Tabulation) 방식

def pebbleSum_DP_bottomup(w):
  cache = [[None for j in range(4)] for i in range(len(A))]
  for i in range(len(A)):
    if i == 0:
      cache[0] = w[0]
    else:
      cache[i][3] = cache[i-1][1] + w[i][3]
      for p in range(3):
        cache[i][p] = max([cache[i-1][x] for x in range(4) if x != p]) + w[i][p]
  return max([cache[-1][x] for x in range(4)])

start_time = time.time()
w = append_weight(A)
# w = append_weight(A2)
print(pebbleSum_DP_bottomup(w))
print("\n %.4f sec." % (time.time() - start_time))

3) DP : Top-Down(Memoization) 방식

def pebble_memo(w, i, p, cache):
  if i == 0:
    cache[0] = w[0]

  if cache[i][p] != None:
    return cache[i][p]

  else:
    if p == 3:
      M = pebble_memo(w, i-1, 1, cache)
    else:
      M = max([pebble_memo(w, i-1, j, cache) for j in range(4) if j != p])
    cache[i][p] = M + w[i][p]
    return M + w[i][p]


def pebbleSum_DP_topdown():
  cache = [[None for j in range(4)] for i in range(len(A))]
  n = len(w)
  m = [pebble_memo(w, n-1, i, cache) for i in range(4)]
  return max(m)


start_time = time.time()
w = append_weight(A)
# w = append_weight(A2)
print(pebbleSum_DP_topdown())
print("\n %.4f sec." % (time.time() - start_time))

2️⃣ 최소 행렬경로 문제

1) 재귀적 해법

# 예시로 사용
m1 = [[6,7,12,5], [5,3,11,18], [7,17,3,3], [8,10,14,9]] 
m2 = [[6,7], [5,3], [7,17]]
m3 = [[6,7,12,5], [5,3,11,18], [7,17,3,3], [8,10,14,9],
      [6,7,12,5], [5,3,11,18], [7,17,3,3], [8,10,14,9]]

def matrixPath(i, j):
  if (i==0)&(j==0): return m[0][0]
  elif i == 0: return matrixPath(0, j-1) + m[i][j]
  elif j == 0: return matrixPath(i-1, 0) + m[i][j]
  else: return min(matrixPath(i-1, j), matrixPath(i, j-1)) + m[i][j]

m = m3     # m1, m2, m3로 바꿔가면서 테스트해볼 수 있음
matrixPath(3,3)

2) DP : Bottom-Up(Tabulation) 방식

def matrixPath_DP_BU(i, j):
  n1 = len(m)
  n2 = len(m[0])
  c = copy.deepcopy(m)
  for i in range(1, n1):
    c[i][0] = m[i][0] + c[i-1][0]
  for j in range(1, n2):
    c[0][j] = m[0][j] + c[0][j-1]
  for i in range(1, n1):
    for j in range(1, n2):
      c[i][j] = m[i][j] + min(c[i-1][j], c[i][j-1])
  return c[n1-1][n2-1]

m = m1
print(len(m)-1, len(m[0])-1)
matrixPath_DP_BU(len(m)-1, len(m[0])-1)

3) DP : Top-Down(Memoization) 방식

import copy

m1 = [[6,7,12,5], [5,3,11,18], [7,17,3,3], [8,10,14,9]]   # 교재의 예제
m2 = [[6,7], [5,3], [7,17]]
m3 = [[6,7,12,5], [5,3,11,18], [7,17,3,3], [8,10,14,9],
      [6,7,12,5], [5,3,11,18], [7,17,3,3], [8,10,14,9]]

m = m1     # m1, m2, m3로 바꿔가면서 테스트해볼 수 있음
n1 = len(m)
n2 = len(m[0])
c = [[None]*n2 for x in range(n1)]

def matrixPath_DP_TD(i,j):
  # Top-Down 방식의 DP로 구현하시오.
  # (0,0)인 경우,
  if (i==0)&(j==0):
    c[0][0] = m[0][0]
    return c[0][0]

  # 0행인 경우,
  if (i==0)&(j!=0):
    c[i][j] = matrixPath_DP_TD(0, j-1) + m[i][j]
    return c[i][j]

  # 0열인 경우,
  if (i!=0)&(j==0):
    c[i][j] = matrixPath_DP_TD(i-1, 0) + m[i][j]
    return c[i][j]

  # 이미 계산한 적 있으면 반환
  if c[i][j] != None:
    return c[i][j]

  # 계산한 적 없는 경우,
  c[i][j] = min(matrixPath_DP_TD(i-1, j), matrixPath_DP_TD(i, j-1)) + m[i][j]
  return c[i][j]

print(len(m)-1, len(m[0])-1)
matrixPath_DP_TD(len(m)-1, len(m[0])-1)

3️⃣ 연쇄행렬 최소곱셈 순서 문제

행렬에서 곱셈연산의 수는 행렬의 크기의 곱으로 나타낼 수 있다. 예를 들어 A(2x3), B(3x4)크기의 행렬끼리의 곱인 AxB을 하면, 2x3x4번의 곱셈이 필요하다.

문제는 세 개 이상의 행렬의 곱에서는 어떤 행렬끼리의 곱을 먼저 수행하느냐에 따라 곱셈 연산 수가 많이 달라진다는 것이다.

예를 들어 아래 행렬을 보자. 괄호 안은 행렬의 크기를 의미한다. A행렬 : (10x100) B행렬 : (100x5) C행렬 : (5x50)

• (AB)C 로 수행하는 경우

  • AB 행렬곱에는 10x100x5 번의 곱셈 필요 -> 10x5 행렬 생성
  • 총 10x100x5 + 10x5x50 = 7500 번의 곱셈 필요

• A(BC) 로 수행하는 경우

  • BC 행렬곱에는 100x5x50 번의 곱셈 필요 -> 100x50 행렬 생성
  • 총 100x5x50 + 10x100x50 = 75000 번의 곱셈 필요

• 따라서 이 경우에는 (AB)C로 계산하는 게 효율적이다. 이렇듯, 행렬의 곱의 순서에 따라 효율성이 달라지니, 어떻게 계산하는 게 더 좋은지 알아볼 필요가 있다.

풀이

행렬이 A, B, C, D 로 4개가 있을 땐, 총 $$4$$번의 경우의 수를 살펴봐야 한다.

1) ((AB)C)D 2) A(B(CD)) 3) (AB)(CD) 4) (A(BC)D)

n개의 행렬이 있을 때는 몇 번의 경우의 수를 살펴봐야할까?

• 아래처럼 n개의 행렬이 있을 때 마지막으로 행렬곱이 수행되는 상황에서는 n-1개의 경우의 수가 나온다.

• 두 개씩 묶인 2번과 달리 1번과 3번은 또 괄호 안의 경우에 대해 최소로 곱셈연산이 수행되는 것을 찾아야 한다.

• 이렇게 작은 문제로 나누어서 풀 수 있기 때문에 Divide and Conquer로 풀 수 있다. 분할 정복 알고리즘은 보통 재귀 함수(recursive function)를 통해 자연스럽게 구현된다.

  • 분할 정복에 대한 내용은 여기에서 확인 가능

• 재귀적 관계를 알아보자 $$A_1A_2A_3 ...A_n$$의 행렬곱의 최소 곱셈 연산을 구하는 경우, $$M[i][j]$$는 $$A_iA_{i+1}..A_j$$에서의 최소 곱셈 연산이고 $$A_k$$ 의 차원을 $$p_{k-1}\times p_k$$ 라고 할 때, 아래처럼 재귀관계를 작성할 수 있다.

  • $$M[i][j] = min(M[i][k] + M[k+1][j] + p_{i-1}p_{k}p_{j}), (i < j )$$
  • $$M[i][j] = 0 , (i = j)$$

1) 재귀적 해법

위 식을 이해했다면 이를 Divide and Conquer 방식인 재귀로 풀어보자.

# 예시로 사용
p1 = [10, 100, 5, 50]   # 10x100, 100x5, 5x50 행렬을 곱하는 경우를 의미
p2 = [10, 100, 5]       # 10x100, 100x5 행렬을 곱하는 경우를 의미
p3 = [10, 100, 5, 50, 10, 100, 5, 50, 10, 100, 5, 50, 10, 100, 5, 50]

import math
def rMatrixChain(i, j):
  if i == j:
    return 0
  minimum = math.inf
  for k in range(i, j):
    q = rMatrixChain(i, k) + rMatrixChain(k+1, j) + p[i-1]*p[k]*p[j]
    if q < minimum:
      minimum = q
  return minimum

import time # 각 방식의 시간을 체크하기 위함
start_time = time.time()
p = p3 # p1, p2, p3로 바꿔가며 테스트
print(rMatrixChain(1, len(p)-1))
print("%.5f sec" %(time.time()-start_time))

2) DP : Bottom-Up(Tabulation) 방식

• 테이블은 아래처럼 채워나가면 된다.

  def matrixChain_DP_BU():
  n = len(p) - 1 # 행렬 개수
  M = [[0]*n for x in range(n)]
  for r in range(1, n):
    for i in range(0, n-r):
      j = i+r
      M[i][j] = min([M[i][k] + M[k+1][j] + p[i-1]*p[k]*p[j] for k in range(i, j)])
  return M[0][-1]
  

p = p2 matrixChain_DP_BU()

### 3) DP : Top-Down(Memoization) 방식
```py
import time
p = p3
n = len(p)-1    # n: 행렬 개수
m = [[None]*(n) for x in range(n)]  # m[i][j]는 Ai~Aj를 곱하는 최소 비용

def matrixChain_DP_TD(i, j):
  if i==j:
    m[i][j] = 0

  # 이미 계산한 적 있으면 반환
  if m[i][j] != None:
    return m[i][j]

  # 계산한 적 없는 경우,
  m[i][j] = min(matrixChain_DP_TD(i,k) + matrixChain_DP_TD(k+1,j) + p[i-1]*p[k]*p[j]for k in range(i, j))
  return m[i][j]


start_time = time.time()
print(matrixChain_DP_TD(0, n-1))
print("\n %.5f sec." % (time.time() - start_time)) # 재귀적 호출에 비하여 시간이 1/1000 수준으로 단축됨

4️⃣ LCS(Longest Common Subsequence) 문제

두 문자열에 공통적으로 들어있는 common subsequence중 가장 긴 것의 길이를 구하는 문제이다. input X = "abcbdab", Y = "bdcaba"

output 4

설명 "abcbdab"와 "bdcaba"에서 "bcba"가 공통적으로 최장 공통부분이 되어 결과값은 이 공통부분의 길이인 4이다.

1) 재귀적 해법

X = "abcbdab"
Y = "bdcaba"

def rLCS(m,n):  # m과 n은 비교할 개수
  if (m==0)|(n==0):
    return 0
  elif X[m-1] == Y[n-1]:
    return rLCS(m-1, n-1) + 1
  return max(rLCS(m-1,n), rLCS(m,n-1))

rLCS(len(X), len(Y))

2) DP : Bottom-Up(Tabulation) 방식

def LCS_DP_BU(m,n):  # m과 n은 비교할 개수
  C = [[0]*(n+1) for x in range(m+1)]

  for i in range(1, m+1):
    for j in range(1, n+1):
      if X[i-1] == Y[j-1]:
        C[i][j] = C[i-1][j-1] + 1
      else:
        C[i][j] = max(C[i-1][j], C[i][j-1])
  return C[m][n]

X = "abcbdab" 
Y = "bdcaba"
LCS_DP_BU(len(X), len(Y))

C는 아래와 같은 Table이 나옴

[[0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 1, 1],
 [0, 1, 1, 1, 1, 2, 2],
 [0, 1, 1, 2, 2, 2, 2],
 [0, 1, 1, 2, 2, 3, 3],
 [0, 1, 2, 2, 2, 3, 3],
 [0, 1, 2, 2, 3, 3, 4],
 [0, 1, 2, 2, 3, 4, 4]]

3) DP : Top-Down(Memoization) 방식

X = "abcbdab"
Y = "bdcaba"

# Top-Down 방식의 DP로 구현하시오.
m = len(X) #7
n = len(Y) #6

C = [[None]*(n+1) for x in range(m+1)]

def LCS2_DP_TD(i,j):  # m과 n은 비교할 개수
  if i == 0 or j == 0:
    return 0

  # 이미 계산한 적 있으면 반환
  if C[i][j] != None:
    return C[i][j]

  if X[i-1] == Y[j-1]:
    C[i][j] = LCS2_DP_TD(i-1, j-1) + 1
    return C[i][j]

  # 같지 않으면
  C[i][j] = max(LCS2_DP_TD(i-1, j), LCS2_DP_TD(i, j-1))
  return C[i][j]

LCS2_DP_TD(len(X), len(Y))

[PGS] 코딩테스트 연습 > 동적계획법(Dynamic Programming) > 정수 삼각형

문제설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예시

파이썬 풀이

아래부터 최대값을 찾아 저장했습니다.

def solution(triangle):
    mx_list = [triangle[-1]]
    for hier in triangle[len(triangle)-2::-1]:
        hier_mx = [max(mx_list[-1][i], mx_list[-1][i+1]) + hier[i] for i in range(len(hier))]
        mx_list.append(hier_mx)
    return mx_list[-1][0]

📕 B-tree

• B-tree는 언제 사용할까? 메모리 접근에서 이 B트리를 사용한다. 메모리 접근시, 하나의 Depth를 내려가는 데에 디스크 블록을 새롭게 찾아야 하기 때문에 Disk Access 시간이 많이 소요된다. 여기서 '블록(페이지)'은 디스크의 접근 단위이다.

" 디스크로부터 데이터를 읽거나 기록할 때 이를 포함하는 디스크 블록 전체를 메모리로 읽어오고 다시 블록 전체를 디스크에 기록하는 방식으로 디스크 I/O "

디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다고 한다. 이때 검색트리가 디스크에 저장되어 있다면 트리의 높이(또는 깊이, Depth)를 최소화 하는 것이 유리하다. 트리에서 같은 level에서 key를 찾는 시간보다 Depth를 내려가는 데에 시간이 더 많이 소요되기 때문이다.

• 다진 검색트리란? 오른쪽, 왼쪽 자식 2가지로 뻗어나가는 이진트리와 다르게 여러 갈래로 나뉘는 트리를 다진검색트리라고 한다. key를 기준으로 뻗어나간다.

• B-Tree B트리는 균형잡힌(Balanced Tree) 다진검색트리다. 그래서 최악의 경우인 한 쪽으로만 노드가 늘어진 경우를 보완하여 디스크 접근 횟수를 줄일 수 있다.

• B-Tree의 성질 B트리는 다음 성질을 만족한다.

  1. 루트를 제외한 모든 노드는 $$\lfloor k/2 \rfloor$$ ~ $$k$$ 개의 키를 가진다.

• 2. 모든 리프노드는 같은 깊이를 가진다(Balanced)*

  • 1번 특성 예시

📗 B-Tree에서의 삽입

B-Tree에서의 삽입을 수도코드와 그림으로 알아보자. 삽입하는 함수 BTreeInsert는 트리의 루트노드인 t와 삽입하고자 하는 키 x를 파라미터로 받는다.

BTreeInsert(t, x)
{
    x를 삽입할 리프노드 r을 찾는다;
    x를 r에 삽입한다;
    if (r에 오버플로우 발생) then clearOverflow(r);
 }

• k=4라고 할 때, 한 노드에서는 2~4개의 키를 가질 수 있다. 이때 key가 하나 더 들어와서 오버플로우가 발생한 경우, 처리를 해줘야 한다.

오버플로우가 발생할 때 처리하는 함수는 clearOverflow(r) 이다.

clearOverflow(r)
{
    if (r의 형제노드 중 여유가 있는 노드가 있음) then {r의 남는 키를 넘긴다};
    else {
            r을 둘로 분할하고 가운데 키를 부모노드로 넘긴다;
            if (부모노드 p에 오버플로우 발생) then clearOverflow(p);
         }
 }

• 오버플로우가 발생하는 경우 두 경우로 나눠서 처리한다. 자세한 방법은 아래 그림에서 확인할 수 있다.
  1. 형제노드에 여유가 있을 때 : 형제노드로 옮긴다.
  2. 형제노드에 여유가 없을 때 : 가운데 키를 부모노드로 넘기고 노드를 분리한다. (부모노드에서도 오버플로우가 발생하면 재귀적으로 clearOverflow 호출)

📘 B-Tree의 삭제연산

삭제연산을 수행하는 BTreeDelete는 트리의 루트노드 t와 삭제하고자 하는 키 x, 그리고 x를 갖고 있는 노드 v를 파라미터로 받는다.

BTreeDelete(t, x, v)
{
    if(v가 리프노드가 아님) then {
        x의 직후원소 y를 가진 리프노드를 찾는다;
        x와 y를 맞바꾼다;
    }
    리프노드에서 x를 제거하고 이 리프노드를 r이라고 한다;
    if(r에서 언더플로우 발생) then clearUnderflow(r);
}

• 그림으로도 삭제연산을 살펴보자.

근데 이때 key의 개수가 적어지는 'Underflow' 가 발생할 수 있다. 이때 clearUnderflow 함수를 호출한다.

clearUnderflow(r)
{
    if(r의 형제노드 중 키를 하나 내놓을 수 있는 여분을 가진 노드가 있음) 
        then {r이 키를 넘겨받는다;}
        else{
                r의 형제노드와 r을 합병한다;
                if(부모노드 p에 언더플로우 발생) then clearUnderflow(p);
        }
}

• 경우1) r의 형제노드 중 키를 하나 내놓을 수 있는 여분을 가진 노드가 있는 경우

  • 아래처럼 회전하듯 처리해준다.

• 경우2) 형제노드 중 키를 넘겨받을 수 없을 때

  • 형제노드와 합병한다. 이때 부모노드 p와 함꼐 병합한다. 부모노드를 가져왔기 때문에 위에서 또 언더플로우가 발생할 수 있고, 이러면 재귀적으로 다시 처리한다.

중요한 건 삭제와 삽입연산에서 루트노드는 키의 개수가 $$\lfloor k/2 \rfloor$$ ~ $$k$$개를 지키지 않아도 된다는 것이다!

(추후 코드 구현해서 추가할 예정입니다.)

📕 불균형 이진트리의 문제점

기존 Binary Search Tree는 노드가 한 쪽으로 치우치는 경우, 즉 불균형 이진 트리(Unbalanced Binary Tree)가 될 수 있다.

이게 왜 문제일까?

• BST의 시간복잡도는 아래와 같다. 여기에서 worst case가 바로 불균형일 때 발생한다.

• BST 장점이 데이터 탐색할 때 절반씩 날리면서 찾을 수 있다는 건데 아래처럼 되어 있으면 그 쓸모가 없을 거다.

BST의 효율을 높이기 위해서는 Unbalanced Binary Tree를 Balanced Binary Tree로 바꿔주어야 한다. Red-Black Tree는 이 문제를 해결해준다.

📗 Red-Black Tree란?

줄여서 RB Tree는 데이터가 추가될 때마다 Balancing을 해주어 깊이를 맞춰준다. 'Red-Black'이라는 이름대로 모든 노드에 블랙 또는 레드 색을 칠한다.

그리고 아래의 '레드블랙 특성'을 만족해야 한다.

레드블랙 특성 1. 루트는 블랙이다. (시작 블랙) 2. 모든 리프는 블랙이다. (끝도 블랙) 3. 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. (레드 다음엔 꼭 블랙, 반대로 블랙의 자식은 꼭 레드일 필요는 없음) 4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.

아래 레드블랙트리를 보자.

1. 루트노드는 블랙이다.
2. leaf 노드를 모두 NIL(None)으로 뒀고, 모두 블랙이다.
3. 레드 다음에 블랙이 온다.
4. 어떤 리프노드로 가든, 그 경로에 3개의 블랙 노드가 있다.

• 

• 실제 구현시에는 아래처럼 NIL을 처리한다.

그럼 이제 RB tree에서의 삽입연산과 삭제연산을 살펴보자. 탐색은 기존 BST와 동일하다!

📘 RB tree의 삽입연산

위에서 말했듯 RBtree에선 새로운 데이터가 들어올 때마다 리밸런싱을 해줘야 하기 때문에 원래 BST와는 다르게 좀 복잡한 삽입연산을 한다.

• 우선 새로 넣을 노드(x)는 '레드'로 칠한다. 아래 예시 그림에서는 분홍색으로 표시했다. BST에서 하는 것처럼 삽입을 진행한다. 이때 왼쪽처럼 부모노드(p)가 블랙이면 아무 문제가 없다. 반면 오른쪽처럼 새로 넣은 노드의 부모가 레드면 '레드블랙 특성 3번'이 깨진다.

오른쪽처럼 레드블랙 특성이 깨지는 경우를 더 자세히 보자. 그 전에 notation은 아래처럼 정한다.

• $$x$$ : 새로 넣은 노드
• $$p$$ : x의 부모노드
• $$s$$ : p의 형제노드
• $$p^2$$ : p의 부모노드

$$p$$가 레드일 때, $$p^2$$와 $$x$$의 형제노드는 반드시 블랙임을 알 수 있다. 그리고 아래처럼 경우의 수를 나눠서 본다.

• Case1 : $$s$$가 레드인 경우
• Case2 : $$s$$가 블랙인 경우
  • case2-1 : $$s$$가 블랙이고, $$x$$가 $$p$$의 오른쪽 자식인 경우
  • case2-2 : $$s$$가 블랙이고, $$x$$가 $$p$$의 왼쪽 자식인 경우

Case1 : $$s$$가 레드일 때

1. 레드 $$p$$를 블랙으로 바꾼다.
2. 블랙 $$p^2$$를 레드로 바꾼다. 블랙 노드수는 1개, 2개, 1개로 바뀌지 않았다. (레드블랙 특성 4 유지) 반면, $$p^2$$ 위에 어떤 노드가 있을지 모른다. 레드노드가 있다면, 특성 3을 위반하는 문제가 또 발생하는 것이다. 이걸 재귀적 문제(recursive problem)이라고 하고, 똑같이 반복해주면 된다. 부모노드가 블랙인 경우에 멈추면 되는데, 루트노드는 항상 블랙이니 루트노드까지 가서 멈출 수도 있다.

Case2 : $$s$$가 블랙일 때

이때는 또 두 가지 case2-1 과 case2-2로 나눠서 본다.

• case2-1 : $$s$$가 블랙이고, $$x$$가 $$p$$의 오른쪽 자식인 경우
• case2-2 : $$s$$가 블랙이고, $$x$$가 $$p$$의 왼쪽 자식인 경우

case2-1 : $$s$$가 블랙이고, $$x$$가 $$p$$의 오른쪽 자식인 경우

• $$x$$의 왼쪽 노드를 $$p$$로 만들고, $$p$$의 부모노드를 $$x$$로 만든다.
• $$x$$의 오른쪽부분트리는 그대로 두고, $$x$$의 왼쪽부분트리를 $$p$$의 오른쪽 자식으로 만든다.

• 그럼 case2-2가 된다. case2-2로 가서 연산을 마저 수행한다.

case2-2 : $$s$$가 블랙이고, $$x$$가 $$p$$의 왼쪽 자식인 경우

• 회전하듯이 $$p$$, $$p^2$$, $$y$$의 위치를 다 바꿔준다.
• 블랙 노드 개수도 1, 2, 2개로 잘 유지되고 레드블랙 특성을 만족하면서 삽입이 완료된다.

📙 RB tree의 삭제연산

삭제연산도 마찬가지로 여러 경우를 생각해보아야 한다. 우선 아래 두 경우에는 그냥 지워주면 된다.

• 경우1 : 삭제 노드(m)가 레드면, 아무 문제 없다.
• 경우2 : 삭제 노드(m)가 블랙이라도 (유일한) 자식이 레드면 문제 없다.

이제부터는 여러 Case 로 나눠서 고려해야 한다. 경우3 : 삭제노드(m)이 블랙이고, 유일한 자식도 블랙인 경우

이 경우 m을 삭제하면 그 루트에서 블랙 개수가 하나 부족해진다. 레드블랙 특성의 4번을 위반하게 된다. 이런 경우 x의 주변상황에 따라 처리 방법이 달라진다. Notation은 아래 사진을 참고하자.

크게 아래처럼 두 Case로 나눌 수 있다.

• Case 1 : 부모노드 p가 레드인 경우 -> s노드는 무조건 블랙
• Case 2 : 부모노드 p가 블랙인 경우

이 두 가지의 경우 더 나뉘어진다. 아래처럼 7가지로 나눌 수 있는데, 같은 유형끼리 묶어서 최종적으로 5개로 묶어서 볼 수 있다. 각 5가지 경우에 어떻게 처리하는지 그림으로 봐보자.

• 1번 : Case 1-1

  • 레드인 p노드를 블랙으로 바꾸고, 블랙이던 s노드를 레드로 바꾼다. 이렇게 블랙 노드의 수를 맞춰줌으로써 삭제가 완료된다.

• ** 2번 : Case *-2**

  • p의 색은 상관없고, 블랙의 s 와 레드 r을 가진 상황이다. 이 경우 회전하듯, s를 루트노드로 만들어주어 블랙 노드 수를 맞춰준다. 삭제가 완료된다.

• 3번 : Case *-3

  • 한번에 삭제가 완료되지 않는다.
  • 삭제가 완료되지 않고 2번(Case *-2)의 모습으로 바뀐다.
  • 2번으로 가서 같은 연산을 수행해준다.

• 4번 : Case *-3

  • 블랙이던 s를 레드로 바꿈으로써 블랙노드 수를 맞춰준다.
  • 그러나 또 p에서 문제가 발생한다. p의 부모노드가 더 있다고 생각해보면 p를 지나는 경로에서 블랙노드 수가 하나 삭제가 된 것이다. 그럼 재귀적으로 윗부분을 계속 수정해주면 된다. 루트노드는 블랙이므로 언젠간 끝나게 되어 있다.
  • 

• 5번 : Case *-3

  • 회전하여 노드를 옮겨준다. 그럼 Case1-1, Case1-2. Case1-3 중 하나로 바뀐다. 해당 상황에 맞는 번호로 가서 연산을 수행해주면 된다.
  • 

이렇게 Red-Black Tree에서의 탐색과 삭제연산을 그림으로 알아봤다. 이후에는 파이썬 코드 구현을 추가하겠다.

📕 이진탐색트리란?

1. 이진트리다.
2. 왼쪽 부분트리에 있는 모든 노드는 그 노드의 데이터보다 작아야 한다.
3. 오른쪽 부분트리에 있는 모든 노드는 그 노드의 데이터보다 커야 한다. ** _이진탐색트리는 **완전이진트리(Complete Binary Tree)라는 보장은 없다._ 따라서 배열이나 파이썬 리스트를 써서 구현하지 않고, 노드 클래스 정의한 후 여러 노드 인스턴스를 생성하고 이 인스턴스를 연결시켜 구현한다.

📗 이진탐색트리 구현

이제 이진탐색트리에서 특정 노드를 검색, 삽입, 삭제 하는 작업을 구현해보자. 코드잇 강의를 들을 때 나왔던 코드와 교재의 코드가 살짝 달라서 둘 다 살펴보자.

ver.1 코드잇

• [자료구조] 이진탐색트리 출력, 삽입, 탐색, 삭제, 최소값 찾기 파이썬 구현 코드잇 강의에서 이진탐색트리를 정리한 내용은 여기에서 더 자세히 확인 가능하다.

노드 클래스 우선 노드 클래스를 만들어준다. 그 노드의 데이터값과 부모노드, 왼쪽자식, 오른쪽자식을 지정할 수 있다.

class Node:
  """이진 탐색 트리 노드 클래스"""
  def __init__(self, data):
    self.data = data
    self.parent = None
    self.left_child = None
    self.right_child = None

이진탐색트리 클래스 이진탐색트리의 연산들을 수행할 수 있는 클래스도 만들어준다. 루트노드를 설정할 수 있도록 한다.

class BinarySearchTree:
    """이진 탐색 트리 클래스"""
    def __init__(self):
        self.root = None

이진탐색트리 검색 이진탐색트리 클래스에 아래 탐색 메소드를 추가해준다. 찾고 싶은 data를 파라미터로 받는다. 비교하는 노드(compare_node)를 먼저 루트노드부터 설정해서 data와 비교한다.

if 1 ) data < compare_node ➡️ compare_node를 왼쪽자식으로 변경한다.

if 2 ) data > compare_node ➡️ compare_node를 오른쪽자식으로 변경한다.

• 만약 왼쪽자식이나 오른쪽자식이 없는 경우(None), None을 리턴한다.

if 3 ) data == compare_node ➡️ compare_node를 반환한다.

def search(self, data):
    """이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
    compare_node = self.root
    while True:
      if data < compare_node.data:
        if compare_node.left_child == None:
          return None
        compare_node = compare_node.left_child

      if data > compare_node.data:
        if compare_node.right_child == None:
          return None
        compare_node = compare_node.right_child

      if data == compare_node.data:
        return compare_node

이진탐색트리 삽입 이진탐색트리 클래스에 아래 삽입 메소드를 추가해준다. 넣고싶은 data를 파라미터로 받고, Node class로 새로운 노드(new_node)를 정의한다.

1. 트리가 비었을 때 a. new_node를 루트노드로 지정한다

2. 비교할 노드(compare_node)를 먼저 루트노드로 설정한다. a. new_node의 값 < compare_node의 값

   1. compare_node의 왼쪽자식이 없으면 ➡️ 거기에 new_node를 넣고, new_node의 부모노드는 compare_node로 설정한다. return 으로 while 문 탈출.

   2. compare_node의 왼쪽자식이 있으면 ➡️ compare_node를 왼쪽자식으로 옮겨준다.

   b. new_node의 값 > compare_node의 값

   1. compare_node의 오른쪽자식이 없으면 ➡️ 거기에 new_node를 넣고, new_node의 부모노드는 compare_node로 설정한다. return 으로 while 문 탈출.

   2. compare_node의 오른쪽자식이 있으면 ➡️ compare_node를 오른쪽자식으로 옮겨준다.

def insert(self, data):
    new_node = Node(data)  # 삽입할 데이터를 갖는 새 노드 생성

    # 트리가 비었으면 새로운 노드를 root 노드로 만든다
    if self.root is None:
        self.root = new_node
        return

    compare_node = self.root
    while True:
      if new_node.data < compare_node.data:
        if compare_node.left_child == None:
          compare_node.left_child = new_node
          new_node.parent = compare_node
          return
        compare_node = compare_node.left_child

      if new_node.data > compare_node.data:
        if compare_node.right_child == None:
          compare_node.right_child = new_node
          new_node.parent = compare_node
          return
        compare_node = compare_node.right_child

이진탐색트리 삭제 삭제 연산이 고려할 게 좀 있는데, 세 가지 경우로 나눠서 생각한다.

• 경우1 : leaf 노드 삭제

  • 

  • 이런 경우 단순히 leaf 노드의 부모노드를 None으로 지정한다.지우려는 노드가 부모노드의 왼쪽자식인지, 오른쪽자식인지 확인하고 처리해준다.

  • 경우1을 코드로 구현하면 아래와 같다.

    def delete(self, data):
    """이진 탐색 트리 삭제 메소드"""
    node_to_delete = self.search(data)  # 삭제할 노드를 가지고 온다
    parent_node = node_to_delete.parent  # 삭제할 노드의 부모 노드
    
    # 경우 1: 지우려는 노드가 leaf 노드일 때
    if node_to_delete.right_child == None and node_to_delete.left_child == None:
      if node_to_delete.data < parent_node.data:
        parent_node.left_child = None
      elif node_to_delete.data > parent_node.data:
        parent_node.right_child = None

• 경우2 : 삭제하려는 데이터 노드가 하나의 자식노드를 가질 때

  • 
  • 10을 지우고 싶은 경우, 자식노드인 14가 부모 노드의 자리를 차지하면 된다. 그리고 14의 부모노드를 8로 지정한다.
  • 코드로 구현하면 아래와 같다.

# 경우 2: 지우려는 노드가 자식이 하나인 노드일 때:
if parent_node.data > node_to_delete.data:
    if node_to_delete.left_child is None and node_to_delete.right_child is not None:
        parent_node.left_child = node_to_delete.right_child
        node_to_delete.right_child.parent = parent_node
    else:
        parent_node.left_child = node_to_delete.left_child
        node_to_delete.left_child.parent = parent_node

else:
    if node_to_delete.left_child is None and node_to_delete.right_child is not None:
        parent_node.left_child = node_to_delete.right_child
        node_to_delete.right_child.parent = parent_node
    else:
        parent_node.left_child = node_to_delete.left_child
        node_to_delete.left_child.parent = parent_node

• 경우3 : 삭제하려는 데이터의 노드가 두 개의 자식이 있을 때
  • 
  • 12를 삭제하고 싶은 경우, 14를 12자리로 옮기면 된다.
  • 지우고싶은 노드(12)의 오른쪽 부분트리에서 가장 작은 걸(14) 선택하면 되는데, 이걸 successor라고 부른다.

• ** 두 개의 자식이 모두 있는 노드를 삭제하는 경우**
  1. 지우려는 successor를 받아온다. (find_min()메소드 활용)
  2. 삭제하려는 노드 데이터에 successor의 데이터를 저장한 다.
  3. successor 노드를 삭제한다.
  • 이때 successor노드가 부모노드의 오른쪽 자식인지, 왼쪽 자식인지,
  • successor 노드가 오른쪽 자식을 가지는지 아닌지를 고려해야 한다.
  • delete() 메소드는 지우려는 데이터 data를 파라미터로 받는다. 그리고 data를 갖는 노드를 트리에서 삭제한다.

# 경우 3: 지우려는 노드가 2개의 자식이 있을 때

else:
  successor = self.find_min(node_to_delete.right_child)

  node_to_delete.data = successor.data

  # successor 노드가 어떤 부모 노드의 왼쪽 자식일 때
  if successor == successor.parent.left_child:
    successor.parent.left_child = successor.right_child
  else: # sucessor 노드가 삭제하려는 노드의 바로 오른쪽 자식일 때
    successor.parent.right_child = successor.right_child

  if successor.right_child is not None: # successor 노드가 오른쪽 자식이 있을 떄
    successor.right_child.parent = successor.parent

(이후 더 추가할 예정) 코드 사용해보기

ver.2 교재 수도코드

검색

삽입

삭제

📘 이진탐색트리 시간복잡도

📙 BOJ 예제풀이

중간고사가 네트워크 차단한 상태로 코딩하는 형식으로 진행된다고 하여 이를 대비하기 위해 코테를 하루에 하나씩 풀 예정이다! 이번 챕터에서는 백준 이분탐색(Binary Search) 문제집 에 있는 문제 두 가지를 꼽아서 풀어보겠다.

1)

2)

+) 기출풀기