구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.

합 배열 S를 만드는 공식 : S[i] = S[i-1] + A[i]

i에서 j까지의 구간 합을 구하는 공식 : S[j] - S[i-1]

• top : 삽입과 삭제가 일어나는 위치
• push : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산

• rear :큐에서 가장 끝 데이터를 가리키는 영역
• front : 큐에서 가장 앞의 데이터를 가리키는 영역
• add : rear 부분에 새로운 데이터를 삽입하는 연산
• poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
• peek : front에 있는 데이터를 확인할 때 사용하는 연산

인접한 두 개의 데이터 크기를 비교해 정렬하는 방법

간단하게 구현할 수는 있지만, 시간복잡도는 O(n²) 으로, 다른 정렬 알고리즘보다 속도가 느린 편

그림과 같이 루프를 돌면서 인접한 데이터 간의 swap 연산으로 정렬함

만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면, 그 영역 뒤에 있는 데이터가 모두 정렬되었다는 뜻이므로 프로세스를 종료해도 된다.

대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법

선택 정렬은 구현 방법이 복잡하고, 시간 복잡도도 O(n²)으로 효율적이지 않아 코딩테스트에서는 많이 사용하지 않지만, 이를 응용하는 문제가 나올 수 있고 기술면접에서 간간히 물어봄

남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다 ➡️ 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 한다 ➡️ 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 번위를 축소한다 ➡️ 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방법

시간 복잡도는 버블정렬, 선택정렬과 동일하게 O(n²)으로 느린 편이지만, 구현하기 쉬운 편 (시간복잡도가 느려서 코테에서 자주 사용하지는 않는 정렬이지만 면접때 정렬 관련된 질문 나오는거에 대비해서 알아두면 좋다)

선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치의 삽입하는 것이 삽입 정렬의 전부다

현재 index에 있는 데이터 값을 선택한다 ➡️ 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다 ➡️ 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다 ➡️ 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 떄까지 반복한다

적절한 삽입 위치를 탐색하는 부분에서 이진 탐색 등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있음!

기준값 (pivort) 을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘

기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균 시간 복잡도는 O(nlogn)이며 최악의 경우에는 시간 복잡도가 O(n²)이 됨

pivort 선정을 운에 맡겨야되서 평균 시간 복잡도랑 최악 시간복잡도 차이가 심한 정렬이지만, 평균 �시간 복잡도는 나름 준수한 편으로 코테에서는 종종 응용하는편 (재귀함수 활용)

분할 정복 (divide and conquer) 방식을 사용해서 데이터를 분할하고, 분할한 집합을 정렬하며 합치는 알고리즘, 시간 복잡도는 O(nlogn) 으로 준수한 편이다

병합 정렬은 2개의 그룹을 병합하는 원리라는걸 꼭 숙지할 것 (투 포인터 활용, 앞 그룹은 정렬 시켜놓고 포인터 주고, 뒷 그룹은 정렬 안 되어있는 상태에서 병합 정렬을 쓰는 것)

너비 우선 탐색 (BFS : breadth-first search) 도 DFS 와 동일하게 그래프를 완전 탐색하는 방법 중 하나고, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다

선입선출 (FIFO) 이 특징이며, 큐 자료구조를 이용한다.

시간복잡도는 O(V + E) (여기서 V : 노드 수 / E : 엣지 수 이다.) 로 DFS와 동일하다

너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로, 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장함

• 1. 현재 데이터셋의 중앙값을 선택한다
  2. 중앙값 > 타깃 데이터 일 때, 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
  3. 중앙값 < 타깃 데이터일 때, 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
  4. 과정 1 ~ 3을 반복하다가, 중앙값 == 타깃 데이터일 때 이진 탐색을 종료한다.

• 1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
  2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
  3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면, 1번으로 돌아가서 같은 과정을 반복한다.

• 1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.

  2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는, 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때, 처음으로 선택된 숫자는 지우지 않는다. ➡️ 이게 소수임

     

  3. 배열의 끝까지 2번을 반복한 후, 배열에서 남아있는 모든 수를 출력한다. ➡️ 소수 모두 출력

