Alex-Moon Alex-Moon

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 #..

https://github.com/practical-tutorials/project-based-learning?fbclid=IwAR2LWDZ6dNjQbyE7o6WkM-ZCowBc1IETYa-0ct-8LQwqipqKZdAIzKIEC8A 영문판 깃헙 모음글 더북 https://thebook.io/006889/ 모두의 자바 https://thebook.io/080200/ 파이썬으로 배우는 자료구조 핵심원리 https://thebook.io/080298/ 쉽게 따라 만드는 파이썬 주식 자동매매 시스템 https://thebook.io/006950/ 컴퓨터 사이언스 부트캠프 with 파이썬 https://thebook.io/006935/ 모두의 알고리즘 with 파이썬 https://thebook.io/00687..