세밍 로그

지난 게시글에 이어서 해쉬테이블에 대해서 알아보도록 할게요 지난 게시글에서 해쉬가 검색, 삽입, 삭제에서 O(1)을 보여주며 굉장히 빠르게 작동하지만 해쉬함수에 따라 해쉬값이 겹치는 Collision(충돌)이 일어날 수 있다고 말씀드렸어요. 애초에 해쉬 값이 겹치지 않을 수 있는 해쉬 함수를 만들거나, 해쉬 테이블이 크면 너무 좋겠지만, 현실에서는 그럴수 없는 경우도 있으니까요 해쉬테이블의 Collision이 발생해도 처리할 수 있는 방법의 흐름에는 크게 2가지가 있습니다. Open Hashing과 Close Hashing이 있어요 Open Hashing은 Collision이 일어났을 때, 외부 저장공간(메모리)를 활용하는 방법입니다. 특히 LinkedList나 BST를 이용하지요. 그래서 Seperat..

Hash Table? 해쉬테이블은 (키-밸류)쌍으로 저장하는 구조이다. 조금 더 정확하게 얘기하자면 (키-밸류)에서 해슁함수를 통한 키값인 해쉬값 위치에 해쉬테이블 주소를 두고 키와 밸류를 저장하는 것을 말한다. (키-밸류)쌍으로 저장하기 때문에 삽입, 삭제, 검색이 모두 O(1)로 정말 빠르다. 하지만 그만큼 공간을 많이 차지하게 되어서 공간과 시간을 맞바꾼 자료구조로 볼 수 있다. 파이썬에는 딕셔너리 구조가 해당된다. 그래서 파이썬에서는 특별하게 해쉬 테이블을 구현할 필요는 없다. 그래도 조금 더 해쉬테이블을 톱아보자 Direct Address Table 해슁 함수를 통한 해쉬 테이블이 있기 전에는 Direct Address Table(직접 주소화 테이블)이 있었다. 직접 주소화 테이블은 키와 밸류가..

Queue와 스택은 둘이 함께 잘 비교가 당한다. 오늘 이 둘을 비교해줘버리자! Stack stack은 FILO 구조로, 처음 들어간 요소가 나중에 나중에 나오는 구조, 나중에 들어간 요고가 처음으로 나오는 구조이다. stack은 요소를 삽입할때 push, 요소를 빼낼때 pop 라고한다. 둘 모두 맨 마지막에 요소를 빼고, 넣기 때문에 O(1)이다. 스택은 대부분 array로 구현하는데, array로 구현하기 때문에, 데이터 최대 갯수를 미리 상정해 놔야 해서, 메모리 낭비가 있을 수 있다. 또한, 스택은 재귀적인 특성을 가지기도 하는데, 재귀적인 형태로 구현을 한다면 파이썬의 경우 1000개의 데이터 까지 넣을 수 있다. def recursive_stack(data): if data

링크드 리스트를 구현하려면 꽤 생각해야 할 것이 많습니다. 하지만 차분히 하나씩 구현해보도록 합시다(나에게 하는 얘기) 1. Node 만들기 링크드 리스트는 일단 데이터와 다음 주소를 가르키는 Node가 필요합니다. Node는 계속 반복해서 만들어질 것이기 때문에 클래스 형태로 만들어 줍니다 class Node: def __init__(self, data, next = None): self.data = data self.next = next 2. Node 연결해보기 앞선 Node 클래스에 만들어 놓은 next로 노드를 연결해줍니다. head도 만들어줘야 하는데, linked list의 시작점을 알려줍니다. node_1 = Node(1) node_2 = Node(2) node_1.next = node_2 ..

파이썬만 지금 거의 6~7년째 접하고 있지만 잘 안쓰는 것들은 잘 까먹게 되는 것 같다. 이번에 한번 더 복습해보고자 한다. 파이썬은 객체 생성 전에 미리 Class를 선언해야 한다. class Quardrangle : pass #pass : 임시코드 작성할때 사용하는 문법, 아무것도 수행하지 않음 클래스에 아직 어떠한 attribute도 넣어준 상태가 아니기 때문에 pass를 넣어서 선언이 끝났다고 알려주자 dir(Quardrangle) dir 를 쓰게 되면, 클래스의 네임스페이스에 등록되어 있는 이름들을 리스트로 반환해주는 내장함수다. 네임 스페이스는 변수명, 함수명, 클래스 명을 언어차원에서 관리하는 매커니즘이라고 보면 된다. 클래스에는 기존의 네임스페이스에 등록된 것에 추가로 변수(attribut..

array와 Linked-List 모두 기본적인 자료구조입니다. 하지만 둘은 memory에 적재되는 방법의 차이로 여러 차이점이 생깁니다. Array array는 정해진 크기의 메모리에 연관된 데이터를 연속적으로 적재합니다. 물리 메모리 상에 봤을때, array의 데이터들이 하나의 4bit씩 차지하며 연달아 있는 것을 볼 수 있습니다. 연달아 붙어 있기 때문에 특정 데이터에 접근하는 것이 굉장히 빠릅니다. array의 첫 데이터 시작부터 접근하고자 하는 데이터의 인덱스(offset)를 산술적으로 더하면 바로 데이터를 찾을 수 있습니다.(O(1), random Access) 마지막의 데이터를 추가(append)하거나 데이터를 삭제하는 것도 마찬가지 입니다. (O(1)) 하지만 중간에 데이터를 삽입(inse..

선택정렬은 데이터에서 작은 수 오름차순으로 찾아서(선택해서) 순차적으로 데이터를 넣어주는 것입니다. 이미 array에 데이터가 있는 상황이기에 앞서 있는 요소와 자리를 바꿔준다고 생각하면 됩니다. 알고리즘을 구현할때 필요한 것 1. 현재 위치를 알 수 있는 것(데이터를 바꿔 넣을 자리를 기억하고 있는 것) 2. 작은 수의 인덱스를 찾을 것 3. 작은 수의 데이터를 바꿔 넣을 자리에 넣어주는 것 def selectionSort(data): for i in range(len(data)): lowest = i #바꿀 자리를 lowest로 초기화 for j in range(i,len(data)): if data[lowest] > data[j] : lowest = j #더 작은 데이터의 인덱스 번호로 바꿔줌 da..

삽입 정렬은 한 요소를 앞의 요소들과 비교해서 나보다 큰 요소가 있다면 그 요소 앞에 해당 요소를 배치하는 것입니다. 그래서 이 알고리즘을 고안하는데 필요한 것은 1. 한 요소를 특정할 수 있는 부분 2. 해당 요소 앞까지 확인할 수 있는 부분 3. 큰 수를 발견했을때, 위치를 바꿔주는 부분 def insertionSort(data): for i in range(len(data)): for j in range(i): if data[j]

버블정렬은 인접한 두 요소의 데이터를 비교해서, 둘의 자리를 바꾸는 것 입니다. 알고리즘에서 고안되어야 할 것은 1. 인접한 두 요소를 받아들이는 것 2. 두 요소의 크기를 비교해서 자리를 바꾸는 것 이 필요합니다. def bubbleSort(data): for i in range(len(data)): for j in range(i,len(data)): if data[i]

문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오. - 입력 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "..