분할 정복이란 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 계산하고 이를 병합해 문제를 해결하는 기법이다. 문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제들로 나누고(Divide) 문제를 해결한 다음(Conquer) 그 결과를 이용해 다시 전체 문제를 해결하며 합치는 방법이다. 관련 알고리즘 분할 정복 방식으로 해결되는 문제로 다음 알고리즘이 있습니다. 정렬 문제(퀵 정렬, 병합 정렬) 큰 숫자 곱하기(Karatsuba 알고리즘) : n자리 수 2개를 곱하여 결과를 나타내는 알고리즘 이진 탐색 (Binary Search) Closet Pair of Points 문제 : 모든 point 쌍의 거리 중 최소의 거리를 찾는 문제 Strassens's 알고리즘 : 두 ..
♾️ Computer Science/자료구조
이름 그대로 두 가지 포인터를 사용하여 문자열이나 배열(또는 리스트)에서 원하는 값을 찾거나 반복문을 써야 할 때 쓰는 방식 투포인터 알고리즘은 Two Pointer Algorithm 또는 Sliding Window라고 부른다. 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다. 코딩 테스트 문제를 풀다 완전 탐색으로 해결하다보면 시간 초과가 나는 문제가 종종 있다. 이러한 경우 투 포인터를 사용하면 메모리와 시간 효율성을 높일 수 있다. 포인터는 크게 두가지 방식으로 쓰인다. 앞에서 시작하는 포인터와 끝에서 시작하는 포인터가 만나는 형식 또는 빠른 포인터(fast runner)가 느린 포인터(slow runner)보다 앞서는 형식 ..
DFS란 말 그대로 깊은 부분을 우선적으로 탐색하는 기법이다. 이 알고리즘의 핵심은 스택(stack) 자료구조를 사용하는 것이다. 스택 자료구조는 FILO (First-In-Last-Out) 방식을 따른다. 즉 스택에 데이터를 집어넣을 때 순서와 스택에서 데이터를 꺼낼 때 순서가 역방향이라는 것이다. DFS는 가능한 모든 경로(후보)를 탐색한다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다. 따라서 N! 가지 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것이다. DFS 알고리즘 구체적인 동작 과정은 아래과 같다. 탐색 시작 노드를 스택에 삽입하고 "방문처리"를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 ..
BFS란 말 그대로 너비를 우선해서 그래프를 탐색하는 기법이다. 이 알고리즘의 핵심은 큐(queue) 자료구조를 사용하는 것이다. 큐를 사용할 때 가장 성능이 좋기 때문이다. BFS는 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 반복적으로 큐에 넣어 먼저 큐에 들어있던 노드부터 방문하면 되는 것이다. BFS 알고리즘 구체적인 동작 과정은 아래와 같다. 탐색 시작 노드 정보를 큐에 삽입하고 “방문 처리” 한다. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 여기서 “방문처리” 란 탐색한 노드를 재방문하지 않도록 구분하는 것이다. 즉, 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체..
다이나믹 프로그램은 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법이다. 다음의 2가지 조건을 만족할 때 다이나믹 프로그래밍을 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있음 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일함 위 조건을 만족하는 대표적인 예로 피보나치 수열이 있다. 피보나치 수열은 다음의 점화식을 만족하는 수열이다. 해당 피보나치 수열을 Python 재귀함수로 구현한다면 다음과 같은 코드로 표현할 수 있다. import time def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) for num in range(5, 40, 10): start = time.time() r..
