[알고리즘] HashMap, TreeMap, HashSet, TreeSet
1. HashMap 해시 함수란, 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 값, 해시 코드, 해시 체크섬 혹은 해시라고 부른다. 보통 해시함수는 해시값이 다르다면 서로 다른 데이터를 가지고 있어야 하지만, 해시 값을 결정하는 함수에 따라서 서로 다른 데이터가 하나의 해시값에 저장이 되는 경우도 있다. 이런 경우를 해시 충돌이라고 한다. 해시 충돌이 빈번하게 발생하면 효율성을 떨어뜨리기 때문에 해시 충돌을 최소화하는 것이 좋다. 파이썬에서는 이러한 hashmap을 간단하게 dictionary의 형태로 나타낼 수가 있다. hashmap은 (key, value)의 쌍으로 이루어져 있기 때문에 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O..
2022. 2. 12.
2021.6.13 TIL : [알고리즘] 백트래킹 (BackTracking)
마지막 알고리즘 수업에서는 백트래킹과 NP-완전을 배웠다. 둘 다 조금은 이해하기 어렵다고 느껴져서 오늘은 이 내용을 정리해보고자 한다. 문제에서 어떤 해를 구할 때, 해의 형태가 n개의 원소로 이루어진 튜플인 경우가 있다. (이 때, 이 튜플 내의 각 원소를 x1, x2, x3, ... xn이라고 한다.) 해의 원소들(xi)은 유한 집합(Si)에서 선택된다. 백트래킹은 기준함수인 P를 최대화/최소화/만족하는 해를 구하는 문제를 해결하는데 적용하는 방법으로 효율적인 알고리즘이 존재하지 않을 경우에 사용한다. 모든 문제의 사례에 대해서 효율적이진 않지만 많은 문제 사례에서 효율적이다. mi를 Si의 크기, 즉 원소의 개수라고 하면, xi가 선택할 수 있는 해는 각각 m1, m2, m3, ..., mi, ...
2021. 6. 13.
