[알고리즘] 4. 알고리즘 작성을 위한 자료구조 (1)

1. 배열

• 알고리즘: 문제 해결을 위한 절차

• 자료구조: 데이터를 효율적으로 이용하기 위해 구성한 논리적 구조

- 자료구조가 결정되면 사용할 수 있는 알고리즘도 결정됨

- 적절한 자료구조를 선택하는 것이 중요

 

1) 자료구조의 종류

• 단순 구조: 정수, 실수, 문자, 문자열 등

• 선형 구조: 자료 간의 관계가 일대일 (배열, 연결 리스트, 스택, 큐)

• 비선형 구조: 자료 간의 관계가 일대다 또는 다대다 (트리, 그래프)

 

2) 배열 (Array)

• 동일한 자료형의 데이터를 연속된 공간에 저장하는 자료구조

• 장점: 인덱스를 통해 O(1)의 시간 복잡도로 빠르게 접근 가능

• 단점: 삽입, 삭제 시 데이터 이동이 필요하여 연산이 비효율적

 

3) 배열 연산

• 삽입: 삽입 위치를 확보하기 위해 요소들을 뒤로 이동 (평균 이동 횟수 (n+1)/2)

• 삭제: 삭제된 위치를 채우기 위해 요소들을 앞으로 이동 (평균 이동 횟수 (n-1)/2)

 

 

 

2. 연결 리스트 (Linked List)

• 데이터가 연속된 공간에 저장될 필요 없이 노드(Node)들이 포인터로 연결된 자료구조

• 장점: 삽입, 삭제 시 데이터 이동이 필요 없음

• 단점: 특정 요소 접근 시 순차 탐색이 필요하여 속도가 느림

 

1) 연결 리스트의 노드 구조

• 데이터 필드: 저장할 데이터

• 링크 필드: 다음 노드를 가리키는 포인터

 

2) 연결 리스트 연산

삽입

• 새로운 노드를 생성하여 데이터 저장

• 링크를 지정하여 기존 노드와 연결

 

삭제

• 삭제할 노드의 앞 노드를 찾아 링크를 조정

• 삭제된 노드 메모리 해제

 

 

 

3. 스택과 큐

1) 스택 (Stack)

후입선출 (LIFO, Last-In First-Out) 구조

 

연산

• Push: 데이터를 스택에 삽입

• Pop: 데이터를 스택에서 삭제

• 활용 예시

- 함수 호출 및 복귀 주소 저장

- 컴파일러의 문법 검사 (괄호 짝 검사)

- 미로 탐색에서 경로 저장

 

2) 큐 (Queue)

선입선출 (FIFO, First-In First-Out) 구조

 

연산

• Enqueue: 데이터를 큐에 삽입

• Dequeue: 데이터를 큐에서 삭제

• 활용 예시

- CPU 작업 스케줄링

- 프린터 버퍼 관리

 

3) 원형 큐 (Circular Queue)

일반적인 큐의 공간 낭비 문제를 해결하기 위해 처음과 끝을 연결한 구조

 

4) 데크 (Deque)

양쪽 끝에서 삽입과 삭제가 가능한 큐

• 입력 제한 덱: 한쪽에서만 입력 가능

• 출력 제한 덱: 한쪽에서만 출력 가능

---

이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.