알고리즘

Undirected Graph Adjacency List, Matrix:: 무 방향 그래프, 인접 목록, 행렬

이 게시물은 개인적으로 알고리즘 공부한 내용과 이곳 저곳 검색하여 얻은 정보, 잡지식을 꾸준히 쌓아가는 글입니다. 출처는 최하단에 남겨두겠습니다. 자료나 궁금한점은 댓글로 질문해주세요.^^ 무방향 그래프를 나타내는 두 가지 방법이 있다. ( 방향이 없는 그래프 ) 인접 행렬 인접 목록 1. 인접 행렬 Adjacency Matrix 그래프 이론에서 어느 꼭짓점들이 변으로 연결되어있는지 나타내는 ㅎㅎㅎㅎ정사각형 행렬(노드의 갯수 x 노드의 갯수)입니다. 연결 행렬이라고도 합니다. 그래프에서 방향이 지정되지 않은 경우 인접 행렬은 대칭이다. 1과 0으로 노드들의 연결 관계를 표현한다. ( True 와 False로 표현하기도 한다.) 즉, 인접 행렬에서 간선인 경우 matrix(i, j) = 1이고 선이 없다면..

[백트래킹] 퇴각검색

BackTracking 백트래킹 = 퇴각검색 백트래킹은 한정 조건을 가진 문제를 풀려는 전략이다. 1950년대 미국 수학자 D.H.레머가 만들었다. 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이뤄지는데, 한정 조건을 구성하려면 각가의 변수들을 값이 있어야 한다. 퇴각 검색은 모든 조합을 시도해서 문제의 해를 찾는다. 이것이 장점이 될 수 있는 이유는 퇴각검색 구현 방법들이 많은 부분 조합들을 배제하기때문이다. 결국 풀이 시간이 단축된다. 주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 DFS를 사용한다. 탐색 중 오답을 만나면 이전 분기점으로 돌아..

Dijkstra Algorithm :: 다익스트라 알고리즘 (최단경로)

이 게시물은 개인적으로 알고리즘 공부한 내용과 이곳 저곳 검색하여 얻은 정보, 잡지식을 꾸준히 쌓아가는 글입니다. 출처는 최하단에 남겨두겠습니다. 자료나 궁금한점은 댓글로 질문해주세요.^^ Dijkstra Algorithm 다익스트라 알고리즘 = 데이크스트라 알고리즘 다익스트라 알고리즘 (Dijkstra Algorithm)은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭지점 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 컴퓨터 과학자 에츠허르 데이크스트라가 1956년 고안했습니다. 1930년생이시며, 72세(2002년에 별세하셨다고 하네요.) 네덜란드 사람이네요. 주요업적 : 다익스트라 알고리즘 프림 알고리즘 차량기지 알고리즘 데드락 방지 알고리즘 은행원 알고리즘 잠자는 이발사 알고리즘 ..