데굴데굴 개발자의 기록

동적 계획법 최적 부분 구조가 가진 중복된 하위 부분해를 사용해서 복잡한 문제를 풀이하는 방법주로 [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) 판단과 가지치기 : 현재 상태가..

Scanner Scanner는 사용자로부터의 입력을 읽기 위한 클래스이며. 주로 키보드 입력을 읽거나 파일에서 데이터를 읽을 때 사용된다. 코딩 테스트를 비롯한 PS 문제에서 BufferedReader와 함께 입력을 받기 위해서 많이 사용된다. Scanner은 BufferedReader에 비해서 사용하기 용이한 메서드들을 클래스에서 많이 제공한다. 따라서 BufferedReader에 비해서 자료형을 처리하거나 간단하게 입력을 처리하기에 용이하다. 그렇지만 데이터를 파싱하기 위해서 내부적으로 정규 표현식 등을 사용하여 BufferedReader에 비해 내부적으로 복잡한 과정을 거쳐 처리 시간이 더 오래 걸린다. 따라서 입력량이 고정되어 있고, 그 양이 많지 않은 경우에는 Scanner를 사용하여 편리하게 ..

정렬  정렬 알고리즘에 대한 연구는 컴퓨터 과학자들 사이에서 오래 전 부터 이루어져 왔다.그 과정에서 많은 정렬 알고리즘들이 탄생했는데, 그 중 잘 알려진 정렬 알고리즘 몇몇개를 살펴 보려고 한다. 살펴볼 것은 아래와 같다. 시간 복잡도가 O(n^2)인 정렬 : 버블 정렬, 삽입 정렬, 선택 정렬시간 복잡도가 O(nlog(n))인 정렬  : 병합 정렬(항상), 퀵 정렬(일반적으로) 참고로 자바에서 내장되어 있는 Arrays.sort() 메서드는 다음 정렬 알고리즘을 사용한다.퀵 정렬: 퀵정렬 중 이중 피벗 퀵정렬을 사용한다.병합 정렬: JDK 6까지 주로 사용되었으며, 아직 남아있는 부분이 있다. 여담으로 현재 가장 많이 사용되고 있는 정렬 알고리즘은 퀵 정렬, 병합 정렬, 힙 정렬 정도가 있다. 그렇다..

해시 테이블 (Hash Table)  해시 테이블(Hash Table)은 데이터를 효율적으로 저장하고 검색하기 위한 자료구조이다.데이터를 키-값 쌍으로 매핑한 후, 이를 배열에 저장하는데, 각 키에 대해서 해시 함수를 적용하여 해시 값을 계산하여 이를 배열의 인덱스로 사용한다. 따라서 특정 키에 대한 검색이 빠르게 이루어질 수 있다. 버킷(Bucket): 해시 테이블의 각 슬롯을 가리키는 용어이다.  데이터 삽입 과정해시 함수 적용: 데이터의 키를 해시 함수에 넣어 해시 값을 계산한다.해시 값의 인덱스 결정: 해시 값을 기반으로 배열에서 저장될 위치인 인덱스를 결정한다.데이터 저장: 결정된 인덱스에 데이터를 저장한다. 만약 해당 인덱스에 이미 데이터가 저장되어 있다면 충돌이 발생한 것이다.충돌 해결: 충..

허프만 코딩 데이터 문자의 등장 빈도에 따라 다른 길이의 부호를 사용하여 데이터를 압축하는 알고리즘이다. 자주 등장하는 문자는 짧은 부호로, 드물게 등장하는 문자는 긴 부호로 표현하여 데이터의 크기를 줄이는 데 효과적이다.알고리즘에서 우선순위 큐가 사용되며, 이를 기반으로 빈도 기반의 허프만 부호화를 효율적으로 수행할 수 있다.Unix 파일압축 명령어에 사용, JPEG, MP3 압축하기 위한 서브루틴으로서도 활용된다.  허프만 코딩 : 과정  1. 입력압축할 데이터에 대해서 입력받는다.AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE 2. 문자 빈도 분석 압출할 데이터에서 각 문자의 등장 빈도를 분석한다.A : 15B : 7C : 6D : 6E : 5 3. 허프만 트리 생성우선 빈..

우선순위 큐 (Priority Queue)   우선순위 큐는 일반적인 큐와 다르게, 우선순위 큐는 각 요소마다 우선순위가 지정되어 있어서, 우선순위가 높은 요소가 일반적으로 먼저 처리되는 형태의 자료구조이다.요소들은 우선순위에 따라 정렬되어 있으며, 우선순위에 따라 삽입된 요소들이 정렬되어 있는 형태를 띈다. 스택과 큐 또한 일종의 삽입 순서에 따른 우선순위 큐의 종류라고 볼 수 있다.   힙(Heap) 힙은 대표적인 우선순위 큐의 종류이다. 주로 이진 힙으로 구현하며, 대표적인 종류로는 최소 힙과 최대 힙이 있다. 완전 이진 트리 : 힙은 완전 이진 트리의 구조를 가지고 노드가 왼쪽부터 차례로 채워진다. 최소 힙과 최대 힙: 최소 힙(Min Heap)의 경우 부모 노드의 값은 자식 노드의 값보다 항상 ..