Computer Science/Algorithm

문자열 알고리즘 - KMP와 Robin-Karp 알고리즘

| 관련 강의 영상 https://www.youtube.com/watch?v=UcjK_k5PLHI - KMP나 Robin-Karp를 사용하면 O(n)의 시간복잡도로 문자열에서 패턴 문자열을 찾을 수 있다. - KMP는 어려워서 일단 Robin-karp 부분만 찾아서 적용해보았다. | Robin-Karp 알고리즘 사용해보기 https://joomn11.tistory.com/111?category=900637 [알고리즘] 라빈 카프(Rabin-Karp)(문자열 탐색)(Rolling Hash) 문자열 탐색 알고리즘 Rabin-Karp는 Hashing을 이용하여 문자열에서 특정 패턴과 일치하는지 찾는 알고리즘이다. 문자열에서 찾고자 하는 패턴의 길이만큼 hash값으로 변환하여, 패턴과 hash값이 같은 joom..

알고리즘 속도 구하기

| 알고리즘 속도 구하는 방법 - 아래와 같은 방법으로 알고리즘 속도를 구할 수 있다. - 예전에 알고 있던 방법이었는데, 금방 잊어버렸기에 생각날 때 노트해두었다. Long start = System.currentTimeMillis(); // 알고리즘 돌리고 Long end = System.currentTimeMillis(); System.out.prinln(end - start + " ms");

[알고리즘] 최소신장트리(MST)

| 최소신장트리 - Mininum Spanning Tree - 그래프의 모든 노드를 연결할 때 가중치 합이 최소가 나오는 트리 - 특징 : (1) 사이클 제외 -- 가중치의 합은 사이클이 포함될 때 최소가 될 수 없다. (2) N개의 노드에 대한 최소신장트리 간선 수는 늘 N - 1개이다. | 종류 크루스칼(Kruskal) 프림(Prim) 핵심 - 최소값의 간선 우선 연결 - 사이클 발생 시 다른 간선 선택 - 임의의 노드에서 시작 - 연결된 간선 중 낮은 가중치 선택 언제? - 간선 수가 비교적 적을 때 - 간선 수가 많을 때 유리 메모리 에지 리스트(or 배열) 유니온 파인드 배열 인접 리스트(or 배열) 방문 배열 속도 O(ElogE) O(ElogV) - 우선순위 큐 사용 시 *O(v2) - 정렬되..

[알고리즘] 최단 경로 구하기 - 3. 플로이드-워셜 알고리즘

| 플로이드-워셜 알고리즘 - 모든 노드의 최단 경로를 구하는 알고리즘으로 전체 간선을 인접 행렬로 표현하고 dp를 통해 최단 경로를 구하는 방식 핵심 : 전체 경로의 최단 경로 = 부분 경로의 최단 경로의 조합 - 기능 : 모든 노드 간에 최단 경로 탐색 - 특징 : 음수 가중치 Ok, 동적 계획법의 원리를 사용 - 시간복잡도 : O(V3) | 플로이드-워셜 구현하기 1 배열을 선언하고 초기화 2 노드의 각 인접 노드 경로 입력 3 점화식으로 배열 업데이트 4 음수사이클 확인 [1] 배열을 선언하고 초기화 - 각각의 노드를 Start지점으로 두고 모든 Start지점에 대한 최단 거리를 구할 예정 1 2 3 4 5 1 0 ∞ ∞ ∞ ∞ 2 ∞ 0 ∞ ∞ ∞ 3 ∞ ∞ 0 ∞ ∞ 4 ∞ ∞ ∞ 0 ∞ 5 ..

[알고리즘] 최단 경로 구하기 - 2. 벨만 - 포드

| 벨만-포드 - 가중치가 양수만 있을 때에 다익스트라를 사용했다면, - 가중치에 음수가 있을 때엔 벨만-포드를 사용한다. - 기능 : 특정 출발 노드에서 도착 노드까지의 최단 경로 탐색 - 특징 : 가중치 음수 OK, 음수 사이클 여부 판단 - 시간 복잡도 : O(VE) | 벨만-포드 구현하기 - 지난번에 구현했던 다익스트라의 우선순위 큐 버전으로 쓰면 음수도 커버가 가능한데 - 벨만-포드를 사용하게 되면 음수 사이클 여부까지 커버할 수 있다. - 구현의 순서 1 에지 배열 & 최단 경로 dp 배열 초기화 2 모든 에지를 하나씩 확인하여 최단 경로 업데이트 3 음수 사이클 여부 확인 [1] 에지 배열(또는 리스트) & 최단 경로 dp 배열 초기화 - 이 부분은 다익스트라의 노드 클래스가 간선 클래스로 ..

