gaori

너비 우선 탐색 a와 인접한 노드들을 차례로 방문 후 인접한 노드들의 이웃들을 차례로 방문한다 큐 : 방문 차례를 기록 BFS 구현 DFS보다 구현하기 쉽다 DFS에서 스택을 큐로 바꾼다 BFS의 큐는 방문한 순서대로 넣어진다 방문한 순서대로 들어가 지금 탐색하고 있는 노드의 인접한 노드를 다 방문했다면 큐에 저장된 순서대로 빼서 그 노드의 인접한 노드를 탐색 python

깊이 우선 탐색 하나를 깊이 파고 든다 a와 인접한 다른 노드 차례로 순회한다 a와 인접한 노드 b를 방문했다면, a와 인접한 다른 노드를 방문하기 위해서는 b와 인접한 노드를 전부 방문한 뒤 a와 인접한 b를 제외한 다른 노드를 방문할 수 있다 스택 : 경로 정보의 추적을 기록 DFS 구현 딕셔너리와 스택을 활용 인접한 노드를 저장하는 adjDict는 연결리스트로 노드의 데이터를 key로 갖는다 방문 정보를 확인하는 visitedInfo는 노드의 데이터를 key로 value에는 방문했을때 1을 저장 python

버블정렬 일반적인 정렬 앞과 뒤를 비교해서 순차적으로 계속 비교해 나가는 모습이 거품이 일어나는 모습에 비유되어 버블정렬이다 O(n2)의 성능을 보인다 버블정렬 구현 이중for문으로 구현한다 for문 한 사이클 돌 때마다 제일 큰 수는 맨 뒤로 간다 python 선택정렬 정렬순서상 가장 앞서는 것을 찾아서 왼쪽에 정렬 원래 정렬에 필요한 별도의 메모리 공간이 필요하지만 위치 교환이 좀 더 효율적이다 O(n2)의 성능을 보인다 선택정렬 구현 이중for문으로 구현한다 for문 한 사이클 돌 때마다 제일 작은 데이터부터 정렬 된다 python 삽입정렬 정렬된 부분과 정렬이 되지않은 부분을 나눠서 정렬된 부분에 정렬이 안된 데이터를 하나씩 뽑아 정렬된 부분의 위치를 찾아 삽입하는 정렬 위치 교환이 아닌 정렬된 ..

이진 탐색 트리 이진 탐색 트리는 이진트리와 다르게 저장 규칙이 있기 때문에 이진 탐색 트리이다 저장규칙 이진 탐색 트리의 노드에 저장된 키는 유일 루트 노드의 키가 왼쪽 서브 트리를 구성하는 노드의 키보다 크다 루트 노드의 키가 오른쪽 서브 트리를 구성하는 노드의 키보다 작다 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다 즉 루트 노드 키보다 작으면 왼쪽 크면 오른쪽 이진 탐색 트리 구현 기존 이진 트리를 활용해서 구현하다 삽입, 탐색 연산 삽입 : 새로운 노드가 추가될 위치를 찾는다 중복을 검사 새 노드를 생성 찾은 위치에 노드 삽입 탐색 : 현재 노드 데이터와 타겟 데이터를 비교 타겟 데이터 크다면 현재 노드를 오른쪽 서브트리로 작다면 현재 노드를 왼쪽 서브트리로 반복해서 타겟데이터를 찾으면 ret..

그래프 정점과 간선으로 이루어져 있다 방향성이 없는 그래프를 가리켜 무방향 그래프 방향정보가 포함된 그래프를 가리켜 방향 그래프, 다이그래프 그 중에서 각각의 정점에서 다른 모든 정점을 연결한 그래프 완전 그래프 간선에 가중치 정보(두 정점 사이의 거리, 두 정점 사이의 걸리는 시간...)를 둔 가중치 그래프 그래프의 표현 그래프 G의 정점 집합 V(G) 그래프 G의 간선 집합 E(G) 으로 표시할때 정점 A 에서 정점 B 간의 간선 하나있는 무방향 그래프는 V(G) = {A, B} E(G) = {} 로 나타낼 수 있다 방향 그래프에서 와 는 다른 간선 이다 그래프의 구현 인접 리스트 배열 또는 해시테이블로 구현하여 각 인덱스마다 존재하는 또 다른 리스트는 연결리스트, 배열 어떤 것으로 구현해도 상관없다..