• 에라토스테네스의 체를 구현하려면 이중 for문을 사용하는게 일반적이라, 시간복잡도는 O(N²)이다.
• 그러나 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문에, 보~통은 구현하면 O(Nlog(logN))이 나온다
• 그래서 소수 구하기 문제에서는 에라토스테네스의 체를 사용하는 것이 일반적인 방법으로 통용되고 있다.

• 1. 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스값으로 초기화한다.

  2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면 (= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열의 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행한다. (여기서 i는 K의 배수)

  3. 배열의 끝까지 2번을 반복하여 오일러 피 함수를 완성한다.

유클리드 호제법이란, 두 수의 최대 공약수를 구하는 알고리즘이다

일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만, 유클리드 호제법을 이용하면 좀 더 간단하게 최대 공약수를 구할 수 있다

유클리드 호제법을 수행하려면, 먼저 MOD (모드) 연산을 이해하고 있어야 한다. (% 나머지 구하는 연산)

MOD : 두 값을 나눈 나머지를 구하는 연산 (ex. 10 MOD 4 = 2, 10 % 4 = 2 와 같음)

MOD 연산으로 구현하는 유클리드 호제법

• 1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
  2. 앞 단계에서의 작은 수와 MOD 연산 결괏값 (나머지) 으로 MOD 연산을 수행한다. (여기서 최대 공약수를 구하는 연산은 일반적으로 gcd 로 정의한다)
  3. 2번 단계를 반복하다가, 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

유클리드 호제법은 코딩테스트에서 재귀함수로 구현하는 편이다

그래프를 구현하는 방법은 총 3가지가 있다.

1. 에지 리스트 (edge list)
   에지를 중심으로 그래프를 표현한다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현하거나, 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.
   에지 리스트는 구현하기는 쉬운 반면, 특정 노드와 관련되어 있는 에지를 탐색하기 쉽지 않다는 단점이 있다.
   에지 리스트는 벨만 포드나 크루스칼(MST) 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.

• 에지 리스트로 가중치 없는 그래프 표현하기

  

  가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로, 배열의 행은 2개면 충분하다. 노드는 여러 자료형을 사용할 수 있으며, 다음의 경우 노드는 Integer형이다.
  방향이 없는 그래프라면, [1, 2] 랑 [2, 1] 은 같은 표현이다.

• 에지 리스트로 가중치 없는 그래프 표현하기

  

  가중치가 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다.

2. 인접 행렬 (adjacency matrix)
   인접행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다. 인접행렬은 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다.
   만약 노드가 5개인 그래프를 인접 행렬로 표현하려면, 5*5 로 표현하면 된다 (A[5][5] 이런식으로)
   인접 행렬의 장점은, 구현이 쉽고 두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있다는 점이다.
   하지만, 인접 행렬의 크리티컬 포인트는 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야하므로 노트 개수에 비해 에지가 적을 때에는 공간 효율성이 떨어지고, 노드 개수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함이 있다. (ex. 노드가 3만 개가 넘으면 java heap space 에러 발생)

• 인접 행렬로 가중치 없는 그래프 표현하기

  

  예를 들어 3에서 4로 가는 에지가 있다면, 3행 4열에 1을 기록한다. (여기서 인덱스를 중심으로 1을 저장하는 이유는 가중치가 없기 때문)

• 인접 행렬로 가중치가 있는 그래프 표현하기

  

  예를 들어 2에서 5로 향하는 에지가 있고, 그 에지의 가중치가 15라면, 2행 5열에 15를 기록하는 방식

3. 인접 리스트 (adjacency list) ⭐️ 가장 중요
   인접 리스트는 ArrayList 로 그래프를 표현한다. 노드 개수만큼 ArrayList를 선언해서 푸는 방식이며, 대부분 인접 리스트 방식으로 코딩테스트 문제를 풀게 된다.
   그래프를 구현하는 다른 방법들에 비해 인접 리스트를 이용한 그래프 구현은 복잡한 편이다. 하지만, 노드와 연결되어 있는 에지를 탐색하는 시간은 매우 뛰어난 편이며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러가 발생하지 않는다.
   이런 장점으로 실제 코딩테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.

• 인접 리스트로 가중치 없는 그래프 표현하기

  

  인접 리스트에는 N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현한다.
  예를 들어, 노드 1과 연결된 2, 3 노드는 ArrayList[1]에 [2, 3]을 연결하는 방식으로 표현한다.

• ⭐️ 인접 리스트로 가중치 있는 그래프 표현하기

  

  가중치가 있는 경우, 자료형을 클래스로 사용해야 한다 (예시에서는 Node 라는 클래스를 자료형으로 사용) 그 다음, (도착 노드, 가중치) 를 갖는 Node 클래스를 선언하여 ArrayList 에 사용한다.
  예를 들어, 그림에서처럼 3 노드 정보를 넣고 싶으면, 먼저 Node 라는 클래스를 상단에 선언하고, A[3].add(New Node(4, 3)) 이런식으로 추가해주면 된다.

1. 1차원 배열을 이용하기

   

   처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스값으로 초기화한다.

2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산 수행

   

   1, 4와 5, 6을 union 연산으로 연결한다. 배열[4]는 1로, 배열[6]은 5로 업데이트한다.
   1은 대표노드, 4는 자식 노드로 union 연산을 하므로, 배열[4]의 대표 노드를 1로 설정한 것이다.
   ➡️ 다시 말해, 자식 노드로 들어가는 노드값 4를 대표 노드값 1로 변경한 것이다. 그 결과, 각각의 집합이었던 1, 4는 하나로 합쳐진다.
   ⭐️ union 연산을 할 때 항상 대표 노드끼리 연결해준다! 처음에는 노드간 연결이 하나도 되어있지 않을 때는 노드 모두가 대표 노드라 그냥 연결되지만, 연결 된 후에는 대표 노드끼리 연결해주게 된다.
   그래서 union(4, 6) 으로 4와 6을 연결하려고 하면, 4와 6은 대표 노드가 아니기 때문에 4의 대표 노드 1에 6의 대표 노드 5을 연결한게 된다. 배열은 그럼 그림처럼 [1, 2, 3, 1, 1, 5] 가 된다.

3. 자신이 속한 집합의 대표 노드를 찾는 연산인 find 연산을 수행 (대표 노드를 찾고, 그래프를 정돈하고, 시간복잡도를 향상시킴)

   

   ⭐️ find 연산 수행 과정

   • 1. 대상 노드 배열에 index값과 value값이 동일한지 확인한다.
     2. 동일하지 않으면 value값이 가리키는 index위치로 이동한다.
     3. 이동 위치의 index값과 value값이 같을 때까지 1~2 과정을 반복한다. (재귀 함수로 구현)
     4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경한다.

   • find 연산 시 왜 시간복잡도가 줄어들까? : find 연산 과정을 위 그림에서 보면, 연산을 할 때 거치는 노드들이 대표 노드와 바료 연결되는 형태로 변경된다. 이러면 추후 노드와 관련된 find 연산 속도가 O(1)로 변경된다. 한 번의 find 연산으로 경로 압축의 효과가 이루어지때문에 시간 복잡도가 줄어든다.

     

     이렇게 그림에서처럼 재귀 함수를 빠져나오면서 find 연산으로 값이 다 업데이트되니까 시간 복잡도 향상 효과가 있다.

1. 진입 차수에 대한 이해 : 진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다.

   

   그림에서 그래프는 ArrayList 로 표현했고, 그래프는 사이클이 없는 상태이다.
   진입 차수 배열 D를 업데이트한다. 1에서 2, 3을 가리키고 있으므로, D[2], D[3] 을 각각 1만큼 증가시신다.

2. 위상 정렬 배열에 진입 차수가 0인 노드의 값을 저장

   

   진입 차수 배열에서 진입 차수가 0인 노드를 선택하고, 선택된 노드를 정렬 배열에 저장, 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.

3. 2번 과정 반복 후 위상 정렬 배열 종료

   

• 1. 진입 차수가 0인 노드를 큐에 저장한다.
  2. 큐에서 데이터를 poll해서 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.
  3. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer 한다.
  4. 큐가 빌 때까지 1~3번 과정을 반복한다.

• 1. 인접 리스트로 그래프 구현하기

     

     다익스트라 알고리즘은 인접 행렬로 구현해도 되지만, 시간 복잡도 측면에서 N의 크기가 클 것을 대비하여 인접 리스트를 선택해서 구현하는 것이 좋다. (N이 커지면 인접 행렬(2차원배열)이 만들어지지 않기 때문에)
     그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치) 와 같은 형태로 선언하여 연결한 점도 참고

  2. 최단 거리 배열 초기화하기

     

     최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화한다. 이때, 무한은 적당히 큰 값을 사용하면 된다. (ex. 99,999,999 같은 엄청 큰 임의의 값)

  3. 값이 가장 작은 노드 고르기

     

     최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 여기서는 값이 0인 출발 노드에서 시작하면 된다.

  4. 최단 거리 배열 업데이트하기

     

     선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트한다. 연결 노드의 최단 거리는 두 값 중 더 작은 값으로 업데이트한다.

  5. 3~4 과정을 반복해서 최단 거리 배열 완성하기

     

     과정 4에서 선택된 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리하고, 모든 노드가 선택될 때까지 반복하면 최단 거리 배열이 완성된다.

