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

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

자료구조 - 이진 탐색 트리 이진 탐색 트리 딕셔너리, 세트 구현에 쓸 수 있음. 이름에서 알 수 있듯 이진 트리이다. 힙이 힙 속성을 갖고 있듯이 이진 탐색 트리도 이진 트리에 일정한 속성을 조건으로 한다. 위 그림처럼 노드를 기준으로 왼쪽 노드들은 전부 더 작은 값이 들어가야 하고, 오른쪽 노드들은 전부 더 큰 값이 들어가야 한다. 이는 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] 정렬 알고리즘: 데이터를 재배치하는 구체적인 방법 삽입 정렬 선택 정렬 퀵 정렬 합병 정렬 배열로 구현한 힙 완전 이진 트리이므로 동적 배열로 구현..