자료구조7 그래프 탐색 -BFS, DFS 그래프 탐색 (그래프 순회) 하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것 BFS 너비 우선 탐색 시작 노드를 방문 표시 후 큐에 넣음 큐에 아무노드가 없을때까지: 큐 가장 앞 노드를 꺼낸다. 꺼낸노드에 인접한 노드들을 모두 보면서: 처음 방문한 노드면: 방문한 노드 표시를 해준다 큐에 넣어준다. BFS 알고리즘 시간 복잡도 BFS 노드 전처리 → O(V) 큐에 노드를 넣고 빼는데 걸리는 시간 → O(V) 큐에서뺀 노드의 인접한 노드들을 도는데 걸리는 시간 →O(E) ⇒총 O(2V+E) ⇒ O(V+E) DFS 깊이 우선 탐색 시작 노드를 옅은 회색 표시후, 스택에 넣음 스택에 아무 노드가 없을때까지 : 스택 가장 위노드를 꺼낸다. 노드를 방문 표시를 한다. 인접한 노드들을 모두 보면서: 처음 방문.. 2024. 1. 23. 그래프 연결 데이터를 저장 할 수 있는 자료구조 세상에는 다양한 연결 관계가 존재하기 때문에 그래프 자료구조는 이를 저장하기 유용하다. 그래프 용어 정리 노드 : 그래프에서 하나의 데이터 단위를 나타내는 객체 엣지: 그래프에서 두노드의 직접적인 연결 관계 데이터 엣지가 방향을 가지면 → 방향그래프 엣지가 어떤 정보를 나타내는 수치를 가지면 → 가중치그래프 차수 : 하나의 노드에 연결된 엣지들의 수 무방향 그래프 → 하나의 노드에 연결된 엣지들의 수를 나타낸다. 방향 그래프 → 노드를 떠나는 엣지의 수를 출력 차수 노드에 들어오는 엣지의수를 입력 차수로 부른다. 경로 : 한 노드에서 다른 노드까지 가는길 경로의 거리 비가중치 그래프 → 엣지의 수 가중치 그래프 → 엣지의 가중치 합 최단 경로 : 두노드 사이의 경.. 2024. 1. 22. 이진 탐색 트리 (binary search tree) → 딕셔너리, 세트를 구현할 때 쓸수있다. 그 이유는 뒤에서 살펴 보겠다. 이진탐색트리속성 부모 노드 왼쪽에는 무조건 부모노드보다 작은 자식노드가 들어가고 부모노드 오른쪽에는 부모노드보다 무조건 큰 자식 노드가 들어간다. 배열이나 파이썬리스트로 구현하지 않고 노드 인스턴스를 연결해서 구현 모든 자식노드가 부모의 레퍼런스를 저장하고 있다. InOrder 순회를 하면 데이터의 값이 순서대로 출력된다. ⇒ ABCDEFGHI 삽입연산 새로운 노드 생성 루트 노드부터 비교하면서 저장할 위치 찾음 찾은 위치에 새롭게 만든 노드 연결 시간복잡도 : O(h) h=높이 탐색연산 주어진 노드의 데이터와 탐색하려는 데이터 비교 탐색하려는 데이터가 더 크면 노드의 오른쪽 자식으로간다. 탐색하려는 데이터가 더 작으면 노드의 왼.. 2024. 1. 19. 힙 형태 속성 : 힙은 완전 이진 트리 (완전 이진 트리의 높이 O(lg(n))) 힙 속성 : 모든 노드의 데이터는 자식 노드들의 데이터 보다 크거나 같다. 정렬 알고리즘 : 데이터를 재배치하는 구체적인 방법 힙 구현하기 완전 이진 트리이기 때문에 동적 배열로 구현 ⇒ 파이썬에서는 동적 배열을 활용한 리스트로 구현 왼쪽 자식 인덱스 : 인덱스 * 2 오른쪽 자식 인덱스 : 인덱스*2+1 Heapify 원하는 노드를 힙속성에 맞는 위치로 재배치 시키는 알고리즘 시간 복잡도 O(lg(n)) 주어진 리스트를 힙으로 만들기 ⇒ 가장 맨마지막 노드부터 루트 노드까지 heapify를 호출해준다. → 역순으로 heapify를 호출해주면 부분트리마다 힙속성을 만족시키고 올라가기 때문에 모든 노드를 힙속성에 맞출수있고 힙이.. 2024. 1. 12. 추상 자료형 기능과 구현 기능 : 연산이 무엇을 하는지 구현 : 연산의 기능을 어떻게 하는지 추상 자료형 자료구조를 추상화 한 것 -> 데이터를 저장, 사용할 때 기능만 생각 추상화 구현을 몰라도 기능만 알면 프로그래밍을 할수있게 해주는 개념 자료구조는 구현까지 알아야해서 생각할 부분이 기능 뿐만 아니라 구현까지 해서 복잡해지지만 추상 자료형은 기능에만 집중 할 수있기 때문에 조금더 생각을 줄일 수있다. ⇒ 추상 자료형을 생각하면 코드의 흐름에 집중 할 수있다. 파이썬 추상화가 많이된 고수준 언어 많은 자료형 이름이 추상 자료형 리스트 데이터간 순서 관계를 유지 할 수있다. 접근 연산 : 특정 위치에 있는 데이터를 가지고 오거나 수정한다. 탐색 연산 : 특정 조건을 만족하는 데이터를 찾는다. 삽입 연산 : 특정 위치.. 2024. 1. 11. 이전 1 2 다음
