• 검색 결과가 없습니다.

9장. 자료 구조

N/A
N/A
Protected

Academic year: 2023

Share "9장. 자료 구조"

Copied!
56
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

9장. 자료 구조

컴퓨터공학 개론

(2)

학습목표

 자료구조의 정의와 사용 방법 학습

 1차원 및 다차원 배열과 이들의 작동 방법 학습

 포인터의 정의와 자료구조에서의 사용 방법 학습

 연결리스트가 동적 정보에 대한 작업을

가능하게 함을 학습

(3)

학습목표(계속)

 스택이 연결리스트의 일종이라는 사실과 스택의 사용 방법을 이해

 큐가 연결리스트의 다른 형태라는 사실과 큐의 사용 방법을 이해

 이진 트리가 계층적 순서로 정보를 저장하는 자료구조임을 학습

 다양한 정렬 루틴의 소개

(4)

자료구조를 배워야 하는 이유

 자료구조는 컴퓨터 내의 데이터를 구성함

 데이터의 효과적인 접근 및 처리

 모든 프로그램은 어떤 형태로든지 자료구조를 사용함

 자료구조를 사용하는 여러 경우 존재

(5)

자료구조

 자료구조 : 데이터를 구성하는 수단

 자료구조의 유형

 주 메모리를 위한 배열, 리스트, 스택, 큐, 트리

 보조기억장치를 위한 다른 파일 구조들

 컴퓨터의 메모리는 셀들로 구성

 메모리 셀은 메모리 주소와 내용을 가짐

 메모리 주소는 연속적으로 구성됨

 자료구조는 물리적인 구현을 은닉함

(6)

배열

 배열

가장 간단한 메모리 자료구조

일련의 연속적인 메모리 셀들로 구성

메모리 셀들은 동질적인 데이터를 저장

저장된 데이터는 정렬되거나 입력된 채로 남아 있을 수 있음

 유용성

학점, 책제목, 교과목 등

많은 수의 비슷한 항목에 대해서 하나의 변수 이름

(7)

[그림 9-2] 배열은 프로그램의 논리를 이해하고 사용하기 쉽도록 해준다.

(8)

배열의 동작방법

선언(정의) : 데이터 유형과 크기를 제공

Java의 예: int[ ] aGrades = new int[5];

“int[ ]”는 컴퓨터에게 배열이 정수를 보관함을 알려줌

“aGrades”는 배열의 이름

“new”키워드는 새로운 배열이 생성됨을 명세함

“int[5]”는 5개의 메모리 장소를 확보함

“=” 기호는 aGrades를 배열의 “관리자”로 지정함

“;”(세미콜론)은 문장의 끝임을 알려줌

헝가리식 표기법 : “aGrades”를 명명하기 위한 표준

(9)

[그림 9-3] 일차원 배열에서 aGrades에 의해 관리되는 5개의 연속적인 메모리 셀

(10)

배열의 동작방법(계속)

 차원성

차원 : 원소(메모리 셀)의 행/열

aGrades는 1차원임(한 줄의 우편함처럼)

 1차원 배열의 조작

처음 주소(위치)는 하한임 : 영(0)

다음 원소는 시작 주소로부터 1만큼 떨어져 있음

인덱스(아래첨자) : 접근을 위해 “[]”내에 위치한 정수

예 : aGrades[0] = 50;

상한은 배열의 크기보다 1만큼 적음 : 사(4)

(11)

[그림 9-5] 배열은 0번째 위치에서 시작하며 다음 원소가 메모리 내의 어디에 위치하는지 알기 위해 오프셋을 사용한다.

(12)

[그림 9-6] 모든 원소들이 저장된 배열

(13)

다차원 배열

 다차원 배열

둘 또는 그 이상의 1차원 배열로 구성됨

각행의 위에 여러 행들이 쌓여 있음

아파트 건물의 우편함

Tic-tac-toe 게임판

 정의 : char[ ][ ] aTicTacToe = new char[3][3];

 지정 : aTicTacToe[1][1] = ’X’;

X를 두 번째 행의 두 번째 열에 놓음

 3차원 이상의 배열은 다루기 어려움

(14)

[그림 9-10] Tic-Tac-Toe 게임판의 두 번째 및 세 번째 행

(15)

[그림 9-11] 배열의 한 위치에 값을 저장

(16)

