자료구조

맵 맵은 원소를 저장하고 키를 이용하여 빠르게 찾을 수 있도록 한다. 엔트리라 불리는 키-값 쌍(k, v)을 저장한다. 맵 ADT에서 각 키는 유일하여 키와 값의 연관은 매핑을 정의한다. 가장 높은 수준의 일반화를 위해, 맵에 저장된 키와 값은 어떠한 객체타입도 가능하다. 키는 일종의 위치 역할을 하는 객체이다. 맵은 객체에 연관된 키가 그 자료구조에서 객체의 위치를 결정하기 때문에 연관된 저장소(associative stores) 또는 연관된 컨테이너(associative container)라고 불리기도 한다. 엔트리와 구성 패턴 엔트리는 구성 패턴(Composition Pattern)이라 불리는 객체지향 설계 패턴의 한 예로 다른 객체들로 구성된 단일 객체를 정의한다. 쌍은 가장 간단한 구성이다. 두..

링크드 리스트 : 어떤 노드를 저장할 때 그 다음 순서의 자료가 있는 위치를 포함시키는 상식으로 자료를 저장 단일 링크드 리스트(singly linked list) : 각각의 노드가 값과 다음 노드를 가리키는 포인터 next를 저장한다. next 참조를 통해 한 노드에서 다른 노드로 이동하는 것을 링크 연결하기(link hopping) 또는 포인터 연결하기(pointer hopping)라고 한다. 링크드 리스트의 제일 처음과 마지막 노드를 각각 그 리스트의 head와 tail이라 부른다. null값을 참조하는 next 값을 가진 node가 tail이다. 배열과 마찬가지로 단일 링크드 리스트도 특정 순서로 원소들을 저장하며, 이 순서는 next 링크의 연결로써 결정된다. 배열과 다른 점은 단일 링크드 리스..

그래프의 표현 위의 그래프는 정점(vertex)이 6개, 간선(edge)이 8개 있다. (정점들을 연결한 게 간선이다.) 간선에 방향이 없기 때문에, 방향이 없는 그래프이다. 정점은 단순하게 그냥 숫자를 저장하면 된다. (숫자가 아닌 다른 게 vertex여도 숫자로 바꿔서 저장하면 된다.) vertex : {1, 2 ,3, 4, 5, 6} edge : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)} 간선(edge)을 저장하는 방법은 여러 가지가 있다. 1. 인접 행렬 (Adjacency - matrix) 정점의 개수를 V라고 했을 때, VxV 크기의 이차원 배열을 이용한다. A[i][j] = 1 (i -> j 간선이 있을 때), 0 (없..

이거 수업시간에 배웠을 때는 교수님이 데크라고 부르시던데 남들은 다 덱이라고 쓰니까 나도 덱이라고 써야지!!ㅋㅋㅋㅋㅋ 덱(deque)은 double-ended queue의 약자로 양방향 큐이다!! 그러니까 큐에서는 앞에서 pop이 일어나고 뒤에서 push가 일어나는 대기줄이라고 말했었는데 덱은 앞에서도 pop과 push가 가능하고 뒤에서도 pop과 push가 가능하다. 덱의 method는 push_front : 덱의 앞에 자료를 넣는 연산 push_back : 덱의 뒤에 자료를 넣는 연산 pop_front : 덱의 앞에서 자료를 빼는 연산 pop_back : 덱의 뒤에서 자료를 빼는 연산 front : 덱의 가장 앞에 있는 자료를 보는 연산 back : 덱의 가장 뒤에 있는 자료를 보는 연산 등이 있다...

큐(Queue)는 뒤에서 자료를 넣고 앞에서 뺄 수 있는 자료구조이다. 대기줄을 생각해보면 된다. 놀이공원에 줄을 섰을 때 가장 먼저 줄을 선 사람이 기구를 먼저 타러 가고 늦게 온 사람들은 줄 서있는 사람들 뒤에 줄을 서지 바로 앞으로 가서 줄을 서면 안된다!! 큐가 이런 대기줄 개념이다. 먼저 넣은 것이 가장 먼저 나오기 떄문에 First In First Out(FIFO)라고도 한다. queue의 method 들을 살펴보면 push : 큐에 자료를 넣는 연산 pop : 큐에서 자료를 뺴는 연산 front : 큐의 가장 앞에있는 자료를 보는 연산 back : 큐의 가장 뒤에있는 자료를 보는 연산 empty : 큐가 비어있는지 아닌지를 알아보는 연산 size : 큐에 저장되어있는 자료의 개수를 알아보는 ..

스택 관련 문제들 계속 풀어보고 있다!! 백준 1874번 www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 : 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First o..

Stack(스택)은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다. 마지막으로 넣은 것이 가장 먼저 나오기 때문에 last in first out (LIFO)라고도 한다. stack의 기본적인 기능은 push: 스택에 자료를 넣는 연산 pop: 스택에서 자료를 빼는 연산 top: 스택의 가장 위에 있는 자료를 보는 연산 empty: 스택이 비어있는지 아닌지를 알아보는 연산 size: 스택에 저장되어있는 자료의 개수 를 알아보는 연산 스택은 밑이 막혀있는 그릇 같은?? 구조라고 보면 되는데 우리가 먼저 넣은 음식이 맨 밑에 깔리는 거랑 같다고 보면 된다. 그래서 1 2 3 4 5 를 차례대로 스택 안에 넣었다고 가정하면 가장 먼저들어간 1이 가장 밑에 깔리고 제일 늦게 들어간 5가 스택의 맨 위에 있..