알고리즘/개념 정리
-
Hash / Hash Table / Hash Function 및 백준 문제알고리즘/개념 정리 2021. 8. 11. 22:10
해시 함수(Hash Function) 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수. → 해시 함수를 구현하는 방법에 따라서 서로 다른 문자열이 같은 고정 문자열로 되기도 하는데, 이를 충돌이라고 한다. key를 해쉬한 결과를 배열의 index로 사용하게 된다. 해시 충돌(Hash Collision) 서로 다른 문자열을 Hash한 결과가 동일한 경우 해시 함수를 H()라고 했을 때 , H(s1) = H(s2)인 경우 Chaining 또는 Open Addressing을 통해서 해결해야 한다. index가 겹치면 선형 검색을 하는 경우도 있음 → Hash가 항상 O(1)을 보장하는 것은 아님. 해시 테이블(Hash table) Key, Value로 된 쌍을 저장하는 구조 Hash table V..
-
비트마스킹(BitMasking) 정리알고리즘/개념 정리 2020. 12. 27. 14:56
비트마스킹(BitMasking) 정리 목차 비트마스킹이란? 비트 켜고 끄기 활용 방법 비트마스킹이란? 비트 마스킹이란, 어떤 정수 값을 비트를 이용해 이진수로 표현하는 방법을 말합니다. 예시를 하나 들어보겠습니다. 책상 5개가 일렬로 있는데 ( . . . . . ) 여기에 사람을 앉히는 경우는 (OXXXXX, OOXXX) 등등 2^5 가지가 있겠죠 이 상태를 모두 표현하여 가지고 있고 싶은데 이 때 활용할 수 있는 방법이 비트마스킹입니다. ex) OOOXX > 이 경우에는 11100(2) == 28 OXXXXO > 이 경우에는 10001(2) == 17 등등 이런식으로 상태를 저장하여 활용하는 방식입니다. 비트마스킹의 이점은 더 적은 메모리로 많은 상태를 표현할 수 있다는 것입니다. 비트 켜고 끄기 비트..
-
LCA(Lowest Common Ancestor) / 최소 공통 조상 알고리즘알고리즘/개념 정리 2020. 12. 27. 01:26
LCA(Lowest Common Ancestor) / 최소 공유 조상 목차 1. LCA란? 2. O(N) LCA 알고리즘 3. O(logN) LCA 알고리즘 LCA란? LCA란 말 그대로 최소 공유 조상이다. 그래프에서 두 노드 각각의 부모들을 쭉 타고 올라갔을 때 최초로 공유하는 부모를 말한다. 이 예시에서 노드 5와 노드 3의 최초 공유 조상은 1이 된다. 이 경우에 노드 12와 노드3의 최소 공유 조상은 1이 된다. O(N) LCA 알고리즘 자 그러면 이제 LCA 알고리즘을 구현해 봅시다. LCA 구현을 위해 3가지 단계가 필요합니다. 각 노드들의 depth를 구하여 가지고 있는다 ( depth : root 노드부터 자기 노드까지의 거리(깊이)) LCA를 구하려는 두 노드 중 더 깊은 노드의 dep..