[그림 9-12] 3차원 배열

(17)

배열의 사용

 배열의 장점

메모리 셀의 순차 접근을 허용

이름과 데이터를 사용하여 데이터를 검색/저장

구현이 쉬움

프로그램 작성과 판독을 단순화

 제약점 및 단점

클래스와 달리 이질적인 항목들을 저장할 수 없음

동적인 메모리 할당 불가능

정렬되어 있지 않은 배열의 탐색은 효율적이지 않음

(18)

리스트

 리스트 : 동적 자료구조

 예 : 과목 등록, 수리 의뢰된 차량, e-메일함

 데이터의 양이 알려져 있지 않거나 변화할 수 있는 경우에 적절함

 기본적인 세가지 리스트 형태 :

 연결리스트

 큐

 스택

(19)

연결리스트

 연결리스트

가변 데이터 집합을 위해 사용되는 구조

배열과는 달리 데이터를 불연속적으로 저장

데이터와 다음에 연결된 셀의 주소를 관리

예 : 교수연구실을 방문하는 학생의 이름,

좋아하는 비디오 게임에서 얻은 점수, 스팸 메일 발송자 리스트

 연결리스트는 고급자료구조의 기본임

큐와 스택

이런 각각의 구조들은 포인터에 기반함

(20)

연결리스트(계속)

포인터 : 데이터로서 주소를 가지는 메모리 셀

주소 : 메모리내의 위치

예 : 연결리스트 게임

학생들은 종이를 들고 원형으로 앉음

종이의 왼쪽 위 구석과 중앙에는 네모칸이 있음

왼쪽 위 네모칸은 학생 번호를 나타냄

가운데 네모칸은 두 부분으로 나뉨

학생은 중앙의 왼쪽 부분에 좋아하는 색상을 기록함

(21)

[그림 9-14] 연결 리스트 구조

(22)

연결리스트(계속)

종이는 두 부분으로 구분된 하나의 노드를 나타냄

데이터(첫 번째 부분, 색상)

포인터 : 다음 위치(학생 ID 번호)

교수의 종이 : 데이터가 없는 헤드 포인터

마지막 학생 : 포인터 값은 NULL임

새로운 원소의 삽입

배열과 달리 크기 조정이 불필요함

두개의 노드 구조를 가진 새로운 “종이”를 만듬

새로운 노드(종이)를 수용하도록 포인터를 조정

(23)

[그림 9-15] 연결 리스트에 대한 원소의 삽입

(24)

연결리스트(계속)

 항목의 삭제를 위해서도 유사한 과정

 목표 항목의 앞에 있는 원소의 포인터를 변경

 원소를 이동시키지 않고 리스트로부터 학생을 제거

 동적 메모리 할당

 연결리스트가 배열보다 더 효율적임

 메모리 셀들은 연속적일 필요 없음

(25)

[그림 9-16] 연결 리스트로부터 원소의 삭제

(26)

스택

스택 : 특별한 형태의 리스트

새 항목의 저장을 위해, 리스트에 “푸시(push)”함

현재항목의 검색을 위해, 리스트로부터 “팝(pop)”함

비슷함

식당에 있는 아래에 스프링이 달려 있는 접시

문서 편집기에서 문자 버퍼

LIFO 자료구조

스택에 처음 푸시된 항목이 가장 오랫동안 기다림

스택으로부터 맨 처음 팝된 항목이 가장 최초에

(27)

[그림 9-17] 스택의 개념

(28)

스택(계속)

 스택의 사용 : 원시 코드의 처리

원시코드는 논리적으로 프로시져로 구성됨

스택을 사용해 프로시져 호출을 기억함

프로시져의 주소를 스택으로부터 팝함

 포인터 : 스택 포인터는 스택의 맨위(top)를 감시

 팝이나 푸시 연산의 적용 이전에 스택을 검사

 연결리스트와 배열처럼 스택은 논리적

구조로 조직화된 메모리 장소

(29)

[그림 9-18] 항목이 제거 될 때 스택 포인터가 감소한다.

(30)

 큐 : 다른 유형의 연결리스트

선입선출(FIFO) 저장시스템을 구현

삽입은 큐의 끝에서 이루어짐

삭제는 처음에서 이루어짐

기다리는 줄과 같음

 큐의 사용 : 프린터 예

