[Java/알고리즘] 알고리즘을 들어가며..

알고리즘이란?

• 문제를 해결하기 위해 사용되는 절차 또는 방법
• 프로그래밍에서 알고리즘은 효율적인 문제 해결의 핵심 요소. 같은 결과를 내더라도 알고리즘에 따라 수행 시간과 메모리 사용량에 큰 차이가 발생한다.
• 수학의 공식처럼, 특정 형태 또는 구조를 갖는 프로그래밍 문제에는 공식화된 알고리즘이 존재함.

 

한 문제를 푸는 방법은 무수히 많다 → 따라서, 가장 적합한 알고리즘을 선택하려면 평가 기준을 이해하고 있어야 한다

**알고리즘**
│
├─ **1. 정렬 (Sorting)**
│ ├─ 1) 단순 정렬( O(n²)): 버블 / 선택 / 삽입
│ ├─ 2) 효율 정렬(O(n log n)): 퀵 / 병합 / 힙 / 트리
│ └─ 3) 특수 정렬: 계수 / 기수 / 버킷
│
├─ **2. 탐색 (Searching)**
│ ├─ 1) 기본 탐색
│ │ ├─ 선형 탐색
│ │ ├─ 이진 탐색
│ │ └─ 해시 탐색
│ ├─ 2) 상태공간·완전 탐색
│ │ ├─ 브루트 포스
│ │ ├─ 백트래킹
│ │ │ ├─ 순열/조합/부분집합 생성
│ │ │ ├─ 제약 충족(스도쿠, N-Queen 등)
│ │ │ └─ 비트마스크(부분집합 표현)
│ │ └─ 이분 탐색(Parametric Search)
│ ├─ 3) 비선형 구조 탐색
│ │ ├─ 트리 순회: 전위/중위/후위
│ │ └─ 그래프 탐색: DFS / BFS 
│ └─ 4) 자료구조 특화
│ └─ 이진 탐색 트리(BST): 삽입 / 삭제 / 탐색
│
├─ **3. 그래프 알고리즘 (Graph Algorithms)**
│ ├─ 1) 그래프 표현: 인접 리스트 / 인접 행렬
│ ├─ 2) 그래프 탐색: DFS / BFS ← (탐색 2-3과 연결)
│ ├─ 3) 최단 경로: 다익스트라 / 벨만–포드 / 플로이드–워셜
│ ├─ 4) 서로소 집합 : 유니온 파인드 - Union by Rank, Union by Size
│ ├─ 5) 최소 신장 트리(MST): 크루스칼 / 프림
│ ├─ 6) 위상 정렬(Topological Sort)
│ ├─ 7) 강한 연결 요소 : SCC, Kosaraju/Tarjan
│ ├─ 8) 네트워크 플로우: Ford–Fulkerson / Edmonds–Karp
│ └─ 9) 최대 매칭: Hopcroft–Karp
│ 
│
└─ **4. 문제해결 전략 (Problem-Solving Strategies)**
  ├─ 그리디(Greedy)
  ├─ 분할 정복(Divide & Conquer)
  ├─ 동적 계획법(DP)
  ├─ 투 포인터 & 슬라이딩 윈도우
  └─ 이분 탐색 응용(Parametric Search)[전략]

알고리즘에 정답은 없고, 분류도 명확하진 않지만 최대한 여러 인사이트를 찾아보며 분류해본 결과가 다음과 같다..!

 

알고리즘 평가 기준

1. 시간 복잡도 (Time Complexity)
   • 알고리즘이 입력 크기 n에 따라 얼마나 빨리 동작하는지를 나타냄.
   • Big-O 표기법으로 표현하며, 주로 **최악의 경우(worst-case)**를 기준으로 계산.
   • 예: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
2. 공간 복잡도 (Space Complexity)
   • 알고리즘이 실행 중 필요한 메모리 양.
   • 공간을 늘리면 시간을 줄일 수 있고(예: 해시맵), 반대로 메모리를 줄이면 시간이 늘어나는 trade-off 관계.
3. 구현 복잡도
   • 협업 가능성과 유지보수를 고려한 코드 복잡도.
   • 너무 복잡한 알고리즘은 실무·테스트에서 오히려 불리할 수 있음.

 

코딩 테스트에서의 활용 팁

 

시간 복잡도와 실행 시간 감 잡기

시간 복잡도 입력 크기 n 대략적인 최대 n 한계 (1초 기준) 예시 알고리즘

O(1)	무관	무제한	해시 접근, 단일 연산
O(log n)	매우 큼	10¹⁸ 이상 가능	이진 탐색, 균형 트리
O(n)	최대 10⁸	1억	단일 루프, 해시맵
O(n log n)	최대 10⁶	100만	병합 정렬, 퀵 정렬
O(n²)	최대 10⁴	1만	완전탐색(이중 루프)
O(n³)	최대 500	500	플로이드–워셜
O(2ⁿ)	최대 20	20	부분집합, 백트래킹
O(n!)	최대 10~11	10~11	순열

• 1억 번 연산 ≈ 1초 (대략적인 기준)
• O(n²): n=10⁴ 이상이면 위험
• O(n log n): n=10⁶까지 안전
• O(n): n=10⁸까지 가능
• 데이터 크기 100,000 이상 → O(n²) 금지, O(n log n) 이하 알고리즘 필요
• 데이터 크기 1,000 이하 → 완전탐색(O(n²)~O(n⁴))도 가능
• 순열/조합 문제는 보통 데이터 크기를 작게 줌 → 백트래킹 사용
• 정렬 활용: sort 후 투 포인터, 이분 탐색 적용 가능
• 해시맵 활용: O(1) 접근으로 시간 절약 가능 (메모리 여유 필요)

이 시리즈에서는 각 알고리즘을 Java를 사용하여 구현하고, 설명하는 글을 작성할 예정.

(아마 그때그때 공부하는 내용을 정리할 꺼라 포스팅 순서는 뒤죽박죽이겠지만 시리즈에는 예쁘게 정리해둘게요!)