Circular Dependencies

의존성 순환이란 코드를 모듈화 하여 작업할 때 생기는 모듈간의

의존성이 순환하며 무한루프를 일으키게 되는 현상을 뜻한다.

A라는 모듈이 B를 참조하여 의존성을 가지게 되고

B모듈 역시 A모듈을 참조하여 서로 의존성을 가지게 되면

A 혹은 B 모듈중 하나만 실행되어도 멈추지 않고

A모듈과 B모듈을 지속 실행하게 된다.

Node.js의 의존성 순환

기본적으로 자바스크립트 모듈 시스템은 순환 참조를 허용한다.

때문에 런타임 오류가 발생하진 않지만 간혹 참조 평가 순서에 의해

순환참조로 인한 에러를 마주할 수 있다.

여기서 "평가 순서"란 객체가 파라미터를 넘기고 수행하는 시점을 뜻한다.

해결책

결과적으로는 서로 순환참조할 수 없도록 평가 순서에 영향을

미치지 않는 새로운 모듈을 정의하고 이를 필요한 모듈에서

가져와 사용한다면 해결할 수 있다.

• 예시 코드

// modules.js  (새롭게 정의한 모듈)
export * from './B.js';
export * from './A.js';

// index.js  (A, B 모듈을 사용)
import { A, B } from './modules.js';

// A.js  (B에 의존성을 가진 모듈A)
import { B } from './modules.js';
export const A = 'My name is A!';
B("Hello! ");

// B.js  (A에 의존성을 가진 모듈B)
import { A } from './modules.js';
export const B = (Hello) => {
  alert(`${Hello + A}`);
};

위 예시 코드는 새로 정의한 modules.js 파일에 모듈을

집합 시켜 평가 순서를 결정할 수 있도록 정의했기 때문에

모듈을 가져올 때 반드시 modules.js 파일에서 가져온다.

위 예시 코드는 모듈들을 번들링하여 순환 참조를

해결하는 하나의 방법론이다.

조영호 님의 '우아한 객체지향' 세미나에서 언급했던 이야기 중 [ 설계란, 코드를 어디에 위치시킬 것인가에 대한 의사 결정이며 이에 대한 결정은 " 변경 " 에 초점을 맞추는 것이다. " 변경되는 코드들을 함께 " 넣어야 하고 " 변경의 핵심은 의존성 "이다. ] 라고 조언해 주신 것이 순환 참조, 의존성에 대한 개념과 이해도를 높일 수 있는 키워드가 되었던 것 같다.

마치며...

깃허브를 둘러보다 Node.js런타임에서 개발되는 코드들을(주로 React) 봤을때 위 방식으로 순환참조를 방지하는 것을 종종 보았다. 분명 좋은 방법처럼 보이지만 개인적인 견해로는 차라리 폴더 아키텍처를 조금 더 구분감 있게 분류한다면 자연스럽게 해결할 수 있지 않을까? 싶은 생각이 들었다. 이 처럼 다양한 문제를 다양한 사고방식의 사람들이 다양한 방법론을 제시하고 발전시켜 왔기 때문에 지금처럼 개발 생태계를 발전시킬 수 있었던 것 같다.

API

Application Programming Interface의 약자로 응용 프로그램에서

운영체제나 프로그래밍 언어가 제공하는 기능을 제어 가능하도록

만든 인터페이스이며, 프로그램들이 서로 상호작용하는 것을

돕는 매개체라고 볼 수 있다.

REST

HTTP를 기반으로 필요한 자원에 접근하는 방식을 정의해둔

아키텍처이다. REST는 웹의 기존 기술과 HTTP 프로토콜을 그대로

활용하기 때문에 웹의 장점을 최대한 활용가능한 것이 특징이다.

REST의 속성

1. 서버의 모든 자원은 클라이언트가 접근할 수 있는 고유 URI가 존재한다.
2. 클라이언트가 요청할 때마다 필요한 정보를 보내주기 때문에 세션 정보를
   보관할 필요가 없어 서비스의 자유도가 높아지고 유연한 아키텍처 적용이 가능하다.