인쇄되는 첫 항목은 가장 오랫동안 기다린 문서임

현재 항목이 큐로부터 삭제된 후 다음 항목이 인쇄됨

(31)

큐(계속)

 포인터

헤드 포인터는 큐의 시작을 유지함

테일 포인터는 큐의 끝을 유지함

 디큐 연산

큐로부터 항목(가장 오래된 엔트리)을 제거

헤드 포인터는 리스트내에 다음 항목을 가리키도록 변경됨

 인큐 연산

리스트의 끝에 항목이 놓여지며, 테일 포인터가 변경됨

(32)

[그림 9-19] 큐는 FIFO 구조를 사용한다.

(33)

[그림 9-21] 큐에 항목을 삽입

(34)

트리

 트리 : 조직도나 가계도와 유사한 계층 자료 구조

 트리내의 각 장소는 노드 또는 점검이라 함

 트리의 시작 노드는 루트라 함

 노드들 사이에는 부모-자식 관계가 있음

 자식이 없는 노드는 리프 노드라 함

 깊이(레벨) : 루트 노드로부터의 거리를 나타냄

 높이 : 최대 레벨 수

(35)
(36)

[그림 9-23] 트리의 노드들

(37)

트리(계속)

 이진 트리 : 트리의 한 유형

부모 노드는 0, 1 또는 2개의 자식 노드를 가질 수 있음

자식은 “왼쪽” 또는 “오른쪽” 위치로 구분됨

 이진 탐색 트리 : 이진 트리의 한 종류

왼쪽 자식 노드의 데이터 값 < 부모 노드의 값

오른쪽 자식 노드의 데이터 값 > 부모 노드의 값

 이진 탐색 트리는 유용한 탐색 구조임

(38)

[그림 9-24] 이진 트리의 레벨과 높이

(39)
(40)

이진 트리의 탐색

 이진 탐색 트리는 세 요소를 포함

 왼쪽 자식 포인터

 오른쪽 자식 포인터

 데이터

 루트 : 트리의 접근을 위한 초기 시작점

 선수요건 : 이진 탐색 트리가 적절히 정의

되어야 함

(41)

[그림 9-26] 이진 트리 노드

(42)

이진 트리의 탐색(계속)

탐색 루틴

루트 위치에서 시작

경로가 왼쪽 또는 오른쪽 자식으로 이동하는지 결정

데이터의 방향(왼쪽 또는 오른쪽)으로 이동

값이 발견되면 노드에서 정지하고 호출자에게 반환

값이 발견되지 않으면 자식 노드에 대해서 과정 반복

NULL 포인터를 가진 자식은 경로를 단절 시킴

경로가 형성될 수 있는 동안 탐색을 진행

결과 : 값이 발견되거나, 발견되지 않음

(43)
(44)
(45)

정렬 알고리즘

정렬 : 데이터 구성을 위한 자료 구조에 영향을 줌

정렬대상 데이터의 몇몇 예

사전내의 단어

디렉토리내의 화일

책의 색인

대학의 과목 안내서

알고리즘은 정렬을 위한 과정을 정의함

항상 최고인 정렬루틴은 없음

초점 : 선택 정렬과 버블 정렬

(46)

선택 정렬

 선택 정렬 : 수작업 정렬 과정을 흉내 냄

리스트에서 최소값을 찾음

첫 번째 위치에 있는 항목과 교환

두 번째 위치로 이동

줄어든 리스트(첫 번째 위치가 제외된)를 대상으로 과정 반복

마지막 항목의 바로 이전 항목까지 과정을 진행

 선택 정렬은 사용과 구현이 간단

선택 정렬은 큰 리스트에 비효율적

(47)

[그림 9-30] 선택 정렬

(48)

버블 정렬

버블 : 가장 오래된 정렬 방법 중 하나

리스트 내의 마지막 원소부터 시작

이 원소의 값을 바로 위 항목의 값과 비교

만일 더 작으면 위치를 변경하고 리스트의 위를 계속함

더 작은 항목이 발견될 때까지 비교를 계속함

더 작지 않으면 다음 항목을 그 위의 항목과 비교

가장 작은 값이 꼭대기로 올라갈 때까지 검사를 계속함

처음 항목이 제외된 리스트에 대해서 과정 반복

버블정렬은 구현이 단순

버블정렬은 큰 리스트에 비효율적

(49)

