[자료구조/알고리즘] 자료구조

김수민·2023년 12월 15일

알고리즘 자료구조

알고리즘

목록 보기

2/2

[자료 구조]

1. 자료 구조

여러 데이터 묶음을 저장하고, 사용하는 방법을 정의한 것
데이터를 구조에 따라 체계적으로 정리하여 저장하는 것이 데이터 활용에 유리
특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있음

[Stack]

1. Stack

쌓다, 쌓이다, 포개지다와 같은 의미
데이터를 순서대로 쌓는 자료 구조
가장 먼저 들어간 데이터가 마지막으로 나올 수 있는 구조(LIFO)
입력과 출력이 한 방향으로 이루어지는 제한적 접근
Stack에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'이라고 함
- peek()과 pop()의 차이
  peek() : 스택에 쌓인 가장 위의 요소를 반환하는 메서드
  pop() : 스택에 쌓인 가장 위의 요소를 꺼내는 메서드

2. Stack 특징

LIFO(Last In First Out)

먼저 들어간 데이터는 가장 나중에 나오는 후입선출의 구조를 가짐

데이터는 하나씩 넣고 뺄 수 있음

데이터가 아무리 많아도 하나씩 데이터를 넣고, 뺄 수 있음
한꺼번에 여러 개 X

하나의 입출력 방향을 가지고 있음

데이터의 입출력 방향이 같음

3. Stack 자료 구조 장점

후입선출의 구조를 가지기에, 스택에 저장된 데이터를 가져오는 속도 ↑

삽입/삭제가 항상 스택의 맨 위에서 이루어지기 때문에, 데이터 삽입/삭제 시 다른 데이터의 위치를 변경할 필요 X
데이터 삽입/삭제 시, 모든 데이터를 순회할 필요가 없기 때문

별도의 라이브러리나 모듈을 설치할 필요가 없음

자바에서는 이미 Stack 클래스가 구현되어 있어, 자료 구조의 특징과 메서드를 활용할 수 있을 경우 바로 사용 가능

4. Stack 자료 구조 단점

크기 제한이 없음

데이터를 저장할 때 크기가 제한되지 않기 때문에, 메모리 사용량이 불필요하게 증가할 수 있음
스택의 크기를 미리 정해두거나, 동적으로 크기를 조절하는 방법 사용(Java X)

Vector 클래스를 상속받아 구현되어 있어, 크기를 동적으로 조정 X

Vector 클래스는 내부적으로 배열을 사용
배열의 크기는 지정된 크기만큼만 할당되고, 스택에 저장되는 데이터 개수가 배열의 크기를 초과할 경우 새로운 배열을 할당해, 기존 데이터를 새로운 배열로 복사하는 작업 수행
즉, 크기가 자주 변하는 스택에서는 다른 자료 구조 사용이 효율적

Vector 클래스를 상속받아, 중간에서 데이터 삽입/삭제가 가능

Vector 클래스를 상속받기 때문에, Vector 클래스의 모든 메서드 사용 가능
이러한 구현 방식은 스택의 의도된 동작을 방해할 수 있기 때문에 주의 필요

[Queue]

1. Queue

줄을 서서 기다리다, 대기행렬이라는 의미
가장 먼저 들어온 데이터가 가장 먼저 나가는 구조(FIFO)
입력과 출력의 방향이 고정되어 있으며, 두 곳으로 접근이 가능
Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 함
데이터가 입력된 순서대로 처리할 때 주로 사용

2. Queue 특징

FIFO(First In First Out)

먼저 들어간 데이터가 가장 처음에 나오는 선입선출의 구조를 가짐

데이터는 하나씩 넣고 뺄 수 있음

데이터가 아무리 많아도, 하나씩 데이터를 넣고 뺌

두 개의 입출력 방향을 가짐

데이터의 입력/출력 방향이 다름

3. Queue 자료 구조 장점

자료를 넣은 순서대로 데이터를 꺼내 처리 가능

가장 앞에 가장 오래전에 삽입된 데이터가 위치하고, 가장 뒤에 가장 최근에 삽입된 데이터가 위치
즉, Queue에 데이터를 삽입/삭제 순서가 동일하게 유지됨
데이터 처리나 작업 처리에서 순서가 중요한 경우 용이

중간 원소를 삭제하는 연산이 없어 다른 자료 구조에 비해 상대적으로 빠른 속도를 보임

