누적합 알고리즘

누적합 알고리즘은 어원 그대로 특정 값을 누적해서 더해줄때 사용되는 알고리즘이다.

코딩테스트에서 구간의 합을 구하는 문제에서 주로 사용된다.

누적합 알고리즘 동작방식

• 접두사 합(Prefix Sum): 배열 가장 앞부터 특정하는 위치까지 각 누적합을 미리 구해놓은 것이다.
• 접두사 합을 활용하여 알고리즘을 을 아래와 같이 만들 수 있다.
  위치 각각에 대한 접두사 합을 계산하여 P에 저장한다.
  매번 특정 수 만큼의 쿼리정보를 확인할때 구간 합은 P[right] - P[left - 1] 이다.

• 주어진 배열

• 접두사 합 배열

이에 [주어진 배열]에서 각 인덱스별로 누적합을 구한 것이 [접두사 합 배열 (p)]이다.

누적합 알고리즘에서 주어지는 공식 P[right] - P[left - 1] 를 생각했을때 아래의 예시를 확인해보자.

[주어진 배열]에서 1부터 3번째 인덱스가 가진 value의 누적합을 구해야 하는 문제이다.

[1, 3] => p[3] - p[0] = 9

< [주어진 배열]을 확인하면 3 + 2 + 4 이기 때문에 결과는 9가 되는 것을 확인 할 수 있다. >

[주어진 배열]에서 1부터 3번째 인덱스가 가진 value의 누적합을 구해야 하는 문제이다.

[3, 5] => p[5] - p[2] = 7

< [주어진 배열]을 확인하면 4 + 1 + 2 이기 때문에 결과는 7이 되는 것을 확인 할 수 있다. >

누적합 알고리즘을 활용한 예시문제

• 데이터의 개수 N이 8로 주어진다.
• 찾고자 하는 데이터 4번째 부터 8번째의 값의 누적합을 구해야 한다. (left = 4, right = 8)

let n = 8;
let arr = [3, 2, 4, 1, 2, 2, 1, 5];

// 접두사 합 배열
let sumValue = 0;
let prefixSum = [0];

for (let i of arr) {
  sumValue += i;
  prefixSum.push(sumValue);
}

// 네 번째 수부터 여덟 번째 수까지
let left = 4;
let right = 8;

console.log(prefixSum[right] - prefixSum[left - 1]);

마치며...

누적합 알고리즘은 내가 생각했던 것 보다 훨씬 효율적으로 특정 범위의 누적합을 구하는 방식이었던 것 같다. 알고리즘을 공부하면서 컴퓨터 공학과 수학은 뗄레야 뗄 수가 없는 관계인 것을 다시금 느꼈다.

투 포인터 (Two Pointer)

리스트에서 순차적으로 기록하며 처리할 때 두가지 위치(점: point)를지정하여 처리하는 알고리즘이다.

예를 들어 [1, 2, 3, 4, 5, 6, 7, 8, 9] 리스트에서 4, 5, 6, 7, 8 을 말할때 "4에서 8까지의 수" 라고 말한다.

위 예시에서 처럼 4~8까지의 수를 "시작점 4"와 "끝점 8"로 2개의 점으로 데이터의 범위를 특정하여

문제를 처리하는 알고리즘을 뜻한다.

투 포인터를 활용하기

부분 연속 수열찾기 문제에서 투 포인터 알고리즘을 활용하여 문제를 해결할 수 있다.

1. 시작점과 끝점이 첫 인덱스 0을 가리키도록 만든다.
2. [현재 부분의 합 S]가 [찾아야할 값 M]과 같다면 카운트에 추가해준다.
3. S가 M보다 작거나 같으면 끝점을 1 증가시켜준다.
4. S가 M보다 크면 시작점을 1증가시킨다.
5. 모든 경우를 2번~ 5번까지의 과정을 반복하며 값을 얻는다.

투 포인터를 활용한 예시문제

• 데이터의 갯수 N이 8로 주어진다.
• 찾고자하는 부분 합 M이 5로 주어진다.
• 주어지는 수열은 [3, 2, 1, 4, 2, 1, 1, 5] 이다.
• 부분 수열의 합이 M이되는 경우의 개수를 출력하시오.

