해시맵

CS/자료구조

[자료구조 및 프로그래밍] 12. Hashing & Hash Table

2023.12.02

자료구조와 탐색 시간 지금까지 자료구조를 정리하면서 주요하게 다뤘던 내용 중 하나는 바로 "탐색" 이었다. 그리고 원하는 자료를 탐색하기 위해 수행한 가장 근본적인 동작은 바로 키를 비교하는 것이었다. 어떤 키가 다른 키와 같은지 다른지, 혹은 큰 지 작은 지를 비교하여 원하는 값을 탐색해내갔다. 여기 3글자 알파벳 소문자로 이루어진 이름과 4개의 숫자 쌍을 저장하는 간단한 주소록 프로그램이 있다. 그리고 이 주소록 프로그램에서 주소록 정보를 BST를 이용해 저장한다고 해보자. 만약 1000개의 주소록 데이터를 BST에 저장한다면, 최적의 경우 BST의 높이는 log(1000) 이므로 대략 10이라고 할 수 있고, 최악의 경우의 높이는 대략 1000이 될 것이다. 또 평균적으로는 1000개의 데이터를 B..

알고리즘 (PS)/BOJ

[백준] 1701 - Cubeditor (G2)

2022.01.31

https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 같은 부분 문자열이 2개 이상 나타나는 가장 긴 부분 문자열의 길이를 찾는 문제이다. 나는 골드 3의 티어로 난이도를 낮게 매겼다. 나는 신촌 연합 알고리즘 캠프에서 배운 라빈 카프 알고리즘에 이분탐색을 더하여 풀었다. 이분탐색을 사용한 이유는 다음과 같다. 부분문자열의 길이가 n일 때 문제 조건을 만족한다면 이 해당 부분문자열의 부분문자열도 문제의 조건을 만..

[자료구조 및 프로그래밍] 12. Hashing & Hash Table

[백준] 1701 - Cubeditor (G2)

티스토리툴바