코딩테스트/[알고리즘] 알고리즘 정리

문자열 패턴 매칭 알고리즘

고지식한 알고리즘 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식 시간 복잡도 O(MN) 라빈-카프 알고리즘 문자열 검색을 위해 해시 값 함수를 이용 패턴 내의 문자들을 일일이 비교하는 대신 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시값만을 비교 최악의 시간 복잡도 O(MN), 평균적으로 선형에 가까운 빠른 속도 ,대략 O(M+N) 숫자 문자열 : 6843212431 찾으려는 패턴 : 4321 패턴의 해쉬값을 계산 -> 각 자리의 숫자에 자리값을 곱하여 더함 ("4321"은 정수 4321이 됨) 찾고자 하는 문자열에서 4자리씩 해쉬값을 계산 -> (6843, 8432...) 새로 추가되는 문자와 그전에 읽었던 값을 이용해서 해쉬값을 구함 ((6843 % 10..

이진 탐색 알고리즘

순차 탐색 : 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 단계마다 탐색범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N 에 비례한다. 시간 복잡도는 O(logN)을 보장 이진 탐색은 최적화 문제를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 문제에 사용가능 예) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 재귀 함수를 이용한 이진 탐색 예제 import java.util.*; public class Main { // 이진 탐색 소스코드 구현(재귀 함수) public static int binary..

다이나믹 프로그래밍

다이나믹 프로그래밍(DP) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메로리 영역에 저장 Top-down Bottom-up 다음 조건을 만족할 때 사용가능 최적 부분 구조 큰문제를작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제 동일한 작은 문제를 반복적으로 해결해야 한다. 예) 피보나치 수열 Top-down으로 구현한 피보나치 (재귀) import java.util.*; public class Main { // 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화 public static long[] d = new long[100]; // 피보나치 함수(Fib..

그리디 알고리즘

그리디 알고리즘 현재 상황에서 지긤 당장 좋은 것만 고르는 방법 최소한의 아디디어를 떠올릴수 있는 능력을 요구한다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 해야한다. 거스름돈 문제 일반적인 상황에서는 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제된다. 거스름돈 문제 코드 public class Main { public static void main(String[] args) { int n = 1260; int cnt = 0; int[] coinTypes = {500, 100, 50, 10}; for (int i = 0; i ..

백트래킹 알고리즘

백트래킹 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾는 알고리즘 DFS는 가능한 모든 경로를 탐색하지만 백트래킹은 해를 찾아가는 도중 경로가 해가 될 거 같지 않으면 그 경로를 더 이상 찾아가지 않고 되돌아 간다. 가지치기 - 불필요한 부분을 쳐내고 최대한 올바른 쪽을 간다 백트래킹은 모든 경우의 수 중에서 특정한 조건을 만족하는 경우만 탐색하는 것이다. 해가 될 만한지 판단 후 유망하지 않으면 가지치기 후 이전(부모) 노드로 돌아간다. N-Queen public class NQueen{ static int N = 4; static int[][] board = new int[4][4]; public static void main(String[] args){ if(put_queen(0) ..

그래프 탐색 알고리즘 - DFS / BFS

스택 자료구조 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조 (입구, 출구 동일) 큐 자료구조 먼저 들어온 데이터가 먼저나가는 형식의 자료구조 DFS 깊이 우선 탐색 (깊은 부분을 우선적으로 탐색) 스택 자료구조 또는 재귀 함수를 이용한다. 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리, 인접 노드가 없으면 스택에서 최상단 노드 꺼냄 2번을 수행할 수 없을때까지 반복 DFS 예제 코드 import java.util.*; public class Main { public static boolean[] visited = new boolean[9]; public static ArrayList graph = n..

최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜)

최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 단일 출발 최단 경로 : 어떤 하나의 지점에서 나머지 모든 지점으로 경로 단일 도착 최단 경로 : 모든 지점에서 어떤 하나의 지점으로 경로 (간선을 뒤집으면 단일 출발 최단 경로 문제와 같음) 단일쌍 최단 경로 : 모든 지점 쌍들 사이의 최단 경로 BFS 가중치가 없거나 모든 가중치가 동일한 그래프에서 사용 다익스트라 음이 아닌 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착 에서 사용 벨만-포드 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착에서 사용 플로이드-워셜 전체 쌍 최단 경로에서 사용 다익스트라 최단 경로 ..