![]()
Chaining 이외에도 해시테이블의 충돌을 해결하는 방식 중 Open Addressing이 있다. Open Addressing의 개념은, 해시테이블에 동일한 해시함수 값을 가진 데이터들이 저장될 경우 다른 비어 있는 자리를 찾아 해당 데이터를 삽입한다는 것이다. Open Addressing은 선형탐사(Linear probing), 제곱탐사(Quadratic probing), 그리고 이중해싱(Double hashing)가 있다. 1. 선형탐사 (Linear probing) 선형탐사는 데이터가 삽입될 자리에 이미 다른 데이터가 있다면, 한 칸씩 내려가며 빈 자리에 데이터를 저장한다. 76, 93, 40은 각각의 해시함수값이 6, 2, 5로 서로 겹치지 않아 해당 인덱스에 저장된다. 다음으로 삽입되는 47은..
문제 (링크) https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 나의 풀이 n = int(input()) data = list(map(int, input().split())) data.sort() # 걸리는 시간을 오름차순으로 정렬했을 때 최솟값이 나온다 waiting_time = [] for i in range(n): waiting_time.append(sum(data[:i+1])) # 걸리는 시간을 인덱싱한 후 sum한 값을 waiting_time에 추가 print(sum..
문제 (링크) https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 나의 풀이 n = int(input()) def change(n): count = 0 while n % 5 != 0: n -= 2 count += 1 if n < 0: return -1 count += (n // 5) return count print(change(n)) 바로 직전의 설탕 배달 문제와 동일한 문제로, n이 5로 나누어떨어질 때까지 2를 빼주면서 count를 1씩 추가해주고, n이 0보다 작아지면 -1을 리턴하며 함수를 끝내준다. 혹은 n에서 2씩 빼주는 과정에서 5로 나누어떨어지는 값이..
문제 (링크) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 나의 풀이 n = int(input()) result = 0 while n % 5 != 0: # n -= 3 if n < 0: result = -1 break result += 1 result += (n // 5) # n < 0일 때도 이 코드를 거쳐가서 오류 발생. print(result) n이 5의 배수가 될때까지 (while n%5 != 0) n에서 3을 빼주고 봉지 개수를 +1 해준다...
![]()
재귀함수란 함수 내에서 그 함수를 다시 사용하는 것을 말한다. 약간 인셉션 느낌이 드는 방식의 이 함수는 실제 코드를 보면 더 쉽게 이해될 수 있다. def recursive(): print("이것은 재귀함수입니다.") recursive() recursive() #함수 호출 이 함수는 "이것은 재귀함수입니다." 를 무한히 출력하는 재귀함수이다. recursive라는 재귀함수가 호출되면 print문을 수행하고 다시 recursive함수를 호출하는 모습이다. 하지만, 재귀적으로 진행되는 함수들은 모두 메모리의 스택에 지속적으로 쌓인 후 하나씩 pop하는 형식으로 실행된다. 그러나, 이렇게 쌓이는 데이터가 컴퓨터가 제어해놓은 스택의 제한(recursion depth라고도 부른다)을 초과하게 되면 해당 함수는 ..
![]()
해시테이블의 충돌을 해결하기 위한 대표적인 방식 중 하나로 Chaining 방식이 있다. Chaining 방식은 말 그대로 동일한 해시함수 값을 가진 데이터들을 연결시켜 하나의 인덱스에서 접근할 수 있도록 하는 방식이다. 앞서 포스팅했던 링크드 리스트를 각 chain으로 사용하면 Chaining 방식을 구현할 수 있다. # 더블리 링크드 리스트의 노드 클래스 for Chaining class Node: def __init__(self, key, value): # 각 노드가 key, value를 갖는다 self.key = key self.value = value self.next = None self.prev = None # 더블리 링크드 리스트 클래스 for Chaining class LinkedList..
![]()
해시테이블이란? 해시테이블은 매우 빠른 평균 삽입, 삭제, 탐색연산을 제공하는 유용한 자료구조이다. 해시테이블은 데이터를 key - value 쌍으로 묶어 관리하는데, 국어사전이 낱말들을 적어놓은 방식과 유사하다. 국어사전에서 낱말을 찾아보면, 하나의 낱말에 하나 혹은 이상의 설명들이 적혀있다. 이 때, 낱말을 key, 그에 대한 설명을 value라고 비유할 수 있다. 실제로 파이썬에서 제공하는 dictionary 자료가 대표적인 해시테이블 기반의 자료라고 할 수 있다. 해시테이블의 데이터 저장 방법 해시테이블은 일반적인 배열과는 다르게 자료들을 순차적으로 저장하는 것이 아닌 key값을 인덱스로 저장한다. 예컨대, key가 201503196에 value가 "홍길동"인 데이터를 저장하고자 한다면 0 ~ 2..
더블리 링크드 리스트는 링크드 리스트와 다르게 노드 안에 data와 다음 노드에 대한 정보, 그리고 이전 노드에 대한 정보를 가진다. 따라서 특정 노드를 탐색하거나 리스트 크기를 구할 때는 일반적인 링크드 리스트와 동일한 메서드를 사용할 수 있지만, 노드를 정의할 때와 삽입 및 제거 연산을 해줄 때는 약간은 다른 방식이 필요하다. 먼저, 더블리 링크드 리스트의 노드는 다음과 같다. # 더블리 링크드 리스트의 노드 클래스 class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # 이전 노드에 대한 정보도 저장해준다. 더블리 링크드 리스트의 연산 (삽입, 삭제) 링크드 리스트와는 다르게, 특정 데이터가 삽..
