박종혁교수 ( 컴퓨터공학과 ) jhpark1@seoultech.ac.kr http://www.parkjonghyuk.net 2017-2 학기
학습개요 7장데이터구성 1. 이름 2. 리스트 (List) 3. 그래프 4. 계층 조별과제 다음주강의시간발표 1
학습목표 적절하게이름짓는것의중요성을이해한다. 컴퓨터시스템의메모리안에어떻게데이터가구성하는지를이해한다. 리스트, 트리, 그래프가메모리에어떻게저장되는지를이해한다. 리스트, 트리, 그래프가가계도, 도로지도, 차트와같은우리에게익숙한개념들과어떤연관관계를가지는지를이해한다. 인덱싱 (indexing) 이메모리안의데이터를구성하는데어떻게사용되는지를이해한다. 연결 (linking) 이메모리안의데이터를구성하는데어떻게사용되는 2 지를이해한다
7.1 이름 아이템이이름을적절하게붙이는것은방대한양의아이템을다룰때 아이템의유용성을높인다. 부적절한아이템의이름은혼란을유도한다. 3 이름짓는가이드라인 유일해야한다. 둘이상의아이템이같은이름을가지면안된다. 하나의아이템이하나이상의이름을가져서는안된다. 이름은서술적이어야한다. 예 ) The Star Spangled Banner.mp3 (vs zqiy.mp 보다좋다 ) 항목 (item) 의위치와관련이있어야한다.
7.1 이름 (World Wide Web( 인터넷 ) 에서의이름 ) 비공식적으로웹주소 (web address) 또는공식적으로 URL (Uniform Resource Locator) 라고불림 웹주소의가이드라인 en.wikepedia.org/wiki/coral_snake 유일함 이름을하나만가지고있음 설명적임 (Coral snake 에대한웹페이지임을알수있음 ) 위치를알수있음. Wikipedia 서버에서 wiki 라는폴더 Coral_snake라는파일을나타냄. 4
7.2 리스트 많은자료들이리스트의형태로구성되어있다. 리스트 (List) 특정한순서로배치된일련의항목 예 ) 가장값비싼그림 5 개의리스트 1. 폴세잔의 The Card Player 2. 잭슨폴락의 No. 5, 1948 3. 윌렘드쿠닝의 Woman III 4. 구스타프크림트의 Portrait of Adele Bloch-Bauer I 5. 빈센트반고호의 Portrait of Dr. Gachet 5
7.1 리스트 ( 리스트의저장 ) 인덱싱 (indexing) 데이터의각아이템마다유일한번호를붙이는것 리스트의각아이템들은인덱스숫자에의해식별됨 대괄호 ([ ]) 를사용하여리스트의아이템을표현함 Paintings[0], Paintings[1], 컴퓨터안의모든데이터는메모리안의특정위치에저장됨 메모리위치는 0 부터시작 리스트는테이블처럼표시되지만 ( 왼쪽 ) 실제로는하드디스크안에서아래그림과같이저장됨. 6
7.2 리스트 ( 자료의저장단위 ) 워드 컴퓨터에저장되는가장작은단위 8비트, 32비트, 64비트등컴퓨터마다다르게사용됨 트랙 (track) 디스크를구성하는동심의원 디스크의트랙을따라가며저장된자료들을읽음 섹터 (sector) 트랙을구성하는단위 각섹터마다한워드크기의자료를저장함 7
7.2 리스트 ( 배열 ) 배열 메모리내의리스트를저장하기위한가장간단한저장방법 프로그램에서는왼쪽과같이저장되며, 하드디스크에서는오른쪽과같이저장된다. 8
7.2 리스트 ( 두배열을메모리에저장하기 ) 배열의위치는기준주소또는앵커라불림 배열이메모리에저장되어있는메모리상의위치 9
7.2 리스트 ( 배열을저장하기 ) 배열의아이템접근 기준주소 + 인덱스에의해아이템을접근 배열의장점 배열의어떤아이템도자시의리스트안의위치를알고있으면 쉽게접근가능 배열의단점 배열의크기고정 - 리스트내보의삽입과삭제를위한상당한수의연산을필요로함 10
7.2 리스트 ( 배열자료에접근하기 ) 배열의아이템접근 첫아이템 - Paintings[1] 호출 배열의 3 번째아이템접근 - Paintings[3] 호출 컴퓨터가리스트의 i 번째아이템주소계산방법 Paintings[i] = Paintings 의앵커주소 + (i - 1) 0 인덱싱 i 에 -1 을해줘야하므로연산이많아짐. 따라서배열의첫아이템은 0으로시작하게함. Paintings[0] 을호출하여배열의첫아이템을접근 Paintings[i] 의주소 = Paintings의앵커주소 + i 11
7.2 리스트 ( 배열자료삭제 ) 삭제하려는아이템을제거후, 그아이템다음에위치한모든아이템을하나씩옮김 삭제에시간이많이걸림 12
7.2 리스트 ( 배열자료삽입 ) 삽입하려는위치및그아래에있는모든아이템을옮긴후삽입 삽입에시간이많이걸림 13
7.2 리스트 ( 연결 ) 메모리안의데이터를연결하는것 메모리내의리스트를저장하는가장일반적방법 연결리스트 (linked list): 메모리안에흩어져있는데이터를사슬처럼연결하여리스트를구성하는자료구조 Geocache 시합 (geocaching 의변화된게임 ) 데이터를연결하는기본적인아이디어 geocaching 게임과유사 보물 + 다음 GPS 좌표 시작점 14
7.2 리스트 ( 연결리스트 ) 연결리스트 (linked list): 메모리안에흩어져있는데이터를사슬처럼연결하여리스트를구성하는자료구조 Paintings 연결리스트 자료내용 다음아이템연결주소 노드노드 Woman III The Card Player Portrait of Adele Bloch-Bauer I No 5, 1948 15 Portrait of Dr. Gachet
16 7.2 리스트 ( 연결리스트 )
7.2 리스트 ( 연결리스트의자료접근및삽입 ) 앵커와인덱스만으로직접접근이안됨 앵커에서출발인덱스숫자만큼다음아이템연결주소로이동해야함. 연결리스트자료삽입 1. 삽입할아이템에대한메모리공간확보 아이템데이터 + 아이템다음연결주소가쓰여지는공간 2. 새아이템의다음연결주소는삽입할위치앞의아이템이가지고있는연결 주소로해준다. 3. 삽입할위치앞의아이템의연결주소를새아이템의메모리주소로바꾸어 준다. 17
18 7.2 리스트 ( 연결리스트의자료삽입 )
7.2 리스트 ( 연결리스트의자료삭제 ) 연결리스트자료삭제 1. 삭제할아이템에대한메모리주소확보 2. 삭제할아이템바로앞의아이템메모리주소확보 3. 앞아이템의다음연결주소를삭제할아이템의연결메모리주소로 해준다. 19
7.3 그래프 실생활의많은객체들과개념들은그래프로모델링됨 정점들과정점을잇는간선들의집합 정점 (node): 항목, 간선 (edge): 두개의정점을이어주는관계 방향성그래프 (directed graph) 모든간선들이방향성을가진그래프 방향성을가진간선을아크 (arc) G = (V, E) // g는정점들의집합 V와아크들의집합 E로구성됨 20
7.3 그래프 ( 그래프예시 ) V = {A, B, C, D, E} E = {(A,E), (A,B), (B,A), (B,D), (C,E), (D,C), (E,B), (E,C), (E,D)} G = {{A, B, C, D, E}, {(A,E), (A,B), (B,A), (B,D), (C,E), (D,C), (E,B), (E,C), (E,D)}} 21
7.3 그래프 ( 그래프예시 ) 22 A: 시애틀, B: LA, E: 덴버, C: 시카고, D: 마이애미
23 7.3 그래프 ( 그래프예시 )
7.3 그래프 ( 그래프의중요성 ) 실제세계의대부분의상황들은객체와객체들간의관계로추상화할수있다. 소셜네트워킹 객체 사람, 관계 - 친구관계 지도 객체 지점, 관계 - 도로 수강신청 객체 교과목, 학생 관계 학생-교과목수강신청상황 실제문제를해결하기위한추상화과정에서그래프는유용하게사용된다. 객체 정점 관계 간선 24
7.3 그래프 ( 그래프의용어와특성 ) 그림 7.13 그래프 G 인접성 (Adjacency) 두정점사이에간선이있을때두정점은인접해있다고말한다. 예 ) 아크 (D, C) 가 G 에있다면정점 D 는 C 에인접한다아크 (C,D) 는 G 에없기때문에정점 C 는 D 에인접해있지않다 루프 (Loop) 간선의시작정점과도착정점이일치할때간선은루프를구성한다. 입력차수 (In-degree) 정점 v 를도착정점으로하는간선의수를 v 의입력차수라고한다. 정점 E 의입력차수 2: E 를두번째정점으로하는아크 (A,E), (C,E) 출력차수 (Out-degree) 정점 v 를시작정점으로하는간선의수를 v 의출력차수라고한다. 정점 E 의출력차수 3: E 가처음정점인아크 (E, B), (E, C), (E,D) 25
7.3 그래프 ( 그래프의용어와특성 ) 26 그림 7.13 그래프 G 위수 (Order) 그래프정점들의갯수 ( 예제 위수 : 5) 크기 (Size) 그래프아크들의개수 ( 예제 크기 : 9) 경로 (Path) 그래프내에서아크로이어지는정점들의집합 예 ) [A, E, C] 는경로, [A, B, E] 경로아님 경로길이 (Path length) 경로에있는아크의숫자 예 ) [A, E, C] 경로길이 : 2 사이클 (Cycle) 길이가 0 보다크며처음과마지막정점이일치하는경로 비순환적그래프 : 사이클이없는그래프 예 ) [A, B, A] 는사이클그래프 G 는비순환적이아님
7.3 그래프 ( 저장 ) 메모리에앵커, 출력차수, 인접한정점들의메모리주소를표시함 메모리 14 에저장된정점 E 참고 27
7.4 계층 요소들이레벨별로배치되도록하는방법 각구성원은바로밑에다수의구성원을가질수있으나위에는하나의 구성원만을가지도록제한됨. 많은컴퓨터상의개념들은구성원들을계층화함에의해생성됨 여러실제자료들이계층화되어컴퓨터에저장됨 예 조직차트, 가계도, 생물학, 언어학, 트리 28
7.4 계층 ( 조직차트 ) 조직차트 - 조직의구조를나타내는다이어그램 조직원의관계및보고체계를보여줌 29
7.4 계층 ( 가계도 ) 가계도 조상과후손들사이의유전적인관계를나타내는그림 30
7.4 계층 ( 생물학 ) 분류법 (taxonomy) 31
7.4 계층 ( 언어학 ) 구문해석트리 언어문법을모델링하고언어요소들의의미를명확하게문법을표현해 주는도구 32
7.4 계층 ( 트리 ) 계층데이터를모델링하기위한그래프의한형태 트리의특성 그래프의입력차수가 0인정점이정확히하나 ( 루트라고불림 ) 그래프의루트가아닌모든정점은입력차수가 1 루트에서다른정점들모두에게도달하는경로가있음 말단정점 트리에서의출력차수 0 의정점 33
7.4 계층 ( 트리 ) 트리의루트 입력차수가 0 인정점 오른쪽그림의정점 R 말단정점 출력차수가 0 인정점 오른쪽그림의정점 T, E, C, A 34
조별과제 7 장 데이터구성 발표방식 : ppt 자료활용 2 개조각각 10 분발표 ( 질의응답포함 ) 문제 1 o 우리가생활하면서모든것은자신의생활패턴에대해정리되어있으며, 자신만이식별가능하다. 예를들어난장판이되어있는방을정리하려할때방주인이 이게난장판인것같이보여도나에겐나만의흐름으로정리되어있는거야 ' 이러한말을하는것을볼수있다. 여기서방주인은자신의흐름즉, 이름, 모양, 색등을기준점으로정리할것이다. 이와같이정리된흐름이라는것을하나의데이터라고하며, 이러한데이터를나열하는데사용하는방법으로리스트, 트리, 그래프등다양한방법이있다. 위에제시한데이터나열법에대해실생활에서사용되는예시를하나이상씩조사하고추후적용되어질수있는분야에대해생각해보아라. 문제 2 o 보통우리가사용하는컴퓨터는셀수없을정도의데이터를처리한다. 이러한데이터를구별하기위해가장많이사용되고있는방식이트리구조를이용하는방식이다. 트리구조에대한데이터처리방식의예를들고, 트리구조의장단점이무엇인지설명하여라. 35