자주 나오는 유형
- 그리디
- 구현
- DFS/BFS
- 정렬
- 이진 탐색
- 다이나믹 프로그래밍
- 최단 경로
- 그래프 이론
그리디
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법.
- 각 상황에 대한 명확한 최적의 방법이 존재.
예시
/**
* money:8000, coins:[5000,1000,500,100,50,10] 일때
* 거스름돈을 최소한으로 사용하는 방법
*/
public int greedy(int money, int[] coins) {
int cnt=0;
for(int coin:coins) {
if(money >= coin) {
cnt+=money/coin;
money%=coin;
}
}
return cnt;
}
문제들
구현
- 아이디어를 코드로 바꾸는 유형
- 코딩 피지컬 요구
- 복잡한 지문의 요구사항을 빠짐없이 구현해야함
- 특정한 형태가 없고 집중력있게 풀어야함.
문제들
- 럭키 스트레이트(백준) 문제 java풀이 pyhon풀이
- 문자열 압축(카카오, 프로그래머스) 문제 java풀이 python풀이
- 자물쇠와 열쇠(카카오, 프로그래머스) 문제 java풀이 python풀이
- 뱀(삼성, 백준) 문제 python풀이
- 기둥과 보(카카오, 프로그래머스) 문제 python풀이
- 치킨 배달(삼성, 백준) 문제 python풀이
- 외벽 점검(카카오, 프로그래머스) 문제 python풀이
- 백준 문제 모음 링크
DFS, BFS
- 완전 탐색하는 방법.
- 두 방법 모두 그래프를 끝까지 탐색함.(단 순서가 다름.)
- DFS 목표 : 말단 노드까지 빠른 방문. 방문 가능 여부.
- BFS 목표 : 모든 형제 노드를 체크. 최소 거리.
- 완전 탐색해야한다면 두 방법 모두 사용 가능함.
DFS(깊이 우선 탐색)
- 함수(stack) 사용.
- 재귀 함수 형태로 호출.
- 수직 방향으로 동작함.
- 말단 노드까지 먼저 방문하는것이 특징.
- 그래서 말단 노드까지 방문이 가능한지 여부에 사용됨.
- 백트래킹(backtracking)도 DFS의 부분집합.
- 현재 상태와 부모 노드만 저장하면 되서 메모리 사용량이 적음.
예시
void dfs(int depth,int now,int[] arr) {
// check finished
if(isFin) return;
// end
if(depth==n) {
// check answer
if(check(arr)) isFin=true;
return;
}
// next
for(int next=0;next<n;next++) {
// DFS 는 아래와 같은 문법이 반복되어 사용됨!
if(visited[next]) continue;
arr[depth]=now;
visited[depth]=true;
dfs(depth+1,next,arr);
// 방문 후 반드시 흔적을 지워줘야함.
arr[depth]=-1;
visited[depth]=false;
}
}
BFS(너비 우선 탐색)
- queue 사용.
- 모든 경우를 체크하며 진행.
- 최소 거리를 구할때 사용.
- 단 분기가 많아지고 깊어질수록 메모리 사용량이 급등함.
- 그럴땐 가지치기해서 불필요한 방문을 줄여야함.
예시
Queue<int[]> que=new LinkedList<>(); // (y,x,depth)
que.add(new int[]{0,0,1});
int minDepth=0;
boolean[][] visited=new boolean[n][m];
int[] dy={1,0,-1,0},dx={0,1,0,-1};
while(!que.isEmpty()) {
int[] now=que.poll();
int y=now[0],x=now[1],depth=now[2];
// visited
if(visited[y][x]) continue;
visited[y][x]=true;
// check end
if(y==n-1 && x==m-1) {
minDepth=depth;
break;
}
// next
for(int d=0;d<4;d++) {
int my=y+dy[d],mx=x+dx[d];
if(my<0 || my>=n || mx<0 || mx>=m) continue;
if(!graph[my][mx] || visited[my][mx]) continue;
que.add(new int[]{my,mx,depth+1});
}
}문제들
- 특정 거리의 도시 찾기(백준) 문제 python풀이
- 연구소(삼성, 백준) 문제 python풀이
- 경쟁적 전염(백준) 문제 python풀이
- 괄호 변환(카카오, 프로그래머스) 문제 python풀이
- 연산자 끼워넣기(백준) 문제 python풀이
- 감시 피하기(백준) 문제 python풀이
- 인구 이동(삼성, 백준) 문제 틀림(시간초과)
- 블록 이동하기(카카오, 프로그래머스) 문제 python풀이
- 백준 문제 모음 DFS BFS
정렬
단순히 라이브러리를 쓰면 되는 문제도 있고
각 정렬을 구현해볼줄 알아야함.
선택 정렬
- 선택정렬은 처음부터 끝까지 훑으며 가장 작은 원소를 선택해서 바꾸며 올라가는 알고리즘이다.
- 가장 작은 수가 맨 앞으로 이동.
- 빅오는 N^2.
int[] arr={5,4,1,2,3};
for(int i=0;i<arr.length;i++) {
int minIdx=i;
// compare
for(int j=i+1;j<arr.length;j++) {
if(arr[minIdx]>arr[j]) minIdx=j;
}
// swap (i, minIdx)
int tmp=arr[minIdx];
arr[minIdx]=arr[i];
arr[i]=tmp;
}삽입 정렬
- 삽입 정렬은 정렬된 배열에 원소를 삽입하여 정렬하는 방법이다.
- 빅오는 N^2.
- 정렬이 거의 되어있다면 빅오가 N에 가깝다.
int[] arr={5,4,1,2,3};
for(int i=1;i<arr.length;i++) {
for(int j=i;j>=0;j--) {
// 작다면 스왑
if(arr[j]<arr[j-1]) {
int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}
else break;
}
}퀵 정렬
- 피벗을 하나정하고(맨앞 원소)
- 피벗보다 왼쪽은 다 작고 오른쪽은 다 크게 만듦.
- 나머지 왼쪽과 오른쪽을 다시 퀵 정렬을 시킴. 빅오는 NlogN. 이미 정렬되어있다면 N^2가 된다.
void quick_sort(int s,int e,int[] nums) {
if(s>=e) return;
// partition
int pivot=s,l=s+1,r=e;
while(l<=r) {
// swap 할 l,r 을 찾는 과정
while(e>=l && nums[pivot]>=nums[l]) l++;
while(r>=s+1 && nums[r]>=nums[pivot]) r--;
// swap
// 마지막이라면 (pivot,r) 아니라면 (l,r) swap
swap(l>r?pivot:l,r,nums);
}
// divide
// 마지막에 r과 pivot 스왑해서 r이 pivot
quick_sort(s,r-1,nums);
quick_sort(r+1,e,nums);
}
private void swap(int a,int b,int[] nums) {
int tmp=nums[b];
nums[b]=nums[a];
nums[a]=tmp;
}계수 정렬
- 계수정렬은 계수를 저장하는 방법이다.
- 즉 몇번 나왔는지만 체크한다.
- dfs 구현할때 visited를 생각하면 될거같다.
- 빅오는 N+K다 K는 가장 큰 원소값이다.
- 약 100만이 넘어가면 비효율적이라고 한다.
- 그리고 저장된 정보를 확인은 따로 N번해줘야한다.
#임의의 배열
array=[4,5,0,1,9,7,6]
count=[0]*(max(array)+1)
for i in range(len(array)):
count[array[i]]+=1
# 정렬된 정보 확인
for i in range(len(count)):
for j in range(count[i]):
print(i,end=' ')int[] arr={5,4,1,2,3};
int max=0;
for(int a:arr) max=Math.max(max,a);
boolean[] isIn=new boolean[max+1];
for(int a:arr) isIn[a]=true;
for(int i=0;i<isIn.length;i++) if(isIn[i]) System.out.println(i);merge sort
- 분할 정복 방식.
- 배열의 모든 요소를 쪼개고 합치는 방식.
- 합칠때는 두 배열을 하나씩 비교.
- 최악 최선 평균의 상황에서 모두 nlogn을 유지함.
- 단 길이 n 만큼의 배열이 필요함.(메모리 추가)
void merge_sort(int l,int r,int[] nums,int[] sorted) {
// 크기>=2
if(l>=r) return;
int mid=(l+r)/2;
merge_sort(l,mid,nums,sorted);
merge_sort(mid+1,r,nums,sorted);
// merge
// l mid,mid+1 r
int lIdx=l,rIdx=mid+1;
for(int i=l;i<=r;i++) {
// 한쪽이 비었을때
if(rIdx>r) sorted[i]=nums[lIdx++];
else if(lIdx>mid) sorted[i]=nums[rIdx++];
// 비교
else sorted[i]=(nums[lIdx]<nums[rIdx])?nums[lIdx++]:nums[rIdx++];
}
// copy
for(int i=l;i<=r;i++) nums[i]=sorted[i];
}문제들
이진 탐색
- 값이 정렬되어있을때 빠르게 탐색할 수 있음.
- 절반씩 탐색하므로 빅오는 log N
- 바리에이션이 많아서 그냥 외우면 안됨.
- 특히 s<e, s<=e, 일때 조건이 달라짐.
- 예제
int binary_search(int target) {
int s=0;e=n-1;
while(s<=e) {
int mid=(s+e)/2;
int midValue=arr[mid];
if(midValue==target) return mid;
else if(midValue<target) s=mid+1;
else e=mid-1;
}
// not found
return -1;
}lower_bound, upper_bound
- 이진 탐색의 활용 문제.
- [1,2,2,2,3,3,5,5,6] 같은 배열이 있다 치자.
- 이떄 값 2의 가장 작은 인덱스는?
- 새로운 값 4가 들어갈 인덱스는?
- 이러한 문제들에 대한 솔루션.
- 블로그 포스팅
문제들
- 공유기(백준) 문제 python풀이
- 가사 검색(백준) 문제 python풀이
- 수 찾기(백준) 문제 python풀이
- 나무 자르기(백준) 문제 python풀이
- 랜선 자르기(백준) 문제 python풀이
DP
- 그냥 수학 문제다.
- 학창시절 수학 문제 풀듯이 점화식 찾고 구현하면 된다.
- 답이 크므로 모듈러 연산을 요구한다? -> 무조건 dp.
- 솔루션이 굉장히 짧고 이해하기 어렵다.
다이나믹 프로그램으로 풀 수 있는 문제는
- 큰 문제를 작은 문제로 분할할 수 있고(분할정복)
- 작은 문제가 반복적으로 사용될때.
-
재귀와 반복문으로 풀수있는데 반복문이 힙영역을 쓰지않아 메모리 초과를 막을수있다.
-
재귀로 풀면 탑다운 방식이고 반복문을 사용한다면 바텀업 방식이라고 볼수있다.
-
그래서 먼저 바텀업으로 시도해보자.
-
예제 코드
int dp(int n,int k) {
if(k==0 || k==n) return 1;
if(dt[n][k]!=0) return dt[n][k];
else if(dt[n][n-k]!=0) return dt[n][n-k];
dt[n][n-k]=dt[n][k]=(dp(n-1,k)+dp(n-1,k-1))%MOD_NUM;
return dt[n][k];
}문제들
- 정수 삼각형(백준) 문제 python풀이
- 퇴사(백준0 문제 python풀이
- 가장 긴 증가하는 부분 수열(백준) 문제 python풀이
- 병사 배치하기(백준) 문제 python풀이
- 편집거리(백준) 문제 (아직 안풀어봄)
- 파도반 수열(백준) 문제 python풀이
- 스티커(백준) 문제 python풀이
- 오르막 수(백준) 문제 python풀이
- 백준 문제 모음 링크
최단 경로
다익스트라
-
한점에서 다른 점들까지의 최소 거리
-
시작 노드에서 다른 노드까지의 거리를 찾고
-
최단 거리 노드를 방문하며 시작 노드로부터의 경로를 최소화.
-
모든 노드를 방문할때까지 반복.
-
노드중 가장 짧은 거리를 찾을때 모든 노드를 탐색하는것이 아닌 우선순위 큐를 사용하면 logV번으로 줄일 수 있다. 총 시간복잡도는 ElogV다
// dijkstra
PriorityQueue<Node> pq=new PriorityQueue<>(((o1, o2) -> o1.v-o2.v));
int start=1;
pq.add(new Node(start,0));
int[] dist=new int[vertex_size+1];
for(int i=1;i<=vertex_size;i++) dist[i]=INF;
dist[start]=0;
while(!pq.isEmpty()) {
Node now=pq.poll();
// end
if(now.v==vertex_size) break;
// visited
if(dist[now.v]<now.w) continue;
// next
for(Node next:graph[now.v]) if(dist[next.v]>dist[now.v]+next.w) {
dist[next.v]=dist[now.v]+next.w;
pq.add(new Node(next.v,dist[next.v]));
}
}플로이드 워셜
- 다익스트라가 한점에서 다른 점들까지의 최소거리였다면
- 플로이드 워셜은 모든 점에서 모든 점까지의 최소 거리.(다익스트라를 n 번했다고 생각.)
- 알고리즘은 매우 간단함. 중간지점 k를 만들고 i,j가 이를 거쳐서 방문함.
- 모든 경로의 최단거리가 n*n 매트릭스에 저장된다.
- 노드 n번을 거치는데 각 단계마다 n^2번 연산을 해야하므로 전체 빅오는 n^3가 된다.
for(int k=0;k<n;k++) {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
graph[i][j]=Math.min(graph[i][j],graph[i][k]+graph[k][j]);
}
}
}문제들
- 플로이드(백준) 문제 python풀이
- 최단 경로(백준) 문제 python풀이
- 최소비용 구하기(백준) 문제 python풀이
- 알고스팟(백준) 문제 python풀이
- 파티(백준) 문제 python풀이
- 백준 문제 모음 링크
그래프
union-find(크루스칼 알고리즘), 위상 정렬
union-find
- 그래프에서 서로소 집합을 구하고 싶을때 사용하는 알고리즘
- 구현 방식이 정형화되어있어 외워두면 좋음.
int parent=new int[10001];
int find(int x){
if(parent[x]!=x){
parent[x]=find(parent[x]);
}
return parent[x];
}
void unionParent(int a,int b){
a=find(a);
b=find(b);
// set parent
parent[a]=b;
}트리가 깊어지면 rank 개념을 넣어서 더 높이가 작은게 아래로 가게 넣어줘야함
int parent=new int[10001];
int ranks=new int[10001];
int find(int x){
if(parent[x]!=x){
parent[x]=find(parent[x]);
}
return parent[x];
}
void unionParent(int a,int b){
a=find(a);
b=find(b);
if(a==b){
return;
}
// rank를 비교하고 작은쪽을 큰쪽에 넣기
if (ranks[a]<ranks[b]){
parent[a]=b;
}
else{
parent[b]=a;
}
if (ranks[a]==ranks[b]){
ranks[a]++;
}
}크루스칼 알고리즘
-
신장트리 : 모든 노드가 연결되면서 사이클을 이루지 않는 그래프
-
최소신장트리 : 신장트리중에 간선의 합이 최소인 신장트리
-
크루스칼 알고리즘 : 간선을 오름차순으로 정렬하고 간선의 부모가 다르면 union. 간선의 합이 최소인 최소신장트리 생성됨.
위상 정렬
- 수업을 듣다보면 선수강해야하는 수업이 있다.
- 알고리즘 수업을 듣기위해서는 자료구조와 c언어를 먼저 수강해야한다.
- 다시 소프트웨어공학을 듣기위해서는 알고리즘을 선수강해야한다.
- 그렇다면 수강 순서는 자료구조 -> c언어 -> 알고리즘 -> 소프트웨어공학 순서가 될것이다.(자료구조와 c언어 순서무관)
- 이렇듯 방향 그래프에서 방향을 거스르지 않고 나열하는것을 위상정렬이라고 한다.
구현
- 각 노드에서 입력차원수를 indegree라고 하고 indegree가 0인 노드를 큐에 넣는다.
- 큐에서 하나씩 꺼내며 연결된 방향 노드의 indegree를 줄이고 0이되면 큐에 넣어준다.
- 큐에서 나오는 순서가 위상정렬에 결과가 된다.
- 모든 노드가 포함되기전에 큐가 비게되면 사이클이 존재한다는 뜻이다.
from collections
import deque
v,e=map(int,input().split())
indegree=[0]*(v+1)
graph=[[] for _ in range(v+1)]
for _ in range(e):
a,b=map(int,input().split())
graph[a].append(b)
indegree[b]+=1
def topology_sort():
q=deque()
result=[]
for i in range(1,v+1):
if indegree[i]==0:
q.append(i)
while q:
now=q.popleft()
result.append(now)
for node in graph[now]:
indegree[node]-=1
if indegree[node]==0:
q.append(node)
return result
res=topology_sort()
for r in res:
print(r,end=' ')import java.util.*;
public class Main {
static int n, m;
static int[] in = new int[32001];
static boolean[] visited = new boolean[32001];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
n = Integer.paseInt(br.readLine());
m = Integer.paseInt(br.readLine());
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i <= n; i++) {
list.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
in[b]++;
list.get(a).add(b);
}
Queue<Integer> que = new LinkedList<>();
// 진입차수 0인 노드부터 시작
for (int i = 1; i <= n; i++) {
if (in[i] == 0) que.offer(i);
}
while (!que.isEmpty()) {
int now = que.poll();
visited[now] = true;
System.out.print(now + " ");
for (int i = 0; i < list.get(now).size(); i++) {
int out = list.get(now).get(i);
in[out]--;
if (in[out] == 0) que.offer(out);
}
}
// 남은 노드 출력 (진입차수가 남는 노드는 없다고 가정)
for (int i = 1; i <= n; i++) {
if (!visited[i]) System.out.print(i + " ");
}
}
}
문제들
빈출 유형
코딩테스트 공부순서
백준 상단 문제메뉴 - 알고리즘 분류
기본
- 문자열
- 정렬
- 스택
- 큐
- 우선순위큐(힙)
- Set, Map
- 이분탐색
- DFS(깊이 우선 탐색)
- BFS(너비 우선 탐색)
- 백트래킹
- 시뮬레이션, 구현 (삼성 기출의 대부분)
- 그리디(탐욕법)
- 누적합
- 분할정복
- 투포인터(두 포인터)
- 위상정렬
- DP
심화
- 다익스트라
- 플로이드 와샬
- 벨만 포드
- 유니온-파인드 (Disjoint set)
- MST(최소 스패닝 트리), 크루스칼
- 세그먼트 트리
- 트라이
shining itself