자료구조 & 알고리즘

이 글은 저의 생각을 적은 것이 아닌 알고리즘을 공부할 때 참고하기 위해 작성한 글입니다.

나는 평소 코딩 테스트 문제를 풀면서 자료구조와 알고리즘의 차이를 정확하게 무엇인지 생각해본 적이 없다.

그럼 둘의 차이는 무엇일까?

자료구조

메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁긍적인 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다.

구조에는 Stack, Queue, Graph, Tree 등이 있다.

알고리즘

특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표로 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.

알고리즘의 종류로는 이진 탐색, 최단 거리 찾기 등 여러 알고리즘이 있다.

쉽게 말하면 자료구조는 데이터를 상황에 맞게 저장하기 위한 구조이고, 알고리즘은 자료구조에 있는 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 방법들의 모임이라고 볼 수 있다.

자료구조와 알고리즘이 왜 중요한가? 바로 문제 해결 능력을 기를 수 있기 때문이다.
그리고 문제 해결 능력은 개발자에게 정말 중요한 역량이다.

또한 자료구조와 알고리즘은 변하지 않기 때문에 알고나면 유용하게 사용할 수 있다!

문제 해결 능력을 세부적으로 정리하면 다음과 같다.

• 논리적 사고: 어떤 현상에 대해서 추론하고 구조화하여 해결방법을 내놓음 (해결 방법의 절차가 올바른가)

• 전산화 능력: 현실에 있는 것을 소프트웨어로 구현하는 능력 (컴퓨터적 사고)

• 엣지 케이스 탐색: 예외 상황을 얼만큼 잘 찾는지
  
  

적절한 자료구조를 사용해야 한다.

위에서 말했듯이 자료구조에는 특정 구조들이 존재한다. 이 구조들을 상황에 맞게 사용하지 않으면 메모리를 비효율적으로 느리게 만들 수 있다. 따라서 상황에 대한 적절한 구조를 적용시켜야 한다.

영화 예매에 자료구조를 적용하면

• 영화를 검색한다. -> Trie
• 고객이 많을 경우 줄을 서야한다. -> Queue
• 고객은 좌석을 선택할 수 있어야한다. -> HashTable
  
  

자료구조의 종류

자료구조의 종류에는 단순 구조, 선형 구조, 비선형 구조로 나뉜다.
추가로 파일 구조도 있지만 이 글에서는 다루지 않을 것이다.

1. 단순 구조
   정수, 실수, 문자열, 논리

2. 선형 구조
   배열, 연결 리스트, 스택, 큐

3. 비선형 구조
   트리, 그래프

단순 구조는 기본적인 개념들이라 따로 정리는 하지 않겠다.

선형 구조

선형 구조는 한 원소 뒤에 하나의 원소만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가진다.

비선형 구조

비선형 구조는 원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절하다.
컴퓨터의 폴더 구조, 인간관계 등을 나타낼 때 적절하다.

시간 복잡도

고려할 것이 많아지면서 프로그램의 성능을 정확히 파악하는 것이 불가능하다.
그래서 컴퓨터 과학자들은 대략적인 성능을 비교하기 위한 상대적인 표기법을 사용하기로 했다.
그것이 바로 Big-O 표기법이다.

Big-O 표기법

시간 복잡도를 나타내기 위한 방법 중 하나이다.

표기할 때 2가지만 기억하면 된다고 한다.

1. 상수항은 무시

빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 상수항 같은 사소한 부분은 무시한다.

2. 가장 큰 항 외엔 무시

빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.

추가로 JavaScript에서 성능을 측정하기 위해서는 Date 객체를 사용하면 된다.

const start = new Date().getTime(); // 시작 시간을 구함
const end = new Date().getTime(); // 끝나는 시간을 구함
console.log(end - start) // 걸린 시간

선형 구조

배열

• 연관된 데이터를 연속적인 형태로 구성된 구조를 가진다.
• 배열에 포함된 원소는 순서대로 번호(index)가 붙는다.
• 고정된 크기를 가지며 일반적으로 동적으로 크기를 늘릴 수 없다. - 자바스크립트는 가능함!
• 찾으려는 원소의 index를 알고 있다면 O(1) (상수 시간)으로 원소를 찾을 수 있다.
• 원소를 삭제하면 index에 빈자리가 생긴다.

배열을 추가, 삭제 할때에는 최대 O(n)선형 시간만큼 걸리기 때문에 추가, 삭제가 반복되는 로직이라면 배열 사용을 권장하지 않는다.

그럼 어떨때 사용해야 하나요?

배열은 탐색이 많은 경우에 사용하면 유리하다.

그럼 추가와 삭제가 반복되는 로직이라면 어떻게 해야할까?

