자주 수행되는 작업들 디렉토리 경로 따라가기 디렉토리 내에 존재하는 파일들 나열하기 특정 파일의 존재 유무 판별하기 해당 작업들은 시스템의 성능 저하의 원인이 된다. 이 작업들은 검색에 기반해서 수행되는 작업들이므로 어떻게 해결해야할까. 1. 해싱 특정 항목 검색 시, 탐색 키에 대한 산술적 연산으로 키가 있는 위치를 계산하여 바로 찾아가는 방법이다. O(1) 시간 복잡도 1. 직접 번지 테이블 직접 번지 테이블(배열)에 저장하는 경우 전체 키(key)들의 집합(U)이 작은 경우에 효율적이다. 키 k가 테이블(T)에서 위치 k에 저장 테이블(배열)의 크기 = 집합 U의 크기 그러나 전체 키 값들의 집합 U가 클 때, 현실적인 컴퓨터 메모리 공간에서 테이블 T를 생성하는 것은 불가능하다. 또한 실제 저장되..

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으 www.acmicpc.net 1. 문제 문자열 A, B가 주어진다. A는 B보다 같거나 짧다. 1. A의 앞에 아무 알파벳을 추가한다. 2. A의 뒤에 아무 알파벳을 ..