dmscks3126 님의 블로그

DFS (깊이 우선탐색)더보기비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요함.두 가지 방법깊이 우선 탐색너비 우선 탐색 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면,가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여결국 모든 정점을 방문하는 순회방법가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 DFS 알고리즘 (수도코드)더보기visited[], stack[] 초기화DFS(v) 시작점 v 방문; visited[v]  DFS 예더보기초기상태 : 배열 visited를 False로 초..

스택 스택(stack)의 특성더보기물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조스택에 저장된 자료는 선형 구조를 갖는다. 선형구조 : 자료 간의 관계가 1대 1의 관계를 갖는다.비선형구조 : 자료 간의 관계가 1대 N의 관계를 갖는다. (예: 트리)스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.마지막에 삽입한 자료를 가장 먼저 꺼낸다.후입 선출(LIFO, Last-in-first-out) 이라고 부른다.ex) 스택에 1,2,3 순으로 자료를 삽입한 후 꺼내면 역순 - 3,2,1 순으로 꺼낼 수 있다. 스택의 구현스택을 프로그램에서 구현하기 위해서 필요한 자료구조와 연산더보기자료구조: 자료를 선형으로 저장할 저장소배열을 사용할 수 있다.저장소 자체를 스택이라 부르기도 한다.스택에서 마지막 ..