Computer Science/자료구조, 알고리즘 10

자료구조에 대해 알아보자.배열동일한 데이터 타입의 요소들을 연속된 메모리 공간에 순서대로 저장하는 자료구조데이터 조회에서 O(1)의 시간 복잡도를 가진다.장점연속된 메모리 공간을 사용하므로 처음 데이터의 주소를 알면 나머지도 쉽게 찾을 수 있다.단점크기가 고정되어 추가/삭제에 제약이 있다.연결리스트각각의 데이터가 메모리 공간 상에 고유한 노드로 존재하며, 해당 노드에 앞과 뒤의 메모리 주소를 기억하고 있는 형태즉, 노드들이 서로 연결되어 있는 구조데이터 조회 시 순차적으로 탐색하기 때문에 O(N)의 시간 복잡도데이터 추가와 삭제에는 O(1)의 시간 복잡도Array vs Linked List배열 (Array): 파이썬의 리스트. 접근 쉬움, 삽입 어려움. (파이썬의 리스트)연결리스트: 직접 구현. 접근 어..

BFS와 DFS는 모두 그래프를 탐색하는 방법이다. 그래프는 Node와 Node를 연결하는 Edge로 이루어진 자료구조이고 그래프를 탐색하는 것은 하나의 정점으로부터 연결된 모든 정점들을 한 번씩 차례대로 방문하는 것입니다. 깊이 우선 탐색(DFS, Depth - First Search) 그림과 같이 하나의 정점에서 끝까지 탐색해 최하단의 정점까지 방문 후, 이전 갈림길로 돌아와 선택하지 않은 정점을 방문하는 식으로 탐색한다. DFS는 스택의 자료구조를 이용하고 구체적인 방문 과정은 다음과 같다. 탐색 첫 노드를 스택에 삽입후 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문 처리, 인접 노드가 없다면 스택에서 최상단 노드를 꺼내기 2를 수행할 수 없을때까..