힙 차곡차곡 쌓아 올린 더미 루트노드로 갈 수록 값이 커지면 최대 힙 루트노드로 갈 수록 값이 작아지면 최소 힙 최대 힙, 최소 힙 둘 다 우선순위에 맞게 데이터를 저장하고 삭제한다 힙은 우선순위 큐 구현에 어울리는 완전 이진 트리의 일종이다 힙 구현 저장과 삭제 연산 힙은 새로운 노드를 추가한 이후에도 완전 이진 트리를 유지해야 하기 때문에 연결 리스트로 구현 하게되면 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다 그래서 배열로 구현해야 한다 배열로 구현 시 배열의 인덱스가 0인 위치는 사용하지 않고 노드의 고유번호에 맞게 편의성을 준다 왼쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 * 2 오른쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 * 2 + 1 부모 노드의 인덱스 ..

트리 비선형 자료구조 계층적 관계를 표현하는 자료구조 노드 간선 루트 노드 단말 노드 내부 노드 이진 트리 루트 노드를 중심으로 두 개의 서브 트리 나뉘어진 두 서브 트리도 모두 이진 트리 포화 이진 트리 모든 레벨이 꽉 찬 이진 트리 완전 이진 트리 왼쪽에서 오른쪽으로 순서대로 빈틈없이 채워진 이진트리 이진 트리 구현 배열 기반과 연결 리스트 기반이 있다 typescript 이진 트리의 순회 루트 노드를 기준으로 순회한다 전위 순회(Preorder Traversal) : 루트 노트를 먼저 루트 - 왼쪽 - 오른쪽 중위 순회(Inorder Traversal) : 루트 노드를 중간 왼쪽 - 루트 - 오른쪽 후위 순회(Postorder Traversal) : 루트 노드를 마지막에 왼쪽 - 오른쪽 - 루트 순..

큐 FIFO(First-In-First-Out) 순서대로 처리된다 매표소 앞에 서 있는 사람들을 생각하면 된다 너비 우선 탐색(breadth-first search), 캐시를 구현하는 경우에 사용 예를 들어 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장해서 노드를 접근한 순서대로 처리할 수 있게 된다 큐 연산 enqueue(item) : item을 리스트의 끝부분에 추가한다 dequeue() : 리스트의 첫 번째 항목을 제거한다 peek() : 큐에서 가장 위에 있는 항목을 반환한다 isEmpty() : 큐가 비어 있는지 확인 비어 있다면 true 반환 큐 구현 typescript

스택 쌓아 올린다 문제의 종류에 때라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다 LIFO(Last-In-First-Out) 쌓여있는 접시를 생각하면 된다 재귀 알고리즘, 깊이 우선 탐색(depth-first search)알고리즘을 사용할 때 유용하다 스택 연산 pop() : 스택에서 가장 위에 있는 항목을 제거한다 push(item) : item 하나를 스택의 가장 윗 부분에 추가한다 peek() : 스택의 가장 위에 있는 항목을 반환한다 isEmpty() : 스택이 비어 있는지 확인 비어 있다면 true 반환 스택 구현 스택을 구현하기 위해서 연결리스트 자료구조를 사용 typescript

연결리스트 차례로 연결된 노드를 표현하는 자료구조 단방향, 양방향 단방향의 각 노드는 다음 노드를 가리킨다 양방향의 각 노드는 다음 노드와 이전 노드를 가리킨다 구현 간단하게 연결리스트 구현 python class Node: def __init__(self, d): self.data = d self.next = None def appendToTail(self, d): end = Node(d) while(self.next != None): self = self.next self.next = end def allGet(self): while(self.next != None): print(self.data) self = self.next print(self.data) node = Node("0") node.a..