[알고리즘] 최단 경로 구하기 - 1. 다익스트라

| 다익스트라 - 가중치가 있는 그래프에서, 최단 경로를 구하는 알고리즘 - 핵심 : 그래프의 인접리스트와 DP를 이용 - 기능 : 출발 노드와 모든 노드 간의 최단 거리 탐색 - 특징 : 간선은 모두 양수 - 시간 복잡도 : O(ElogV) * E : 간선수, V : 정점수 | 다익스트라 구현 - 배열을 사용하는 것도 좋지만 배열 크기가 너무 클 경우를 대비해 인접 리스트를 사용 - (1),(2) 모두 기본적으로 동일하게 아래를 세팅 (1) 간선 정보 리스트 : 인접 리스트에 Node(연결된 노드, 가중치) 타입으로 저장 (2) 임시 거리 배열 : 출발지부터 노드 X까지의 현재 최소 거리를 업데이트할 배열 ㄴ start 위치는 자기 자신이므로 0으로 세팅한다. class Node{ int to; int..

[알고리즘] 백트래킹

| 백트래킹 - 모든 가능한 경우의 수 중에서 유망하지 않은 쪽은 제외하고 최적해를 구하는 방법 - 주로 재귀를 사용해서 구현한다. 유망(Promising) 가능성 있다. 가지치기(Pruning) 가능성 없는 것 제외하기 백트래킹(Backtracking) 유망하지 않은 쪽으로는 가지 않고 Back한다. | N-Queen 을 통한 백트래킹 이해 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net - N x N의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치한다고..

[알고리즘] DP (동적 계획법)

| 동적계획법이란? - 복잡한 문제를 여러 개의 간단한 문제로 분리하여 해결하는 방법 - 원리 및 구현 방법 1) 큰 문제를 부분적으로 분리하여 분석한다 --> 부분적인 문제의 결과값은 항상 동일해야한다. 2) 1)을 통해 알게된 규칙을 통해 점화식을 생성한다. 3) 기존 배열과 dp배열을 어떻게 만들지 구상하고 4) 아래 두 가지 방법 중 적절한 구현 방법에 따라 수도 코드를 작성한다. 타뷸레이션 = 바텀-업 - for문을 사용하여 구현 메모이제이션 = 탑-다운 * 이미지 출처 : 나무위키 - 재귀를 사용하여 구현 | 피보나치를 통해 보는 동적 계획법 - 점화식을 통해 재귀로 푼 피보나치 문제 풀이는 아래와 같았다. // 피보나치 수열 // 재귀 (일반풀이 방법) - O(n^2), 계산했던 부분도 다시..

모듈러 산술

| 모듈러 산술 - 모듈러 (=mod = %)는 덧셈, 뺄셈, 곱셈에 있어서 아래와 같은 산술을 할 수 있는 특징이 있다. - 알고리즘 문제를 풀다보면 애매하게 정수 Max값을 넘을랑 말랑 하는 데이터가 있기도 한데, 그럴 때 이 모듈러 산술을 고려해서 문제를 풀면 굳이 Long 타입 변수를 쓰지 않아도 Int만으로 충분히 풀이가 가능하다. (a + b) % C = (a % C + b % C) % C (a - b) % C = (a % C - b % C) % C (a * b) % C = (a % C * b % C) % C | 참고할 만한 문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 ..

[알고리즘] 분할정복

| 분할정복이란? - 폰노이만 구조를 만든 그 폰노이만에 의해 소개된 알고리즘 - 간략하게 말하면, 큰 문제를 작은 단위로 쪼갠 후 다시 조합하여 문제를 해결하는 방법을 말한다. 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다 *출처 : 나무위키 | 분할정복 과정 1. 문제를 하나 이상의 작은 단위로 분할 2. 작은 단위에서 부분적인 해결 3. 부분들의 해결을 조합해 전체 문제의 해답을 찾는다. function F(x): if F(x)가 간단 then: return F(x)를 계산한 값 else: x 를 x1, x2로 분할 F(x1)과 F(x2)..