Computer Science/Algorithm
-
최장 공통 부분 수열(LCS : Longest Common Subsequence)란?Computer Science/Algorithm 2020. 6. 21. 02:49
최장 공통 부분순서란? LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. Subsequence는 부분 수열이라는 뜻으로 연속적이지 않아도 되는 부분 문자열이다. 한마디로 두 문자열을 비교할 때 공통적으로 나타나는 부분 순서들 중 가장 긴 것이다. 예를들어 "ABCBDAB"와 "BDCABA"의 LCS를 구하면 "BCBA"가 나오게 된다. 그리고 LCS는 최적화를 해야 하는 문제이기 때문에 동적계획법(DP)를 사용하여야 가장 효율적으로 구할 수 있다. 그러면 간단하게 LCS를 구하는 예시를 보면서 어떤 느낌인지 생각해보자. 문자열 "CAT"와 "CRAB"의 LCS를 구하여 보자. 위의 c[i][j]의 배열의 의미는 예를들어 c[1][2]라면 "CAT"에서는 C까지..
-
소수 찾기(에라토스테네스의 체)Computer Science/Algorithm 2020. 2. 9. 21:51
일반 방법으로 "소수찾기" 알고리즘 문제를 풀면 시간초과를 경험하는 일이 많기 때문에 에라토스테네스의 체를 이용해서 소수를 구해보자. 2부터 n까지의 모든 수를 나열한다. 2는 소수이므로 소수로 입력한다. 후에 2의 배수들은 소수가 아니게 되므로 n까지의 자기 자신을 제외한 2의 배수를 모두 지운다. 3은 소수이기에 체크하고, 똑같이 3의 배수를 모두 지운다. 다음 소수인 5도 지워지지 않았기에, 5의 배수를 모두 지운다. 위의 과정을 n의 제곱근전의 최대 소수까지 반복을 해준다 (Math.sqrt())를 이용하자. https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 | 프로그래머스 1부터 입력받은 숫자 n 사이에 있는 소수..
-
백 트래킹 (Backtracking) 이란?Computer Science/Algorithm 2020. 1. 30. 14:21
1. 백 트래킹 (Backtracking) 백트래킹 (Backtracking) 또는 퇴각 검색 (Backtrack)으로 불린다. 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보를 체크하지 않을 것을 표기)하고, 바로 다른 후보로 넘어가며, 결국 최적의 해를 찾는 방법 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보)를 상태공간트리(State Space Tree)를 통해 표현 각 후보를 DFS 방식으로 확인 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바..
-
그리디(Greedy) 알고리즘이란?Computer Science/Algorithm 2020. 1. 29. 17:20
1. 탐욕 알고리즘 이란? Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움 최적의 해에 가까운 값을 구하기 위해 사용됨 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 그리디 알고리즘은 항상 최적의 결과를 도출해내는 것은 아니지만 어느정도 최적의 해에 근접하게 구할 수 있다는 장점이 있다. 2. 탐욕 알고리즘 예 문제1: 동전 문제 지불해야 하는 값이 1260원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식이다. 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 가장 큰 동전부터 최대한 지불해야 한다..
-
동적 계획법 (Dynamic Programming)이란?Computer Science/Algorithm 2020. 1. 28. 23:21
1. 정의 동적계획법 (DP 라고 많이 부름) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 Memoization 기법을 사용함 Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨 예: 피보나치 수열 분할 정복 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 일반적으로 재귀함수로 구현 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음 예: 병합 정렬, 퀵 정렬 등 동적 계획법의 핵심은 하나의..
-
Dijkstra의 최단 경로 알고리즘이란?Computer Science/Algorithm 2020. 1. 28. 18:00
최단 경로 문제 종류 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 (single-source shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 예를 들면 A, B, C, D 라는 노드를 가진 그래프에서 특정 노드를 A 라고 한다면, A 외 모든 노드인 B, C, D 각 노드와 A 간에 (즉, A - B, A - C, A - D) 각각 가장 짧은 경로를 찾는 문제를 의미함 2. 최단 경로 알고..
-
Prim 알고리즘 이란?Computer Science/Algorithm 2020. 1. 27. 22:25
1. 프림 알고리즘 (Prim's algorithm) 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘) 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm 과 Prim's algorithm 비교 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함 Prim's algorithm은 특..
-
Union-Find(합집합 찾기)란?Computer Science/Algorithm 2020. 1. 23. 22:12
Union-Find 란? union-find 연산은 Kruskal의 알고리즘에서만 사용되는 것은 아니고 일반적으로 널리 사용된다. union(x, y) 연산은 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합의 합집합을 만든다. find(x)연산은 원소 x가 속해있는 집합을 반환한다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 위와 같이 여러 개의 노드가 연결되지 않은 채로 있다고 가정하자. 여기서 union(1, 4)와 union(5, 2)를 하면 아래와 같은 집합으로 변환된다. {1, 4}, {5, 2}, {3}, {6}, {7}, {8} 위와 같이 합쳐지는 것이다. 더 이해가 필요하기 때문에 구체..