본문 바로가기

5. 방학 활동/Write UP

[2023.2.11] 정처기 자격증 스터디 3주차

자료구조의 개념

- 자료 구조는 컴퓨터상 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조이다. 

- 자료 구조의 현명한 선택을 통해 효율적인 알고리즘을 사용할 수 있게 하여 성능을 향상시킨다. 

 

자료 구조의 분류

- 선형 구조 : 데이터를 연속적으로 연결한 자료 구조 ( ex. 리스트, 스택, 큐, 데크)

- 비선형 구조 : 데이터를 비연속적으로 연결한 자료 구조 ( ex. 트리, 그래프)

 

리스트의 종류

선형 리스트 - 배열과 같이 연속되는 기억 장소에 저장되는 리스트
- 선형 리스트의 대표적인 구조로는 배열 등이 있음
- 가장 간편한 자료 구조이며, 접근 구조가 빠름
- 자료의 삽입, 삭제 시 기존 자료의 이동이 필요
연결 리스트 - 노드의 포인터 부분으로 서로 연결시킨 리스트
- 연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트로 구분
- 노드의 삽입, 삭제가 선형 리스트와 달리 편리
- 연결을 위한 포인터가 추가되어 저장 공간이 추가로 필요
- 포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 느림 

스택의 개념

- 스택은 한 방향으로만 자료를 넣고 꺼낼 수 있는 LIFO 형식의 자료 구조이다. 

-한 방향으로만 PUSH와 POP을 이용하여 자료를 넣고 꺼낸다.

 

스택의 연산

- PUSH : 데이터를 차례대로 스택에 넣는 연산

- POP : 스택에서 가장 위에 있는 데이터를 하나씩 꺼내는 연산 

 

스택 응용 분야

- 인터럽트의 처리 : 현재 진행 중인 명령어 위치를 스택에 PUSH하고, 인터럽트 발생 상황을 처리한 후에 인터럽트 전에 진행 중이었던 명령어 스택에서 POP을 통해 받아옴 

- 함수 호출 : 함수를 호출 시 현재 징행 중인 명령어 주소를 스택에 저장 

- 후위표현 연산 : Postfix를 계산할 때 사용

- 깊이 우선 탐색 : 깊이 내려갈 때마다 스택에 값을 PUSH하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 POP한 노드와 인접한 노드를 찾음 

 

트리 순회 방법

- 전위 순회 : 먼저 노드를 방문하고, 왼쪽 서브 트리를 방문한 후, 오른쪽 서브트리를 방문하는 순으로 순회하는 방식이다. 

- 중위 순회 : 중위 순회는 왼쪽 서브 트리를 중위 순회하고, 노드를 방문한 후, 다시 오른쪽 서브 트리를 중위 순회하는 방식이다. 

- 후위 순회 : 후위 순회는 왼쪽 서브 트리를 후위 순회하고, 다시 오른쪽 서브 트리를 후위 순회한 뒤에 노드를 방문하는 방식이다.