CS/자료구조 및 알고리즘 (2) 썸네일형 리스트형 [알고리즘] 해시 알고리즘 Components of Hashing Key : 해시 함수에 입력값으로 들어가는 문자열 혹은 정수를 의미한다. Key를 통해 해시 테이블의 인덱스 값이나 위치를 알 수 있다. Hash Function : 입력 key 값을 받아 해시 테이블의 인덱스 값을 반환하는 함수이다. Hash Table : key-value 형태의 자료구조 이며, 해시 함수를 통해 해시 인덱스를 구성한다. What is Hash functions? 해시 함수는 수학적인 연산을 통해서, key와 value 사이의 매핑을 만든다. 해시 함수의 결과는 hash value 또는 해시라고 불려진다. hash value는 원래의 문자열을 대표하지만, 일반적으로 원본보다는 길이가 짧다. 해시 함수의 종류 Division Method 해시값을 .. 2023. 12. 12. 11:02 [알고리즘] 백트래킹 백트래킹이란? 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이다. 방식에 따라 DFS, BFS BFS가 있다. 다시 말해, DFS를 사용하여 경로를 탐색하되, 주어진 조건에 일치하지 않는 경우 다시 이전 단계로 돌아가 다른 경로로 탐색을 하는 것이다. 필자는 처음 백트래킹 정의를 보고 DFS를 통해 모든 경로를 탐색하는 것하고 무엇이 다른 지 알지 못하여, 이해하는데 시간이 오래 걸렸다. 이후 생각해보니, 모든 경로를 탐색하는 개념은 동일하지만, 백트래킹은 경로 탐색 중 조건에 부합하지 않거나 or 해가 아닌 경로일 경우 굳이 더 탐색하지 않고 이전 노드로 돌아와 다른 경로를 탐색하는 방식이였다. 즉, DFS를 통한 모든 경로 .. 2023. 11. 21. 20:20 이전 1 다음