Queue의 삽입과 삭제는 각각 Queue의 끝단에서 이루어져, 중간에 있는 원소를 삭제하는 연산이 없음
즉, 삽입과 삭제 연산은 단 한 번의 실행만으로 처리 가능

별도의 라이브러리나 모듈을 설치할 필요 X

Queue 클래스가 자바에 구현되어 있음

4. Queue 자료 구조 단점

중간에 있는 데이터를 조회하거나 수정하는 연산에 적합하지 않음

가장 먼저 추가한 위치에서부터 차례로 데이터를 처리하며, 가장 나중에 추가된 위치에서 새로운 데이터를 추가
즉, 특정 위치의 데이터를 조회하거나 수정하는 연산에 적합하지 않음

크기 제한이 없어 메모리의 낭비가 발생할 수 있음(Java 한정)

Queue 인터페이스는 크기 제한이 없는 큐를 구현할 수 있도록 설계되어 있어, 메모리의 낭비 가능성을 높임
크기 제한 시, 직접 구현하거나 기존의 Queue 인터페이스를 상속받아 크기 제한을 추가한 클래스를 구현해야 함

iterator() 메서드 지원 X (Java 한정)

FIFO 구조를 가지기 때문에 iterator() 메서드 지원 X
따라서, Queue의 데이터를 순회할 때는 peek() 메서드와 poll() 메서드를 사용해 데이터를 차례로 가져와야 함(데이터 제거 메서드)

remove(Object o) 메서드의 동작이 불명확(Java 한정)

remove(Object o) 메서드는 해당 객체를 큐에서 삭제하지만, 큐가 중복된 객체를 허용하는 경우 어떤 객체가 삭제되는지 명확하지 않음
remove(Object o) 대신 poll() 메서드를 사용

[Tree]

1. Tree

그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태로 이루어진 구조
데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료 구조
데이터를 순차적으로 나열한 선형 구조가 아닌, 하나의 데이터 아래에 여러 데이터가 존재할 수 있는 비선형 구조
계층적으로 표현되며, 아래로만 뻗어나가기 때문에 사이클 X

2. Tree의 구조