3. HTTP 메서드를 사용한다.(GET, POST, PUT, DELETE 등)
4. 서비스 내의 자원은 연관된 자원들과 연결되어 표현되어야한다.

REST는 HTTP메서드를 통해 자원을 처리하도록 설계된 아키텍처이다.

REST의 구성 요소

자원(Resource)

모든 자원은 서버에 존재하며 고유 ID를 가지고 있으며,

자원의 위치를 식별하는 URI(Uniform Resource Identifier)를 통해

자원에 접근할 수 있다.

메서드(Method)

• GET: 리소스를 조회
• POST: 리소스를 생성
• PUT: 리소스를 전체 수정
• PATCH: 리소스를 일부 수정
• DELETE: 리소스를 삭제

메시지(Message)

HTTP header, body, 응답 상태 코드 등으로 구성되어 있다.

• header: body에 어떤 형식으로 데이터가 담겼는지 표시
• body: 자원에 대한 정보를 JSON, XML 등으로 전달

응답 상태 코드는 200 ~ 500 사이의 숫자로 클라이언트의

요청에 대한 상태를 나타낸다.

REST의 특징

1. Server-Client 구조

클라이언트는 자원을 요청하고 서버는 자원을 가지고 있으며

API를 제공하여 비즈니스 로직처리 및 저장을 책임진다.

2. Stateless(무상태)

HTTP는 무상태이며 REST는 HTTP를 기본으로 하기 때문에 무상태이다.

클라이언트의 상태(State)를 서버에 저장하지 않는 것을 무상태라고 표현하고

서버에서 클라이언트의 요청을 완전히 별개의 것으로 인식하고 처리한다.

따라서 이전의 요청이 다음의 요청에 연관되지 않고 처리 방식에 일관성을

부여하고 부담이 줄어든다.

3. Cacheable(캐시 처리 가능)
HTTP의 캐싱 기능을 적용할 수 있어 대량의 요청을 효율적으로 처리할 수 있다.

캐시를 활용하여 응답 시간이 빨라지고 성능, 서버의 자원 이용률을 향상할 수 있다.
 
4. Layered System(계층화)
클라이언트는 REST API 서버만 호출하며 REST 서버는 다중 계층 구성이 가능하다.

API 서버는 순수 비즈니스 로직을 수행하고 이의 앞단에서 보안, 로드 밸런싱, 암호화,

사용자 인증 등을 활용해 구조에 유연성을 줄 수 있다.
 
5. Code-On-Demand
서버로부터 스크립트를 받아서 클라이언트에서 실행한다.

(필수 요건 아님)
 
6. Uniform Interface(인터페이스 일관성)
URI를 통해 자원 조작을 통일되고 한정적인 인터페이스로 수행한다.

HTTP 표준 프로토콜에 따르는 모든 플랫폼에서 사용이 가능하며 특정

언어나 기술에 종속되지 않는다.

REST API의 장단점

장점

1. 독립적인 언어와 플랫폼
2. REST API 메시지를 통해 의도를 쉽게 파악 가능
3. REST가 지원하는 프레임워크나 언어 등 없이 구현 가능
4. HTTP로 기존 웹 인프라를 사용 가능
5. 서버와 클라이언트의 역할을 명확하게 분리
6. 다양한 서비스 디자인에서 생길 수 있는 문제 최소화

단점

1. 표준이 존재하지 않음(보안, 정책 등)
2. HTTP프로토콜만 사용 가능

마치며...

얼마 전 회사에 서류합격을 통지받고 면접을 볼 수 있는 기회가 있었다. 지금껏 개발을 해왔지만 정작 이론에 대한 부분은 약하다는 것을 느끼게 되었고 면접결과 역시 좋지 못했다. 한번에 잘 되리라 생각하진 않았지만 생각했던 것 보다 모르는 이론이 너무나도 많았던 것 같다... 기술면접에서 REST API의 특징을 말하는 부분에서 시원하게 답변하지 못했고 이 포스팅을 시작으로 이론공부도 꾸준히 해야겠다!

누적합 알고리즘

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

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

누적합 알고리즘 동작방식

• 접두사 합(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을 다시 보며 복습해야겠다...