Algorithm
1.[알고리즘] 알고리즘 성능
복잡도, 빅오표기법에 대해
2.[알고리즘] 그리디(탐욕법)
✅ 그리디 알고리즘: 현재 상황에서 지금 당장 좋은 것만 고르는 방법. ✅ 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.
3.[알고리즘] 구현
✅ 예시: 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제 / 실수 연산을 다루고, 특정 소수점자리까지 출력해야 하는 문제 / 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 / 적절한 라이브러리를 찾아서 사용해야 하는 문제
4.[알고리즘] DFS & BFS
✅ DFS: 깊이 우선 탐색, 스택 이용 ✅ BFS: 너비 우선 탐색, 큐 이용
5.[알고리즘] 정렬
✅ 선택 정렬: 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 ✅ 삽입 정렬: 적절한 위치에 삽입 ✅ 퀵 정렬: 기준 데이터보다 큰 데이터와 작은 데이터의 위치를 변경
6.[알고리즘] 우선순위 큐
✅ 우선순위 큐: 우선순위가 갖아 높은 데이터를 갖아 먼저 삭제하는 자료구조. ✅ 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.
7.[알고리즘] 이진 탐색
✅ 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법. 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. ✅ 큰 범위를 보면 가장 먼저 이진 탐색을 떠올리자.
8.[알고리즘] 다이나믹 프로그래밍
✅ DP: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
9.[알고리즘] 최단 경로 알고리즘 (다익스트라, 플로이드 워셜)
✅ 다익스트라: 단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾기 위한 알고리즘. ✅ 플로이드-워셜: 모든 정점 쌍 사이의 최단 경로를 찾기 위한 알고리즘.
10.[알고리즘] DFS vs BFS vs Dijkstra
✅ BFS: `최단 경로를 찾을 때` 유용하다. 큐 ✅ DFS: `모든 가능한 경로를 찾을 때` 유용하다. 스택 ✅ 다익스트라: `양의 가중치 그래프에서 여러 경로 중 최단경로를 찾을 때` 유용한다. 우선순위 큐
11.[알고리즘] 기타 그래프 이론
✅ 서로소 집합 ✅ 크루스칼 ✅ 위상 정렬
12.[알고리즘] 기타 알고리즘
✅ 소수 판별 알고리즘 ✅ 에라토스테네스의 체 ✅ 투 포인터 ✅ 구간 합
13.[알고리즘] 벨만 포드 알고리즘
✅ 음의 간선이 포함된 상황에서도 사용할 수 있으며, 음수 간선의 순환을 감지할 수 있다. ✅ 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느리다.
14.[알고리즘] 최소 공통 조상 (LCA, Lowest Common Ancestor)
두 노드의 공통된 조상 중 가장 가까운 조상을 찾는 문제이다.BOJ 'LCA' 문제 中N(2 <= N <= 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1
15.[알고리즘] 바이너리 인덱스 트리(Binary Index Tree, 펜윅 트리)
2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조를 의미한다.정수 7의 2진수 표기0이 아닌 마지막 비트를 찾는 방법은 특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서 K & -K를 계산하면 된다.BOJ '구간 합 구하기' 문제