공부방/알고리즘
Depth First Search Algorithm(DFS, 깊이 우선 탐색)
Depth First Search Algorithm(DFS) 그래프를 탐색하는 방법중 대표적인 DFS, BFS 중 DFS 알고리즘에 대해서 알아보려고 한다. 알고리즘 문제를 접할때 솔루션으로 많이 접하는 알고리즘이기도 하고 해당 탐색으로 부터 해서 특정 조건이 추가 됨으로써 백트래킹으로 확장(?)되기도 하며 최단거리 혹은 경로를 구하는 문제로 적용(확장) 되기도 합니다. 어찌되었든, 그래프를 탐색하는 방법인 Depth First Search Alogithm에 대해서 알아보도록 하겠습니다. 정의(Definition) 그래프 탐색의 한종류로, 특정노드로부터 시작하여 최대로 진입하 '깊이 우선 탐색' 이름에서 알 수 있는 것처럼, 가능한 그래프상에서 '더 깊이', '더 깊게' 탐색을 진행하는 그래프 탐색 방법..
Longest Common Sub-sequence Algorithm(LCS, 최장 공통 부분수열)
Longest Common Sub-sequence Algorithm(LCS) LIS알고리즘을 정리하다가 비슷한류의 알고리즘으로 보여 함께 이어서 정리하려고 한다. 이문제 또한 아마 DP를 이용한 문제가 될것으로 생각된다. 다만 문자로 이루어진 수열이기에 LIS에서 사용했던 이분탐색은 불가능해보인다. 그리고 해당 문제에서도 길이 뿐만이 아닌 해당 부분수열을 구하는 방법도 알아보도록 하겠다. 정의(Definition) 최장 공통 부분수열으로 두 문자열의 가장 긴 공통된 부분문자열을 구하는 문제 Longest Common Sub-sequence 불린다. 여기서 string이 아닌 sequence는 사용하는 이유는 각 단어가 갖는 개념적 의미가 다르기 때문이다. string : 연속된 문자열 sequence :..
Longest Increasing Sub-sequence Algorithm(LIS, 최장 증가 부분 수열 알고리즘)
Longest Increasing Sub-sequence Algorithm(LIS) 동적계획법(DP)문제를 풀다가 우연찮게 해당 알고리즘의 문제를 풀게되면서 이전 기억을 살려 다시한번 정리를 해보려고 한다. 해당 문제는 최장길이만 구하다 보니 동적계획법을 이용해서 해결이 되었지만, 더 다양한 문제를 해결하기 위해 그리고 LIS알고리즘을 더 잘 이해하기 위해 해당 페이지에 정리를 하려고 합니다. 정의(Definition) 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 알고리즘 부분 수열은 연속적이거나 유일한 필요가 없다. 최장길이를 구하거나, 해당 부분수열을 구할 수 있다. 여러 시간복잡도로 문제를 해결할 수 있다. 부분수열이란? 주어진 수열에서 특정 원소들을 선택해서 만들어진 수열을 그 수..
Binary Search Algorithm(이진 탐색 알고리즘)
Binary Search Algorithm 여러가지 탐색 알고리즘들을 보면 여러가지 알고리즘을 찾을 수 있다. 가장 기본적으로는 선형 탐색 방식으로 앞에서 부터 하나씩 비교하며 찾는 방법이다. 말그대로 탐색을 한 쪽 끝에서 다른 끝까지 탐색하기 때문에 탐색 대상이 뒤쪽에 위치해있으면서, 탐색 대상이 많은 경우 매우 비효율적일 수 있다. 하지만, 만약 탐색하고자 하는 데이터가 정렬이 되어 있는 경우 좀더 효율 적인 방법을 이용할 수 있는데 이것이 바로 이진 탐색 알고리즘이다. 정의(Definition) 정렬된 탐색대상에서 특정 대상을 찾고자 할때 사용 할 수 있는 탐색 알고리즘 정렬된 알고리즘으로 부터 탐색 중간값과 탐색대상을 비교후 탐색 범위를 절반으로 줄여가며 찾는 알고리즘 이렇게 정렬된 알고리즘으로 ..
Recursion Algorithm(재귀 알고리즘)
Recursion Algorithm 처음 재귀를 접하게 되면 이해가 안될 것이다. 다만 위 그림을 보면 대충 재귀가 무엇인지 감이 잡힐 것이다. 재귀에 대해서 알아보면 임의의 함수가 자기자신을 호출하는 재귀 호출을 이용하는 알고리즘이다. 같은 행동을 반복적으로 행할때 사용하는 알고리즘인 것이다. 그렇다면 재귀알고리즘은 반복문과는 어떠한 차이가 있을까? 그리고 재귀를 이용함으로써 얻을수 있는 이점은 무엇이고 단점은 무엇인가를 알아보고자한다. 정의(Definition) 임의의 함수가 자기자신을 호출하는 것으로 그 함수를 재귀함수라하며 그 호출을 재귀호출이라한다. 이렇듯 재귀알고리즘은 스스로를 호출하는 함수를 이용한 풀이를 재귀 알고리즘이라고 말한다. 재귀알고리즘을 이용하기 위해 재귀함수를 만들때는 중요한 점..
Euclidean algorithm(유클리드 호제법)
Euclidean Algorithm 유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a,b에서 a를 b로 나눈 나머지를 r이라고 했을때 GCD(a,b) = GCD(b, r)과 같게 되고 r이 0이 될때의 b의 값이 최대공약수가 된다. 일반적으로 쉽게 생각할 수 있는 최대공약수를 구하는 방법은 모든 자연수를 나눠보는 것이다. 하지만 이경우 시간복잡도는 O(n)이 된다. 다만 이 유클리드 호제법을 사용할 경우 O(logN)이 되어 더 빠른 속도를 나타낼 수 있다. Greatest Common Divisor(GCD) 2개의 자연수의 공통된 약수인 공약수 중 가장 큰 공약수가 최대공약수이다. 소스코드 ※ 아래 코드는 a>b 를 만족함을 가정 > C++ int gcd(int a,..
Sieve of Eratosthenes(에라토스테네스의 체)
Sieve of Eratosthenes 수학에서 소수를 찾기 위한 방법중 하나로 고대 그리스 수학자 에라토스테네스가 고안한 방법이다. Prime(소수) 소수는 '양의 약수를 2개만 갖는 자연수' 즉, 자신보다 작은 두개의 자연수를 곱하여 만들수 없는 1보다 큰 자연수로 자기자신과 1의 곱으로만 나타낼수 있는 1보다 큰 자연수를 말한다. Algorithm 해당 에라토스테네스는 자신보다 작은 두개의 자연수를 곱하여 만들수 없다는 성질을 이용한다. 2는 명확히 소수임을 알수 있고 2의 배수는 모두 위의 소수조건을 만족하지 못하므로 소수가 아님을 알 수 있다. 3은 2로 인해 지워지지 않았으므로 3보다 작은수의 배수가 아님을 알 수 있고 즉 소수임을 확인할 수 있으며 3의 배수는 소수가 아니므로 3의 배수 또한..
Hanoi Tower(하노이의 탑)
Hanoi Tower(하노이의 탑) 프랑스 수학자 에두아르 뤼카가 클라우드 교수라는 필명으로 발표하였고 그 후 1년 후 헨리 드 파르빌이 다음과 같은 이야기로 하노이 탑을 소개하였다. 인도베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1 큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일..