[알고리즘 문제 유형] 문제에서 알고리즘 문제 유형 파악하기

내일 비대면 알고리즘 대회에 스터디를 같이 하고 있는 동기들과 참가한다.

뒤에 일정이 있어 대회 시간 절반 정도만 참여를 하기 때문에 입상을 노리고 있진 않지만 이 기회에 한 번 정리해보면 좋을 것 같아 포스팅을 하게 됐다.

 

다양한 언어로 코테를 풀면서 느낀게 문제를 읽고 어떤 걸 이용해 어떻게 풀지 로직만 잘 잡혀 있다면 언어는 그 다음 문제라는 것이다. 

 

알고리즘 유형 별로 문제가 어떤 식으로 많이 나오는 지 정리해봤다.

유형 별로 이해대신 외우는 용도가 아니라 저런 문제에 왜 저 알고리즘을 쓰는지 접근하는 방식으로 활용하면 좋을 것 같다.

항상 백프로 일치하진않고 경향성의 문제이며 아직 배워가는 입장이라 잘못된 정보가 있다면 댓글에 적어주세요!

 

완전탐색

입력 값이 100이하로 작은 문제

 

백트래킹

입력 값이 100이하로 작은 문제

순열, 중복 순열, 조합, 중복 조합

 

BFS

출발 값 존재

도착 값 까지 최소/최단 시간/거리/횟수

무가중 그래프

 

DFS

사이클 찾기 문제

한 가지 정점에서 연결된 모든 정점 탐색

그래프 완전 탐색

무가증 그래프

최단 거리는 절대 x

 

DFS+다이나믹 프로그래밍

갈 수 있는 방향이 목표지점까지로만 갈 수 있도록 제한 

사이클 x

경로 수 구하기

유향 그래프

 

BFS+다이나믹 프로그래밍

가중 그래프

메모이제이션을 통해 재방문이 가능한 경우를 정의할 때

 

이분 탐색

최소/최대 값 구하는 문제

결과 값들이 정렬 되어 있는 경우

X라는 조건 만족하는 최대/최소값

 

해시 맵

배열 내 빈도수 구하기

배열 내 중복된 요소 구하기

 

크루스칼

최소 신장 트리(가장 저렴한 방법으로 모두 연결 등)

 

프림 알고리즘

최소 신장 트리(가장 저렴한 방법으로 모두 연결 등)

 

다익스트라

최단 경로 (특정 노드->모든 노드까지)

가중 그래프

간선마다 가중치가 다른지 파악, 같다면 BFS 사용 가능

 

위상 정렬

주어진 수 정렬 할 때 순서가 정해져 있는 요소가 존재

 

우선 순위 큐/힙

실시간으로 정렬이 이루어져야하는 경우

N번째 요소 구하기

중앙 값 구하기

 

그리디

가장 많은 선택을 할 수 있는, 가장 작은/큰 등의 키워드가 있는 문제

 

플로이드-와샬

모든 노드->모든 노드까지 가는데의 최소 비용

 

 

참고 사이트

https://hh-bigdata-career.tistory.com/24

https://skytitan.tistory.com/217

https://mangkyu.tistory.com/181