• 1. 에지 리스트로 그래프를 구현하고, 최단 경로 리스트 초기화하기

     

     벨만-포드 알고리즘은 에지 중심으로 동작하므로 그래프를 에지 리스트 로 구현한다. 또한, 최단 경로 리스트를 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.

  2. 모든 에지를 확인해서 정답 리스트 업데이트하기

     

     에지의 개수는 사이클이 생기지 않도록 노드 개수 - 1 을 해줘야 한다.
     D[s] != ∞ 이며 D[e] > D[s] + w 일 때, D[e] = D[s] + w 로 리스트의 값을 업데이트한다.
     노드 개수가 N이고, 음수 사이클이 없을 때 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단거리이다.
     음수 사이클이 없을 때, N-1번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려 주는 정답 리스트가 완성된다.

  3. ⭐️ 음수 사이클 유무 확인하기

     

     N-1 에지 사용 횟수를 반복하고나서, 다시 벨만-포드 알고리즘을 실행해서 만약 업데이트 되는 노드가 발생했을 경우, N-1 에지 사용 횟수보다 N에지 사용 횟수가 더 최단 거리라는 얘기가 된다. (사이클이 일어난다는 소리)
     이런 경우, 도출한 정답 리스트가 무의미하고, 최단 거리를 찾을 수 없는 사이클이 있는 그래프라는 소리니까 음수 사이클이 있다는 소리다.
     그래서 3번까지 과정을 거치면 음수 사이클이 존재하는 그래프인지 확인할 수 있다.

