자료구조의 개념
- 자료 구조는 컴퓨터상 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조이다.
- 자료 구조의 현명한 선택을 통해 효율적인 알고리즘을 사용할 수 있게 하여 성능을 향상시킨다.
자료 구조의 분류
- 선형 구조 : 데이터를 연속적으로 연결한 자료 구조 ( ex. 리스트, 스택, 큐, 데크)
- 비선형 구조 : 데이터를 비연속적으로 연결한 자료 구조 ( ex. 트리, 그래프)
리스트의 종류
선형 리스트 | - 배열과 같이 연속되는 기억 장소에 저장되는 리스트 - 선형 리스트의 대표적인 구조로는 배열 등이 있음 - 가장 간편한 자료 구조이며, 접근 구조가 빠름 - 자료의 삽입, 삭제 시 기존 자료의 이동이 필요 |
연결 리스트 | - 노드의 포인터 부분으로 서로 연결시킨 리스트 - 연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트로 구분 - 노드의 삽입, 삭제가 선형 리스트와 달리 편리 - 연결을 위한 포인터가 추가되어 저장 공간이 추가로 필요 - 포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 느림 |
스택의 개념
- 스택은 한 방향으로만 자료를 넣고 꺼낼 수 있는 LIFO 형식의 자료 구조이다.
-한 방향으로만 PUSH와 POP을 이용하여 자료를 넣고 꺼낸다.
스택의 연산
- PUSH : 데이터를 차례대로 스택에 넣는 연산
- POP : 스택에서 가장 위에 있는 데이터를 하나씩 꺼내는 연산
스택 응용 분야
- 인터럽트의 처리 : 현재 진행 중인 명령어 위치를 스택에 PUSH하고, 인터럽트 발생 상황을 처리한 후에 인터럽트 전에 진행 중이었던 명령어 스택에서 POP을 통해 받아옴
- 함수 호출 : 함수를 호출 시 현재 징행 중인 명령어 주소를 스택에 저장
- 후위표현 연산 : Postfix를 계산할 때 사용
- 깊이 우선 탐색 : 깊이 내려갈 때마다 스택에 값을 PUSH하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 POP한 노드와 인접한 노드를 찾음
트리 순회 방법
- 전위 순회 : 먼저 노드를 방문하고, 왼쪽 서브 트리를 방문한 후, 오른쪽 서브트리를 방문하는 순으로 순회하는 방식이다.
- 중위 순회 : 중위 순회는 왼쪽 서브 트리를 중위 순회하고, 노드를 방문한 후, 다시 오른쪽 서브 트리를 중위 순회하는 방식이다.
- 후위 순회 : 후위 순회는 왼쪽 서브 트리를 후위 순회하고, 다시 오른쪽 서브 트리를 후위 순회한 뒤에 노드를 방문하는 방식이다.
'5. 방학 활동 > Write UP' 카테고리의 다른 글
[2023.07.16] 워게임 문제풀이(2) - 1 (0) | 2023.07.17 |
---|---|
[2023.2.10] 공모전 스터디 2주차 (0) | 2023.02.28 |
[2023.01.28] 정처기 자격증 스터디 1주차 (0) | 2023.02.28 |
[2023.02.20] 워게임&CTF 스터디 1팀 문제풀이(암호, 포렌식) (0) | 2023.02.27 |
[2023.02.05] 워게임&CTF 스터디 2팀 문제풀이(rev-basic-3) (0) | 2023.02.27 |