[알고리즘/문자열] 20920번 : 영단어 암기는 괴로워 - python

링크 : https://www.acmicpc.net/problem/20920

20920번: 영단어 암기는 괴로워

 

---

• 문제
• 소요시간: 37분 20초(실패)

---

• 설계하기(접근방법) 

1. 입력받기

 

 

2. 구현하기

 

3. 출력하기

 

 

---

• 코드(출력)

1

---

• 얻어갈 부분

1. 데이터의 중복이 상관없고, 메모리가 충분한 경우 딕셔너리를 사용하는 것이 바람직하다. 딕셔너리의 경우 특정한 키를 찾아서 연산하는 코스트가 O(1)에 가깝기 때문에 연산이 굉장히 빠르게 이루어진다

 

2. 왜 딕셔너리의 연산이 빠른가???

해답 : 해쉬 함수로 구현되어 있기 때문이다.

입력받은 키값에 대해서 해쉬함수를 적용하고

나온 결과에 대한 위치에 값을 저장한다.

 

즉 예를 들어 'John 이라는 사람에 대해서 나이를 17이라고 저장하고 싶을 때'를 가정해보자

 

예를 들어 문자인 John을 정수로 변환하는 함수 ex) 각 문자의 아스키 코드를 더하는 함수라 가정

을 적용해서 200이라는 숫자가 나왔다고 가정하자(실제로는 아님)

 

그리고 그 숫자에 이어서 n mod m 즉 200 mod 55라는 연산을 적용한다고 가정하자

그러면 그 결과로 35라는 나머지값이 나온다

 

35라는 위치의 메모리에 값인 17을 저장해주면

이 John 이라는 숫자는 연산 2번 O(2)번만에 

Key : John을 통해 항상 특정한 위치에 Value : 17 을 저장할 수 있다

 

중복이 일어나는 경우는 체이닝이라는 기법을 통해서 테이블을 확장한다