> For the complete documentation index, see [llms.txt](https://leehyokyun.gitbook.io/openbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leehyokyun.gitbook.io/openbook/1-1.-cs-basic-1.md).

# 1-1. CS / Basic #1

CS 기초 및 알고리즘에 대하여 - 1장

***

### 📌 선형자료구조에 관하여

### 2. 자료구조와 알고리즘

> 프로그램의 본질적 의미이자, 문제를 해결하는 과정은 **어떤 자료구조를 활용하여 어떤 알고리즘을 통해 해를 도출할 것인가**에 대한 과정이다.

* **자료구조:** 데이터를 어떠한 구조로 어떻게 사용할 것인지에 대한 기본적인 방법이다. 변수와 배열도 하나의 자료구조이며, 어떠한 자료구조를 선택하느냐에 따라 구현방법 및 적용 알고리즘이 달라진다.
* **알고리즘:** 문제에 대한 고민 부터 해결까지 일련의 서사를 모두 담고 있는 체계이자 과정이다.
  * 중요한 것은 예외없이 특정 자료구조 및 데이터에 따라 확실하게 원하는 해를 도출해야 한다는 것.
  * 변수 3개의 평균을 구하는 알고리즘과 변수 n개, 변수 n개에 대한 배열의 평균을 구하는 알고리즘은 다르다.

### 3. 시간복잡도

> 더 좋은 알고리즘은 사용자 요구에 따라 달라질 수 있지만, 보통은 처리속도를 성능의 척도로 간주한다. 이때 성능의 척도를 시간복잡도라 한다.

* 컴퓨터 사양마다 알고리즘의 실행 시간은 다를 수 있기에, 알고리즘의 실행시간이 아닌 알고리즘 실행시간(성능)에 영향을 줄 수 있는 부분을 찾아 실행시간을 예측한다. 이때 보통 **반복문의 개수**가 성능에 많은 영향을 준다.
* **빅오 표기법에 따른 시간복잡도 나타내기**
  * 특정 자료구조에 대한 알고리즘은 입력값이 늘어나거나 주어진 자료구조의 크기가 늘어남에 따라 그 성능척도가 달라질 수 있다.
  * 최선의 경우를 **Big-Omega**, 최악의 경우를 **Big-O**, 평균의 경우를 **Big-Theta**로 표현하며 보통은 Big-O 표기법(최악의 경우)을 많이 활용한다.
  * 입력크기에 비례하여 선형적으로 소요시간이 늘어나는 O(N), 입력에 상관없이 일정한 O(1) 등을 시작으로, O(log N), O(Nlog N), O(N^2), O(2^N), O(N) 등의 시간복잡도가 존재한다.
  * Big-O 표기법의 경우 입력량에 따라 늘어나는 계산량을 최악의 경우로 표현한 것이고, 가장 영향을 많이 주는 척도 하나를 대표하여 표기한다.

### 4. 배열 (Array)

> **읽기 : O(1), 쓰기 : O(N)**

* 운영체제 측에선 최초 주소값을 기억하여 offset을 활용하여 데이터를 탐색하고 읽기에, 읽기(참조) 측면에서는 성능이 나쁘지 않다. 배열 크기에 상관없이 O(1)의 시간복잡도를 지닌다.
* 크기를 미리 지정해두어야 하기에 메모리 공간적 효율이 좋지 않으며, 이후 데이터 쓰기 및 삭제작업이 별도로 이루어져 성능이 좋지 않다.

### 5. 연결리스트 (Linked List)

> **읽기 : O(N), 쓰기 : O(N)**

* 기존 배열의 메모리 연속적 할당과 크기 확장 등에 대한 단점을 보완하고자 도입된 자료구조이다.
* 과정적으로 노드의 데이터는 건드리지 않고 다음 포인터 주소만 변경하면 되기에 간단하지만, 이러한 데이터를 탐색하는 과정에서 순차적인 이동이 필요하여 O(N)의 선형복잡도를 가진다.
* 탐색작업이 오래 걸리기에 쓰기 작업의 시간 복잡도에도 영향을 주지만, 메모리 공간적 할당이나 절차적으로 보았을때는 기존 배열보다 더 간편하고 효율적이다.

### 6. 스택 (Stack)

> **First In, Last Out (FILO)**

* 되돌리기를 위한 수행작업 임시 저장, 문법검사 등 여러 알고리즘에 사용 가능하다.

### 7. 큐 (Queue)

> **First In, First Out (FIFO)**

* head, tail을 사용하여 이중 연결리스트(양방향)을 활용해야 효과적으로 활용 가능하다 (O(1)).
* 운영체제의 FIFO 스케쥴링 등 여러 알고리즘에서 사용 가능하다.

### 8. 덱 (Deque)

> **Head In/Out and Tail In/Out**

* 자유로운 데이터 삽입 및 제거가 가능한 자료구조이다.

### 9. 해시테이블 (Hash Table)

> **읽기 : O(1), 쓰기 : O(1)**

* 다수의 데이터를 메모리 공간의 낭비없이 효율적으로 저장하고자 해시함수를 통해 도출한 key값을 인덱스로 매핑하여 배열기반으로 저장하는 자료구조이다.
* 해시함수를 이용하여 추출한 key값과 인덱스를 매핑하여 저장한다.
* 배열을 기반으로 데이터를 저장하는 구조이지만, 배열이 가진 기존 메모리 효율 측면의 단점을 보완하기 위해 도입된 자료구조이다.
* 해시함수로 인한 충돌발생 시 **체이닝**(동일 key값에 대하여 연결리스트로 연결) 및 **개방주소법**으로 파훼한다.
* 해시함수가 그만큼 중요하고, 배열 기반 자료구조이며 "저장"의 효율에 중점을 두었기에 메모리 공간 자체는 많이 필요하다.
* **\[체이닝을 통한 데이터 탐색]**
  * 동일 key(인덱스)에 여러개의 데이터를 연결리스트로 연결하여, 원하는 데이터를 찾을 때까지 데이터를 탐색한다. 이 경우 시간복잡도는 O(N)이다.

### 10. Set

> 데이터 중복을 허용하지 않는 자료구조이다.

* 해쉬테이블 자료구조를 사용하여 해쉬셋이라고도 한다.
* key = value, 즉 데이터를 제거한다는 것은 결국 이와 동일한 key를 찾아 해당 요소를 제거하겠다는 의미이다.

***

### 📌 알고리즘 살펴보기

### 11. 재귀 (Recursion)

* **\[동작]** 자기자신을 참조한다. 재귀적 호출/재귀적 함수란 이러한 재귀용법을 사용하여 로직을 구성하였을 경우를 뜻한다.
* **\[CS - Call Stack]** 변수선언 및 함수호출 시 적재되는 메모리 공간이다. 재귀적 동작 진행할 경우 모함수가 종료될때까지 계속 적재된다. 종료 시에는 이미 실행완료한 자함수들은 순차적으로 Stack에서 제거된다.
* **\[재귀적 관점]**
  * **패턴A (단순반복):** 함수 호출할때마다 Stack 적재, 메모리 공간 낭비 및 성능 하락을 유발한다. (상향식 접근)
  * **패턴B (하향식 접근):** 하위 문제의 결과를 상위 문제 해 도출에 활용하는 관점이다. 이것이 재귀함수를 사용하는 본질적인 이유이다. (예: 팩토리얼, 배열의 합, 지수함수, 하노이탑)

### 12. 정렬 (Sorting)

> 무작위로 섞여있는 배열의 원소들을 정렬하는 방법이다.

* **\[버블정렬 (Bubble Sort)]**
  * 앞의 숫자와 뒤의 숫자를 비교해가면서 정렬, 한 단계마다 가장 오른쪽의 숫자가 정렬이 완료된 상태이다. 시간복잡도는 O(N^2)이다.
* **\[선택정렬 (Selection Sort)]**
  * 정렬되지 않은 구간을 순회하면서 가장 작은 원소를 선택, 이를 정렬되지 않은 첫번째 위치에 배치한다. 시간복잡도는 O(N^2)이다.
* **\[삽입정렬 (Insertion Sort)]**
  * 정렬된 구간과 정렬되지 않은 구간을 나누어, 정렬되지 않은 구간의 첫번째 원소를 정렬구간과 비교해가며 덮어쓰기 및 적절한 위치로의 삽입하는 과정을 반복한다. 시간복잡도는 O(N^2)이다.
* **\[병합정렬 (Merge Sort)]**
  * 분할정복(divide and conquer) 기법으로 문제를 분할하여 해결한다. 재귀적 접근을 통해 범위를 쪼갠 후에, 하향식으로 결과를 병합해나간다.
  * 문제의 범위를 반으로 쪼개어 log N \* 각 단계별 배열크기만큼 순회비교하므로, 이에 대한 시간복잡도는 O(N log N)이다.
* **\[퀵정렬 (Quick Sort)]**
  * 병합정렬과 마찬가지로 분할정복으로 문제를 분할하여 해결한다. 피벗 및 배열의 양 끝 인덱스, 비교를 위한 양쪽의 비교 인덱스를 사용한다.
  * 피벗과 비교해가면서 조건 만족 시 서로의 자리를 swap한다. 비교를 위한 양쪽의 비교 인덱스가 서로를 지나칠때, 피벗과 오른쪽 비교 인덱스를 바꾼다.
  * 이 단계까지 완료하였을 시점에, 자리를 옮긴 피벗(오른쪽 비교 인덱스 자리)보다 왼쪽의 수들은 그보다 작고, 오른쪽의 수들은 그보다 큰 수들이다. 즉 피벗으로 지정한 수의 정렬이 완료되며, 이를 범위분할하여 정복한다.
  * 평균적으로 범위분할 log N \* 분할 후 N 번 순회작업을 거쳐 O(N log N)의 성능을 보이지만, 피벗이 최악으로 치우칠 경우 O(N^2)이 된다.

### 13. 동적 프로그래밍 (Dynamic Programming)

> 재귀는 문제를 쪼개는 관점이며, 여기에 기억을 더한 "재귀의 최적화 방법론"을 동적프로그래밍이라 한다. 하향식 접근 시 memoization, 상향식 접근 시 tabulation이라 한다.

* **\[동적프로그래밍 - 메모이제이션 (Memoization)]**
  * 분할정복 및 재귀를 통한 문제해결은 함수호출로 인한 콜스택 차지 및 성능적으로 그리 좋지 못한 단점이 존재할 수 있다. (다만 크기가 매우 크거나 분할범위가 치우쳐있을 경우이며, 만약 분할정복이 아닌 다른 문제의 해결과정을 그대로 활용할 경우 중복처리 발생 가능성도 존재한다.)
  * 이러한 관점에서, 재귀적인 접근 방법이 곤란하다면 처리 결과를 기억하는 메모이제이션 방법을 사용하여 성능을 보완 할 수 있다. HashTable(O(1))을 활용하여 접근한다.
* **\[동적프로그래밍 - 타뷸레이션 (Tabulation)]**
  * 하향식 접근으로 재귀의 문제해결을 최적화한 과정이 메모이제이션이라면, 상향식 접근으로 재귀의 문제해결을 최적화한 과정이 타뷸레이션이다. 필요한 값을 테이블에 미리 모두 저장해두는 방식이다.

***

### 📌 비선형 자료구조에 관하여

### 14. 트리와 이진트리

* **\[트리 (Tree)]** 각 노드들이 계층적 관계를 형성하여 최종적으로 이어진 모양이 나무와 같은 모양을 하는 자료구조이다. 트리는 다수의 서브트리로 구성할 수 있으며, 더이상의 자식이 없는 터미널 노드(리프 노드)와 루트노드가 동일한 그 자체의 서브트리구조도 볼 수 있다.
* **\[이진트리 (Binary Tree)]** 각 노드들이 최대 2개의 자식노드만을 가지고 있는 트리구조이다. (자식노드가 없거나 1개 보유해도 이진트리)
* **\[포화이진트리 (Full Binary Tree)]** 이진트리의 최대레벨까지 존재하는 모든 노드가 꽉 채워져 있으며, 모든 리프노드가 동일한 깊이인 트리구조이다.
* **\[완전이진트리 (Complete Binary Tree)]** 이진트리의 최대레벨까지 모든 노드가 채워져 있으며, 최하층 리프노드들은 왼쪽부터 채워져있는 상태의 트리구조이다.
* **\[순회 (Traversal)]**
  * **전위순회 (Pre-order):** 루트노드를 최우선적으로 탐색, 그 후 왼쪽서브트리와 오른쪽서브트리를 순회하는 방법.
  * **중위순회 (In-order):** 왼쪽서브노드를 최우선적으로 탐색, 그 후 루트노드와 오른쪽서브트리를 순회하는 방법.
  * **후위순회 (Post-order):** 왼쪽서브노드를 최우선적으로 탐색, 그 후 오른쪽서브노드와 루트노드를 순회하는 방법.

### 15. 이진탐색 알고리즘 (Binary Search)

> 찾고자 하는 특정 값을 배열의 범위를 반으로 줄여 나가면서 탐색해나가는 알고리즘이다.

* 단, 배열이 정렬된 상태이어야 가능하다.
* 배열 자료구조의 특성상 메모리 효율이나 데이터 삽입/제거 성능 측면에서 비효율적이다.

### 16. 이진탐색트리 (BST - Binary Search Tree)

> 데이터 삽입, 제거, 탐색 성능을 모두 보완하기 위해 활용하는 자료구조이다.

* 기존 이진탐색 알고리즘의 배열정렬조건 및 해시테이블의 메모리 효율 단점을 보완한다.
* 이진트리의 구조를 가지면서, 각 노드의 왼쪽트리에는 이보다 작은 값만, 오른쪽트리에는 큰 값만 들어갈 수 있다. 이진탐색 알고리즘이 중간값을 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값이 위치한다는 점에서 원리가 유사하다.
* 단, 한 쪽으로 치우치면 연결리스트와 비슷한 성능을 보이고(O(N)), 완전이진트리 및 포화이진트리의 균형 구조여야 개선된 성능(O(log N))을 보인다. 모든 노드들은 데이터 중복이 불가능하다.
* **\[삽입]** 이진탐색트리 자료구조의 정의를 활용하여 삽입할 노드 자리를 구할때까지(삽입하고자 하는 자리의 노드가 없을때까지) 자리를 찾아 삽입한다.
* **\[제거]**
  * 터미널(리프) 노드 제거 시 그대로 제거한다.
  * 인터벌 노드 중 자식 노드가 1개 존재하는 노드 제거 시 인터벌 노드 제거 후 해당 자식 노드로 연결한다.
  * 인터벌 노드 중 자식 노드가 2개 존재하는 노드 제거 시 인터벌 노드 제거 후 왼쪽자식노드 중 가장 큰 값으로 연결한다.

### 17. 자가균형 이진탐색 트리 (Self-Balancing BST)

> 기존 이진탐색트리가 데이터 삽입 및 제거 시 균형이 깨질 위험이 있기에, 이를 보완한 자료구조(트리)이다. AVL Tree, Red-Black Tree가 존재한다.

* **\[AVL 트리]**
  * 이진탐색트리의 데이터 삽입/제거가 일어날때마다 불균형 여부를 판단하여 트리균형을 맞추는 트리구조이다.
  * LL(오른쪽으로 치우쳐져 있을때), RR(왼쪽으로 치우쳐져 있을때), LR(왼쪽으로 치우친 불균형), RL(오른쪽으로 치우친 불균형) 상태에 대해 적절한 회전을 처리한다.
* **\[Red-Black 트리]**
  * AVL트리에 비해 균형을 엄격하게 보지 않고, 데이터 삽입 및 제거 시 회전이 덜 발생하는 트리구조이다.
  * 데이터 삽입 시 높이조정 및 회전, ReColoring을 진행한다. (빨간색 노드가 연속적으로 오는 경우)
  * 데이터 제거 시 높이조정 및 회전, ReColoring을 진행한다. (검은색 노드를 제거하였을때 Black Height가 모두 달라지는 경우)
  * **\[Red-Black 트리 규칙]**
    1. 모든 노드는 빨간색 및 검은색 노드로 이루어진다.
    2. 루트노드는 반드시 검은색이다.
    3. 모든 터미널노드는 NILL 노드이며, 특정 노드의 자식노드가 없다면 NILL노드로 채운다.
    4. 모든 터미널(NILL) 노드는 검은색이다.
    5. 연속해서 빨간색 노드가 올 수 없고, 검은색 노드는 올 수 있다.
    6. 루트노드에서 터미널 NILL노드까지 마주치는 검은색 노드는 모두 동일해야 한다.

### 18. 우선순위 큐와 힙 (Priority Queue & Heap)

* **\[우선순위 큐]** 들어간 데이터 순서에 상관없이 우선순위가 높은 순서대로 데이터를 추출할 수 있는 자료구조이다. 힙 자료구조를 활용하여 구현한다.
* **\[힙]** 트리의 일종이며 완전이진트리이다. 루트노드를 기준으로 최소값이면 최소힙, 최대값이면 최대힙이다.
  * **삽입:** 완전이진트리에 맞게 왼쪽부터 노드를 채워나가며, 이후 부모노드와 우선순위를 비교해가면서 자리를 교체해나간다.
  * **제거:** 가장 마지막에 데이터를 삽입한 위치의 데이터를 루트노드로 추출하며, 이후 자식노드와 비교해가면서 우선순위를 재배치한다. O(log N)의 삽입/제거 성능을 보인다.

### 19. 힙정렬 (Heap Sort)

> 힙을 활용한 정렬 알고리즘이다.

* 최소힙을 통해 오름차순 정렬, 최대힙을 통해 내림차순 정렬이 가능하다. 단순히 힙을 사용하여 넣고 빼며, 이 추출한 값을 특정 저장소에 넣어준다.
* 퀵 정렬과 비슷한 O(N\log N)의 성능을 보이지만, 피벗이 따로 없기에 안정적이다. (퀵정렬의 피벗이 불안정하게 치우칠 때보다 유리하다)

### 20. 트라이 (Trie)

> 자식노드 개수에 제한이 없는 트리형태의 자료구조이다.

* 자동완성에 많이 활용하는 자료구조로, 루트노드부터 시작하여 1글자씩 자식노드의 단어와 자식노드(주소값)을 저장하여 가지치기를 한다.
* 단어의 끝은 `key = *`, `value = dummy(0)`을 삽입한다. 즉 온전한 단어를 찾기 위해 `key = *`인 자식노드를 탐색하여 내려간다.
* 성능은 글자수 k에 따라 결정되므로 O(k)이다.

### 21. 그래프 (Graph)

> 서로의 연결관계를 표현하는 자료구조이다.

* 그래프에서 각 정점의 부모/자식간 계층관계 표현과 사이클 제거 시 트리가 된다. 연결관계의 방향성 여부에 따라 방향그래프, 무방향그래프로 분류한다.
* **\[그래프를 탐색하는 방법]**
  * **DFS (깊이우선탐색):** Stack과 Hash Table(방문접점기록)을 활용하여 정점들을 탐색한다. 재귀적으로 탐색을 진행하면서, 인접 정점들 중 탐색하지 않은 정점들을 대상으로 깊이 끝까지 파고든다. 핵심은 인접노드를 동시에 탐색하지 않고, 인접노드의 인접노드 경로로 계속 깊게 진입한다는 점이다.
  * **BFS (너비우선탐색):** Queue와 Hash Table(인접노드순회기록)을 활용한다. 재귀적으로 탐색을 진행하면서 Queue에 인접노드를 순회 기록하고, Dequeue하면서 인접한 노드들을 우선적으로 방문해나간다.
* **\[시간복잡도]** 보통은 정점의 인접정점을 순회할때마다 비용을 소모한다. 간선 1개에 서로 인접하는 정점은 2개이므로 O(V+2E)로 표기한다.
* **\[사이클(Cycle)의 사전적 정의]** 그래프 내에서 시작 정점과 끝 정점이 동일한 폐경로(closed path)를 말한다. 즉, 어떤 정점에서 출발하여 간선을 따라 이동했을 때 출발점으로 되돌올 수 있는 경로를 뜻한다.

### 22. 가중그래프 (Weighted Graph)

> 간선에 크기(거리 혹은 비용)를 저장하는 그래프이다.

* 방향그래프 환경에서 이동 방향에 따라 가중치는 서로 달라질 수 있다.

### 23. 다익스트라 알고리즘 (Dijkstra)

> 가장 빠른 경로를 찾는 대표적인 최단경로 알고리즘 중 하나이다.

* 출발지점을 지정한 후, 그 지점의 인접노드 중 가중치 합이 가장 작은 노드로 이동해가면서 출발지점에서 모든 지점으로의 최단 경로를 구한다.
* 출발지점은 항상 고정이며, 방문 후 인접노드들의 가중치 합을 계산해나간다. 계산 이후 가중치 테이블에서 출발지점 기준 가장 값이 작은 노드를 다음 방문지로 지정한다.

### 24. 탐욕 알고리즘 (Greedy)

> 매 선택 시 특정한 기준으로 가장 좋은(최적의) 선택지를 선택하여 해를 구하는 방법이다.

* 매트로이드 문제 상황에 대한 접근방법이다.
* **탐욕스러운 선택 속성**(앞의 선택이 뒤 선택에 영향을 주지 않는다) 및 **최적 부분 구조 조건**(문제의 최적해가 부분 문제에서도 최적해이다)을 모두 만족할때 최적의 해를 도출할 수 있다.
* 각 순간의 선택 혹은 그 선택의 기준은 변하지 않으며, 매 순간의 최선이 최종 최적해를 보장하는 조건 하에 사용한다.

### 25. 최소신장트리 (MST - Minimum Spanning Tree)

> 모든 정점들을 사이클 없이 연결하되 가중치의 합을 최소로 만드는 그래프(트리) 구조이다. (E = V-1)

* 프림(Prim) 및 크루스칼(Kruskal) 알고리즘을 활용하여 구현하며, 무방향 그래프에서 최소 가중치를 찾아낸다.
* 최초 지점 기준의 최단거리를 구하는 다익스트라 알고리즘과 달리, MST는 전체를 연결하는 총 비용의 최적화에 집중한다는 점에서 차이가 있다.

### 26. 최대유량문제 (Network Flow)

> 각 정점간에 흐를 수 있는 용량이 정의되어 있을때 최대로 흘려보낼 수 있는 유량의 총합을 도출하는 문제이다.

* 에드먼드 카프 알고리즘은 BFS와 탐욕 알고리즘을, 포드 폴커슨 알고리즘은 DFS와 탐욕 알고리즘을 조합하여 사용한다.
* 흐른 유량만큼 역방향 상수도관을 가상으로 설치하며, 이는 최적의 경로를 찾기 위한 상쇄(unDo) 개념으로 사용한다.

### 27. 인터벌 스케쥴링 (Interval Scheduling)

> 겹치는 세션없이 가장 많은 세션을 배정할 수 있는 방법을 찾는, 탐욕 알고리즘의 대표적 케이스이다.

* "종료시간이 가장 이른 세션"부터 우선적으로 선택해 나가는 전략을 취한다.

### 28. 비트마스킹 (Bitmasking)

* **\[개념]** 기존의 원시자료형보다 더 적은 메모리로 빠른 연산을 기대할 수 있는 비트 활용 기법이다. (AND `&`, OR `|`, XOR `^`, 왼쪽시프트 `<<`, 오른쪽시프트 `>>`)
* **\[외판원 문제 (TSP)]** 최소 비용의 순회 경로를 추출하는 NP-Hard 문제이다. 모든 노드를 단 한번씩만 방문하고 출발 노드로 돌아오는 최소비용 경로를 구한다. 동적 프로그래밍(DP)의 메모이제이션과 비트마스킹을 결합하여 기존 O(N^N)의 복잡도를 O(N^2 \* 2^N) 수준까지 개선할 수 있다.

***

### 📌 결정문제, N, NP 체계의 이해

* **\[결정문제]** 어떠한 문제가 주어졌을때, Yes or No로 대답할 수 있는 문제이다.
* **\[최적화문제]** 최소비용, 가장 짧은 경로 등 최적의 해를 구하는 문제이다. 대부분의 경우 적절한 한계치를 설정하여 결정문제로 바꾸어 해결할 수 있다.
* **\[P문제]** 다항시간(Polynomial Time) 내에 결정론적 튜링 방식을 활용하여 답을 구할 수 있는 쉬운 문제이다. 분기처리에 의해 다음 상태가 유일하게 결정되는 로직을 사용한다.
* **\[NP문제]** 비결정론적 튜링 방식을 활용하여 다항시간 내 답을 구할 수 있는 문제이다. 결정론적 방식을 쓰면 다항시간 내 풀기 어렵지만(지수/팩토리얼 시간 소요), 주어진 힌트나 상황에 대한 '검증' 자체는 다항시간 내에 가능하다.
* **\[NP-Hard 문제]** 어떤 NP문제들을 해결하기 위해 다른 문제로 환원(Reduction)하여 접근할 수 있을 때, 그 환원해 들어간 대상 문제를 일컫는다. 비결정론적 튜링 머신으로도 다항 시간 내 해를 도출할 수 없는 매우 어려운 영역이다.
* **\[NP-Complete 문제]** NP-Hard 문제들 중에서도 명확히 NP문제군에 포함되는 균형점을 말한다. 비결정론적 방식을 가동하면 어떻게든 다항시간 내 해결 자체는 가능한 문제들 중 가장 어려운 문제들이다.

***

### 📌 Appendix. 알고리즘의 구현 전략

* **전략 #1. 단계적 접근**
  * 예외의 경우 혹은 동작이 불가능한 상황에 대한 경계 조건을 중심으로 예외 처리를 먼저 구성한 뒤 상황별 분기 처리를 구현한다.
* **전략 #2. 이전의 구현로직을 활용한다**
  * 활용도가 높은 부분적 로직을 공통 메서드로 먼저 정의하고, 추가적인 기능을 구현할 때 이전에 만들어둔 검증된 구현 로직을 최대한 재사용한다.
* **전략 #3. 재귀와 재귀적 접근**
  * 큰 문제를 작은 범위로 쪼개어 나간다면 하향식(Top-Down), 처음부터 가장 작은 기본 단위부터 접근하여 Table에 채워나간다면 상향식(Bottom-Up)이다. 재귀적 접근에 기억 공간이 결합되면 그것이 곧 DP(메모이제이션/타뷸레이션)이다.
* **전략 #4. 객체적 접근**
  * 프로퍼티는 자료구조 그 자체로 다루고, 매개변수는 프로퍼티 구성에 필요한 최소 정보로 채우며, 반환값(`getter`)은 객체의 정제된 상태 정보를 넘기도록 명확히 분리한다.

***

### 📌 이 외 유의하면 좋은 정보들

#### 🔹 String vs StringBuilder vs StringBuffer

* **String:** 불변 객체. 변수 로딩 시 상수풀(Interned pool)에 저장된 불변 객체를 지칭하며 동일 리터럴은 재사용된다. 참조 속도는 안정적이나 문자열 변경 시 매번 새 객체가 생성된다.
* **StringBuilder:** 내부 버퍼가 가변적(`char[]`)이다. append 시 다른 문자배열에 복사 후 교체하는 배열 성격을 지닌다. 데이터 쓰기 작업 시 비용이 드는 대신 인덱스 참조 연산은 O(1)이며 단일 스레드에서 가장 빠르다.
* **StringBuffer:** 내부 구조는 StringBuilder와 같으나 멀티스레드 환경의 안전성을 보장하기 위해 `synchronized` 기반 동작을 수행한다. 단일 스레드 상황에서는 역으로 오버헤드가 발생할 수 있다.

#### 🔹 char vs String 변환 법칙

* `char` > `String`: `String.valueOf(char)` 사용
* `String` > `char`: `toCharArray()` 혹은 `charAt(0)` 사용
* 문제 해결의 최소 단위가 문자(`char`)이면 매개변수를 문자로 받고 내부에서 파싱하며, 문자열 단위 결합이 핵심이면 `String`으로 제어 흐름을 가져간다.

#### 🔹 Top-down vs Bottom-up의 진입점

* 문제 해결과정의 진입점이 가장 큰 최종 문제라면 하향식(Top-Down), 가장 작은 기저 상태부터 시작한다면 상향식(Bottom-Up)이다. 분할정복의 경우 대개 재귀적 하향식 흐름을 탄다.

#### 🔹 ArrayList vs LinkedList 선택 기준

* **ArrayList:** 내부가 연속된 메모리(동적 배열) 구조이므로 정렬, 인덱스 탐색, 데이터 반복 조회가 주 목적일 때 무조건 선택한다.
* **LinkedList:** 비연속 메모리(노드 연결) 구조이므로 데이터의 중간 삽입과 삭제가 매우 빈번하게 발생하는 시나리오에 한해 선택한다.

***

### 📊 자료구조별 Big-O 성능 평점표

| 자료구조                        | 접근 (Access) | 탐색 (Search) | 삽입 (Insert) | 삭제 (Delete) | 비고                               |
| --------------------------- | :---------: | :---------: | :---------: | :---------: | -------------------------------- |
| **배열 (Array)**              |     O(1)    |     O(N)    |     O(N)    |     O(N)    | 인덱스 접근 빠름, 중간 삽입·삭제 시 이동 필요      |
| **연결 리스트 (Linked List)**    |     O(N)    |     O(N)    |     O(1)    |     O(1)    | head/tail 기준 연산은 매우 빠름           |
| **스택 (Stack)**              |     O(N)    |     O(N)    |     O(1)    |     O(1)    | top에서만 연산 가능 (LIFO 구조)           |
| **큐 (Queue)**               |     O(N)    |     O(N)    |     O(1)    |     O(1)    | front/rear에서만 연산 가능 (FIFO 구조)    |
| **우선순위 큐 (Priority Queue)** |     O(N)    |     O(N)    |   O(log N)  |   O(log N)  | 주로 힙(Heap) 구조를 기반으로 작동           |
| **힙 (Heap)**                |     O(N)    |     O(N)    |   O(log N)  |   O(log N)  | 최댓값/최솟값에 대한 즉각 접근(O(1)) 제공       |
| **이진트리 (Binary Tree)**      |     O(N)    |     O(N)    |     O(1)    |     O(1)    | 자체 정렬 구조 없음, 전체 순회 필요            |
| **이진탐색트리 (BST)**            |   O(log N)  |   O(log N)  |   O(log N)  |   O(log N)  | 균형 유지 기준이며, 한쪽 치우침 시 O(N) 가깝게 붕괴 |

***

### 📊 정렬별 작동원리와 Big-O 성능 평점표

| 정렬 알고리즘   | 작동 원리 (간략 요약)                             |   평균 복잡도  |   최악 복잡도  |   최선 복잡도  |  공간 복잡도  |
| --------- | ----------------------------------------- | :-------: | :-------: | :-------: | :------: |
| **버블 정렬** | 인접 두 원소를 비교하여 교환. 큰 값이 매 단계마다 맨 뒤로 이동.    |   O(N^2)  |   O(N^2)  |    O(N)   |   O(1)   |
| **선택 정렬** | 정렬되지 않은 구간을 전체 순회하며 최소값을 찾아 맨 앞으로 교환.     |   O(N^2)  |   O(N^2)  |   O(N^2)  |   O(1)   |
| **삽입 정렬** | 데이터를 순차적으로 비교하며 이미 정렬된 서브 배열의 적절한 위치에 삽입. |   O(N^2)  |   O(N^2)  |    O(N)   |   O(1)   |
| **병합 정렬** | 배열을 최소 단위까지 반으로 쪼갠 뒤 재귀적으로 병합하며 정렬합치기 수행. | O(Nlog N) | O(Nlog N) | O(Nlog N) |   O(N)   |
| **퀵 정렬**  | Pivot 기준 대소 분할 후 자리를 swap하며 범위를 좁혀 정복.    | O(Nlog N) |   O(N^2)  | O(Nlog N) | O(log N) |
| **힙 정렬**  | 데이터를 완전이진트리 힙으로 빌드한 뒤 루트 노드를 반복 추출.       | O(Nlog N) | O(Nlog N) | O(Nlog N) |   O(1)   |


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation by asking a question.

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://leehyokyun.gitbook.io/openbook/1-1.-cs-basic-1.md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.