[Python] 99클럽 코테 스터디 1일차 TIL - 암기왕

 

오늘의 학습 키워드

 

#해시 테이블

공부한 내용 본인의 언어로 정리하기

해시테이블이란 (key, value) 형태로 데이터를 저장하며 key 값으로 value를 빠르게 찾을 수 있는 자료구조다.

오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했나요?

암기왕 문제는 특정 숫자가 존재하는지 존재하지 않는지 찾는 문제였다. 그리고 특정 숫자를 배열로 받아옥 때문에 처음에는 list에서 in 명령어로 안에 있는 요소를 찾으려고 했다. 

  for x in M:
    if x in N:
      print(1)
    else:
      print(0)

어떻게 해결했나요?

하지만 그렇게되면 파이썬에서는 list의 요소를 순차적으로 찾기 때문에 리스트의 길이에 비례해서 시간이 증가하게 된다. 그래서 처음에 시간초과가 떴다. 그래서 이후에는 탐색 시간을 줄일 수 있는 이분탐색을 해야하나 고민했는데, 향해99를 같이하는 친구에게 물어보니 단순히 list 자료형을 set으로 바꿔서 탐색 시간을 줄인 것을 알게 되었다. python에서 집합 set은 해시 테이블 기반으로 동작하기 때문에 평균적으로 O(1)의 시간 복잡도를 갖기 때문이다.

def solution(N_count, N, M_count, M):
  for x in M:
    if x in N:
      print(1)
    else:
      print(0)

T = int(input())
for x in range(T):
  N_count = int(input())
  N = set(map(int, input().split()))
  M_count = int(input())
  M = map(int, input().split())

  solution(N_count, N, M_count, M)

무엇을 새롭게 알았나요?

아직 탐색 알고리즘을 어떻게 짜야하는지 다 기억나지 않아 다음에 또 탐색 문제가 나온다면 공부해서 써봐야겠다는 생각을 하게 되었다. 또한, 평소에 프로그래머스에서만 코딩을 하다가 백준에서 푸니까 값을 입력받는 코드를 짜는 것부터 애를 먹었었다. list의 모든 요소를 string 타입에서 int로 바꾸는 함수(map)가 존재한다는 사실도 까먹어서 다시 찾아보고 그랬다. 그리고 set 자료형이 해시테이블로 존재한다는 사실도 까먹었었다... 다시 공부해야할 게 많다.

내일 학습할 것은 무엇인가요?

내일은 푸는 문제와 관계없이 이분탐색에 대한 알고리즘을 공부해서 정리해봐야겠다고 생각했다. 그리고 시간이 남는다면 다른 탐색 알고리즘도 다시 찾아서 공부해야겠다.