루트(root) : 하나의 꼭짓점 데이터로, Tree의 최상단 시작지점
간선(edge) : 여러 데이터를 연결하는 선
노드(node) : 트리 구조를 이루는 모든 개별 데이터
두 노드가 상하 계층으로 연결되면 부모/자식 관계를 가지며 부모/자식 노드로 표현
리프 노드 : 자식이 없는 노드
깊이(depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이
레벨(level) : 같은 깊이를 가지고 있는 노드의 묶음(=형제 노드)
높이(height) : 리프 노드를 기준으로부터 루트까지의 높이
서브 트리 : 루트에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리

3. Tree의 장점

효과적인 계층 구조 표현
정렬/탐색에 활용

이진 탐색 트리, 힙 등과 같은 형태로 사용가능하며, 정렬/탐색 알고리즘 구현에 사용

삽입/삭제 용이

삽입/삭제 시 해당 노드의 부모와 자식 노드만 수정하기 때문

구조 파악 용이

시각화가 쉬워 구조 파악이 용이

다양한 분야에서 활용

데이터베이스, 알고리즘 등 다양한 분야에 사용

4. 이진 트리

각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조
이진 탐색 트리(Binary Search Tree) : 각 노드의 왼쪽 서브 트리에는 해당 노드보다 작은 값이, 오른쪽 서브 트리에는 해당 노드보다 큰 값이 저장되는 규칙을 가진 이진 트리
힙 : 각 노드의 값이 자식 노드의 값보다 작거나, 큰 특정 순서를 유지하는 구조의 완전 이진 트리
트라이(Trie) : 문자열을 저장하고 검색하는 데 특화된 트리 구조로 각 노드가 문자열의 한 문자를 저장(문자열 검색, 자동 완성 등에 사용)

5. 이진 트리 종류

정 이진 트리 : 각 노드가 0개 혹은 2개의 자식 노드를 가짐
포화 이진 트리 : 정 이진 트리이면서 완전 이진 트리인 경우로, 모든 리프 노드의 레벨이 같고 모든 레벨이 가득 채워져 있는 이진 트리
완전 이진 트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하며, 마지막 레벨의 노드의 왼쪽은 모두 채워진 이진 트리

6. 이진 탐색 트리

이진 탐색 속성이 이진 트리에 적용된 특별한 형태의 이진 트리
- 이진 탐색
  정렬된 데이터 중 특정한 값을 찾기 위한 탐색 알고리즘
  오름차순으로 정렬된 데이터를 같은 크기의 두 부분으로 나눈 후, 두 부분 중 탐색이 필요한 부분에서만 탐색하는 알고리즘
루트 노드는 이진 탐색에서 전체 데이터의 중간값
왼쪽은 모두 루트의 값보다 작은 값이며, 오른쪽은 모두 루트의 값보다 큰 값
각 노드에 중복되지 않는 Key(노드에 입력된 값)가 존재
좌우 서브 트리 모두 이진 탐색 트리

7. 이진 탐색 트리의 탐색 과정

루트 노드의 키와 찾고자 하는 값 비교(같은 경우, 탐색 종료)
찾고자 하는 값 < 루트 노드의 키, 왼쪽 서브 트리 탐색
찾고자 하는 값 > 루트 노드의 키, 오른쪽 서브 트리 탐색

[Graph]

1. Graph

여러 개의 점들이 서로 복잡하게 연결되어 있는 관게를 표현한 자료 구조

2. Graph의 구조

직접적인 관계가 있는 경우 두 점을 이어주는 선이 존재
간접적인 관게가 있는 경우 몇 개의 점과 선에 걸쳐 이어짐
하나의 점을 정점이라 표현하며, 하나의 선은 간선이라고 표현

3. Graph 표현 방식

인접 행렬

두 정점을 바로 이어주는 간선이 있을 경우 '인접한다' 라고 표현
서로 다른 정점들이 인접한 상태인지를 표현한 행렬로 2차원 배열의 형태로 나타냄
이어져 있을 경우 1(true), 이어져 있지 않을 경우 0(false)

인접 리스트

각 정점이 어떤 정점과 인접하는지를 리스트 형태로 표현
각 정점마다 하나의 리스트를 가지고 있으며, 자신과 인접한 다른 정점을 담고 있음

[Tree Traversal(트리 순회)]

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것

1. 전위 순회(preorder traverse)

루트에서 시작해 왼쪽의 노드를 차례로 둘러본 뒤, 오른쪽 노드를 탐색
주로 트리를 복사할 때 사용
부모 노드가 제일 먼저 방문되는 순회 방식

2. 중위 순회(inorder traverse)

루트를 가운데 두고 순회
제일 왼쪽 끝에 있는 노드부터 순회하기 시작해, 왼쪽 노드 순회가 끝나면 루트를 거쳐 오른쪽 노드를 탐색
부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식
이진 탐색 트리의 오름차순으로 값을 가져올 때 사용

3. 후위 순회(postorder traverse)

루트를 가장 마지막에 순회
제일 왼쪽 끝에 있는 노드부터 순회하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문
트리를 삭제할 때 사용

[Graph Search Alogrithm]

1. Graph Traversal

그래프의 탐색은 하나의 정점에서 시작해, 그래프의 모든 정점을 한 번씩 방문하는 것이 목적
데이터가 배열처럼 정렬되어 있지 않기 때문에, 원하는 자료를 찾아야 할 경우 하나씩 모두 방문하여 찾아야 함

2. BFS(Breadth-First Search)

너비를 우선적으로 탐색하는 너비 우선 탐색
인접한 정점부터 방문하는 방식으로 구현
큐 자료 구조를 활용
최단 경로 탐색에 유리(가까운 정점부터 방문하기 때문)
방문한 정점들을 저장해야 하는 경우 메모리 사용 ↑
그래프의 크기와 밀도에 따라 성능이 달라짐(간선의 개수가 많을 경우 BFS 성능 ↓)
시작 정점에서 도달할 수 없는 정점에 대해 탐색 X
방문 여부르르 체크하는 자료 구조를 사용해야 함(무한 루프 방지)

3. DFS(Depth-First Search)

깊이를 우선적으로 탐색하는 깊이 우선 탐색
모든 정점을 방문하는 알고리즘
스택 자료 구조 혹은 재귀를 이용해 구현
한 분기를 탐색한 후, 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색
그래프 내 순환구조(cycle)을 고려하여 방문한 정점을 다시 방문하지 않도록 해야함

이전 포스트

[자료구조/알고리즘] 재귀

0개의 댓글