자료구조 - 그래프 탐색 그래프 탐색이란? 하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것. 이런 무방향 그래프가 있다고 해보자. B 노드에서 탐색을 시작한다고 할 경우, 결국 모든 데이터를 돌게 된다. 그래프 같은 경우에도 연결된 모든 데이터를 순회하므로 그래프 순회라고도 부른다. 그래프 순회를 통해 알 수 있는 것은, A - BCD 이런식으로 A만 빼고 B ~ D가 연결이 되어 있는 그래프의 경우 A와 B, C, D는 서로 연결되지 않았다는 사실이다. 탐색을 사용하는 또다른 대표적인 예시는 그래프에서 두 노드 사이 최단 경로를 구하는 방법이다. 그래프 순회를 통해 A와 D 사이에 몇 다리가 걸쳐 있는지를 알 수 있게 된다. 그래프 탐색 알고리즘은, 각 노드를 어떤 순서로 탐색하는지에 따라 BFS..

자료구조 - 그래프 자료구조를 공부하는 이유 중 하나는, 상황에 맞는 방식으로 데이터를 저장하고 사용하기 위해서이다. 데이터 사이에 어떤 관계가 있는지에 따라 적절한 자료구조를 골라서 사용해야 한다. 예를 들어 앞과 뒤라는 관계를 저장하고 싶으면 배열이나 링크드 리스트같은 선형적 자료구조를 쓰면 되고, 위와 아래라는 관계를 저장하고 싶으면 트리같은 계층적 자료구조를 쓰면 된다. 이러한 다양한 목적 중 그래프는 연결 관계를 표현하기 위해 사용된다. 예시로는 위치 데이터, 사회 연결망(페이스북 내 친구 관계 등) 등이 있다. 실생활에서도 다양한 연결 관계가 나타난다. 통신: 수많은 컴퓨터들의 연결 관계인 인터넷 생물: 유전자와 단백질의 상호 작용 관계 이것들 뿐만 아니라, 세상에는 무궁무진한 연결 관계들이 ..

이진 탐색 트리 삭제 II 삭제하려는 데이터의 노드가 두 개의 자식이 있을 때 우선 지우려는 노드의 오른쪽 자식(16)으로 간다. 여기서, find_min 메소드의 파라미터에 root 대신 이 16을 넣어주면 된다. 여기서 가장 작은 노드는 14이다. 여기서 어떻게 이진 탐색 트리의 속성을 해치지 않고 12의 위치를 대체할 수 있는지 생각해보자. 12 기준 오른쪽 자식 노드는 왼쪽 자식 노드들보다 전부 크다. 그렇기 때문에 12를 14로 바꿔도 왼쪽 노드는 상관이 없다. 14는 12보다 큰 데이터 중 가장 작은 데이터이다. 14가 12의 위치를 대체해도 오른쪽 모든 노드는 14보다 크다. 이진 탐색 트리에서는 어떤 노드보다 큰 모든 노드 중 가장 작은 노드, 그러니까 값 기준으로 어떤 노드의 바로 다음 ..

자료구조 - 이진 탐색 트리 이진 탐색 트리 딕셔너리, 세트 구현에 쓸 수 있음. 이름에서 알 수 있듯 이진 트리이다. 힙이 힙 속성을 갖고 있듯이 이진 탐색 트리도 이진 트리에 일정한 속성을 조건으로 한다. 위 그림처럼 노드를 기준으로 왼쪽 노드들은 전부 더 작은 값이 들어가야 하고, 오른쪽 노드들은 전부 더 큰 값이 들어가야 한다. 이는 root 노드에만 해당되는 사항이 아니라, 모든 노드에 대해 해당되는 사항이어야 한다. 즉 이와 같이 다른 노드들에 대해서도 이렇게 해당되는 사항이어야 한다는 것이다. 이것이 바로 이진 탐색 트리 속성이다. ex) 4를 찾고 싶을 때 -> root노드를 기준으로 왼쪽은 작고 오른쪽은 크므로 왼쪽 / 오른쪽 자식 노드로 이동하면서 저장한 데이터를 찾는 연산을 실행할 수..

자료구조 힙 (heap) 두 가지 조건을 만족하는 자료 구조이다. 형태 속성: 힙은 완전 이진 트리여야 한다. 힙 속성: 힙 내에 있는 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같아야 한다. 힙을 통해 정렬 문제를 해결할 수 있고(11, 2, 5, 7, 3 -> 2, 3, 5, 7, 11), 또한 우선순위 큐를 구현할 수 있다. 정렬 여러 개의 데이터 요소들을 특정 순서로 배치하는 것 ex) [4, 1, 6, 2, 8, 5]인 파이썬 리스트 오름차순 배치 -> [1, 2, 4, 5, 6, 8] 내림차순 배치 -> [8, 6, 5, 4, 2, 1] 정렬 알고리즘: 데이터를 재배치하는 구체적인 방법 삽입 정렬 선택 정렬 퀵 정렬 합병 정렬 배열로 구현한 힙 완전 이진 트리이므로 동적 배열로 구현..

알고리즘 및 운영체제 정규학기 수업 대비 자료구조 공부를 하고 있다. 자료구조 트리(Tree) 데이터의 상-하 관계(계층적 관계)를 저장하는 자료 구조이다. 컴퓨터 폴더 구조 및 클래스 상속 관계 등을 예로 들 수 있다. 배열 및 링크드 리스트: 선형적 자료 구조 (앞과 뒤 라는 순서를 저장할 수 있음) 해시 테이블: 데이터 관계를 저장하지 않음 -> 계층적 데이터 관계를 저장하기에 적합하지 않다. 트리를 통해 저장할 수 있다. 트리 노드는 하위 관계가 있는 노드를 가리키는 레퍼런스를 갖는다. B와 C를 A의 자식 노드로 만들고 싶다고 해보자. 그럴 경우 A에 B와 C를 가리키는 레퍼런스를 저장하면 된다. 트리에서는 보통 이 레퍼런스를 화살표로 나타낸다. 더 많은 노드를 만들고, 이 노드들 사이에 부모-..