Algorithm & Data Structure Coding Test Preparation

이 공간은 코딩테스트를 준비하는 분들을 위해 자료구조와 알고리즘의 핵심 이론과 실전 문제 풀이를 정리한 곳입니다. 각 챕터별로 이론 설명과 예제, 그리고 실전 문제 풀이를 다룹니다.

---

목차

1. 자료구조
   • 선형 자료구조
     • 배열
     • 연결리스트
     • 스택과 큐
     • 데크와 우선순위큐
     • 해시 테이블
   • 비선형 자료구조
     • 그래프와 최단경로문제
     • 트리
     • 힙
2. 알고리즘
   • 정렬
   • 이진검색
   • 슬라이딩 윈도우
   • 그리디 알고리즘
   • 분할 정복
   • 다이나믹 프로그래밍

---

폴더 구조

.
├─ README.md
├─ notes/ # 요약 노트(개념/패턴/실수 모음)
│  ├─ cheatsheet_ds.md
│  ├─ cheatsheet_algo.md
│  └─ pitfalls.md
├─ templates/ # 문제 풀이/테스트/입출력 템플릿
│  ├─ solution_template.py
│  └─ io_helper.py
├─ data_structures/
│  ├─ linear/
│  │  ├─ array/
│  │  ├─ linked_list/
│  │  ├─ stack_queue/
│  │  ├─ deque_pq/
│  │  └─ hash_table/
│  └─ nonlinear/
│     ├─ graph_shortest_path/
│     ├─ tree/
│     └─ heap/
├─ algorithms/
│  ├─ sorting/
│  ├─ binary_search/
│  ├─ sliding_window/
│  ├─ greedy/
│  ├─ divide_and_conquer/
│  └─ dynamic_programming/
└─ tests/     # pytest 기반 단위 테스트
   ├─ test_ds.py
   └─ test_algo.py

---

자료구조

선형 자료구조

1. 배열 (Array)

• 정의: 동일한 자료형의 데이터를 연속적으로 저장하는 자료구조
• 특징: 인덱스를 통한 빠른 접근, 삽입/삭제는 느림
• 활용 예시: 리스트, 문자열, 행렬 등

2. 연결리스트 (Linked List)

• 정의: 각 노드가 데이터와 다음 노드의 포인터를 가지는 자료구조
• 특징: 동적 메모리 할당, 삽입/삭제가 빠름, 임의 접근은 느림
• 종류: 단일 연결리스트, 이중 연결리스트, 원형 연결리스트

3. 스택과 큐 (Stack & Queue)

• 스택: LIFO(Last-In-First-Out) 구조, 함수 호출, 괄호 검사 등 활용
• 큐: FIFO(First-In-First-Out) 구조, BFS, 캐시 등 활용

4. 데크와 우선순위큐 (Deque & Priority Queue)

• 데크: 양쪽 끝에서 삽입/삭제가 가능한 큐
• 우선순위큐: 우선순위가 높은 데이터가 먼저 나오는 큐 (힙으로 구현)

5. 해시 테이블 (Hash Table)

• 정의: 키-값 쌍으로 데이터를 저장, 해시 함수를 통해 빠른 검색
• 활용 예시: 딕셔너리, 집합, 중복 체크 등

비선형 자료구조

1. 그래프와 최단경로문제 (Graph & Shortest Path)

• 그래프: 정점과 간선으로 이루어진 자료구조, 방향/무방향, 가중치 등
• 최단경로: 다익스트라, 플로이드-워셜, 벨만-포드 등 알고리즘

2. 트리 (Tree)

• 정의: 계층적 구조, 루트-자식 관계, 이진트리, 이진 탐색 트리 등
• 활용 예시: 파일 시스템, 이진 탐색, 힙 등

3. 힙 (Heap)

• 정의: 완전 이진트리 기반의 우선순위 큐 구현 자료구조
• 종류: 최소 힙, 최대 힙

---

알고리즘

1. 정렬 (Sorting)

• 종류: 선택, 삽입, 버블, 병합, 퀵, 힙 정렬 등
• 특징: 시간복잡도, 공간복잡도, 안정성 등 비교

2. 이진검색 (Binary Search)

• 정의: 정렬된 배열에서 탐색 범위를 절반씩 줄여가며 찾는 알고리즘
• 활용 예시: 값의 위치, 조건 만족하는 값의 경계 찾기 등

3. 슬라이딩 윈도우 (Sliding Window)

• 정의: 일정 범위의 부분 배열/부분 문자열을 효율적으로 탐색
• 활용 예시: 부분합, 최장/최단 부분 배열 등

4. 그리디 알고리즘 (Greedy Algorithm)

• 정의: 매 순간 최적의 선택을 하는 알고리즘
• 활용 예시: 동전 거스름돈, 회의실 배정 등

5. 분할 정복 (Divide and Conquer)

• 정의: 문제를 작은 단위로 분할해 해결 후 합치는 방식
• 활용 예시: 병합 정렬, 퀵 정렬, 이진 검색 등

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

• 정의: 부분 문제의 정답을 저장해 중복 계산을 피하는 최적화 기법
• 활용 예시: 피보나치 수열, 최단 경로, 배낭 문제 등

---

참고 자료

• 파이썬 알고리즘 인터뷰 (이론)
• 백준, 프로그래머스 (실전 문제)

---