바로 연결 리스트를 사용하면 된다.

연결 리스트

• 각 요소를 포인터로 연결하여 관리하는 선형 자료구조
• 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.
• 탐색은 O(n)이 소요
• 추가 삭제는 O(1)이 소요
• Singly Linked List, Double Linked List, Circular Linked List가 존재한다.

Singly Linked List

• Head에서 Tail까지 단방향으로 이어지는 연결 리스트
• 헤드 포인터: 가장 첫번째 출발점
• 마지막 노드의 Tail이 NULL이면 끝을 의미

Double Linked List

• 양방향으로 이어지는 연결 리스트
• Singly Linked List보다 자료구조의 크기가 조금 더 크다.
• 이전과 다음 노드를 둘다 가리킴

Circular Linked List

• 다른 연결 리스트와 한가지 다른점은 Tail이 Head로 연결되는 것이다.
• 메모리를 절약할 수 있고, 원형 큐 등을 만들때도 사용한다.

스택

• LIFO(Last In First Out) 개념의 선형 자료구조
  Push: 요소를 넣음
  Pop: 요소를 뺌
  Top: 맨 위에 있는 요소

스택을 쓰는 대표적인 예시로는 스택 메모리가 있다.
배열로 표현하면 적절함 (스택은 중간 요소의 추가 삭제를 하지 않기 때문에 배열과 잘맞음 + 동적으로 크기 조절)

큐

• First In First Out이라는 개념을 가진 선형 자료구조
• Linear Queue와 Circular Queue가 존재한다.
  Front: 맨 앞
  Rear: 맨 뒤
  EnQueue: 큐에 요소를 추가
  DeQueue: 큐에서 요소를 뺌

큐를 배열로 표현하면 공간이 무한대로 늘어날 수 있기 때문에 원소를 앞당기는 작업이 필요한데 O(n)선형 시간이 소요됨 = 비효율적 (하지만 코테에서는 배열로 구현하는 것이 간단해서 추천)

연결 리스트로 구현하면 Head = Front, Tail = Rear로 볼 수 있다. (index 걱정 안해도 됨)

shift 함수는 사용하지 않기 (선형 시간이 소요돼서 비효율적)

자바스크립트에서 Circular Queue는 별로 안 씀

해시 테이블

키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형 자료구조
삽입은 O(1)상수 시간, 키를 알고있으면 탐색, 삭제도 O(1)상수 시간으로 수행

각 테이블에 해당하는 인덱스를 Bucket이라고 한다.
테이블의 요소는 키와 값을 저장하고 있어야 한다.

해시 함수

입력받은 값을 특정 범위 내 숫자로 변경하는 함수
따로 구현 방법은 없고 마음대로 정하면 됨 ex) 입력받은 문자열을 각 문자열의 아스키 코드를 더한 값을 해시로 정할 수 있음

해시 테이블의 문제점

해시 함수의 결과가 동일하여 겹치면 해시 충돌이 일어난다.

해시 충돌 해결법

• 선형 탐사법
  충돌이 발생하면 옆으로 한 칸 이동
• 제곱 탐사법
  충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동
• 이중 해싱
  충돌이 발생하면 다른 해시 함수를 이용한다.
• 분리 연결법
  버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가
  

그럼 해시 테이블은 언제 사용하는가?

배열의 경우 index를 모를 경우 탐색에 O(n)이 걸리고, 연결 리스트도 O(n)의 시간복잡도가 걸린다.
반면 해시 테이블은 키를 통해서 삽입, 삭제, 탐색이 모두 O(1)이다. 최악의 경우는 탐색에 O(n)이 걸릴 수도 있지만 다른 구조보다 안정적이다.

비선형 구조

그래프

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
정점(Node) 집합과 간선(Edge) 집합으로 표현할 수 있다.
Ex) 인물 관계도, 지하철 노선도
인물 = 정점
관계도 = 간선

그래프의 특징

• 정점은 여러 개의 간선을 가질 수 있다.
• 크게 방향 그래프(간선의 방향이 존재)와 무방향 그래프(간선의 방향이 존재하지 않음)로 나눌 수있다.
• 간선은 가중치를 가질 수 있다.
• 사이클이 발생할 수 있다. (무한 루프에 빠지지 않도록 사이클을 찾아야 함)

방향에 따른 분류

무방향 그래프

• 양방향으로 이동 가능
• (A,B)와 (B,A)는 같은 간선으로 취급

방향 그래프

• 간선에 방향성이 존재하는 그래프
• 양방향으로 갈 수 있더라고 (A,B)와 (B,A)는 다른 간선으로 취급
  
  

연결 상태에 따른 분류

연결 그래프

• 모든 정점이 서로 이동 가능한 상태인 그래프 (끊어진 곳이 없음)

