전체 글
-
[Data Structure] 스택, 큐, 딕셔너리알고리즘 & 자료구조 2021. 1. 25. 16:49
큐 큐는 값이 아래로 쌓이는 구조이다. 값을 넣고 뺄 때 '선입선출' 또는 'FIFO' 라는 방식을 따르게 된다. 가장 먼저 들어온 값이 가장 먼저 나가는 것이다. 식당에서 주문을 하기 위해 줄을 설때 가장 먼저 줄을 선 사람이 가장 먼저 주문을 하는것 과 동일하다. 배열이나 연결리스트를 통해 구현 가능하다. ***예제 소스코드 바로가기 ====>>> junecode.tistory.com/49 [baekjoon] 10828번 스택 (스택) 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위 junecode.tistory.com 스택 반면 스택은 값이 위로 ..
-
[Data Structure] 트라이알고리즘 & 자료구조 2021. 1. 25. 16:32
'트라이'는 기본적으로 ' 트리' 형태의 자료 구조이다. 특이한 점은 각 노드가 '배열'로 이루어져 있다는 것이다. 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장 한다고 하면 이 노드는 a부터 z까지의 값을 가지는 배열이 된다. 그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z배열)를 가리킨다. 아래 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보자 루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 된다. 단순히 문자열의 각 문자를 보며 트리를 탐색해나가기만 하면 되기때문에, 위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 '문자열의 길이'에 의해 한정된다. 일반적인 영어 이름의 길이를 n이라고 할때, 검색 시간은 O..
-
[Data Structure] 해시 테이블알고리즘 & 자료구조 2021. 1. 25. 16:13
해시 테이블은 '연결 리스트의 배열' 이다. 여러 값들을 몇 개의 바구니에 나눠 담는 상황을 생각해보자 각 값들은 '해시 함수' 라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정된다. 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결리스트로 이어진다. 이와 같이 연결 리스트가 담긴 바구니가 여러개 있는 것이 '연결 리스트의 배열' , 즉 '해시 테이블' 이 된다. 쉬운 예로 아래 그림과 같이 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ' 이름의 가장 첫 글자' 인 경우를 생각해보자 그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며. 각 포인터는 그 알파벳을 시작하는 이름들을 저장하는 연결 리스트를 가리키게 된다. 만약 해시 함수가 이상적이라면, 각 바구..