전체 글11 [자료구조]해시 해시함수 해시테이블 충돌 개념, 해결법 여기서는 자료구조를 설명하는 것이 주된 목표이기 때문에 해시에 대해서는 간단하게 짚고 넘어간다. 1. 해시 해시는 어떤 데이터를 크기가 고정된 다른 값으로 변환하는 것을 뜻한다. 따라서 모든 해시값들은 같은 크기를 가지며, 같은 입력 데이터에는 동일한 해시값을 반환한다. 주로 암호학에 많이 사용되며 데이터의 무결성을 검사하는 데에 사용되기도 한다. 2. 해시 함수 입력값에 따라 일정한 값을 반환하는 함수로 수많은 함수들이 해시함수가 될 수 있지만, 몇 개의 조건이 존재한다. 일관성 : 같은 입력값에는 언제나 같은 반환값을 가져야한다. 고유성 : 입력값이 다르다면 반환하는 해시값도 달라야 한다.(서로 다른 입력에 동일한 해시값이 나오는 충돌을 최소화해야 한다.) 고르게 분포 : 가능한 모든 해시값이 균등하.. 2024. 1. 31. [자료구조]우선순위 큐, 힙 개념 작동 방식 1. 우선순위 큐 (Priority Queue) 일반적인 큐(Queue)는 스택과 비교되어 선입선출의 규칙을 가지는 자료구조를 의미한다. 큐는 무조건 삽입되는 순서에 따라 나오는 순서가 정해지며, 만약 우선순위가 있는 경우 데이터가 삽입될 때마다 정렬을 새로 해야하므로 매우 비효율적이다. 우선순위 큐는 선형적인 구조가 아닌 이진트리의 구조를 사용한다. 따라서 각각의 요소들은 우선순위 값과 데이터로 구성되어 있다. 2. 이진 힙 우선순위 큐를 구현하기 위해 힙(Heap)을 주로 사용한다. 이진 힙은 완전 이진 트리의 형태를 가져야 하며, 최소힙과 최대힙으로 종류가 나뉘게 된다. 따라서 i번째 노드의 부모노드를 찾으려면 (i-1)/2, 자식노드는 2i+1와 2i+2로 찾을 수 있다. 최소힙은 루트노드가 가장.. 2024. 1. 30. [자료구조]이진트리 개념, 종류, 순회방법, 활용 1. 이진트리 기본적인 트리 중에서 모든 노드의 자식노드의 개수가 2 이하인 트리를 의미한다. 일반적인 트리에서 사용되는 용어들은 모두 동일하다. 루트(root)노드를 중심으로 두 개의 이진트리로 쪼갤 수 있으며 아래와 같은 구조를 가져야 한다. 2. 이진트리의 몇 가지 종류 포화 이진 트리 (Full Binary Tree) : 단말 노드를 제외한 모든 노드의 차수가 2인 이진 트리 완전 이진 트리 (Complete Binary Tree) : 단말 노드들이 트리의 왼쪽부터 채워진 형태의 이진 트리 완벽 이진 트리 (Perfect Binary Tree) : 포화 이진 트리 + 모든 단말 노드의 깊이가 같은 트리 3. 이진 트리 순회 방법 이진트리에 있는 데이터를 탐색하기 위한 순회 방식으로 크게 3개로 나.. 2024. 1. 29. [자료구조]그래프, 트리 개념&예시 1. 그래프 그림과 같이 여러개의 정점(노드)과 그 정점들을 연결하는 간선(edge)로 이루어진 자료구조이다. 크게 방향 그래프와 무방향 그래프로 나뉘는데, 방향그래프는 간선에 방향이 정해져 있어 해당 방향으로만 이동할 수 있는 그래프이다. 그래프에서는 다음과 같은 용어들을 사용한다. 인접 : 간선에 의해 어느 두 정점이 직접적으로 연결되어있는 경우 인접했다고 표현한다. 차수 : 하나의 정점에 연결된 간선의 개수를 나타낸다. 사이클 : 그래프 내부에 어느 한 정점에서 시작하여 다시 그 정점으로 돌아오는 경로가 있는 경우 이를 사이클이라고 부른다. 활용 예시) 네비게이션 : 교통 상태를 그래프로 표현하여 최적의 길을 도출해낼 수 있다. 전자회로 설계 : 각 부품을 정점으로 하여 회로를 살계할 수 있다. 데.. 2024. 1. 27. [자료구조]스택, 큐 개념&예시 스택과 큐는 어떠한 정보를 저장하기위한 방식으로 서로 상반된 구조를 가지고 있다. 1. 스택(stack) 영어단어에서 유추할 수 있듯이 데이터를 쌓아 올리는 것을 의미한다. 사진과 같이 데이터를 저장하고 꺼내는 작업이 한쪽에서만 이루어지기 때문에 가장 먼저 저장된 데이터가 가장 마지막에 나오게된다. 이와같은 방식을 후입선출, 즉 LIFO(Last In First Out) 방식이라고 부른다. 스택의 바닥을 bottom, 데이터 이동이 일어나는 윗 부분을 top이라 한다. top에서 이루어지는 데이터를 저장하는 작업은 push, 꺼내는 작업은 pop으로 부른다. 활용 예시) 함수 호출 : 기본적으로 함수를 호출하면 스택 구조로 실행된다. 깊이 우선 탐색 : 인접한 노드들을 스택에 저장하면서 탐색한다. 후위 .. 2024. 1. 26. 그래프 탐색 방법, 예시(DFS, BFS) 그래프를 순회하는 방법에는 여러가지가 있지만 대표적으로 깊이우선탐색과 너비우선탐색이 존재한다. 1. 깊이 우선 탐색 (DFS) 어느 한 지점에서 시작하여 최대한 깊숙히 들어가서 확인한뒤 다른 루트를 확인하는 방식으로 다른 길이 발견되면 길이 있다라는 점만 기억한뒤 나중에 방문한다. 재귀호출을 사용하여 구현하거나 스택을 이용할 수 있다. 장점 그래프에서 사이클이 있는지 판단할 수 있다. 현재 경로의 노드만 기억하므로 저장 공간의 부담이 적다. 단점 스택 오버플로우를 조심해야한다. 단순한 검색 속도는 BFS에 비해 느리다. 예시1) 이와 같은 그래프가 있을때, A부터 시작하여 알파벳 순서를 기준으로 탐색한다고 가정한다. 처음 A을 방문하고 A와 연결되어있는 노드 중 알파벳 순서가 빠른 B를 방문한다. 이후 .. 2024. 1. 25. 이전 1 2 다음