비연결 그래프

• 특정 정점쌍 사이에 간선이 존재하지 않는 그래프 (끊어져있음)

완전 그래프

• 모든 정점끼리 연결된 상태인 그래프 (마법진)

사이클

그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분 (무한 루프 가능)

그래프의 구현 방법

인접 행렬, 인접 리스트 방식으로 구현 가능

인접 행렬

• 2차원 배열을 만들고 false로 초기화
• 연결됨을 true로 나타냄
• 열 부분을 시작 정점, 행 부분을 도착 정점으로 나타냄
• 가중치를 넣으려면 true, false가 아니라 null과 가중치 값을 넣으면 됨
• 무방향 그래프를 구현하려면 모든 값을 대칭으로 넣어주면 됨

인접 리스트

• 정점의 수만큼 배열을 만들고 연결할 정점을 배열에 추가하면 됨
  
  

트리

방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 구조를 가지고 있다.
Ex) 조직도, 디렉터리 구조

Root: 가장 상위에 위치하는 정점
Node: 정점
Leaf Node: 더 이상 자식이 없는 정점
Level: Root로부터 몇번째 깊이인지를 나타냄
Degree(차수): 한 정점에서 뻗어나가는 간선의 수

트리의 특징

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
• 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
• 루트에서 특정 정점으로 가는 경로는 유일하다.

이진 트리 (탐색을 위한 알고리즘에 많이 쓰인다.)

각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.

• 완전 이진트리: 마지막 레벨을 제외하고 모든 정점이 채워져있는 트리
• 포화 이진트리: 마지막 레벨도 채워져있음
• 편향 트리: 한 방향으로만 정점이 이루어짐

일반적인 이진트리를 사용하는 경우는 많지 않다. 다음 자료구조에 응용된다.

• 이진 탐색 트리
• 힙
• AVL 트리
• 레드 블랙 트리

트리의 구현 방법

그래프와 마찬가지로 인접 행렬, 인접 리스트 방식으로 구현 가능
1차원 배열 또는 링크가 2개 존재하는 연결리스트로 구현

배열

// 편의상 0번 인덱스는 비워둠
왼쪽 정점 = index * 2
오른쪽 정점 = inex * 2 + 1
부모 정점 = floor(index / 2)

연결 리스트는 기존 연결리스트의 next 대신 left, right로 연결해서 사용 가능

힙

우선순위 큐

FIFO인 큐와 다르게 우선 순위가 높은 요소가 먼저 나가는 큐
자료구조가 아니고 개념이다.

우선순위 큐를 구현하는데 힙이 적합하다.

힙은 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때
바로 정렬되는 특징이 있다.

힙의 특징

• 우선순위가 높은 요소가 루트가 되고 가장 먼저 나가는 특징을 가진다.
• 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있다. (내림차순, 오름차순 차이)
• JS에서는 직접 구현해야 함

힙 요소 추가 알고리즘

• 요소가 추가될 때는 트리의 가장 마지막 정점에 위치한다.
• 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
• 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
• 완전 이진 트리의 높이는 log N이기에 힙의 요소 추가 알고리즘은 O(log N) 시간복잡도를 가진다.

힙 요소 삭제 알고리즘

• 요소 제거는 루트 정점만 가능하다.
• 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
• 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
• 두 자식 정점이 우선위가 더 낮을 때 까지 반복한다.
• 마찬가지로 O(log N) 시간복잡도를 가진다.
  
  

트라이

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
Ex) 검색어 자동 완성, 사전 찾기

트라이의 특징

• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
• L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
• 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다는 단점이 있다.

트라이 구조

• 루트는 비어있다.
• 각 간선은 추가될 문자를 키로 가진다.
• 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
• 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.
  
  

정렬 알고리즘

요소들을 일정한 순서대로 열거하는 알고리즘

정렬의 특징

• 정렬 기준은 사용자가 정할 수 있다.
• 크게 비교식과 분산식 정렬로 나눌 수 있다.
• 대부분의 언어가 빌트인으로 제공해준다.
• 버블, 선택, 삽입, 머지, 힙, 퀵, 정렬 등 다양한 정렬 방식이 존재한다.

비교식 정렬

다른 요소와 비교를 통해 정렬하는 방식

버블 정렬

서로 인접한 두 요소를 검사하여 정렬하는 알고리즘
O(n^2)2차 시간의 시간복잡도를 가진다.

선택 정렬

선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘
O(N^2)2차 시간의 시간복잡도를 가진다.

삽입 정렬

선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘
O(N^2)2차 시간의 시간복잡도를 가진다.
복잡하지만 어느 정도 정렬이 되어있다는 가정하에 퀵 정렬보다도 빠른 성능을 보여준다.

