리스트 파이썬 리스트는 굉장히 활용 범위가 큰 자료형입니다. 프로그래밍을 할 때 사실상 리스트만 사용하면 대부분의 경우 필요한 기능을 모두 사용할 수 있죠. 너무 사용 가능 범위가 넓다 보니까 어떤 다른 자료형을 사용할지 생각하지 않고 바로 리스트를 사용해 버리는 경우가 많은데요. 무조건 리스트를 사용해버리면 효율적으로 프로그래밍을 하기 힘듭니다. 이게 무슨 말인지 안 와닿을 수도 있는데요. 코드 예시를 하나 볼게요. 바로 리스트를 사용할 때 여러 개의 데이터(정확히는 0부터 999999까지의 정수)를 저장한 후, 특정 데이터를 탐색하는 코드를 써볼 건데요. 대부분의 상황과 비슷하게 동적 배열로 구현돼 있는 파이썬 리스트를 사용하면 원하는 코드를 쓸 수 있습니다. 바로 해볼게요. # 예시를 위해 사용할 ..
이번 포스팅에서는 파이썬 자료형들에서 많이 사용하는 연산들의 시간 복잡도를 정리해보겠습니다. 이 시간 복잡도를 바탕으로 파이썬 자료형들을 사용할 때 얼마나 효율적으로 하는지를 떠올릴 수 있을 것 같습니다. 리스트 (동적 배열) 연산 예시 시간복잡도 접근 list_1[0], list_1[0] = 5 O(1) 추가 list_1.append(2) O(1) (분할 상환) 맨 뒤 삭제 list_1.pop() O(1) (분할 상환) 길이 확인 len(list_1) O(1) 삽입 list_1.insert(3, "성태호") O(n) 삭제 del list_1[0], list_1.pop(3) O(n) 탐색 "이재하" in list_1 O(n) deque (더블리 링크드 리스트) 연산 예시 시간 복잡도 맨 앞 삭제 dequ..
1. 해시 테이블 - 해시 테이블을 이용하면 key-value 데이터를 저장할 수 있다. - 해시 테이블에는 데이터 간 순서 관계를 나타낼 수 없다. - 해시 함수는 특정 값을 넣었을때 원하는 범위의 자연수를 리턴하는 함수다. - Direct Access Table을 이용하면 key - value 데이터를 시간 효율적으로 저장하고 찾을 수 있다. - 해시 함수는 원하는 범위의 자연수를 빠르게(O(1)으로) 리턴하면 좋다. 2. 해시 테이블 충돌과 Chaining - 충돌은 해시 테이블에서 한 인덱스에 두 개의 key - value 쌍을 저장해야 되는 경우이다. - 충돌이 일어나면 해시 테이블을 제대로 사용하기 위해 Chaining이나 Open addressing 등을 이용해 충돌을 해결해야 한다. - C..
1. 링크드 리스트 - 배열과 같이 데이터를 순서대로 저장해주는 자료 구조다. - 각 노드가 다음 노드에 대한 레퍼런스만 저장하는지, 아니면 다음과 전 노드에 대한 레퍼런스를 모두 저장하는지에 따라 싱글리 링크드 리스트와 더블리 링크드 리스트로 구별할 수 있다. - 링크드 리스트 노드들은 메모리에 연속적이거나 순서대로 저장되지는 않는다. 메모리 이곳저곳 아무 데나 저장돼 있을 수 있다. - 싱글리 링크드 리스트는 처음에 크기를 정하지 않아도 그냥 새로운 노드를 만들어서 기존 노드들에 연결만 시켜주면 계속해서 새로운 데이터를 더해줄 수 있다. - 파이썬에서는 노드 클래스를 정의하고, 인스턴스들을 만들어서 연결하면 링크드 리스트를 구현할 수 있다. 2. 싱글리 링크드 리스트와 더블리 링크드 리스트 연산 - ..
파이썬 hash 함수 파이썬 언어도 내부적으로 hash라는 함수를 제공합니다. 근데 이건 우리가 방금 배운 해시 함수랑 조금 다른데요. 파이썬 해시 함수는 파라미터로 받은 값을 그냥 아무 정수로만 바꿔주는 함수입니다. 저희가 배웠던 해시 함수와는 달리 특정 범위 안에 있는 정수가 아니라 아무 정수로 바꿔주죠. 정수형, 소수형, 문자열 타입에 hash 함수를 호출했을 때 나오는 결과를 살펴보겠습니다. # 정수 값 print(hash(12345)) # 12345 print(hash(12345)) # 12345 # 다른 정수 값 print(hash(12346)) # 12346 # 소수 값 print(hash(15.1234)) # 284541027336970255 print(hash(15.1234)) # 284..
이번 포스팅에서는 해시 함수에 대해서 조금 더 알아보고 해시 함수를 구현할 수 있는 가장 간단한 방법들에 대해서 살펴보겠습니다. 101호: 최지웅 204호: 강영훈 302호: 성태호 711호: 김현승 942호: 손동욱 먼저 주어진 key를 원하는 범위의 자연수로 바꿔서 리턴해주는 것 말고 다른 해시 함수의 조건들을 볼게요. 한 해시 테이블의 해시 함수는 결정론적이어야 된다. 똑같은 key를 넣었을 때는 항상 똑같은 결과가 나와야 한다는 건데요. 942를 해시 함수에 넣을 때 어쩔 때는 5이 나오고 어쩔 때는 10이 나오고 이러면 안 된다는 거죠. 942를 넣으면 항상 똑같은 결과가 나와야 됩니다. 결과 해시값이 치우치지 않고 고르게 나온다. 그러니까 해시 함수에 101, 204, 302, 711, 942..
__str__ 메소드 링크드 리스트를 클래스로 만들었으니까 링크드 리스트를 문자열로 표현해주는 __str__ 메소드를 정의해봅시다. __str__ 메소드는 그냥 링크드 리스트를 출력할 때 자동으로 링크드 리스트의 내용을 사람들이 이해할 수 있는 문자열로 리턴해주는 메소드로 이해하시면 됩니다. 링크드 리스트 __str__ 메소드 class LinkedList: """링크드 리스트 클래스""" def __init__(self): self.head = None # 링크드 리스트의 가장 앞 노드 self.tail = None # 링크드 리스트의 가장 뒤 노드 def append(self, data): """링크드 리스트 추가 연산 메소드""" new_node = Node(data) # 링크드 리스트가 비어 있으..
동적 배열 크기 줄이기 동적 배열은 내부적으로 정해진 크기의 정적 배열을 사용하고 있습니다. 값을 추가하다가 내부 배열이 꽉 차면, 더 큰 내부 배열을 사용하도록 자동으로 늘려 주는 거죠. 반대로 삭제를 할 때에는 내부 배열의 크기를 줄이기도 하는데요... 왜 내부 배열의 크기를 줄여야 될까? 데이터 요소 10000 개가 들어 있는 동적 배열이 있다고 생각해 봅시다. 편의상 배열의 크기가 꽉 찼다고 생각할게요. 여기서 요소 9900 개를 삭제하면 100 개밖에 남지 않는데요. 그러면 나머지 9900 개의 요소를 저장할 수 있는 메모리는 낭비되겠죠? 동적 배열은 요소의 개수가 어느정도 줄어들면 내부 배열의 크기도 적절히 줄여서 공간을 좀 더 효율적으로 사용합니다. 내부 배열의 크기는 어떻게 줄어들까? 위의..
이번 포스팅에서는 동적 배열에서 특정 위치에 있는 데이터를 지우는 삭제 연산에 대해서 배워 보겠습니다. 삭제 연산 동작 바로 예시를 볼게요. 이렇게 2, 3, 5, 7, 11이 있는 동적 배열에서 인덱스 1에 있는 3을 지우고 싶다고 할게요. 한 단계씩 봅시다. 인덱스 1 뒤에 있는 데이터를 모두 한 칸씩 앞으로 밀어서 저장합니다. 인덱스 1에 인덱스 2에 있던 5를 저장합니다 인덱스 2에 인덱스 3에 있던 7을 저장합니다 인덱스 3에 인덱스 4에 있던 11을 저장합니다 동적 배열은 배열의 크기와 개발자가 사용하는 인덱스들의 범위를 따로 관리합니다. 데이터를 삭제했으니까 동적 배열에서 접근할 수 있는 인덱스 범위도 1을 줄여 줍니다. 동적 배열에 남은 데이터를 확인해보면 2, 5, 7, 11입니다. 인덱..
분할 상환 분석은 연산을 n 번 했을 때 총 드는 시간 X를 n으로 나눠주는 “할부” 개념이라고 배웠는데요. 최악의 경우로 시간 복잡도를 얘기하는 것이 비합리적인 경우에 사용하죠. 이번 레슨에서는 동적 배열의 추가(append) 연산에 직접 분할 상환 분석을 해 봅시다. 동적 배열 동작 동적 배열에 추가를 할 때는: 새로운 인덱스에 데이터를 저장하는 시간 기존 배열의 크기가 부족해서 더 큰 배열을 만들고, 기존 배열의 데이터들을 옮기는 시간 이 두 가지를 나눠서 생각하면 편합니다. 우선 기억을 상기시키기 위해서 동적 배열에 데이터를 추가할 때 일어나는 일들을 쭉 나열해 볼게요. 비어 있는 동적 배열에 추가 연산을 9번 한다고 가정합시다. 처음 시작할 때 동적 배열은 크기가 1인 배열입니다. 첫 번째 요소..
