[알고리즘] 공부 목표 & 학습자료

 

학습 자료 - BaaaaaaaarkingDog 님의 강의 목차 및 알고리즘 공부 순서

https://blog.encrypted.gg/919

실전 알고리즘 강좌 리뉴얼에 대한 안내

 

 

0x00강 - 오리엔테이션
0x01강 - 기초 코드 작성 요령 I
0x02강 - 기초 코드 작성 요령 II
0x03강 - 배열
0x04강 - 연결 리스트
0x05강 - 스택
0x06강 - 큐
0x07강 - 덱
0x08강 - 스택의 활용(수식의 괄호 쌍)
0x09강 - BFS
0x0A강 - DFS
0x0B강 - 재귀
0x0C강 - 백트래킹
0x0D강 - 시뮬레이션
0x0E강 - 정렬 I
0x0F강 - 정렬 II
0x10강 - 다이나믹 프로그래밍
0x11강 - 그리디
0x12강 - 수학
0x13강 - 이분탐색

0x14강 - 투 포인터
0x15강 - 해쉬
0x16강 - 이진 검색 트리
0x17강 - 우선순위 큐
0x18강 - 그래프
0x19강 - 트리
0x1A강 - 위상정렬
0x1B강 - 최소 신장 트리
0x1C강 - 플로이드 알고리즘
0x1D강 - 다익스트라 알고리즘

0x1E강 - KMP 알고리즘 
0x1F강 - 트라이

---

1. 기초 알고리즘

목표: 알고리즘의 기본적인 동작 원리를 이해하고, 기초적인 구현 능력을 익힘.

주제

1. 시간 복잡도와 공간 복잡도
   • Big-O 표기법 이해.
   • 효율적인 코드 작성 방법 학습.
2. 정렬 알고리즘
   • 버블 정렬, 선택 정렬, 삽입 정렬.
   • 고급 정렬: 퀵 정렬, 병합 정렬.
3. 탐색 알고리즘
   • 선형 탐색 (Linear Search).
   • 이진 탐색 (Binary Search).

학습 팁

• 쉬운 문제부터 시작 (예: 배열 정렬, 특정 값 찾기).
• 정렬 알고리즘은 반드시 구현해 보기.

---

2. 자료구조

목표: 알고리즘을 효과적으로 구현하기 위한 자료구조를 익히고 활용.

주제

1. 배열과 문자열
   • 배열의 삽입, 삭제, 탐색.
   • 문자열 처리와 패턴 매칭.
2. 스택과 큐
   • 스택: 후입선출(LIFO) 구조.
   • 큐: 선입선출(FIFO) 구조.
   • 응용: 브래킷 밸런스 검사, BFS.
3. 연결 리스트
   • 단일 연결 리스트(Singly Linked List).
   • 이중 연결 리스트(Doubly Linked List).
4. 트리와 그래프
   • 이진 탐색 트리(Binary Search Tree).
   • 그래프 표현 방법 (인접 리스트, 인접 행렬).
   • DFS와 BFS 알고리즘.

학습 팁

• 자료구조를 직접 구현해 보며, 각각의 동작 원리를 이해.
• 스택과 큐는 알고리즘 문제에서 자주 사용되므로 꼼꼼히 학습.

---

3. 탐욕 알고리즘 (Greedy Algorithm)

목표: 탐욕적인 선택이 최적의 해를 보장하는 문제를 이해하고 풀이.

주제

1. 개념
   • 탐욕적 선택이란 무엇인가?
   • 탐욕 알고리즘이 작동하는 조건.
2. 대표 문제
   • 활동 선택 문제(Activity Selection Problem).
   • 최소 동전 거스름돈 문제.
   • 크루스칼 알고리즘(최소 신장 트리).

학습 팁

• 각 단계에서 탐욕적 선택이 항상 최적의 해를 보장하는지 이유를 분석.
• 잘못된 탐욕 알고리즘의 반례를 통해 한계를 이해.

---

4. 분할 정복 (Divide and Conquer)

목표: 문제를 작게 나누고 해결한 뒤 병합하는 방법을 학습.

주제

1. 개념
   • 문제를 분할, 정복, 병합.
2. 대표 알고리즘
   • 퀵 정렬 (Quick Sort).
   • 병합 정렬 (Merge Sort).
   • 이진 탐색 (Binary Search).

학습 팁

• 대표 문제들을 손으로 직접 풀이하면서 재귀적 사고를 훈련.
• 병합 정렬과 퀵 정렬의 차이점을 이해.

---

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

목표: 중복되는 계산을 줄이고 효율적으로 문제를 해결.

주제

1. 개념
   • 최적 부분 구조 (Optimal Substructure).
   • 중복되는 부분 문제 (Overlapping Subproblems).
   • 메모이제이션 (Top-Down)과 테이블화 (Bottom-Up).
2. 대표 문제
   • 피보나치 수열.
   • 최소 비용 경로 문제.
   • 배낭 문제(Knapsack Problem).

학습 팁

• 문제를 작은 부분 문제로 나누고, 이를 점진적으로 해결.
• 점화식(Recurrence Relation)을 직접 작성해 보기.

---

6. 그래프 알고리즘

목표: 그래프의 탐색 및 경로 문제를 해결.

주제

1. 그래프 탐색
   • 깊이 우선 탐색 (DFS).
   • 너비 우선 탐색 (BFS).
2. 최단 경로 알고리즘
   • 다익스트라 알고리즘 (Dijkstra's Algorithm).
   • 벨만-포드 알고리즘 (Bellman-Ford Algorithm).
3. 최소 신장 트리
   • 크루스칼 알고리즘.
   • 프림 알고리즘.

학습 팁

• 그래프 문제는 BFS, DFS를 확실히 이해하는 것이 핵심.
• 다익스트라와 벨만-포드의 차이점과 활용 상황 이해.

---

7. 고급 알고리즘

목표: 더욱 복잡한 알고리즘과 실전 문제를 해결.

주제

1. 백트래킹
   • 대표 문제: N-Queen 문제, 부분 집합 생성.
2. 분지 한정 (Branch and Bound)
   • 대표 문제: 여행하는 외판원 문제 (TSP).
3. 최적화 알고리즘
   • 유량 문제 (Ford-Fulkerson 알고리즘).
   • 이진 탐색 응용.

학습 팁

• 실전 문제 풀이를 통해 응용력을 키움.
• 어려운 문제일수록 단계별로 나누어 해결.

---

8. 실전 문제 풀이

목표: 알고리즘 대회 또는 코딩 테스트 준비.

주제

1. 문제 풀이 사이트 활용
   • 백준, 프로그래머스, LeetCode, Codeforces.
2. 알고리즘 문제 유형
   • 완전 탐색(Brute Force).
   • 최적화 문제 (Optimization).
   • 조합론 및 수학적 문제.

학습 팁

• 문제를 이해하고 적합한 알고리즘을 선택하는 훈련.
• 시간을 재며 제한 시간 내에 해결하는 연습.

---

학습 순서 요약

1. 기초 알고리즘: 시간 복잡도, 정렬, 탐색.
2. 자료구조: 스택, 큐, 트리, 그래프.
3. 탐욕 알고리즘: 간단하고 직관적인 문제 해결.
4. 분할 정복: 퀵 정렬, 병합 정렬, 이진 탐색.
5. 동적 프로그래밍: 점화식 작성과 메모이제이션.
6. 그래프 알고리즘: BFS, DFS, 최단 경로, 최소 신장 트리.
7. 고급 알고리즘: 백트래킹, 유량 알고리즘.
8. 실전 문제 풀이: 알고리즘 대회 및 코딩 테스트 준비.