Patience conquers the world Patience conquers the world

트리에서는 네 가지 순회 알고리즘을 가진다. 1) 전위 순회(Pre-Order Traverse) 2) 중위 순회(In-Order Traverse) 3) 후위 순회(Post-Order Traverse) 4) 단계 순위 순회(Level-Order Traverse) 1. 전위 순회 A -> B -> D -> E -> C -> F -> G 2. 중위 순회 D -> B -> E -> A -> F -> C -> G 3. 후위 순회 D -> E -> B -> F -> G -> C -> A 4. 단계 순위 순회 A -> B -> C -> D -> E -> F -> G 5. 트리 순회 알고리즘 코드 트리 클래스 구조 코드 eusun0830.tistory.com/45?category=718944 [Python Algori..

트리 구조는 연결 리스트와 비슷하게 노드와 링크를 이용하지만 동작 구조는 매우 다르다. 트리는 그래프의 일종이며 서로 다른 두 노드를 잇는 링크가 하나뿐인 그래프를 트리라고 표현한다. 1. 트리 구조 트리구조에서 가장 상위에 있는 노드를 루트(root)노드라 한다. 또한 어떤 노드보다 상위에 있는 노드를 부모 노드(parent node)라 하고 하위에 있는 노드를 자식 노드(child node)라고 표현한다. 같은 부모를 두고 있는 경우에는 형제 노드(sibling node)라 부른다. 최하위에 있는 노드들은 리프 노드(leaf node)가 된다. 트리 구조에는 레벨(level)과 높이(height)가 존재하는데 레벨은 루트 노드에서부터 특정 노드까지 찾아오는데 방문한 총 노드의 수를 말하고 높이는 트리..

큐(Queue)는 스택과 함께 많이 사용되는 기본 자료구조이다. 스택이 LIFO(Last In First Out) 방식이라면 큐는 FIFO(First In First Out) 선입선출 방식이다. 큐라는 이름에서 알 수 있듯이 줄을 선 사람들의 모습을 생각하면 이해하기 편하다. 줄을 선 사람들은 줄을 선 순서대로 입장하거나 물건을 살 수 있기 때문에 선입선출의 구조라고 볼 수 있다. 큐에서 줄을 서는 것과 같은 역할을 풋(put)이라 하고 앞에서부터 입장하는 것과 같은 역학을 겟(get)이라 한다. 큐는 스택과 달리 배열을 사용하는 것이 더 유용하다. def put(item): queue.append(item) def get(): return queue.pop(0) if __name__ == '__main..

스택(Stack)은 선형 구조의 알고리즘으로 LIFO(Last In First Out) 후입선출의 구조를 가지고 있다. 쉽게 말하면 그릇이 쌓여있는 모습을 생각하면 새로 쌓을 그릇은 맨 위에 쌓이고 그 중 사용할 그릇은 맨 위에 그릇을 사용하는 모습을 생각하면 이해하기 쉽다. 스택에서 자료를 넣는 것을 푸쉬(push)라 하고, 자료를 꺼내는 것을 팝(pop)이라 한다. 이런 선형구조를 이용해 리스트의 끝에서만 접근이 일어나기 때문에 제한적인 접근이 가능하다. 파이썬에서는 스택의 기본 구조를 리스트(list)로 사용한다. 리스트에는 리스트 멤버 함수인 append, push, pop이 있어 코드 구현이 매우 용이하다. def push(item): stack.append(item) def pop(): ret..

이중 연결 리스트는 (단일) 연결 리스트와 다르게 두 개의 포인터를 이용해 양방향으로 이동할 수 있는 자료구조이다. (단일) 연결 리스트와는 연결 링크(포인터)가 하나 추가되었다는 것 이외에 큰 차이점은 없다. 1. 노드(Node) 정의하기 class Node: def __init__(self, data, next=None, prev=None): self.date = data self.next = next self.prev = prev (단일) 연결 리스트와의 차이점으로는 prev라는 포인터가 하나 더 생겼다는 것을 알 수 있다. 2. 이중 연결 리스트 초기화하기 class Node: def __init__(self, data, next=None, prev=None): self.date = data se..

연결 리스트는 데이터와 다음 노드를 가리크는 링크를 묶어서 노드로 정의하여 사용하는 알고리즘이다. 순서가 있는 데이터 묶음이라는 점에서 배열과 유사하다고 생각할 수도 있다. 배열은 한 번 생성시 총 메모리를 확보해 프로그램 실행 중간에 크기를 변경할 수 없고 배열 안의 값을 정렬할 때에도 하나씩 메모리에 저장되어 있는 값을 바꿔주어야 한다. 하지만 연결 리스트는 배열과는 다르게 연속적이지 않은 데이터들을 링크로 서로 연결해줌으로써 배열이 가지는 단점을 보완할 수 있다. 1. 노드(Node) 정의하기 class Node: def __init__(self, data, next=None): self.data = data self.next = next 노드를 클래스로 정의할 때, 노드의 데이터인 data를 지정..

최근 가장 핫한 키워드를 하나만 뽑으라면 단연 알고리즘일 것이다. (아마도..) 많은 회사들이 개발자 입사 시험에 알고리즘 테스트를 넣고 있고 개발자의 역량 강화에서도 중요한 부분이라고 알려져 있어 많은 사람들이 관심을 가지고 공부하고 있다. 나도 마찬가지로 입사를 위해서..ㅋㅋ 열심히 공부하고 있는 중이다. 먼저 알고리즘이 무엇인지 살펴본 뒤, 알고리즘을 어떻게 평가해야하는지, 파이썬으로 알고리즘을 어떻게 표현할 수 있을지를 다뤄보려 한다. 알고리즘 알고리즘은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것 [출처: 위키백과] 이라 설명되어 있다. 나는 특히 컴퓨터 과학에서 알고리즘을 "주어진 환경에서 컴퓨터로 문제를 ..