Algorithm

주의 사항

테스트 케이스가 여러 개일 때 클래스 변수를 사용할 경우 루프 안에서 매번 초기화 필요

Java

배열 출력 방법

1차원 배열 - Arrays.toString(arr)
다차원 배열 - Arrays.deepToString(arr)

Long

답이 int 범위(약 20억)를 벗어나는 경우 long을 사용

Integer 배열

Integer 타입 배열의 경우 0이 아닌 null로 초기화됨

시간복잡도

1초 = 약 1억 번의 연산(n) 가능

자료구조

우선순위 큐

반복적으로 최솟값, 최댓값을 구해야 하는 경우

완전 탐색

DFS 이용

2차원 배열 탐색

재귀를 이용하여 2차원 배열을 한칸씩 탐색하는 경우 -> 몫과 나머지를 이용

// n: 행 길이, m: 열 길이
void dfs(int index) {
   if (index == n * m) {
      return;
   }
   int r = index / m;
   int c = index % m;
   // graph[r][c] = ~ 
   dfs(index + 1);
}

완전 탐색으로 시간 초과가 발생하는 경우

이분 탐색 -> 답을 mid로 두고 범위를 좁혀가며 탐색
DP(메모이제이션)
투 포인터
누적합 -> 배열에 변경 지점을 표시한 후 누적해서 더함
해시

Dynamic Programming

When

부분(하위) 문제로 나눌 수 있는 경우
이전 선택이 다음 선택에 영향을 미치는 경우
현재의 값은 최적의 값이라 생각
중복 계산을 피하기 위해 값 저장
구해야 하는 답을 dp로 표현

-> 점화식으로 나타내어 해결

How

Bottom-up
반복문 이용
초기값 설정 후 값을 누적해서 채워나감
1차원 또는 2차원 배열 이용
인덱스를 이용해 항(구간) 표현
Top-down
재귀 이용
종료 조건으로 초기값 반환
파라미터를 이용해 항(구간) 표현
Memoization을 이용하여 재귀 호출을 줄일 수 있음(가지치기)

Tip

IndexError 주의
index - 1을 하는 경우를 위해 인덱스는 1 ~ n으로 설정

조합

nCr = n-1Cr + n-1Cr-1

트리 dp

특정 노드가 루트 노드인 서브 트리에서의 부분 문제로 나눔
재귀 이용
리프 노드에서부터 값을 계산해서 올라옴

그리디

현재 상태에서의 최적 선택
정렬, 우선순위 큐 이용

최단 경로

BFS

가중치가 없거나 모두 동일한 경우
방향까지 고려해야 하면 3차원 배열 이용

DFS는?
DFS를 사용해도 최단 경로를 구할 수 있지만 모든 경로를 탐색해야 하기 때문에 시간이 오래 걸림
BFS의 경우에는 depth를 1씩 늘려가며 탐색하기 때문에 가장 먼저 도착한 경로가 최단 경로가 됨
visited 배열로 방문하지 않은 노드만 탐색해도 BFS는 돌아가지 않지만 DFS는 돌아가는 경우가 발생

다익스트라

가중치가 양수인 경우
특정 노드에서 나머지 노드로의 최단 거리를 구하는 경우
간선 방향을 반대로 하여 특정 노드로의 최단 거리를 구할 수도 있음

플로이드 와샬

시간복잡도가 O(n^3)이므로 노드 수가 작은 경우
모든 노드 간의 최단거리를 구하는 경우
처음에 가중치를 초기화할 때 (Integer.MAX_VALUE/2)로 초기화 -> 가중치끼리 더해서 정수 범위 초과하는 것 방지

분리집합(Union-Find)

주의점

집합의 루트 노드를 찾고 싶을 때는 parent가 아닌 find로 찾아야 함

최소 신장 트리(MST)

최소의 비용으로 모든 노드를 연결
분리집합, 그리디 이용

위상정렬

Directed Acyclic Graph
순서, 선행 관계 중 일부만 주어졌을 경우
답이 여러 개 존재할 수 있음

비트마스킹

Boolean 배열을 이진수로 표현

연산

1로 만듬

bits |= (1 << n)

0으로 만듬

bits &= ~(1 << n)

같은지 검사

(bits & pattern) == bits

특정 위치가 0인지 검사

int digit = 1 << n;
(number & digit) == 0

특정 위치가 1인지 검사

int digit = 1 << n;
(number & digit) == digit

최장 증가 부분 수열(LIS)

dp 사용 시 O(n^2)에 수행 가능

최적화

이분탐색(lowerBound)을 이용하여 O(nlogn)에 수행

최소 공통 조상(LCA)

트리에서 두 노드의 가장 가까운 공통 부모 노드를 찾음
dp를 이용하여 O(n^2) -> O(nlogn)으로 최적화 가능

최장 공통 부분 수열(LCS)

2차원 dp를 이용하여 구간 표현

KMP

문자열이 특정 패턴을 포함하는지 검사
O(NM)(루프로 탐색 시) -> O(N+M)으로 검사 가능

jyunkim/java-algorithm