[그림 9-31] 버블 정렬

(50)

[그림 9-32] 버블 정렬(계속)

(51)

다른 유형의 정렬

다른 정렬 루틴

퀵 정렬, 합병 정렬, 삽입 정렬, 쉘 정렬

더 적은 비교로 데이터를 처리

선택 정렬, 버블 정렬보다 더욱 시간 효율적임

퀵 정렬

“분할 및 정복” 논리를 사용함

하나의 큰 리스트보다는 두 개의 작은 리스트를 정렬하는 것이 보다 쉬움

문제를 해결하기 위해 순환(자기 호출)을 사용

정렬된 모든 부분 리스트들은 하나의 정렬된 리스트로 통합됨

대량의 데이터 집합에 대해서 매우 빠르고 유용함

(52)

다른 유형의 정렬(계속)

합병 정렬 : 퀵 정렬과 유사

순환을 사용하여 데이터 집합을 계속해서 반으로 나눔

정렬된 반쪽들이 다시 하나의 리스트로 합병됨

시간 효율적이나 퀵 정렬만큼 공간 효율적이지 않음

삽입 정렬 : 수작업 카드 정렬을 흉내 냄

두 개의 리스트가 필요

복잡하지 않으나 크기 > 1000인 리스트에는 비효율적

쉘 정렬 : 증가하는 데이터에 대해서 삽입 정렬을

(53)

맺음말

 필수적인 기초 : 자료구조, 정렬 및 탐색 알고리즘

 공개적으로 사용 가능한 루틴을 잘 알고 있어야 함

 “이미 존재하는 것을 다시 개발”하느라 시간을 낭비 말 것

 정렬 루틴 구현 시 고려 요소

프로그래밍 코드의 복잡도

시간 및 공간 효율성

(54)

요약

 자료 구조는 데이터를 조직화

 기본 자료 구조 : 배열, 연결 리스트, 큐, 스택, 트리

 배열은 데이터를 연속적으로 저장

 배열은 1 또는 그 이상의 차원을 가질 수 있음

 연결 리스트는 데이터를 동적인

용기(구조)에 저장함

(55)

요약(계속)

 연결리스트는 불연속적인 저장을 위해 포인터를 사용

 포인터 : 변수의 데이터 타입이 메모리 주소임

 스택 : LIFO 용기(구조)로서 구조화된 연결 리스트

 큐 : FIFO 용기(구조)로서 구조화된 연결 리스트

 트리 : 노드로 구성된 계층 구조

(56)

요약(계속)

 이진 트리 : 노드는 기껏해야 두 자식을 가짐

 이진 탐색 트리 : 왼쪽 자식< 부모 < 오른쪽 자식

 정렬 알고리즘 : 구조 내에 데이터를 구성

 정렬루틴의 이름 : 선택 정렬, 버블 정렬, 퀵 정렬, 합병 정렬, 삽입 정렬, 쉘 정렬

 정렬 루틴은 코드, 공간, 시간 복잡도에 따라

분석됨

참조

관련 문서

❹ The great explosion of scientific creativity in Europe was certainly helped by the sudden spread of information brought about by Gutenberg’s use of

캐나다 몬트리올 콩코디아 대학교에서 물리 화학, 전자를 전공한 작가는 건축과 공연 예술의 교차점에 있는 인터랙티브 설치 작업을 주로 해오고 있다.. 그는 로봇

채워지지 않은 최외각 궤도를 가지고 있는 원자는 전자를 얻거나 버려서, 혹은 다른 원자와 전자를 공유함으로써 안정 된 전자 배위를 가지려고 한다...

천체투영관 시스템 구조 - 소프트웨어, SkyExplorer. 천체투영관 시스템 구조

다변량 자료 : 3가지 이상의 변수를 가지고 있는 자료로 측정대상으로부터 여러 개의 변수들을 측정하여 구하는 자료..

공명구조 (resonance contributor) → 가상의 구조 : 실제 구조와 근접한 편재화된 전자를 가진 구조.. 공명혼성구조(resonance hybrid)

• 경제구조가 서비스업 중심 으로 바뀐 후 대형이벤트의 개최, 프로구단 보유 등이 도시의 상징이 되는 추세. 타

@사출 속도가 증가할수록 수지의 유동 거리는 증가 성형의 각 조건과 유동 거리와의 관계.. 