본문 바로가기

자료구조

(11)
그래프 (Graph) 그래프는 트리와 비슷하게 생긴 자료구조로 정점과 간선으로 이루어져있다.먼저 용어정리를 하자면 정점(Node, Vertex)은 각각의 자료를 말한다.정점과 정점을 잇는 선을 간선(Edge)라고 한다.차수(Degree)는 한 정점에 몇 개의 간선이 연결되어 있는가라는 것인데, 위의 사진에서 보면정점 2의 차수는 4라는 것을 알 수 있다. 자기 자신으로 다시 돌아올 수 있는 경로를 사이클(Cycle)이라고 한다. 그래프는 사람과 사람을 연결해주는 네트워크에서 볼 수 있는 구조이기도 하고,지하철 노선도 역시 그래프로 해석할 수 있기 때문에, 현실의 많은 것들과연관이 되어있기 때문에 중요한 자료구조라고 할 수 있다.그러므로 수학적 정리가 매우 방대하고, 스택과 큐 같은 자료구조는 구현이 간단하지만그래프는 그만큼 ..
힙을 이용한 우선순위 큐 구현 1) 삽입연산 (push)- 힙은 완전 이진 트리 형태이기 때문에 삽입연산을 할 때에는 배열의 길이면서 원소를 삽입해주는 인덱스를 표현해주는 len 변수를 선언해서 큐의 len에 원소를 삽입해주고 len의 길이를 1 늘린다.- 그리고 나는 idx 라는 변수를 선언해서 새로운 원소가 삽입된 자리의 인덱스를 기억해서 부모와 우선순위를 비교 했다.- 부모의 인덱스, 즉 idx / 2 와 비교 해서 idx가 더 작게 되면 자리를 계속해서 바꿔주고, 아니면 반복문을 빠져나간다. 여기서 주의 할 점은 삽입한 원소가 가장 우선순위가 높아 루트노드 까지 가게 되면 더이상 비교할 것이 없기 때문에 반복문을 멈춰줘야 하는데, while 문의 조건을 보면 idx > 1일때만 실행 되게 하여 idx 가 1이 되었을 때 (루트..
힙 (Heap) 힙은 부모의 값이 항상 자식보다 우선순위가 높은 (사진상에서는 작은 숫자가 우선순위가 높다고 가정) 완전 이진 트리이다.완전 이진 트리는 자식이 항상 2개이고, 왼쪽에서 오른쪽방향으로 원소가 추가 되는 트리를 말한다. 힙에서는 2가지 연산을 할 수 있다.1) 원소를 추가하는 연산2) 원소를 삭제하는 연산 힙에 값을 삽입할 때 힙은 완전 이진 트리이기 때문에 무조건 사진의 화살표 방향으로 원소를 추가해야 한다.위의 사진상에 4를 추가한다고 해보자. 4를 추가하면 사진처럼 완전이진트리에 삽입된다. 근데 힙은 항상 부모 노드의 값이 자식노드보다 우선순위가 크기 때문에 4를 삽입했을 때 올바른 자리가 아니다.그러기 때문에 4노드의 부모노드인 7과 우선순위를 비교해서 자리를 바꿔줘야 한다. 4와 7의 자리를 바꾼..
우선순위 큐 (Priority Queue) 우선순위 큐는 원소를 push하는 방법은 기존의 큐와 똑같지만 삭제 연산을 할 때 우선순위가 높은 원소 순서대로 제거 하는 큐이다. 그림처럼 원소를 1 -> 3 -> 4 -> 5 순서로 push한다. 큐 안에 push 된 원소들은 1, 3, 4, 5 순서대로 있지만 우선순위 큐에서는 우선순위를 부여하여 우선순위가 가장 높은 순서대로 원소를 제거 한다.그림상에서는 숫자가 큰 순서대로 우선순위가 크다고 가정했다. 우선순위 큐는 배열로 구현 할 수 있는데, 삽입 연산은 그대로 큐의 끝에 원소를 삽입하여 O(1)의 시간이 걸린다.하지만 삭제 연산을 할 때, 배열의 처음부터 큐의 길이 까지 우선순위를 탐색하여 가장 큰 원소를 삭제하고그 다음에 삭제한 원소의 빈자리를 오른쪽에서 부터 한칸씩 당겨야 하기 때문에 O(..
트리순회 결과 출력하기 문제루트가 0인 이진트리가 주어질 때, 이를 전위순회, 중위순회, 후위순회한 결과를 각각 출력하는 프로그램을 작성하시오. 아래 그림은 이진트리의 예제와, 이 이진트리를 전위순회, 중위순회, 후위순회 한 결과를 나타낸다. 입력첫 번째 줄에 트리의 노드 개수 n이 주어진다. ( 1 ≤ n ≤ 100 ) 두 번째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c로 이루어지며, 그 의미는 노드 a의 왼쪽 자식노드가 b, 오른쪽 자식노드가 c라는 뜻이다. 자식노드가 존재하지 않을 경우에는 -1이 주어진다. 출력첫 번째 줄에 전위순회, 두 번째 줄에 중위순회, 세 번째 줄에 후위순회를 한 결과를 출력한다. 예제 입력6 0 1 2 1 3 4 2 -1 5 3 -1 -1 4 -1 -1 5 -1 -1 예..
트리 (Tree) 하나의 정점을 Node 라고 하고 Node 와 Node를 이어 주는 선을 간선(Edge) 이라고 한다. 1은 부모노드이고 1의 자식노드는 2와 3이다 Node 4 하나도 트리라고 한다. 자식노드가 2개 이하인 트리를 이진트리(Binary Tree)라고 한다. 트리 순회는 재귀적으로 구현한다.출처 : AlgorithmLABS
원형 큐 구현하기 문제이 문제에서는 원형 큐를 구현한다. 선형 큐는 “큐가 실제로는 비어있어도 Push와 Pop을 할 수 없는" 문제가 발생할 수 있다. 원형 큐는 이 문제를 해결한다. 원형 큐 역시 큐와 마찬가지로 다음 세 개의 연산을 지원한다.Push X : 큐에 정수 X를 push한다. 만약 rear 포인터가 더 이상 뒤로 갈 수 없다면, “Overflow”를 출력한다.Pop : 큐에서 정수 하나를 pop한다. 만약 front 포인터가 더 이상 뒤로 갈 수 없다면, “Underflow”를 출력한다.Front : 큐의 front에 있는 정수를 출력한다. 만약 큐가 비어있다면 “NULL”을 출력한다.크기가 n인 원형 큐에 m개의 연산을 하는 프로그램을 작성하시오. 입력의 편의를 위해서 Push는 “1”, Pop은 “2”..
원형 큐 (Circular Queue) 큐 구현의 문제점은 계속 rear에 원소를 추가하게 되면 위의 사진처럼 길이 10짜리 배열을 선언하고 큐의 크기를 4짜리를 사용하다 보면 배열의 크기를 벗어나게 되면 앞의 공간이 비게 되어 공간의 효율성이 매우 떨어진다. 공간의 효율성이 떨어지는 큐를 개선한 원형 큐 (Circular Queue)는 front와 rear을 연결하여 그림과 같이 공간을 효율적으로 사용할 수 있다. data 배열의 길이를 8로 선언하고, 길이가 4인 원형 큐를 구현하는 방법을 보자.rear 에 원소를 계속 추가하다 보면 data 가 꽉차게 되는데 이때 rear을 다시 0으로 바꾸는 것이다. 그러면 비어있는 앞의 공간을 활용할 수 있다. front 역시 배열의 끝까지 도달하게 되면 다시 0으로 front를 옮겨주어 공간 활용을..