PS/자료구조 & 알고리즘
분할 정복법 (Divide and conquer) 큰 규모의 문제를 풀기 위해 하위 문제로 나누어 풀이하고 이들의 해답을 결합하여 최종 해답을 얻는 방법이다.문제를 가장 작은 단위의 문제로 분할한 후, 해당 문제들을 결합하여 부분 해답을 도출, 또 다시 부분 해답을 결합하는 과정을 통해서 최종적으로 큰 규모의 문제를 풀이한다. 분할 정복법의 과정1. 분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.2. 정복(Conquer): 나눈 작은 문제를 각각 해결한다.3. 통합(Combine): (필요하다면) 해결된 해답을 모은다. 분할 정복법의 조건 1. 문제의 분할이 쉽게 가능해야 한다.주어진 문제를 작은 부분 문제들로 나눌 수 있어야 한다. 또한 문제를 분할하는 과정이 너무 복잡..
그리디 알고리즘 (Greedy) 나는 미래를 위해서 지금 어떤 행동을 해야 가장 효율적일지 모른다. 하지만 눈앞에 보이는 상황에서 현재의 최선을 다하려고 한다.그리고 이것은 그리디 알고리즘을 설명하는 말이다. 그리디 알고리즘은 매번의 선택의 순간에서의 최선인 답을 도출하면서 결과를 도출하는 방법이다.해당 방법은 매 순간에서는 최선일 수 있고 적당히 좋은 값을 찾는 것이 목표이지, 전체적으로 보았을 때에는 항상 최적이라는 보장이 없다. 그리디의 최적 조건 그리디가 항상 최적해를 보장하지 못한다고 하였다. 따라서 그리디를 이용하여 최적해를 구해야 하는 경우에 따져봐야 하는 조건이 있다. 1. 탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 미쳐서는 안 된다.2. 최적 부분 구조: 작은 부분 문..
동적 계획법 최적 부분 구조가 가진 중복된 하위 부분해를 사용해서 복잡한 문제를 풀이하는 방법주로 [Top-Down + 메모리제이션]혹은 [Bottom-Up + 타뷸레이션]을 사용하는 전략을 사용하며동일한 작은 문제가 여러 번 반복되는 경우가 많은 경우 유용하게 사용된다. Top-down 방식 DP: 재귀 호출을 사용하여 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해를 계산할 때 해당 결과를 저장하고 재활용한다. 이를 통해 중복 계산을 피하고 연산 시간을 절약할 수 있다.Bottom-up 방식 DP : 작은 부분 문제부터 시작하여 상위 문제로 올라가면서 저장해둔 부분 문제의 결과를 사용한다. 동적 계획법(다이나믹 프로그래밍, DP)에 대한 자세한 설명은 아래의 포스팅을 살펴보자.https://s..
동적 계획법 최적 부분 구조가 가진 중복된 하위 부분해를 사용해서 복잡한 문제를 풀이하는 방법주로 [Top-Down + 메모리제이션]혹은 [Bottom-Up + 타뷸레이션]을 사용하는 전략을 사용하며동일한 작은 문제가 여러 번 반복되는 경우가 많은 경우 유용하게 사용된다. Top-down 방식 DP: 재귀 호출을 사용하여 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해를 계산할 때 해당 결과를 저장하고 재활용한다. 이를 통해 중복 계산을 피하고 연산 시간을 절약할 수 있다.Bottom-up 방식 DP : 작은 부분 문제부터 시작하여 상위 문제로 올라가면서 저장해둔 부분 문제의 결과를 사용한다. 동적 계획법(다이나믹 프로그래밍, DP)에 대한 자세한 설명은 아래의 포스팅을 살펴보자.https://s..
누적합 (Prefix Sum) 배열 또는 리스트 등에서 일정 구간의 합을 빠르게 계산하기 위한 방법이면서 동적 계획법(DP)의 형태 중 하나이다.기본적인 방식은 각 요소까지의 누적 합을 계산하여 이를 배열에 저장해 두는 것이다. 이후에 특정 구간의 합을 구할 때는 해당 구간의 끝 지점까지의 누적 합에서 시작 지점까지의 누적 합을 빼는 것이다. 해당 알고리즘은 배열 또는 리스트의 요소가 고정되어 있을 때 구간 합을 반복적으로 계산해야 하는 경우 유용하게 사용될 수 있다. 1차원 배열의 누적합 (백준 11659) 다음 문제를 보면, 1차원 배열이 주어지며, 그 이후로 주어지는 시작 인덱스와 마지막 인덱스의 쌍에 대해서 그 구간의 합을 구하는 문제이다.진짜 단순하게 각 입력에 대해서 일일이 반복문을 돌려..
부분 문제 해결 : Top-Down & Bottom-Up 이전 포스팅에서 재귀와 반복 알고리즘을 살펴보면서, 복잡한 문제를 하위 문제로 나누어 해결하는 방법들에 대해서 살펴 보았었다.부분 문제 해결 방법에는 크게 두 가지 방식이 있다. 1. Top-Down 방식 : 재귀적인 방식으로 문제를 해결해서 큰 부분의 문제를 작은 부분의 문제로 쪼개가면서 해결하고, 작은 부분 문제들을 결합하여 전체 문제의 해를 구하는 방식이다. 2. Bottom-Up 방식 : 주로 반복적인 방법을 사용하여, 먼저 작은 부분 문제들을 해결하고 이를 이용하여 더 큰 부분 문제들을 해결하는 과정이다. 피보나치 수열의 Top-Down 방식static int fib(int n){ if(n 피보나치 수열의 Bottom-Up..
백트래킹(Backtracking) 어떤 문제를 풀 때에 모든 경우의 수를 체크해보면서, 해가 아닌 케이스의 경우를 만나면, 그 이전 상태로 되돌아가서 다른 케이스를 체크하는 알고리즘이다. 상태 공간은 문제를 해결하기 위해 가능한 모든 상태의 집합을 의미하는데, 이를 트리 형태로 표현할 수 있을 때 유용하게 사용될 수 있는 방법이다. 즉 상태공간 트리를 탐색하는 알고리즘이라고 보아도 무방하다. 1. 깊이 우선 탐색(DFS) : 백트래킹은 DFS와 같이 재귀적으로 깊숙하게 확장해나가면서 해를 찾아간다. 그렇지만 DFS와 달리 해를 찾아가는 중 해당 경로가 틀린 해답이라는 것을 알아챈다면 바로 이전 상태로 Backtracking한다. 2. 유망성(Promising) 판단과 가지치기 : 현재 상태가..
정렬 정렬 알고리즘에 대한 연구는 컴퓨터 과학자들 사이에서 오래 전 부터 이루어져 왔다.그 과정에서 많은 정렬 알고리즘들이 탄생했는데, 그 중 잘 알려진 정렬 알고리즘 몇몇개를 살펴 보려고 한다. 살펴볼 것은 아래와 같다. 시간 복잡도가 O(n^2)인 정렬 : 버블 정렬, 삽입 정렬, 선택 정렬시간 복잡도가 O(nlog(n))인 정렬 : 병합 정렬(항상), 퀵 정렬(일반적으로) 참고로 자바에서 내장되어 있는 Arrays.sort() 메서드는 다음 정렬 알고리즘을 사용한다.퀵 정렬: 퀵정렬 중 이중 피벗 퀵정렬을 사용한다.병합 정렬: JDK 6까지 주로 사용되었으며, 아직 남아있는 부분이 있다. 여담으로 현재 가장 많이 사용되고 있는 정렬 알고리즘은 퀵 정렬, 병합 정렬, 힙 정렬 정도가 있다. 그렇다..
해시 테이블 (Hash Table) 해시 테이블(Hash Table)은 데이터를 효율적으로 저장하고 검색하기 위한 자료구조이다.데이터를 키-값 쌍으로 매핑한 후, 이를 배열에 저장하는데, 각 키에 대해서 해시 함수를 적용하여 해시 값을 계산하여 이를 배열의 인덱스로 사용한다. 따라서 특정 키에 대한 검색이 빠르게 이루어질 수 있다. 버킷(Bucket): 해시 테이블의 각 슬롯을 가리키는 용어이다. 데이터 삽입 과정해시 함수 적용: 데이터의 키를 해시 함수에 넣어 해시 값을 계산한다.해시 값의 인덱스 결정: 해시 값을 기반으로 배열에서 저장될 위치인 인덱스를 결정한다.데이터 저장: 결정된 인덱스에 데이터를 저장한다. 만약 해당 인덱스에 이미 데이터가 저장되어 있다면 충돌이 발생한 것이다.충돌 해결: 충..
