[패스트캠퍼스 :: 코딩테스트 인강] 3주차 ② 해쉬 테이블 + 기초 문제풀이

알고리즘/기술면접 완전 정복 올인원 패키지 Online

 

20. 해쉬 테이블 - 4

21. 해쉬 테이블 - 5

기본 자료구조 - 01. 기초 문제풀이

---

강의 + 코드 + 문제풀이 == 정신없다

 

기억에서 잊히기 전에 해쉬 테이블 복습과 추가 개념 학습을 했고,

애매하게 흐름이 끊길 것 같아서 이전에 학습한 배열 개념이 적용된 문제를 푸는

강의를 추가로 들었다.

 

---

 

 

기존의 해쉬 테이블에서 충돌이 일어날 때,

해결방법 01. Chaining 기법 (이전 게시물)

해결방법 02. Linear Probing 기법

 

• 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법

• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장하는 기법

  • 저장공간 활용도를 높이기 위한 기법

 

<조건이 주어진 해쉬 테이블 함수 정의>

1. 해쉬 함수: key % 8
2. 해쉬 키 생성: hash(data)

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]
                return
            elif hash_table[index][0] == index_key:
                hash_table[index][1] = value
                return
    else:
        hash_table[hash_address] = [index_key, value]

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                return None
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None

 

 

 

 

해쉬 구조의 시간 복잡도

 

---

문제풀이

백준 알고리즘 - 음계 문제

2920번: 음계

a = list(map(int, input().split(' '))) # map 함수를 이용해서 공백을 중심으로 나누어 int 타입으로 리스트 저장

# 초기값 설정
ascending = True 
descending = True

# 전체 리스트를 반복하면서 배열의 특성을 활용하여
# 이전 인덱스에 위치한 원소와 비교
for i in range(1, 8):
	if a[i] > a[i-1]:
    	descending = False
	elif a[i] < a[i-1]:
    	ascending = False
        
# 반복문을 통해 나온 결과를 가지고
# 출력값 판단
if ascending:
	print('ascending')
elif descending:
	print('descending')
else:
	print('mixed')

 

 

 

---

이전에 학습한 자료구조보다는 확실히 레벨이 올라간 듯한 느낌이 드는 자료구조였다.

해쉬 테이블이 어떤 문제에 어떻게 적용이 될지도 궁금해졌다.

항상 자료구조를 공부하면서 느끼는 점이지만

이러한 구조들이 실생활에, 실제 코드에, 문제 풀이에 어떻게 적용되는지가 가장 궁금하고,

또 그러한 알고리즘을 잘 짤 수 있을지도 두렵기도 하고 무섭기도 하다.

 

이번에 풀어본 문제는 난이도 '하'였는데, 의외로 알고 나면 간단한 문제인데

혼자서 로직을 짜보았을 때는 자꾸 복잡한 구조를 생각하게 된다.

 

조금은 더 단순하고 간단하게 생각할 필요가 있을 것 같다.

 

직관적이고, 단순하지만 또 제 기능은 갖추는 그런 Clean한 해결 구조로 생각해야 하는 것이 내가 해결해 나가야 할 문제!

 

이게 난이도가 '하'라면 도대체 기업 문제는 어떨까...

 

더 열심히 들어야겠다.

V^___^

 

 

 

 

 

[패스트캠퍼스 100% 환급 챌린지 미션 중입니다.]

 

 

 

 

 

알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. | 패스트캠퍼스