• A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 점
  ex. 1에서 5까지 가는 최단 경로를 구했다고 가정하면, 1에서 4까지의 최단 경로와 4에서 5까지의 최단 경로 역시 1에서 5까지의 최단 경로에서 나올 수 밖에 없다

• 1번에서 도출한 플로이드-워셜 알고리즘의 점화식 : D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

• 1. 리스트를 선언하고 초기화하기

     

     S와 E값이 같은 칸은 모드 0으로, 나머지 칸은 무한대로 초기화 한다. (S == E는 자기 자신에게 가는 데 걸리는 최단 경로값을 의미하기 때문)

  2. 최단 거리 리스트에 그래프 데이터 저장하기

     

     D[S][E] = W 로 에지의 정보를 리스트에 입력한다. (여기서 W는 가중치를 의미함) ➡️ 인접 행렬로 표현

  3. ⭐️ 점화식으로 리스트 업데이트하기 (3중 for문 형태로 반복하면서 리스트 값을 업데이트)

     

     여기서 완성된 리스트는 모든 노드 간의 최단 거리를 알려준다. (ex. 1번 -> 5번 최단 거리는 D[1][6]=6)

• 1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트로 초기화하기 (사이클 판별을 위함)

     

     최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장한다. 그래서 인접 리스트가 아닌 에지 리스트 형태로 저장한다.
     이 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다. 사이클 처리를 위한 유니온 파인드 리스트도 함께 초기화한다. 리스트의 인덱스를 해당 자리의 값으로 초기화하면 된다.

  2. 그래프 데이터를 가중치 기준으로 정렬하기

     

     에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.

  3. 가중치가 낮은 에지부터 연결 시도하기

     

     가중치가 낮은 에지부터 순서대로 선택해서 연결을 시도한다. 이때, 바로 연결하지 않고, 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find 연산을 이용해서 확인한 후 사이클이 형성되지 않을 때만 union 연산을 이용해서 두 노드를 연결한다.

  4. 과정 3번을 연결한 에지의 개수가 N-1이 될 때까지 반복

     

  5. 총 에지 비용 출력하기

     

