Week 1
이번부터는 데이터구조 강의를 시작한다.
우선 Array & Linked List chapter부터 시작하며 Array의 정의부터 등장한다. Array란 위에서 정의한 바와 같이 같은 사이즈의 요소로 이루어져있으며 인덱스가 순차적 정수로 결정된 연속적인 메모리 공간을 말한다.
Array에 각 요소에 접근하기 위해서는 주소를 알아햐 하는데 이때 위와 같은 수식으로 간단히 계산이 가능하다.
마침 퀴즈가 등장해 적용해보자면 array_addr = 1000, elem_size = 8, i = 6, first_index = 0이므로 1000 + 8 * ( 6 - 0 ) = 1048이 6번째 인덱스의 주소값이다.
1차원을 벗어다 2차원 및 다차원으로 가게되면 주소는 위와 같이 확장된다.
array_addr + elem_size * ((row_index - initial_row_index) * units_per_row + (column_index - initial_column_index))
또한 Array에 다차원으로 저장이 될 때 행우선(Row-major)인지 열우선(column-major)인지에 따라 저장 순서가 달라진다.
3차원 배열에서 열우선일 때의 다음 메모리의 요소를 묻는 퀴즈인데 열은 고정인 상태이므로 최초행이 변동이 된 (2, 1, 1)이 되겠다.
메모리 상에 데이터를 배치할 때 몇번의 과정을 거치는지 정리한 표인데 배열의 시작점에 값을 입력해야한다면 데이터가 차지하고 있는 만큼(n) 순서를 거처야하고 제거할 때에도 마찬가지이다. 이에 반해 끝부분에 입력할때나 삭제할 시는 간단하게 한번에 끝낼 수 있다.
요약된 내용이며 다음은 Linked List로 넘어간다.
연속된 배열이 아닌 포인터로 연결된 리스트는 위와 같은 구조를 가진다. 각 노드는 키와 다음 포인터로 구성이 되어 있으며 다음 값이 존재하는 곳을 가리킨다.
리스트에 관련된 API 목록이며,
간단한 퀴즈를 통해 이해해 볼 수 있었다.
1. PushBack을 통해 a를 입력하고 [a]
2. PushFront로 b를 앞에 입력 [b][a]
3. PushBack으로 뒤쪽에 d를 입력 [b][a][d]
4. PushFront로 c를 앞쪽에 입력 [c][b][a][d]
5. PopBack으로 뒤쪽의 값을 제거 [c][b][a]
PushFront의 원리는 위와 같은 리스트가 존재할 때 26이라는 값을 삽입하기 위해서는,
26의 다음 포인터가 7을 먼저 가리키고,
다음에 head가 26을 가리키면 완료된다. 따라서 배열에서 n번의 순서를 거친데 비해 리스트에서는 1번에 가능한 것을 확인할 수 있다.
PopFront 함수 또한 마찬가지로 head가 다시 7을 가리키고 26의 연결을 끊으면 완료된다.
PushBack은 리스트가 포인터로 이루어져 있기 때문에 리스트의 끝까지 찾아가서 null(nil)에 도달해야 한다는 특징이 있다. 따라서 13까지 도달하여 다음 포인터값이 nil인 것을 확인 후 포인터에 다음값의 주소를 넣어주면 완료된다. 따라서 n번의 순차적인 과정을 거쳐야 한다.
PopBack도 마찬가지로 리스트의 nil값을 가진 키직전까지 이동 후 직전값의 포인터를 nil로 변경한다.
이번에는 head가 리스트의 초기키를 알려주는 지표라면 종료키를 알려주는 tail이 존재할 때 상황이다. PushBack의 경우 tail이 13을 가리키고 있다가,
13의 다음포인터 주소값이 nil에서 8의 주소를 가진다음,
tail이 새로운 nil값을 향해 주소가 바뀐다. 물론 1번만에 바꿀 수 있으므로 Order(1)이 된다.
PopBack도 단순하다. 13의 다음포인터를 nil값으로 변환 후 tail이 13을 가리킨 뒤 8을 삭제하면 끝이다.
위에서 언급한 순서를 알고리즘화 한 PushFront의 logic이다
PopFront의 logic
PushBack의 logic
PopBack의 logic
간단한 퀴즈가 나왔는데 약간 당황했던 것이 p.next.next였다. 단순히 리스트의 기준점에서 다음다음번이 무었인지를 묻는건데. 노드의 시작점이 a이므로 a.next.next = c일 것이고 c는 다음포인터에 nil값을 가지지 않으므로 p는 b가 되고 한번 더 연산. b.next.next = d이며 이 키는 마지막이기에 nil값을 가진다. 고로 while문은 2회 반복되고 끝난다.
AddAfter라는 함수도 소개하는데 중간에 어떻게 끼워넣는지 보여주는 logic이다.
배열과 마찬가지로 각 함수들이 몇번의 순서를 거쳐야 해당 함수의 역할이 종료되는지 정리된 표이다.
이번에는 항상 다음으로만 진행이 가능하고 역순은 불가능했던 Single Linked List와 달리 역순까지 가능한 Doubly Linked List이다. 이 노드에서는 다음포인터값뿐만 아니라 이전포인터값까지 가지게 된다. 그리고 항상 tail을 가지게 된다.
PopBack을 통해 13을 제거하는 모습이다. tail이 있는 single linked list와 마찬가지로 먼저 13의 이전값인 4를 가리키고 4의 다음포인터값을 nil로 변환 후 13을 삭제하는 순이다.
PushBack의 logic이며 위에서 본 PopBack의 역순으로 진행된다.
PopBack의 logic
AddAfter의 logic이며 10을 7 다음으로 삽입할 때 10의 다음주소값과 이전값이 각각 4와 7의 주소값으로 변경이 되고 이전에 연결되었던 포인터들이 사라진다.
AddBefore도 마찬가지로 진행된다.
Doubly linked list의 Order 표이다.
이번에는 Stack & Queues에 대해 살펴보는데 먼저 Stack에 대해 알아본다.
먼저 스택이란 추상적인 데이터 타입이며 Push, Top, Pop, Empty와 같은 연산자를 활용하게 된다.
Balanced Bracket이라는 개념이 등장하는 데 이는,
위와 같이 제대로 짝을 이루고 있다면 Balanced, 짝이 맞지 않는다면 Unbalanced인 상태라고 볼 수 있다.
이를 확인하는 함수는 IsBalanced이며 위와 같은 로직을 가진다.
간단한 퀴즈를 통해 이해하는데 스택에서 위와 같은 unbalanced string이 존재한다면 스택은 짝이 맞는 ()뒤 (의 짝을 찾기 위해 계속 진행하지만 결국 []이후에도 )는 없으므로 루프가 종료될 때까지 남게되는 것은 (이다.
배열을 통한 스택을 이해하게 되면 현재 Top은 b인 상태이고 이후 값이 입력되면 Top은 최후에 입력된 값으로 변경이 된다.
Pop을 통해 마지막으로 입력된 c를 제거할 수 있으며,
Push를 통해 키들을 입력할 수 있다.
배열이 꽉 찬 상태에서는 Push를 통해 키를 입력하려해도 당연히 에러가 발생하면
Empty또한 False로 반환이 될 것이다.
Pop을 통해 값들을 제거해나가고,
결국 요소가 모두 없다면 이 때의 Empty는 True를 반환하게 된다.
Linked List에서 스택 또한 비슷한 경향을 볼 수 있는데, Push를 통해 키를 추가하고 Top을 통해 마지막으로 입력된 함수를 반환 받을 수 있다.
그리고 배열과 달리 계속해서 추가해나갈 수 있다.
Stack의 Summary 스택에서의 Order은 모두 1번인 것을 알 수 있다. 그리고 LIFO(Last In First Out) queues라고 표기된 것처럼 마지막에 입력된 것부터 순차적으로 빠지게 되는 구조이다.
이번에는 Queue의 정의이며 마찬가지로 추상적인 데이터 타입인데 Enqueue, Dequeue, Empty와 같은 기능을 활용하며 스택과 달리 FIFO(First In First Out)의 구조이다.
List에서 a, b, c를 Enqueue를 통해 순차적으로 입력하고,
Dequeue를 사용하면 a부터 빠지는 것을 알 수 있다.
다시 Enqueue를 통해 키들을 연결하고,
Dequeue를 통해 입력한 순서대로 모두 삭제하면,
Empty는 True로 반환된다.
위의 기능들은 다음과 같은 함수명으로 활용이 된다.
이번엔 배열에서의 Queue의 동작이다. a, b, c 키값들을 순차적으로 Enque한 뒤 Deque를 하면 a부터 사라진다. 이 때 head와 tail처럼 read와 write의 값이 변하게 된다. read는 가장 먼저 들어온 값이며 write는 입력이 될 장소를 의미한다.
dequeue를 통해 b도 없애주면 위와 같이 c만 남고
다시 Enqueue를 통해 d, e, f를 입력하는데 재밌는 점이 배열의 끝까지 간 뒤에 Enqueue를 진행하면 빈 자리로 키를 채우는 것을 알 수 있다.
하지만 한개의 자리만 빈 상태에서 Enqueue를 진행하려면 에러가 발생하고 이는 Queue의 특성상 배열이 어느곳이 처음인지 구분하기 위해 비워두도록 한다고 설명한다.
모든 값들을 삭제하고 read와 write가 같아진 시점에서 Empty는 True를 반환한다.
다음은 Tree에 관한 설명이다. Tree구조는 위와 같이 문장을 구성성분(품사별)로 구분짓는다면 I는 주어(S)이자 명사(NP), ate은 동사(VP), the는 명사구(NP)에서 정관사(Det)로 분류가 가능하다.
수식에서도 위와 같은 식을 트리구조로 변환이 가능하며,
각 국가별 지역 또한 트리구조화 시킬 수 있다.
코드에 대해 트리구조로 변환도 가능한 것을 알 수 있다.
이번에는 2분 탐색 트리형에 대해 살펴보는데 이전의 Introduction강의에서 David가 전화번호부 예시를 들은 것과 일치한다.
Tree의 정의로는 empty이거나 node인데 key와 child tree로 이루어진다.
Empty tree의 경우 당연히 없는 것이며 one node만 있을 때와 two node일 때 위와 같이 구조가 증가하는 것을 볼 수 있다.
용어에 대해 하나씩 살펴보자면
Node는 key, children(, parent)를 가지고 있다.
또한 이번에 보는 2분 탐색 트리에서는 children을 left와 right로 나눠 칭한다고 한다.
Height이라는 개념이 등장하는데 이에 대한 logic이고 트리구조에서 가장 깊이 내려 갔을 경우의 높이를 의미한다.
이번에는 트리구조를 탐색할 때를 Walking a Tree라고 표현하며 이때 탐색법 2개를 소개한다.
Depth-first는 순차적으로 깊이 파고드는 방법이며, 그중 InOrderTraversal는
위와 같이 Les의 하위 Cathy의 하위 Alex까지 도달 후 출력하고 다시 Cathy로 돌아와 출력, 다시 Frank로 내려가 출력, 그 후 Les까지 올라와서 출력, 이후 Sam으로 내려가는 방식이다.
PreOrderTraversal은,
접근한 순서대로 Les, Cathy, Alex, Frank, Sam,... 출력하는 형식이다.
PostOrderTraversal의 경우,
먼저 children부터 출력하고 이후 Parent를 출력하는 방식이다.
Breadth-first 기법은,
LevelTraversal 방법을 사용하며 Queue에 대기열을 생성 후 Parent에 대한 Children을 먼저 출력 후 하위 노드로 접근한다. (세대별로)
Tree의 Summary이며 DFS(Depth-First Search)와 BFS(Breadth-First Search)에 대해 자세히 살펴보았다.
이번부터는 데이터구조 강의를 시작한다.
우선 Array & Linked List chapter부터 시작하며 Array의 정의부터 등장한다. Array란 위에서 정의한 바와 같이 같은 사이즈의 요소로 이루어져있으며 인덱스가 순차적 정수로 결정된 연속적인 메모리 공간을 말한다.
Array에 각 요소에 접근하기 위해서는 주소를 알아햐 하는데 이때 위와 같은 수식으로 간단히 계산이 가능하다.
마침 퀴즈가 등장해 적용해보자면 array_addr = 1000, elem_size = 8, i = 6, first_index = 0이므로 1000 + 8 * ( 6 - 0 ) = 1048이 6번째 인덱스의 주소값이다.
1차원을 벗어다 2차원 및 다차원으로 가게되면 주소는 위와 같이 확장된다.
array_addr + elem_size * ((row_index - initial_row_index) * units_per_row + (column_index - initial_column_index))
또한 Array에 다차원으로 저장이 될 때 행우선(Row-major)인지 열우선(column-major)인지에 따라 저장 순서가 달라진다.
3차원 배열에서 열우선일 때의 다음 메모리의 요소를 묻는 퀴즈인데 열은 고정인 상태이므로 최초행이 변동이 된 (2, 1, 1)이 되겠다.
메모리 상에 데이터를 배치할 때 몇번의 과정을 거치는지 정리한 표인데 배열의 시작점에 값을 입력해야한다면 데이터가 차지하고 있는 만큼(n) 순서를 거처야하고 제거할 때에도 마찬가지이다. 이에 반해 끝부분에 입력할때나 삭제할 시는 간단하게 한번에 끝낼 수 있다.
요약된 내용이며 다음은 Linked List로 넘어간다.
연속된 배열이 아닌 포인터로 연결된 리스트는 위와 같은 구조를 가진다. 각 노드는 키와 다음 포인터로 구성이 되어 있으며 다음 값이 존재하는 곳을 가리킨다.
리스트에 관련된 API 목록이며,
간단한 퀴즈를 통해 이해해 볼 수 있었다.
1. PushBack을 통해 a를 입력하고 [a]
2. PushFront로 b를 앞에 입력 [b][a]
3. PushBack으로 뒤쪽에 d를 입력 [b][a][d]
4. PushFront로 c를 앞쪽에 입력 [c][b][a][d]
5. PopBack으로 뒤쪽의 값을 제거 [c][b][a]
PushFront의 원리는 위와 같은 리스트가 존재할 때 26이라는 값을 삽입하기 위해서는,
26의 다음 포인터가 7을 먼저 가리키고,
다음에 head가 26을 가리키면 완료된다. 따라서 배열에서 n번의 순서를 거친데 비해 리스트에서는 1번에 가능한 것을 확인할 수 있다.
PopFront 함수 또한 마찬가지로 head가 다시 7을 가리키고 26의 연결을 끊으면 완료된다.
PushBack은 리스트가 포인터로 이루어져 있기 때문에 리스트의 끝까지 찾아가서 null(nil)에 도달해야 한다는 특징이 있다. 따라서 13까지 도달하여 다음 포인터값이 nil인 것을 확인 후 포인터에 다음값의 주소를 넣어주면 완료된다. 따라서 n번의 순차적인 과정을 거쳐야 한다.
PopBack도 마찬가지로 리스트의 nil값을 가진 키직전까지 이동 후 직전값의 포인터를 nil로 변경한다.
이번에는 head가 리스트의 초기키를 알려주는 지표라면 종료키를 알려주는 tail이 존재할 때 상황이다. PushBack의 경우 tail이 13을 가리키고 있다가,
13의 다음포인터 주소값이 nil에서 8의 주소를 가진다음,
tail이 새로운 nil값을 향해 주소가 바뀐다. 물론 1번만에 바꿀 수 있으므로 Order(1)이 된다.
PopBack도 단순하다. 13의 다음포인터를 nil값으로 변환 후 tail이 13을 가리킨 뒤 8을 삭제하면 끝이다.
위에서 언급한 순서를 알고리즘화 한 PushFront의 logic이다
PopFront의 logic
PushBack의 logic
PopBack의 logic
간단한 퀴즈가 나왔는데 약간 당황했던 것이 p.next.next였다. 단순히 리스트의 기준점에서 다음다음번이 무었인지를 묻는건데. 노드의 시작점이 a이므로 a.next.next = c일 것이고 c는 다음포인터에 nil값을 가지지 않으므로 p는 b가 되고 한번 더 연산. b.next.next = d이며 이 키는 마지막이기에 nil값을 가진다. 고로 while문은 2회 반복되고 끝난다.
AddAfter라는 함수도 소개하는데 중간에 어떻게 끼워넣는지 보여주는 logic이다.
배열과 마찬가지로 각 함수들이 몇번의 순서를 거쳐야 해당 함수의 역할이 종료되는지 정리된 표이다.
이번에는 항상 다음으로만 진행이 가능하고 역순은 불가능했던 Single Linked List와 달리 역순까지 가능한 Doubly Linked List이다. 이 노드에서는 다음포인터값뿐만 아니라 이전포인터값까지 가지게 된다. 그리고 항상 tail을 가지게 된다.
PopBack을 통해 13을 제거하는 모습이다. tail이 있는 single linked list와 마찬가지로 먼저 13의 이전값인 4를 가리키고 4의 다음포인터값을 nil로 변환 후 13을 삭제하는 순이다.
PushBack의 logic이며 위에서 본 PopBack의 역순으로 진행된다.
PopBack의 logic
AddAfter의 logic이며 10을 7 다음으로 삽입할 때 10의 다음주소값과 이전값이 각각 4와 7의 주소값으로 변경이 되고 이전에 연결되었던 포인터들이 사라진다.
AddBefore도 마찬가지로 진행된다.
Doubly linked list의 Order 표이다.
List의 Summary
이번에는 Stack & Queues에 대해 살펴보는데 먼저 Stack에 대해 알아본다.
먼저 스택이란 추상적인 데이터 타입이며 Push, Top, Pop, Empty와 같은 연산자를 활용하게 된다.
Balanced Bracket이라는 개념이 등장하는 데 이는,
위와 같이 제대로 짝을 이루고 있다면 Balanced, 짝이 맞지 않는다면 Unbalanced인 상태라고 볼 수 있다.
이를 확인하는 함수는 IsBalanced이며 위와 같은 로직을 가진다.
간단한 퀴즈를 통해 이해하는데 스택에서 위와 같은 unbalanced string이 존재한다면 스택은 짝이 맞는 ()뒤 (의 짝을 찾기 위해 계속 진행하지만 결국 []이후에도 )는 없으므로 루프가 종료될 때까지 남게되는 것은 (이다.
배열을 통한 스택을 이해하게 되면 현재 Top은 b인 상태이고 이후 값이 입력되면 Top은 최후에 입력된 값으로 변경이 된다.
Pop을 통해 마지막으로 입력된 c를 제거할 수 있으며,
Push를 통해 키들을 입력할 수 있다.
배열이 꽉 찬 상태에서는 Push를 통해 키를 입력하려해도 당연히 에러가 발생하면
Empty또한 False로 반환이 될 것이다.
Pop을 통해 값들을 제거해나가고,
Linked List에서 스택 또한 비슷한 경향을 볼 수 있는데, Push를 통해 키를 추가하고 Top을 통해 마지막으로 입력된 함수를 반환 받을 수 있다.
그리고 배열과 달리 계속해서 추가해나갈 수 있다.
Stack의 Summary 스택에서의 Order은 모두 1번인 것을 알 수 있다. 그리고 LIFO(Last In First Out) queues라고 표기된 것처럼 마지막에 입력된 것부터 순차적으로 빠지게 되는 구조이다.
이번에는 Queue의 정의이며 마찬가지로 추상적인 데이터 타입인데 Enqueue, Dequeue, Empty와 같은 기능을 활용하며 스택과 달리 FIFO(First In First Out)의 구조이다.
List에서 a, b, c를 Enqueue를 통해 순차적으로 입력하고,
Dequeue를 사용하면 a부터 빠지는 것을 알 수 있다.
다시 Enqueue를 통해 키들을 연결하고,
Dequeue를 통해 입력한 순서대로 모두 삭제하면,
Empty는 True로 반환된다.
위의 기능들은 다음과 같은 함수명으로 활용이 된다.
이번엔 배열에서의 Queue의 동작이다. a, b, c 키값들을 순차적으로 Enque한 뒤 Deque를 하면 a부터 사라진다. 이 때 head와 tail처럼 read와 write의 값이 변하게 된다. read는 가장 먼저 들어온 값이며 write는 입력이 될 장소를 의미한다.
dequeue를 통해 b도 없애주면 위와 같이 c만 남고
하지만 한개의 자리만 빈 상태에서 Enqueue를 진행하려면 에러가 발생하고 이는 Queue의 특성상 배열이 어느곳이 처음인지 구분하기 위해 비워두도록 한다고 설명한다.
모든 값들을 삭제하고 read와 write가 같아진 시점에서 Empty는 True를 반환한다.
Queue에 대한 Summary이며 Stack과 마찬가지로 모든 기능은 Order(1)으로 1번만에 결과를 낼 수 있다.
다음은 Tree에 관한 설명이다. Tree구조는 위와 같이 문장을 구성성분(품사별)로 구분짓는다면 I는 주어(S)이자 명사(NP), ate은 동사(VP), the는 명사구(NP)에서 정관사(Det)로 분류가 가능하다.
수식에서도 위와 같은 식을 트리구조로 변환이 가능하며,
각 국가별 지역 또한 트리구조화 시킬 수 있다.
코드에 대해 트리구조로 변환도 가능한 것을 알 수 있다.
이번에는 2분 탐색 트리형에 대해 살펴보는데 이전의 Introduction강의에서 David가 전화번호부 예시를 들은 것과 일치한다.
Tree의 정의로는 empty이거나 node인데 key와 child tree로 이루어진다.
Empty tree의 경우 당연히 없는 것이며 one node만 있을 때와 two node일 때 위와 같이 구조가 증가하는 것을 볼 수 있다.
용어에 대해 하나씩 살펴보자면
- Root : 트리의 가장 상위 키(Fred)
- Child : 바로 상위에 있는 키의 하위 키들 (ex. Sam is child of Kate)
- Parent : Child의 반대 개념 (ex. Kate is parent of Sam)
- Ancestor : 하위 트리의 관점에서 상위 키들 (ex. Fred is ancestor of Hugh)
- Descendant : Ancestor의 반대 개념 (ex. Sally is Descendant of Fred)
- Sibling : 두개의 노드가 같은 Parent를 공유할 때 (ex. Kate and Jim is sibling)
- Leaf : Children이 없는 노드 (ex. Jim)
- Interior node : non-leaf (ex. Kate)
- Level : Root와 노드 간의 숫자(세대차)
- Forest : Tree구조가 독립적으로 여러개 있을 경우
Node는 key, children(, parent)를 가지고 있다.
또한 이번에 보는 2분 탐색 트리에서는 children을 left와 right로 나눠 칭한다고 한다.
Height이라는 개념이 등장하는데 이에 대한 logic이고 트리구조에서 가장 깊이 내려 갔을 경우의 높이를 의미한다.
이번에는 트리구조를 탐색할 때를 Walking a Tree라고 표현하며 이때 탐색법 2개를 소개한다.
Depth-first는 순차적으로 깊이 파고드는 방법이며, 그중 InOrderTraversal는
위와 같이 Les의 하위 Cathy의 하위 Alex까지 도달 후 출력하고 다시 Cathy로 돌아와 출력, 다시 Frank로 내려가 출력, 그 후 Les까지 올라와서 출력, 이후 Sam으로 내려가는 방식이다.
PreOrderTraversal은,
접근한 순서대로 Les, Cathy, Alex, Frank, Sam,... 출력하는 형식이다.
PostOrderTraversal의 경우,
먼저 children부터 출력하고 이후 Parent를 출력하는 방식이다.
Breadth-first 기법은,
LevelTraversal 방법을 사용하며 Queue에 대기열을 생성 후 Parent에 대한 Children을 먼저 출력 후 하위 노드로 접근한다. (세대별로)
Tree의 Summary이며 DFS(Depth-First Search)와 BFS(Breadth-First Search)에 대해 자세히 살펴보았다.
댓글
댓글 쓰기