분산식 정렬

요소를 분산하여 정렬하는 방식

분할 정복

문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략
다양한 알고리즘에 응용되는 전략이다.

합병 정렬

• 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘
• O(n log n) 시간복잡도를 가진다.
• 나눌 수 있을 때 까지 나누고 합치면서 정렬

퀵 정렬

• 분할 정복 알고리즘을 이용한 매우 빠른 정렬이지만 최악의 경우가 존재하는 불안정 정렬
• O(n log n) 시간복잡도를 가진다.
• 좌측과 우측을 나눠 작은 값은 왼쪽, 큰 값은 우측으로 정렬
• 첫번째 값이 기준점이 됨

자바스크립트에서 정렬은 sort()함수로 매우 사용하기 쉽다.
한 가지 조심해야 할 것은 그냥 정렬함수를 이용할 경우 아스키 문자 순서로 정렬된다.
따라서 a - b, b - a 조건을 추가해야 한다.

이진 탐색 알고리즘

선형 탐색

순서대로 하나씩 찾는 탐색 알고리즘
O(n) 시간복잡도가 걸린다.

이진 탐색

정렬 되어 있는 요소들을 반씩 제외하며 찾는 알고리즘
O(log n)의 시간복잡도가 걸린다.

이진 탐색의 특징

• 반드시 정렬되어 있어야 한다.
• 배열 혹은 이진 트리를 이용하여 구현할 수 있다.
• O(log n)인 만큼 빠르다.

배열은 left mid right로 구현

이진 탐색트리

• 이진 탐색을 위한 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

이진 탐색트리의 문제점

• 최악의 경우 한쪽으로 편향된 트리가 될 수 있다.
• 그런 경우 순차 탐색과 동일한 시간복잡도를 가진다.
• 이를 해결하기 우해 다음과 같은 자료구조를 이용할 수 있다.
  AVL 트리
  레드-블랙 트리

코테에서 거의 배열로 구현

너비 우선 탐색 (BFS)

그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘

특징

• Queue를 이용하여 구현할 수 있다.
• 시작 지점에서 가까운 정점부터 탐색한다.
• V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)다.

깊이 우선 탐색 (DFS)

그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘

특징

• Stack을 이용하여 구현가능
• 시작 정점에서 깊은 것 부터 찾는다.
• V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)다.

그리디 알고리즘

매 선택에서 지금 이순간 가장 최적인 답을 선택하는 알고리즘
최적해 보장해주지 않는다.

특징

• 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.
• 크루스칼, 다익스트라 알고리즘 등에 사용된다.
• 코테에서 직관적인 문제 풀이에 적합하다.
  
  

백트래킹 알고리즘

• 모든 경우의 수를 탐색하는 알고리즘
• DFS나 bfs를 이용할 수 있다.
• 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기(Pruning)라고 한다.
• 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다.
• 코딩 테스트에선 이를 고려하여 재귀로 작성해도 풀 수 있도록 문제를 제출하는 경우도 있다.
• 탐색에서 순환이 발생할 수 있다면 BFS를 이용하는 것이 편하다.

백트래킹에서는 가지치기가 효율성을 결정한다!

가지치기 잘하는 법

• 우선 모든 경우의 수를 찾을 수 있도록 코딩
• 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머지는 탐색하지 않도록 조건문을 작성
• 즉, 절대로 답이 될수 없는 것은 탐색을 종료한다.

백트래킹과 관련된 유명한 문제로 N-Queen 문제가 있다.
ex) 길이가 N인 체스판 위에 N개의 퀸이 서로 공격할 수 없도록 배치할 수 있는 경우의 수는?

동적계획법 알고리즘

• 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식
• 그리디나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미한다.
• Dynamic Programming(DP)라고도 부른다.
• 메모리를 많이 사용하는 대신 빠른 성능을 자랑한다.
• 두 가지 방법론이 있다.

1. 메모이제이션 = 이미 해결한 문제는 기록해두자!
2. 타뷸레이션 = 문제를 미리 해결하고 꺼내 쓰자!

메모이제이션

• 하향식 접근법
• 동적 계획법에서 작은 문제들의 결과는 항상 같다.
• 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션이다.

타뷸레이션

• 상향식 접근법
• 필요한 값들을 미리 계산해두는 것
• 메모이제이션은 필요할 때 계산한다면 타뷸레이션은 미리 계산해둔다.
• 보통 코딩 테스트에서는 메모이제이션을 쓰는 경우가 대부분이다.

동적 계획법 문제의 접근법

• 가장 작은 문제를 정의할 수 있는지?
• 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는지?

참고
https://slidesplayer.org/slide/14444350/
https://noahlogs.tistory.com/27