자료구조

자료구조와 알고리즘 자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조이고, 알고리즘이란 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임입니다. 스택, 큐, 트리, 힙 구조 설명 스택: 세로로 된 바구니와 같은 구조로 먼저 넣게 되는 자료가 마지막으로 나오게 되는 First-In Last-Out(FILO) 구조이다. 큐: 가로로 된 통과 같은 구조로 먼저 넣게 되는 자료가 가장 먼저 나오는 First-In First-Out(FIFO) 구조이다. 트리: 정점과 간선을 이용해 사이클을 이루지 않도록 구성한 Graph의 특수한 형태로, 계층이 있는 데이터를 표현하기에 적합하다. 힙: 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로, 각 노드..

BFS이란? BFS(Breadth First Search) 또는 너비 우선 탐색이라고 함 시작 정점으로부터 가까운 정점을 먼저 방문하는 그래프 탐색 방법 큐(queue)를 이용해 방문한 정점들을 차례로 저장하고 꺼냄 DFS와 BFS의 차이점 DFS 는 탐색하는 원소를 최대한 깊게 따라가야 한다. 이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색하면 된다. → 스택 BFS 는 현재 인접한 노드 먼저 방문해야 한다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. → 큐 구현 (Python) 1. 루트 노드를 큐에 넣는다. 2. 현재 큐의 노드를 빼서 visited 에..

DFS란? DFS(Depth-First Search) 또는 깊이 우선 탐색이라고 부름 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘 스택 자료구조 또는 재귀 함수를 이용함 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다. 위 과정을 반복한다. 구현 (Python) from dfs_bfs.prac import dfs_recursive, dfs_stack # 테스트 코드 assert dfs_recursive(1, []) == [1, 2, 5, 6, 7, 3, 4] # dfs로 방문한 경우 assert dfs_stack(1) == [1, 4, 3,..

그래프란? 연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조 자료구조는 크게 비선형구조, 선형구조로 구분된다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다. 이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있다. 그래프에서 사용되는 용어 노드(Node): 연결 관계를 가진 각 데이터를 의미 . 정점(Vertex)이라고도 함. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) 그래프의 종류 그래프는 유방향 그래프와 무방향 그래프 두가지가 있다. 유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간..

힙이란? 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 항상 최대/최소의 값들이 필요한 연산이 있는 경우 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조 부모 노드의 값이 자식 노드의 값보다 항상 큼 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 간다. 따라서 최대의 값들을 빠르게 구할 수 있게 된다. 8 Level 0 6 3 Level 1 2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아니다 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이 4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞다 ..

해시 테이블 해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다. 해시 함수 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 해시 함수 값 충돌의 최소화 쉽고 빠른 연산 해시 테이블 전체에 해시 값이 균일하게 분포 사용할 키의 모든 정보를 이용하여 해싱 해시 테이블 사용 효율이 높을 것 해싱 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 말한다. h(x) = x mod m 로드 팩터(Load Facto..