SW알고리즘5 [DFS & BFS] 깊이 우선 탐색과 너비 우선 탐색의 이해 및 구현 "DFS & BFS" 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) DFS, BFS는 트리 탐색 알고리즘의 기본으로 그래프, 경우의 수 등 다양하게 쓰이는데 모든 알고리즘에 사용된다고 해도 과언이 아닙니다. DFS와 BFS의 차이와 서로 간 장단점에 대해서 알아보고, 탐색하는 코드를 직접 구현해보겠습니다. DFS 이론 깊이 우선 탐색 (DFS / Depth First Search)은 해가 존재할 가능성 있으면 계속 전진하는, 일단 만나는 노드의 다음 레벨(자식)로 넘어가며 탐색하는 전위 순회 방식의 탐색 방법입니다. 일반적으로 Stack 자료구조를 이용하나 재귀함수나 배열을 잡아서도 사용하기도 하는데, 재귀 호출이 이루어질 때마다 위치가 점점 깊게 들어가고 (레벨링이 높아짐) 너무 깊게 들어가면 o.. 2021. 1. 12. [허프만 코드] Huffman Code의 이해 및 구현 "허프만 코드" 문자 빈도 수를 이용해 통계적으로 압축하는 알고리즘 이론 허프만 코드는 압축 알고리즘 중 하나로, 입력 데이터를 더 적은 용량으로 만드는 것입니다. 허프만 코드의 요점은 자주 나오는 문자에는 짧은 비트를, 조금 나오는 문자에는 긴 비트를 할당하는 것입니다. 예를 들어 AABBAC라는 문자열을 살펴보면, 각 문자의 빈도수는 아래와 같습니다. A : 3번 B : 2번 C : 1번 이에 따라, 가장 자주 나오는 문자 A에는 0, B는 10, C는 11을 부여하면 001010011로 나타내어집니다. 원래의 문자열 AABBAC는 6글자 이므로 48 bit가 사용되지만, 압축된 코드 001010011은 9bit만 사용되어 표현할 수 있습니다. 1. 주.. 2020. 12. 19. [문자열 문제] 가장 긴 '반복 부분 문자열' 길이 구하기 참고 문제 출처 www.acmicpc.net/problem/1605 1605번: 반복 부분문자열 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열' www.acmicpc.net 문제 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분 문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분 문자열을 '반복 부분 문자열'이라고 부르자. 문자열이 주어지면, 가장 긴 '반복 부분 문자열'의 길이를 구하는 프로그램을 작성하시오. 입력 (+테스트 케이스 추가, -문자열의 길이 제공X) 첫째 줄에 테스트 케이스의 수 .. 2020. 12. 17. [파라메트릭 서치] Parametric Search의 이해 및 구현 "파라메트릭 서치" 최적화 문제를 결정 문제로 바꾸어 푸는 것 이론 파라메트릭 서치 (Parametric search)는 이분 탐색(binary search)의 일종으로 선형 탐색에 비해 효율적인 시간 복잡도를 가집니다. 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정문제 로 바꾸어 푸는 것이라고도 할 수 있습니다. 어떤 명제 에 대해 True와 False의 경곗값 v0를 찾아야 할 경우 파라메트릭 서치를 이용하게 됩니다. 중간 위치는 (0+8)/2 =4 이므로, p(4)를 확인해보니 True -> 4는 v0의 후보군이 되고, 5~8은 탈락. 다음 중간 위치는 (0+3)/2 =1 이므로,p(1)을 확인해보니 False -> 0~1은 탈락. 다음 중간 위치는 (2+3.. 2020. 12. 16. [Hash 알고리즘] 해시의 이해 및 구현 "해시" 데이터를 다른 형태로 변환해주는 함수 이론 해시함수(hash function)는 데이터를 다른 형태로 변환해주는 함수를 뜻합니다. 해시 함수에 의해 얻어지는 값은 해시값, 해시 코드, 해시 체크섬 또는 간단하게 "해시"라고 합니다. 해시 함수만 사용했을 때보다 자료구조와 연결하면 강력한 성능을 발휘하게 됩니다! 많이 쓰는 자료구조로는 해시 테이블 (hash table)을 들 수 있습니다. 해시 테이블은 데이터의 삽입, 삭제, 탐색을 지원하는 자료구조입니다. 해시 테이블의 삽입, 삭제, 탐색은 평균적으로 O(1), 최악의 경우 O(n) 시간이 소요됩니다. 크기가 S인 해시 테이블의 구조를 보면, 0~ S-1 까지 번호가 붙은 버킷이 S개 존재합니다. 데이터 A를 삽입/삭제/탐색할 때에는 해시함수에.. 2020. 12. 16. 이전 1 다음
