LG유레카 4기 5주차 회고 TIL4월 다섯째 주(4/27~5/3)

1. 주간 학습 핵심 (Core Topics)

• 그래프 심화 및 위상 정렬
• 분할 정복 (Divide & Conquer)
• 동적 프로그래밍 (DP) 기초

2. 상세 학습 내용

 그래프 및 위상 정렬 (Topological Sort) [04-27 ~ 04-29]

• 다익스트라(Dijkstra): 가중치가 있는 그래프에서 시작점으로부터 모든 정점까지의 최단 거리를 구하는 알고리즘입니다. PriorityQueue를 활용하여 가장 짧은 거리의 노드를 우선적으로 탐색하는 것이 핵심입니다.
• 플로이드-워셜(Floyd-Warshall): 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘으로, 경유지(k) → 출발지(i) → 도착지(j) 순서의 3중 for문 패턴을 숙지해야 합니다.
• 유니온 파인드(Union-Find): 서로소 집합을 관리하며, 두 원소가 같은 집합에 속해 있는지(연결 여부)를 빠르게 확인할 때 사용합니다.
• 위상 정렬 (04-29): 방향 사이클이 없는 그래프(DAG)에서 정점들을 선후 관계에 따라 정렬하는 알고리즘입니다. 진입차수(In-degree)와 큐(Queue)를 사용하는 구현 방식을 학습하였습니다.

분할 정복 (Divide & Conquer) [04-30]

• 문제를 더 이상 나눌 수 없을 때까지 반으로 나누어 각각 해결한 뒤, 결과를 다시 합쳐서 문제를 해결하는 패턴입니다.
• 재귀적인 구조를 활용하며, 병합 정렬이나 퀵 정렬의 기본 원리가 됩니다.

 동적 프로그래밍 (DP) 기초 [04-30 ~ 05-03]

• 핵심 개념: 큰 문제를 작은 문제로 나누고, 작은 문제의 정답을 저장(Memoization)하여 중복 계산을 방지하는 최적화 기법입니다.
• 주요 문제 패턴:
  • LIS (Longest Increasing Subsequence): 가장 긴 증가하는 부분 수열 찾기.
  • 배낭 문제 (Knapsack): 한정된 무게 내에서 가치의 합을 최대화하기.
  • 계단 오르기: 전형적인 점화식 구성 문제.

3. 학습 포인트 및 팁

• 암기해야 할 틀: 위상 정렬의 '진입차수 + 큐' 방식과 분할 정복의 '나누고 합치는' 구조를 손에 익히는 연습이 필요합니다.
• 문제 해결 전략: 중복되는 계산이 많다면 DP를, 요소 간의 연결 여부를 확인해야 한다면 유니온 파인드를 선택하는 등 상황에 맞는 알고리즘 선택 능력을 기르는 데 집중했습니다.