let n = 8;
let m = 5;
let data = [3, 2, 1, 4, 2, 1, 1, 5];
let cnt = 0;
let intervalSum = 0;
let end = 0;
// start를 순차적으로 증가시키며 반복한다.
for (let start = 0; start < n; start++) {
  // end를 조건에 맞는경우 가능한 만큼 이동시키기
  while (intervalSum < m && end < n) {
    intervalSum += data[end];
    end += 1;
  }
  // 부분합이 m일 때 카운트++
  if (intervalSum == m) cnt += 1;
  intervalSum -= data[start];
}
console.log(cnt); // output: 3

마치며...

평소에 코딩테스트를 한번씩 풀어보는데 나도 모르는 사이에 투포인터 알고리즘을 사용하는 경우가 종종 있었던 것 같다. 확실히 용어를 알고 원리를 제대로 파악하니 좀 더 전략적으로 코드를 작성할 수 있게 된 것 같아 뿌듯했다.

최단경로 알고리즘, 다익스트라(Dijkstra)

음의 가중치가 없는 그래프에서 한 정점에서 모든 정점까지의 최단거리를 각각 구하는

알고리즘을 에츠허르 "다익스트라(Edsger Wybe Dijkstra)"라는 컴퓨터 과학자가 만들었다.

그렇기 때문에 음의 간선이 존재하지 않는 최단경로 알고리즘을

"다익스트라" 알고리즘이라고 부른다.

최단경로 알고리즘 동작과정

최단거리 테이블은 각 노드에서 현재노드까지의 최단 거리 정보를 가지며

처리 과정에서 더 짧은 경로를 찾아다니며 더 짧은 경로로 값을 갱신한다.

1. 출발 노드를 설정
2. 최단거리 테이블을 초기화
3. 방문하지 않은 노드 중 최단거리 비용이 가장 적은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 최단거리 테이블에 갱신한다.
   < 우선순위 큐에 삽입하는 방식으로 사용가능 >
5. 3번, 4번 과정을 끝날때까지 반복한다.

플로이드 알고리즘

전산학자 로버트 플로이드(Robert W Floyd)가 만든 알고리즘이다.

모든 노드에서 다른 모든 노드까지의 최단경로를 계산하는 알고리즘으로

다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다.

플로이드 워셜은 2차원 테이블을 통해서 최단거리 정보를 저장하며

다이나믹프로그래밍에 속하기도 한다.

< 단계별로 점화되기 때문에 점화식이기도 하다. >

• 플로이드 워셜의 점화식
  [ A에서 B로가는 거리보다 K를 거쳐가는 A - K - B 의 거리가 더짧은지 체크 ]
  D[A][B] = Math.min(D[A][B], D[A][K] + D[K][B])

벨만포드 알고리즘

미국의 두 수학자 "리처드 벨만(Richard Bellman)"과 "카탈리스트인 포드(Alfonso Shimbel)"에 의해

독립적으로 개발된 알고리즘이다. 리처드 벨만의 "벨만"과 카탈리스트인 포드의 "포드"를 따서

"Bellman-Ford Algorithm"으로 불리게 되었다. 벨만포드 알고리즘은 음수의 간선이 포함되어도

최단거리를 계산할 수 있는 최단경로 알고리즘이다. 하지만 경로를 탐색하다 음수순환이 존재하면

무한루프에 빠져 값을 반환할 수 없게된다

음수순환이란?

알고리즘을 통해 경로를 탐색하면서 계속해서 가장 짧은 거리를 찾아야하는 갱신해주어야 하지만

특정 경로에서 사이클이 생겼을때 모두 거쳐 갔을때 음수가 되는 경우 사이클을 계속해서 돌면서

값이 작아지기 때문에 음수의 순환이되고 음의 무한인 노드가 되어버린다. 그렇기 때문에

음수순환이 발생하는지에 대해 검사를 해주어야 한다.

벨만포드 알고리즘 동작 과정

