Share
Sign In
TIL 웹개발
TIL 웹개발 - 자료구조
서경태
👍
기본적인 자료구조
연결리스트
스택
큐
해시테이블
힙
연결리스트
Array
LinkedList
특정 원소 조회
O(1)
O(N)
중간에 삽입 삭제
O(N)
O(1)
데이터 추가
데이터 추가시 모든 공간이 다 차버렸다면 새로운 메로리 공간을 할당받아야한다.
모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리
데이터에 접근하는 경우가 빈번하다면 Array를 사용하자
삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 좋다.
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class LinkedList: def __init__(self): self.head = None def append(self, val): if not self.head: self.head = ListNode(val, None) return node = self.head while node.next: node = node.next node.next = ListNode(val, None)
스택
LIFO (Last I First Out) : 마지막에 들어온 것이 먼저 나오는 구조
class Node: def __init__(self, val=0, next=None): self.val = val self.next = next class Stack: def __init__(self): self.top = None def push(self, value): self.top = Node(value, self.top) def pop(self): if self.top is None: return None node = self.top self.top = self.top.next return node.val def is_empty(self): return self.top is None
큐
스택과 반대로 먼저 들어온 것이 먼저 나오는 구조
class Queue: def __init__(self): self.front = None def push(self, value): if not self.front: self.front = Node(value) return node = self.front while node.next: node = node.next node.next = Node(value) def pop(self): if not self.front: return None node = self.front self.front = self.front.next return node.val def is_empty(self): return self.front is None
해시테이블
해시함수를 이용해 키를 값에 매핑하는 자료구조
class HashNode: def __init__(self, key=None, value=None): self.key = key self.value = value self.next = None class HashTable: def __init__(self): self.size = 10 self.table = [None] * self.size def _hash_function(self, key): return key % self.size def put(self, key, value): index = self._hash_function(key) if self.table[index] is None: self.table[index] = HashNode(key, value) else: node = self.table[index] while node.next is not None: node = node.next node.next = HashNode(key, value) def get(self, key): index = self._hash_function(key) node = self.table[index] while node is not None: if node.key == key: return node.value node = node.next return -1 def remove(self, key): index = self._hash_function(key) node = self.table[index] prev_node = None while node is not None: if node.key == key: if prev_node is None: self.table[index] = node.next else: prev_node.next = node.next return prev_node = node node = node.next
힙
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
최대 힙 삽입
class BinaryMaxHeap: def __init__(self): # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다. self.items = [None] def insert(self, k): self.items.append(k) self._percolate_up() def _percolate_up(self): # percolate: 스며들다. cur = len(self.items) - 1 # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2 parent = cur // 2 while parent > 0: if self.items[cur] > self.items[parent]: self.items[cur], self.items[parent] = self.items[parent], self.items[cur] cur = parent parent = cur // 2
최대 힙 추출
class BinaryMaxHeap: def __init__(self): # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다. self.items = [None] def insert(self, k): self.items.append(k) self._percolate_up() def _percolate_up(self): # percolate: 스며들다. cur = len(self.items) - 1 # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2 parent = cur // 2 while parent > 0: if self.items[cur] > self.items[parent]: self.items[cur], self.items[parent] = self.items[parent], self.items[cur] cur = parent parent = cur // 2 def extract(self): if len(self.items) - 1 < 1: return None root = self.items[1] self.items[1] = self.items[-1] self.items.pop() self._percolate_down(1) return root def _percolate_down(self, cur): biggest = cur left = 2 * cur right = 2 * cur + 1 if left <= len(self.items) - 1 and self.items[left] > self.items[biggest]: biggest = left if right <= len(self.items) - 1 and self.items[right] > self.items[biggest]: biggest = right if biggest != cur: self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur] self._percolate_down(biggest)
Subscribe to 'kyugntae-ai'
Welcome to 'kyugntae-ai'!
By subscribing to my site, you'll be the first to receive notifications and emails about the latest updates, including new posts.
Join SlashPage and subscribe to 'kyugntae-ai'!
Subscribe
👍
Other posts in 'TIL 웹개발'See all
서경태
TIL 웹개발 - CS 모의 면접 정리
우선 CS 면접의 경험을 정리해보면, 왜 CS를 공부해야하는지 이제서야 알게 된 느낌이었다. 단순히 개념과 설명을 반복해서 표현하는게 아니라 각 개념들 간 관계를 알고 차이점까지 설명할 줄 알아야 실무에서도 적용할 수 있다. 주로 두 가지 개념에 대해 묻는다. 이렇게 두 가지를 물어보는 이유는 차이점이 존재하기 때문에 그 특징을 잘 설명하는 것이 중요하다. 배열, 연결리스트 자료구조에서 배열과 연결리스트는 모두 데이터를 저장하고 관리하는데 사용된다. 배열 연속적인 메모리 공간에 정하는 데이터 구조 고정 크기를 가지며 한번 선언되면 크기를 변경할 수 없다. → 이는 단점으로도 작용하는데 배열의 크기를 동적으로 변경할 수 없다. 인덱스를 사용해 데이터에 접근이 빠르다. → O(1)의 시간복잡도를 가진다. 삽입 및 삭제의 비효율성 → 배열 중간에 삽입하거나 삭제할 경우 나머지 요소들을 이동시켜야하므로 O(n)이 걸린다. 연결리스트 각 요소가 노드로 구성되고, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 표함되는 데이터 구조 동적 크기로 필요에 따라 노드를 추가하거나 제거하여 크기를 동적으로 변경할 수 있다. → 각 노드는 효율적인 삽입/삭제 리스트의 중간에 요소를 삽입하거나 삭제하는데 O(1) 시간이 소요된다. → 반면 특정 위치를 찾는데 O(n)의 시간이 걸려 접근이 느리다. 비연속적 저장으로 메모리 활용이 유연하다. 프로세스와 스레드 프로세스 실행중인 프로그램의 인스턴스를 의미하며, 프로그램이 메모리에서 실행되는 상태를 말한다. 각 프로세스는 독립된 메모리 공간을 가지며, 다른 프로세스와 메모리 공간을 공유하지 않는다. 실행에 필요한 자원(파일, 메모리, CPU 등) 을 소유한다. 운영체제는 프로세스를 생성, 스케쥴링, 종료등의 작업을 관리한다.
서경태
TIL 웹개발 - CS면접 대비 정리글
모의 CS면접을 하루 앞두고 기억나는대로 정리를 해보려한다. 컴퓨터 구조 컴퓨터는 네 가지 장치로 이뤄진다. CPU 컴퓨터의 뇌에 해당하며 연산을 담당한다. 주기억장치 = RAM , 메모리 보조기억장치에 저장된 프로그램을 실행시키면 주기억장치에 올라와 사용한다. 전원이 꺼지면 주기억장치에 담긴 메모리도 없어진다. 보조기억장치 HDD, SSD 등 컴퓨터가 꺼져도 유지되는 장치. 평소 보조기억장치에 저장되었다가 프로그램이 실행되면 주기억장치에서 작동한다. 입출력장치 마우스, 키보드, 모니터 등 컴퓨터에 입력 혹은 출력을 할 수 있는 것들을 말한다. 프로세스: 작업이 이루어지는 것을 말한다. 프로세스의 순서 신규, 준비, 실행, 대기, 종료 로 이루어진다. 프로그램을 불러오면 신규에서 준비단계로 넘어온다. 메모리의 할당을 마치면 준비에서 실행 단계로 넘어가 실행된다. 실행 중 입력이 필요하면 대기단계로 넘어간다. 입력을 마치면 다시 준비 단계로 넘어가고 실행단계에서 출력한다. 종료를 하면 실행에서 종료 단계로 넘어간다. 프로세스 구조
서경태
TIL 웹개발 - 유연한 사고를 가져라
알고리즘 조금 풀어봤다고 모든걸 알고리즘으로 풀려고 하기 시작했다. 펠린드롬 관련 문제를 백트래킹으로 풀면 결국 풀리는거 아냐? 하고 시작했는데... 파이참이 계산을 하다가 꺼져버렸다... 그래서 아 이건 안되겠구나 싶어.. 다시 코드를 작성했다. 조금만 더 유연한 사고를 가지면 사실 펠린드롬은 1/2로 충분히 계산할 수 있고 경우의 수가 아니면 굳이 백트레킹을 사용할 필요도 없다. 결국 내가 작성한 코드는 시간 복잡도는 O(n^2)다. 이상한거에 매몰되어 시간을 낭비하지 말자. 공부시간이 줄어든다.