EDWARD

1.1 트리 용어 정리 트리는 그래프 일종이므로 그래프에서 사용하는 용어를 대부분 적용할 수 있습니다. 다만 그래프에서 정점이라고 하는 것을 트리에서는 노드라고 합니다. root는 노드 1입니다. 노드 2와 노드 3은 노드 1의 자식(child)입니다. 노드 1은 노드 2와 노드 3의 부모(parent)입니다. 노드 1은 노드 4, 노드 5, 노드 6, 노드 7, 노드 8의 조상(ancestor)입니다. 노드 4, 노드 5, 노드 6, 노드 7, 노드 8은 노드 1의 자손(descendant)입니다. 그래프 용어에서 차수(degree)를 배운 적이 있습니다. 트리에도 차수 개념이 있는데, 트리에서는 좀 더 특정 지어서 차수란 ‘어떤 노드의 자식 노드 개수’를 의미합니다. 트리의 차수(degree of a..

그래프는 로봇이 최단 경로를 계산해서 움직일 때나 내비게이션에서 경로를 안내할 때, 지하철역을 어디에 건설해야 가장 효율적인지 계산하는 등 매우 폭넓게 사용됩니다. 게다가 최근에 가장 중요한 이슈인 머신 러닝도 그래프를 활용합니다. 이 장에서는 그래프에 대한 이론적인 내용과 실제로 구현할 때 표현(representation), 모든 정점을 방문하는 방법인 순회(traversal) 등 그래프의 기본 내용을 다루어 보겠습니다. 1.1 그래프 용어 정리 자료구조 - 그래프 정의 그래프(graph)는 연결된 객체들 사이의 관계를 표현할 수 있는 자료구조이다. 지하철 노선도나 전기회로 같이 다양한 객체들이 서로 복잡하게 연결되어 있는 구조를 표현할 수 있는 논리적 edwardmoon.tistory.com self..

1.1 스택 스택(stack)은 접시 쌓기를 떠올리면 됩니다. 데이터가 들어오면 차곡차곡 쌓이고 나갈 때는 맨 위에 있는 데이터부터 나갑니다. 즉, 맨 마지막에 들어온 데이터가 맨 처음 나가게 되지요. 이를 LIFO(Last In First Out)라고 합니다. 스택의 ADT를 정의한 후 어떻게 객체를 표현하고 연산을 구현할지 고민해 보겠습니다. Stack - Object : LIFO 객체 - Operation 1. empty( ) -> Boolean: 스택이 비어 있으면 TRUE, 아니면 FALSE 반환 2. push(data): data를 스택의 맨 위에 삽입 3. pop( ) -> element: 스택의 맨 위에 있는 데이터를 삭제하며 반환 4. peek( ) -> element: 스택의 맨 위에 ..

1. 연결리스트 동적 배열은 탐색 기능이 막강하며 배열 마지막에서 삽입 및 삭제 연산 속도가 빨라 프로그램을 처음 작성할 때 가장 먼저 사용을 고려하는 자료 구조입니다. 하지만 데이터를 배열 중간에 삽입하거나 삭제해야 할 때는 원소들을 옮겨야 하는 부담이 있지요. O(n) 정도면 성능이 훌륭하지 않나 하고 생각할 수도 있습니다. 그래도 중간에 삽입과 삭제가 자주 일어나는 상황에서 좀 더 나은 삽입 및 삭제 연산을 제공하는 자료 구조가 있다면 배열보다 그것을 선택하는 것이 나을 수 있습니다. 연결 리스트(linked list)는 이런 고민에서 만들어진 자료 구조입니다. 연결 리스트는 그 자체만으로는 동적 배열에 비해 쓰임새가 적은 편입니다. 삽입과 삭제가 빈번한 경우에 사용을 고민해 볼 수 있겠지요. 연결..

1. 동적 배열 초기 배열은 같은 데이터 타입을 가진 변수 집합이었습니다. 아직도 많은 언어에서 배열은 같은 타입 변수들을 저장합니다. 하지만 C 언어를 제외한 거의 대부분의 언어가 초기 형태의 배열이 아닌 동적 배열을 지원합니다. 동적 배열은 기존 배열이 가지는 장점은 유지하면서 여러 단점은 보완한 형태로 구현되었습니다. 메모리에 데이터를 저장하는 영역은 세 군데인데, 그중 스택과 힙 영역이 있습니다. 스택은 실제 스택 프레임(파이썬의 스택 프레임과 개념은 같지만 실제 할당되는 공간은 다름)이 쌓이는 메모리 공간이고, 힙은 변수의 생성 시기와 소멸 시기를 프로그래머가 결정할 수 있는 메모리가 동적으로 할당되는 영역입니다. 동적 배열 개념을 이해하려면 스택과 힙 차이를 알아야 합니다. 스택 프레임을 할당..

1. 재귀함수 재귀(recursion) 함수란 호출된 함수가 자기 자신을 다시 호출하는 풀이 방식입니다.실제 개발할 때 재귀 함수를 보기란 쉽지 않습니다. 하지만 커다란 문제를 쪼개 부분 문제로 만들어 해결함으로써 전체 문제를 풀어 나가는 구조를 설계할 때는 반드시 필요하기에 자료 구조나 알고리즘에서는 알아야 하는 필수 개념입니다. 스택 프레임과 지역 변수의 역할을 알고 나면 쉽게 이해할 수 있습니다. 1.1 재귀 함수로 팩토리얼 구현하기 n의 팩토리얼은 1부터 n까지 곱을 의미하고 n!라고 표기합니다. 4!은 1×2×3×4을 의미합니다. 4! = 3!×4과 같이 풀어 쓸 수도 있습니다. 일반화하면 n! = (n-1)!×n def factorial(n): return factorial(n-1) * n #..

정의 그래프(graph)는 연결된 객체들 사이의 관계를 표현할 수 있는 자료구조이다. 지하철 노선도나 전기회로 같이 다양한 객체들이 서로 복잡하게 연결되어 있는 구조를 표현할 수 있는 논리적 도구이다. (선형 자료구조, 트리도 그래프로 표현할 수 있다.) 그래프는 정점과 간선의 집합으로 구성되는데, 정점은 노드(node), 간선은 링크(link)라고 한다. 수학적으로 그래프는 G = (V, E)와 같이 표시하는데, V(G)는 정점들의 집합, E(G)는 간선들의 집합을 의미한다. 정점은 객체(object)를 의미하고, 간선은 이러한 객체들 간의 관계를 의미하는데, 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. 시각적인 형태가 그래프의 정의는 아니다. 아래의 두 그래프는 ..

이진 트리 : 노드가 left child와 right child만을 갖는 트리를 이진트리(binay tree)라고 한다. 이때 두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 상관없다. 이진 트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다. 예를 들어 노드 B의 left child는 D이고, right child는 E이다. 또 왼쪽 자식을 루트로 하는 서브 트리를 왼쪽 서브트리(left subtree), 오른쪽 자식을 루트로 하는 서브트리를 오른쪽 서브 트리라고 한다. 완전 이진 트리 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리를 완전 이진 트리(complete binary tree)라고 한다. 노드를 채우는 ..

트리의 구조와 관련 용어 트리는 아래의 사진과 같이 노드(node)와 가지(edge)로 구성된다. 각 노드는 가지를 통해 다른 노드와 연결된다. 루트 : 트리의 가장 위쪽에 있는 노드를 루트라고 한다. 루트는 트리 하나에 1개만 존재한다. 리프 : 가장 아래쪽에 있는 노드를 의미한다. 단말 노드(terminal node), 외부 노드(external node)라고도 한다. 물리적으로 가장 밑에 위치한다는 의미가 아니라 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 뜻이다. 비단말 노드(non-terminal node) : 리프를 제외한 노드. 내부 노드(internal node)라고도 한다. 자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드. 노드는 자식을 몇개라도 가질 수 있다. 부모 ..

리스트는 데이터에 순서를 매겨 늘어놓은 자료구조다. 구조가 간단한 리스트로 선형 리스트(linear list) 또는 연결 리스트(linked list)가 있다. 위의 그림은 연결 리스트의 기본 구조다. A에서 F까지 데이터가 순서대로 나열되고 각 데이터가 화살표로 연결되어 있다. 이런 구조에서는 누군가를 건너뛰거나 뒤돌아 앞사람에게 연락해서는 안 된다. 연결 리스트에서 각각의 원소를 node라고 한다. 노드는 data와 pointer를 갖고 있다. 맨 앞에 있는 노드를 head node, 맨 끝에 있는 노드를 tail node라고 한다. 각 노드에서 바로 앞에 있는 노드를 predecessor node, 바로 뒤에 있는 노드를 successor node라고 한다. 배열로 연결 리스트 만들기 뒤쪽 노드 꺼..