1. 출발 노드 설정
2. 최단거리 테이블 초기화
3. 아래 과정을 N - 1만큼 반복해준다.
   3-1. 모든 간선 E개를 하나씩 체크한다.
   3-2. 각 간선을 거쳐서 다른 노드로 가는 최단거리의 비용을 테이블에 갱신한다.
   
   
4. < 음수 순환을 체크하기 위해서는 3번 과정을 한 번 더 수행한다. >
   최단거리 테이블이 갱신되다면 음수순환이 존재

마치며...

최단경로 알고리즘을 학습할때 벨만포드 알고리즘이 가장 어려웠다. 특히 음의 순환의 경우 이해하는데 꽤 애를 먹었는데 잘 생각해보면... 최소값(최단경로)을 찾는 문제에서 사용했기 때문에 탐색을 할때 계속해서 작은 수가 발견되면 자연스럽게 무한으로 감소한다는 것은 당연한 것이었는데 말이다. 항상 차근차근 발단부터 연관성을 가지고 이해해야 한다는 것을 다시금 느끼게되는 학습이었다.

다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍은 문제에서 "최적 부분 구조" 또는 "반복되는 부분 문제"에 해당하는 경우

사용할 수 있는 알고리즘이다.

1. 최적 부분 구조
   => 커다란 문제를 작은 문제로 나눌 수 있고 그 형태가 모두 유사하다면 이를 모아서 큰 문제를 해결하는 것
2. 반복되는 부분 문제
   => 형식이 동일한 작은 문제를 반복적으로 해결해야 할때의 문제

점화식과 최적 부분 구조

점화식은 인접한 항으로서 현재 값을 결정하는 관계식을 말하며

점화식은 주로 최적 부분 구조를 만족한다는 특징이 있다.

