빠르고 꾸준하게

자료구조 & 알고리즘/자료구조

자료구조에서의 스택(Stack) 이란?

최근 친구와 카공을 하고 있었는데 친구가 갑자기 저에게 '야 스택이 뭐야?' 라는 질문을 던졌습니다. 애석하게도 바로 답변이 나오지 않더군요.. 결국 '쌓는거..?' 라는 대답을 해버렸습니다. 이번 주말에는 자료구조에서의 스택(Stack) 과 프로세스 메모리 에서의 스택(Stack) 에 대해 정리를 해보면서 리마인드를 하려고 합니다. 먼저, 자료구조에서의 스택(Stack) 개념을 정리해보겠습니다. 스택의 사전적 정의를 보면 쌓는 거 , 더미 모두 맞습니다. 쉽게 설명하자면, 아래가 막혀있는 긴 상자라고 생각하면 됩니다. 아래가 막혀있으니 물건을 위로만 넣을 수 있고, 당연히 뺄 때도 위로만 뺄 수 있겠죠? 이러한 구조로 인해서 상자 안의 물건은 처음 들어왔으면 맨 마지막으로 나가고 마지막에 들어왔으면 제..

자료구조 & 알고리즘/자료구조

자료구조 해쉬테이블(HashTable)

컴퓨터는 어쨌든 숫자로 이루어져있고 숫자로 모든작업을 수행한다. 이를 이용해서 특정 데이터를 찾을 때 숫자를 이용한 인덱스로 메모리의 위치에서 데이터를 가져올 수 있다. 해쉬 테이블이란? 해시 테이블은 키(Key), 해시함수(Hash Function), 해시(Hash), 값(value), 저장소(Bucket, Slot)로 이루어져 있다. 해쉬 테이블은 key-value 쌍에서 key 값을 테이블에 저장할 때 데이터를 직접 넣는 방법과는 다르게 key(숫자) 값을 Hash함수를 이용해 계산을 수행한 후, 결과값을 테이블에 넣는 것이다. Hash함수는 입력으로 key값을 받고, 0부터 (배열의 크기-1) 사이의 값을 출력해준다. 이 경우 k값이 h(k)로 해쉬되었다고 하고, h(k)는 k의 해쉬값 이라고 한..

자료구조 & 알고리즘/자료구조

자료구조 트리(Tree)

트리란? 트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다. 트리관련용어 루트 노드(root node) : 부모가 없는 최상위 노드를 의미한다. 위 그림에서는 A이다. 단말 노드(leaf node) : 자식이 없는 노드. 위 그림에서는 G,H,E,I 이다. 크기(size) : 트리에 포함된 모든 노드의 개수. 위 그림에서는 9이다. 깊이(depth) : 루트 노드부터의 거리. 위 그림에서 B의 깊이는 1이다. D의 깊이는 2이다. 높이(height) : 깊이 중 최댓값. 위 그림에서는 G,H,I의 깊이는 3이다. 차수(degree) : 각 노드의 (자식 방향) 간선 개수 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 개이다. 이진 탐색 트리 (Binary Sea..

자료구조 & 알고리즘/자료구조

다익스트라 알고리즘(Dijkstra Algorithm)(feat.힙(heap))

다익스트라 알고리즘 최단경로 알고리즘으로 특정 노드에서 출발해서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. '음의 간선'이 없을 때 정상적으로 동작하고 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 매번 '간선 비용'이 가장 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘을 사용하기도 하고, 다이나믹 프로그래밍(DP) 알고리즘 또한 사용한다. 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만든다. 방문한 적이 있는지 체크하는 목적의 리스트를 만든다. 최단 거리 테이블을 하나 만들어놓고 모두 무한 (INF, 1e9 또는 987654321 로 보통 초기화시켜준다)으로 초기화 시켜준다. 파이썬 코드로 작성해보면 아래와 같이 생각할 수 있다. def sm..