트리의 구성 요소

코딩테스트에서의 트리

• 1. 그래프로 푸는 트리 문제 : 노드와 에지를 인접리스트로 표현할 수 있으니까 이걸 활용해서 DFS, BFS 알고리즘으로 표현해서 문제를 풀 수 있다.
  2. 트리만을 위한 문제 : 트리 중에서 이진 트리, ⭐️세그먼트 트리(index tree), ⭐️최소 공통 조상(LCA) 를 활용해서 문제를 풀 수 있다. 특히 세그먼트 트리와 LCA는 1차원 배열로 트리를 표현한다.

이진 트리는 각 노드의 자식 노드(차수)의 개수가 2이하로 구성된 트라를 말한다. 트리 영역에서 가장 많이 사용되는 형태

이진 트리의 종류로는 편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있다.

데이터를 트리 자료 구조에 저장할 때, 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비되는 단점이 있다. 일반적으로 코딩 테스트에서 데이터를 트리에 담는다고 하면, 이진 트리 형태(완전 이진 트리)로 담게 된다.

• 이진트리는 1차원 배열의 형태로 표현할 수 있다.

  

• 1. 트리 초기화하기
     리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다. 트리 배열의 크기를 구하는 방법은 2의 k제곱 >= N 을 만족하는 k의 최솟값을 구한 후, 2의k제곱 * 2 를 트리 배열의 크기로 정의하면 된다.

     

  2. 질의값 구하기
     주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경한다. 기존 샘플을 기준으로 한 인덱스 값과 세그먼트 트리 배열에서의 인덱스값이 다르기 때문에 인덱스를 변경해야함!

     

     과정 1 ~ 2에서 해당 노드를 선택했다는 것은 해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가기 때문에 해당 노드를 질의값에 영향을 미치는 독립 노드로 선택하고,
     해당 노드의 부모 노드는 대상 범위에서 제외한다는 뜻이다.
     부모 노드를 대상 범위에서 제거하는 방법은 바로 3 ~ 4에서 질의 범위에 해당하는 부모 노드로 이동하기 위해 인덱스 연산을 index / 2 가 아닌 (index + 1) / 2, (index - 1) / 2 로 수행하는 것이다.
     (질의에 해당하는 노드를 선택하는 방법은 구간 합, 최댓값 구하기, 최솟값 구하기 모두 동일하며 선택된 노드들에 관해 마지막에 연산하는 방식만 다르다.)
     

     

     
     

  3. 데이터 업데이트하기
     업데이트 방식은 자신의 부모 노드로 이동하면서 업데이트한다는 것은 동일하지만, 어떤 값으로 업데이트할 것인지에 관해서는 트리 타입별로 다르다.
     (부모 노드로 이동하는 방식은 세그먼트 트리가 이진 트리이므로 index = index / 2 로 변경하면 된다.)

     
  
  

• 문제를 분석할 때, 계속 구간합을 구하라고 하는 문제는 구간합(합배열) 을 이용하는 경우 시간이 오래 걸리기 때문에 세그먼트 트리 알고리즘을 활용하는게 좋다. (단순 구간합이 아닌 구간합이 반복되는 경우)

일반적인 최소 공통 조상 구하기