• 피보나치 수열 (점화식): a(n) = a(n -1) + a(n-2), [ (a(1) = 1, a(2) = 1 ]

점화식의 구성요소

"초기항"과 "인접한 항과의 관계"가 필요하다.

점화식은 재귀함수로 표현이 가능하며 재귀함수의 경우 종료조건이 반드시 있어야 하는데

종료조건이 점화식의 초기항 과 같은 역할을 수행한다.

function fibo(n) {
	if (n == 1 || n == 2) return 1; // 종료조건이 없으면 무한루프된다.
    return fibo(n - 1) + fibo(n - 2); // 점화식
}

다이나믹 프로그래밍의 형태 예시

function dp() { /*
    1. 종료하는 조건
    2. 이미 해결한 문제 = 정답을 return
    3. 점화식 계산
*/ }

다이나믹 프로그래밍 문제를 해결하는 과정은

1. 점화식을 찾아내고
2. 구현방식을 상향식, 하양식을 선택한 후에
   상향식: 반복문을 통해 초기항부터 계산 방법
   하양식: 재귀함수로 큰 항을 구하기 위해 작은 항을 호출하는 계산 방법
3. 점화식을 코드로 구현해주면 된다.
   < 계산이 완료된 값을 담는 테이블을 주로 DP테이블이라고 부른다. >

마치며...

다이나믹프로그래밍에 대해서 혼란스러울땐 피보나치 수열을 떠올리는 것이 가장 좋은 것 같다.

1. DFS, 깊이 우선 탐색 (Deep-First-Search)

깊이 우선 탐색은그래프나 트리 자료구조에서 모든 노드를 한번씩 탐색할때 쓰이는 기본적인 방법이다.

완전탐색을 할 때 가장 간단한 방법 중 한가지다.

스택(Stack) 자료구조를 사용하는 것이 일반적이다.

DFS 기본 동작 방식

1. 시작 노드를 스택에 넣은 후 방문처리 한다.
2. 스택에 마지막으로 들어온 노드에 방문하지 않은 인접노드의 존재 여부를 확인한다.
   방문하지 않은 노드가 존재한다면 노드를 스택에 넣고 방문처리한다.
   없다면 현재의 노드 즉, 스택에 마지막으로 들어온 노드를 스택에서 추출한다.
3. 2번 과정을 반복할 수 없을때까지 반복해준다.

DFS 구현 특징

• 스택 사용을 사용하거나 재귀함수를 사용한다.
• 재귀함수는 스택과 동작원리가 동일하기 때문에 구현의 편리성이 존재한다.
• 완전 탐색을 목적으로 하는 경우에는 BFS보다 느릴 수 있기 때문에 적재적소에 사용하는 것이 좋다.
• 탐색속도가 느리더라도 구현의 편리함 때문에 BFS대신 DFS를 사용하는 경우도 적지않다.

DFS를 사용하는 경우는?

1. 간결한 코드로 구현해야 할 떄
2. 큐 라이브러리를 사용할 수 없을 때
3. 트리에서 최단 거리를 탄색해야 할 때
   -> 트리에서는 두 노드를 잇는 경로가 하나만 존재하는 경우만

2. BFS, 너비 우선 탐색 (Breadth-First-Search)

깊이 우선 탐색과 마찬가지로 그래프나 트리에서 모든 노드를 한번씩 탐색할때 쓰이는 알고리즘이다

모든 간선의 길이가 동일하게 주어졌을때 최단거리를 탐색하기 위한 목적으로 사용할 수 있으며

큐(Queue) 자료구조를 사용한다.

BFS 기본 동작 방식

1. 시작 노드를 큐에넣고 방문처리를 해준다.
2. 큐에서 원소를 dequeue(삭제/꺼내기) 해주어 방문하지 않은 인접한 노드를 확인한다.
   방문하지 않은 인접노드가 있다면 해당 노드를 큐에 모두 삽입하며 방문처리한다.
3. 2번 과정을 반복할 수 없을때까지 반복해준다.

BFS를 사용하는 경우는?

1. 간선의 비용이 모두 동일하게 주어졌을때 최단거리 문제를 해결할 때
2. 완전 탐색을 DFS로 진행했을때 메모리 혹은 시간초과되는 경우

백트래킹 (Back-Tracking)

백트래킹은 해를 찾는 도중 해가 아닌 경우 다시 되돌아가 다시 해를 탐색하는 알고리즘이다.

일반적으로 그래프나 트리의 모든 원소를 완전탐색하기 위해서 많이 사용된다.

백트래킹은 재귀함수를 이용해 구현할 수 있다. 정석적인 완전 탐색과는 다르게 조건에 따라서

더 유망한 노드로 이동한다.

백트래킹 알고리즘을 이용하여 풀 수 있는 문제

백트래킹을 이용한 코딩테스트 문제중에서 가장 유명한 N퀸 문제이다.

탐색을 진행하면서 유망한 경우에 대해서만 탐색을 진행해야 한다.

예를 들면 미리 table을 만들어두고 탐색을 진행한 후 문제의 조건대로 경로가 겹쳐

탐색할 필요가 없는 table의 index번째를 false에서 true로 바꾸어 미리 건너뛰어 줄 index를

지정한 후 재귀탐색을 하는 방식으로 풀이할 수 있다.

백준 코딩테스트 페이지: https://www.acmicpc.net/problem/9663

마치며...

공부하면서 이해하기 가장 어려웠던 방식의 알고리즘이었다. 특히 재귀적으로 처리한다는 방식 자체가 처음 접했을때 상당히 혼란스러웠다. 이해하기 어려운 만큼 하나씩 직접 그림을 그리면서 적용해보면서 이해할 필요가 있었다. 초반에 로직에 대한 이해 때문에 내가 애용하는 Google Keep에 하나씩 적으며 풀이해둔 것을 저장해 두었다. 혹시 시간이 지나고 재귀적인 처리작업을 불가피하게 해야 할 때 포스팅과 Google Keep을 다시 보며 복습해야겠다...

이진탐색 (Binary Search)

정렬이 되어있는 리스트에서 탐색 범위를 반씩 좁혀가며 데이터를 탐색하는 것이다.

각 단계마다 탐색 범위를 2로 나누어 탐색하기 때문에 시간복잡도는 O(log N)이다.

때문에 이진탐색은 매우 넓은 탐색범위(억 단위 이상)에서 최적의 해를 찾아야 하는 경우나

데이터를 정려한 후 다수의 쿼리를 날려야 하는 경우에 많이 사용할 수 있다.

이진탐색 동작 방식

아래 리스트 표에서 값이 15인 위치를 찾고자 한다고 가정해보자.

1. 정렬이 이미 되어 있다는 것을 가정하고 이를 통해서 [start, mid, end] 3포인트를 지정한다.
   mid는 배열의 크기를 2로 나누었을때 소수점을 버린 값이다. (10 = 5, 9 = 4)
   {start: 0, mid: 8, end: 20}
   
   
2. 이진탐색의 방식은 결과적으로 mid가 탐색값이 되면 탐색을 멈추고 mid를 반환하는 방식이다.
   탐색값과 mid를 비교해서 탐색값이 더 크다면 start = mid를 해주어 탐색 범위를 좁히고
   변경된 start를 기준으로 mid = parseInt((start + end) / 2) 를 작성해서 mid위치를 재지정해준다.
   반대로 탐색값이 더 작다면 end = mid, mid = parseInt((start + end) / 2)를 작성하여
   end위치와 mid위치를 재지정해주면 된다.

마치며...

이진 탐색코드 같은 경우엔 코딩테스트에서도 분명 이점이 있지만 프로젝트를 진행할 때 특정 값을 정렬된 데이터들 내에서 탐색하는 방법을 사용할때 많이 이용하게 될 것 같다.

탐욕알고리즘 (Greedy Algorithm)

현재 상황에서 가장 좋아보이는 상황만을 선택하는 알고리즘이다.

흔히 그리디, 탐욕알고리즘이라고 부리기도 하며 최적의 해를 구하기위한

방법으로 사용될 때가 많다.

탐욕 알고리즘의 접근방법

1. 현재 상황에서 어떤 것을 선택할지 방법을 고안한다.

2. 자신이 고안한 알고리즘이 항상 최적의 해를 보장하는지 정당성을 확인해야한다.

탐욕 알고리즘 문제

전형적인 탐욕 알고리즘을 이용해 풀 수 있느 문제로 "거스름 돈" 문제가 있다.

거스름 돈 문제를 통해서 그리디알고리즘에 대해서 이해해보자.

문제는 아래와 같은 조건과 답을 내어야 한다.

• 카운터에 500원 100원 50원 10원이 무수히 많다고 가정한다.
• 손님에게 11,480원을 거슬러 주어야 할때, 동전 개수의 최소값은?

결론부터 말하자면 이 문제의 해결방법은 가장 큰 화폐단위부터 거슬러 주는 것이다.

즉 500원부터 10원까지 거슬러 줄 수 있는 만큼 거술러주면 되는 것이다.

동전 개수의 최소값은 30이다.

큰 화폐부터동전의 개수를 구하며 내려왔을때 최적의 해를 구할 수 있는 이유는

각 화폐단위가 배수 관계에 속하기 때문에 그렇다.

예를 들어 640원을 거슬러 주어야한다고 하고 220원, 200원, 10원 동전이 있다고 가정하면

220원 2개, 200원 1개로 총 3개가 필요할 것이다. 이 또한 배수관계에 속하기 때문에

가장 큰 수의 동전부터 나눌 수 있는 만큼 나누고 점차 작은 수의 동전으로 나누어주는

같은 방식의 탐욕알고리즘을 사용하여 문제를 해결할 수 있다.

마치며...

탐욕알고리즘에 대해서는 간단하게 포스팅을 해보았다. 실질적으로 탐욕알고리즘은 코딩테스트를 볼 때 중요했던 개념이었다. 나는 탐욕알고리즘을 파악할때 예시로 주어지는 입력값과 출력값(정답)을 보며 연관성을 최대한 찾아보고 답을 만들기 위한 코드설계와의 연관성과 규칙성이 있는지를 확인하면서 코드를 작성할때 어떠한 연관성이 있는지를 파악하면서 실마리를 찾아냈던 것 같다. 개인적으로 익숙해지기 어려운 접근방식이었던 기억이 있다...