알고리즘 종류와 유형

알고리즘 종류와 유형

1. 문자열

• 특정 문자열 검색하기
• https://www.acmicpc.net/problem/6550
• 문자열 정렬
• https://www.acmicpc.net/problem/20291
• https://www.acmicpc.net/problem/17413
• https://www.acmicpc.net/problem/20210
• 문자열 조건 따지기
• https://www.acmicpc.net/problem/17609
• https://www.acmicpc.net/problem/20437

2. 분리집합(유니온 파인드)

• 집합성 문제
• https://www.acmicpc.net/problem/1717
• https://www.acmicpc.net/problem/1976
• https://www.acmicpc.net/problem/16562
• https://www.acmicpc.net/problem/18116
• https://www.acmicpc.net/problem/10775

3. 트리

• https://www.acmicpc.net/problem/9934
• https://www.acmicpc.net/problem/5639
• 트리 변형 관련 문제
• https://www.acmicpc.net/problem/14675
• https://www.acmicpc.net/problem/1068
• 트리 특정 조건 관련 문제
• https://www.acmicpc.net/problem/17073
• baekjoon/tree at main · tony9402/baekjoon · GitHub

4. 완전탐색

• https://www.acmicpc.net/problem/15686
• https://www.acmicpc.net/problem/1025
• https://www.acmicpc.net/problem/21278

5. 그래프 탐색

• 직접적인 그래프 탐색
• https://www.acmicpc.net/problem/1260
• 경로 찾기형 문제
• https://www.acmicpc.net/problem/2178
• https://www.acmicpc.net/problem/1325
• https://www.acmicpc.net/problem/13549
• 행렬 응용문제
• https://www.acmicpc.net/problem/2178
• https://www.acmicpc.net/problem/14940
• https://www.acmicpc.net/problem/5547

6. 이분탐색

순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라

탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법이다.

• 검색형 문제
• https://www.acmicpc.net/problem/10815
• https://www.acmicpc.net/problem/2512
• https://www.acmicpc.net/problem/7453
• 최적의 경우 탐색형
• https://www.acmicpc.net/problem/2512
• https://www.acmicpc.net/problem/3079
• https://www.acmicpc.net/problem/2470

7. 투포인터

리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

• 특정 조건에 해당하는 범위를 찾는 조건
• https://www.acmicpc.net/problem/21921
• https://www.acmicpc.net/problem/2470
• 수치 배열에서 특정 조합 찾기
• https://www.acmicpc.net/problem/21921
• https://www.acmicpc.net/problem/15961

8. 동적계획법

조건

1. 최적 부분 구조 : 큰문제를 작은 문제로 나누며 작은 문제의 답으로 큰 문제를 해결할수 있는가
2. 동일하게 반복되는 작은 문제로 해결할수 있는가

공략

1. 점화식을 구해야한다.
2. 동적계획법의 조건을 따벼보고 최종적으로 해결해야할 문제를 확인한다.
3. 작은 문제와 큰문제 사이의 관계를 점화식으로 표현해본다.
   1. 메모이제이션을 이용한 재귀함수 해결법(Top-down)
   2. 결과 저장용 리스트 DP테이블을 이용한 해결법(Bottom-up)

• 최적의 배치를 찾는 유형(최대, 최소의 경우의수 찾기)
• https://www.acmicpc.net/problem/21317
• https://www.acmicpc.net/problem/2156
• https://www.acmicpc.net/problem/15486
• https://www.acmicpc.net/problem/1823
• 사건의 결과를 구하는 유형(~했을때 결과는?)
• https://www.acmicpc.net/problem/10844
• https://www.acmicpc.net/problem/1915

9. 백트래킹

개요

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다.

이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다.

답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 백트래킹이라고 생각하면 됩니다.

• N과 M 시리즈
• https://www.acmicpc.net/problem/15649
• https://www.acmicpc.net/problem/15664
• https://www.acmicpc.net/problem/10971
• 배치형 문제
• https://www.acmicpc.net/problem/18430
• https://www.acmicpc.net/problem/9663
• https://www.acmicpc.net/problem/2580
• 조건 수열형 문제
• https://www.acmicpc.net/problem/1174
• https://www.acmicpc.net/problem/2661
• https://www.acmicpc.net/problem/1062

10. 누적합

누적 합이란, 말 그대로 나열된 수의 누적된 합을 말한다.

• https://www.acmicpc.net/problem/20438
• https://www.acmicpc.net/problem/11660
• https://www.acmicpc.net/problem/10986

11. 탐욕법

탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

• https://www.acmicpc.net/problem/16953
• https://www.acmicpc.net/problem/1931
• https://www.acmicpc.net/problem/13975
• https://www.acmicpc.net/problem/2212

12. 최단거리 알고리즘

다익스트라 알고리즘

**다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.**

1. 출발 노드 지정

2. 최단 거리 테이블 초기화

3. 방문한 적 없는 노드 중에서 최단 거리가 제일 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 거리를 구하여 최단 거리 테이블을 업데이트

5. 위 3, 4번 과정을 모든 노드를 방문할 때까지 반복

플로이드 알고리즘

플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다.

모든 노드 간의 최단거리를 구해야 하므로 2차원 인접 행렬을 구성합니다. 알고리즘은 여러 라운드로 구성됩니다. 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복합니다.

• https://www.acmicpc.net/problem/11403
• https://www.acmicpc.net/problem/13549
• https://www.acmicpc.net/problem/11404
• https://www.acmicpc.net/problem/1956

13. 시뮬레이션

일련의 명령에 따라서 개체를 차례대로 이동시키는 것

• https://www.acmicpc.net/problem/16234
• https://www.acmicpc.net/problem/21610
• https://www.acmicpc.net/problem/17144
• https://www.acmicpc.net/problem/17140

14. 분할정복

분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다.

• https://www.acmicpc.net/problem/18222
• https://www.acmicpc.net/problem/2447
• https://www.acmicpc.net/problem/2448

15. 구현

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

• https://www.acmicpc.net/problem/2615
• https://www.acmicpc.net/problem/22856
• https://www.acmicpc.net/problem/14719