코딩테스트에서 자주 출제되는 유형
브루트 포스
DFS
BFS
시뮬레이션/구현 // 가장 많이 출제됨
DP
그리디
이분탐색
투포인터
이 외에도
우선순위 큐
해시 맵
trie 알고리즘
유니온 파인드
크루스칼 알고리즘
트리의 지름 구하기
-
브루트 포스(완전 탐색)
모든 경우를 다 탐색하는 경우. 주어진 범위 내에 모든 수를 탐색해보면서 조건에 해당하는지 탐색하는 경우 -
DFS(깊이 우선 탐색)
-
한 가지 정점과 연결된 모든 정점을 탐색해야 하는 경우
일반적인 DFS 알고리즘을 사용하면 된다. 해당 지점 방문 여부를 체크할 수 있는 배열을 선언한 뒤, 한 정점씩 방문 후 그 정점과 인접한 정접들 중 아직 방문하지 않은 정점을 다시 재귀 호술하는 방식을 이용 -
경로를 찾아야 되는 경우
연결 요소를 찾는 것이 아닌 경로를 찾아야 하는 경우. 약간 변형하여 이용 -
사이클이 존재하는 경로 찾는 경우
이전에 방문했던 곳을 다시 방문해 일종의 원형 반복 사이클이 생겼다는 것을 의미.
기존에 사용하던 방문여부 체크 배열 외에 경로가 시작된 정점을 저장하기 위해 배열을 하나 추가로 생성한다. 그리고나서 dfs 탐색을 하되 이번에는 기존에 방문했던 정점들에 대해서도 조건 체크를 해주어야 함
- BFS(넓이 우선 탐색)
단계 별 탐색이 가능하기 때문에 최단 거리를 구할 수 있다
-
최단 거리를 구해야 하는 경우
큐(Queue)를 이용하여 단계별로 정점들을 탐색 -
최단 거리를 구하되, 여러 개 존재하는 경우(방문한 지점도 다시 방문 가능)
주어진 조건이 다수라 고려해야 할 사항이 많은 경우에는 큐에 해당 조건을 모두 저장하기 위해 커스텀 클래스를 하나 선언해준 뒤, 큐에 모든 정보를 저장하면서 BFS 알고리즘 수행
단, 기존의 BFS와 달리 기존에 방문했던 정점이라도 최소 비용으로 업데이트가 가능한 경우에는 큐에 새로 추가한다
- 시뮬레이션
문제에 나와 있는 상황과 조건을 토대로 구현하면 되는 문제. 다양한 문제를 경험해보는 것이 중요
- DP(동적 프로그래밍)
- long 형으로 배열을 선언한다
- 문제에서 구하려고 하는 부분을 배열로 선언한다
- 조건이 여러 개인 경우네는 2차원 배열을 선언한다
구간을 구하는 문제같은 경우는 A[i]를 끝 점으로 하는 수열의 최장 길이, A[i]를 시작으로 하는 수열의 최장 길이 이런식으로 배열을 선언하면 좋다
-
그리디
그때그때 상황에서의 최적해가 전체 최적해가 된다는 원리를 이용한 방식 -
이분탐색(파라메트릭 서치)
정렬된 배열이 있을 때 중간부터 탐색을 시작하여 탐색할 문제를 점차 반씩 줄여나가는 방식을 이용
- 먼저 정렬되어 있는지 확인하고 정렬되어 있지 않다면 정렬을 먼저 수행
- 문제에서 구하라고 하는 값의 범위를 고려하여 이분 탐색의 범위로 할당
- 투포인터
구간을 구하기 위해 사용하는 알고리즘. 효율성 측면에서 사용하는 거시 좋다.
배열의 인덱스를 가르키는 start와 end포인터 두 가지를 두고 조건에 맞춰 end 포인터를 ++1, start 포인터를 ++1 해나가는 방식
-
대상이 되는 배열이 1개인 경우
-
대상이 되는 배열이 2개인 경우
부분수열은 일반적으로 조합(완전 탐색)을 이용하여 풀이. 다만 해당 문제는 N의 범위가 크기 때문에 완전 탐색으로 풀게 되면 시간 초과가 나기에 N/2 단위로 완전 탐색을 한 뒤, 각각 두 배열을 하나는 오름차순, 하나는 내림차순 정렬을 하여 두개의 포인터를 이용하여 답을 구해야 한다
- 우선순위 큐
자바를 기준으로 기본 반환 순서는 최소 힙 형태이다.
- N번쨰 요소 구하기(큐의 크기를 n으로 유지한 뒤 n+1개가 들어올때 가장 작은 요소와 비교
- 중앙값 구하기(두 개의 우선순위 큐를 이용해서)
- 2,5,8,111... (2,5,8 초기값을 큐에 넣고 하나씩 뽑으면서 연산을 진행한 두 n번째 요소 구하기
- 해시 맵
- 배열 내 빈도 수 구하기
- 배열 내 중복된 요소 구하기
- HashMap<Integer, LinkedList>...
- 유니온 파인드
특정 두 노드가 어느 집합에 속하는지 반별하고 두 노드를 하나의 집합으로 합칠 때 사용하는 알고리즘. 크루스칼 알고리즘과 더불어 많이 사용되거나 독립적으로 사용
- Trie 알고리즘
문자열 검색 및 처리를 위한 알고리즘. String클래스를 이용해 선형적으로 저장하지 않고, Tree형태로 저장하여 검색 속도의 향상을 추구하는 알고리즘
- 크루스탈 알고리즘
크루스칼 알고리즘은 MST를 구하기 위한 알고리즘. N개의 노드로 이루어진 그래프가 주어졌을 때, N-1개의 간선을 이용한 최소 가중치의 트리를 구할 때 사용
- 간선들을 모두 오름차순 정렬한다
- 가중치가 가장 작은 간선부터 선택하면서 사이클이 생기지 않는 경우 해당 간선을 선택
- N-1개의 간선이 선택될 때까지 반복