• 1. 루트 노드에서 탐색을 시작해서 각 노드의 부모 노드 깊이를 저장한다

     

     4번 15번 노드의 최소 공통 조상을 구하려고 할 때, 먼저 루트 노드에서 탐색을 시작해서 각 노드의 부모 노드 깊이를 저장한다.
     여기서 탐색할 때는 DFS나 BFS 를 이용해서 수행하면 된다.
     

  2. 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 부모 노드로 1개씩 올려주면서 갚은 깊이로 맞춰준다. 이때, 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료한다.

     

최소 공통 조상 빠르게 구하기

• 빠르게 구하는 방법의 핵심은 서로의 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존의 한 단계씩 올려주는 일반적인 방법에서 2의 k제곱씩 올라가서 비교하는 방식이다.
• 기존에 자신의 부모 노드만 저장해 놓던 방식에서 2의 k제곱번째 위치의 부모 노드까지 저장해줘야된다. (그래서 단계가 하나 더 늘어나서 3단계가 됨)

• 1. 부모 노드 저장 배열 만들기

     

     여기서 k는 트리의 깊이 > 2의 k제곱 을 만족하는 최대값이다. 만약 트리의 최대 깊이가 5일 경우, k의 최대값은 2가 된다 (트리의 높이보다 클 수 없다)
     
     

     

  2. 선택된 두 노드의 깊이 맞추기

  3. 최소 공통 조상 찾기

     

     P배열을 이용해서 최초로 두 노드의 부모가 달라지는 값을 찾는다. 여기서 K가 0이 될 때까지 반복해서 최소 공통 조상을 찾는다.

     

조합 (Combination) 은 _nC_r 로 표현되고, n가의 숫자 r개를 뽑는 경우의 수를 뜻한다.

조합과 비교되는 순열은 _nP_r 로 표현되고, n개의 숫자 중 r개를 뽑아 순서를 고려해서 나열할 경우의 수를 뜻한다.

순열과 조합의 차이는 순서의 고려 유무인데, 즉, 조합에서는 데이터 1, 2, 3과 3, 2, 1을 같은 경우라고 판단하고, 순열은 다른 경우로 판단한다.

실제 코딩테스트에서는 순서를 고려하는 순열 보다는 조합의 출제 빈도 수가 높고, 응용할 수 있는 문제도 많다.

분모에 r!은 순서가 다른 경우의 수를 제거하는 역할을 한다. (그래서 순열 공식에는 분모에 r! 없이 (n-r)! 만 해준다)

• 1. 특정 문제를 가정하기

     

     (여기서는 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정한다.)

  2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기

     

  3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기
     ⭐️ D[i][j] = D[i-1][j-1] + D[i-1][j] ⭐️

• 1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
  2. 작은 문제들이 반복되어 나타나고 사용되며, 이 작은 문제들의 결괏값은 항상 같아야 한다.
  3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며, 추후 재사용할 때는 이 DP 테이블을 이용한다. 이를 메모이제이션 기법 이라고 한다.
  4. 동적 계획법은 탑-다운 방식과 바텀-업 방식으로 구현할 수 있다.

• 피보나치 수열 공식 : D[N] = D[N-1] + D[N-2] (N번째 수열 = N-1번째 수열 + N-2번째 수열)

• 1. 동적 계획법으로 풀 수 있는지 확인하기
     예를 들어, 6번째 피보나치 수열은 5번째 피보나치 수열과 4번째 피보나치 수열의 합이다.
     즉, 6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 4번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있고, 수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있다.

  2. 점화식 세우기
     점화식을 세울 때는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요하다.

  3. 메모이제이션 원리 이해하기
     메모이제이션은 부분 문제를 풀었을 때, 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용하는 것을 말한다.
     

     

  4. 탑-다운 형식 or 바텀-업 방식으로 문제 풀이
     두 방식 중 더 안전한 방식은 바텀-업 방식이다. (탑-다운 방식은 재귀 함수 형태로 구현되어있기 때문에, 재귀의 깊이가 매우 깊은 경우 런타임 에러가 발생할 수 있기 때문, 정말 가끔 있는 경우)