0과 1의 모든 기록저장소

https://velog.io/@fldfls/%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC-MST-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 최소 신장 트리 (MST, 크루스칼, 프림 알고리즘) 원래의 그래프의 모든 노드가 연결 되어있으면서 트리의 속성을 만족하는 그래프 조건본래의 그래프의 모든 노드를 포함모든 노드가 서로 연결 되어있다트리의 속성을 만족 (사이클이 존재하 velog.io 최소 신장 트리 (Minimum Spannig Tree) spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리. MST는 ..

그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. 📌여기서 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다. 1. 깊이 우선 탐색 (DFS, Depth-First Search) : 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 출처 https://developer-mac.tistory.com/64 💡 깊이 우선 탐색의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다. 예를 들어, 미..

이번에 살펴볼 개념은 백트래킹에 관한 내용입니다. 백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. Backtracking(백트래킹) 완전탐색 : 여러 개의 solution을 가진 문제에서, 모든 solution을 탐색하는 전략 대표적 예 : 재귀 호출 or 스택을 통한 DFS 백트래킹의 원리 어떤 노드의 유망성을 점검 후, 유망하지 않으면 배제시킨다. = 가지치기 해당 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. → 풀이시간 단축 유망성과 가지치기 유망성(Promising) : 가망이 있는가 없는가를 따지는 기준 가지치기(Pruning) : 유망성을 따져보고, 유..

1.알고리즘(algorithm) 문제를 해결하기 위한 여러 동작들의 모임 어떤 기능이 일어나기 위해 내재된/독립된 단계적 명령어들의 집합 1) 알고리즘의 조건 입력 : 외부에서 제공되는 자료가 0개 이상 존재 출력 : 적어도 2개 이상의 서로 다른 결과 도출 명확성 : 모호하지 않은 명령어로 구성되며 수행 과정이 명확해야 함 (→ 정밀/유일성) 유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내) 종료 효율성 : 모든 과정은 명백하게 실행가능(검증가능) 한 것이어야 한다. (=타당성) 2) 알고리즘 전략세우기(Pseudo-code) 일반적인 알고리즘 순서 ① 문제 정의 → ② 모델 고안 → ③ 명세 작성 → ④ 설계 → ⑤ 검증 → ⑥ 분석(복잡도 등) → ⑦ 구현 → ⑧ 테스트 → ⑨ 문서화..