Coding/Algorithm

Coding/Algorithm
[C/C++] 완전탐색 Brute Force 개념 정리
완전탐색(Brute Force) 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하며 답을 찾는 방법 Brute Force 라고도 부르는데, 뜻은 무식하게 푼다! 완전탐색은 알고리즘이 아닌, 문제를 푸는 방법이라고 할 수 있다. 완전 탐색 기법 1. 단순 Brute Force if문이나 for문을 사용해 모든 case를 탐색하는 방법 2. Bit-mask 모든 경우의 수가 각각의 원소에 포함되거나 포함되지 않는 두 가지 선택으로 구성되는 경우 용이하다. 이를 통해 집합을 정수로 나타내거나 집합의 모든 부분집합을 정수로 표현할 수 있다. {1, 2, 3, 4, 5} -> 1 1 1 1 1 -> 31 {1, 2, 3, 4} -> 1 1 1 1 0 {2, 3, 5} -> 0 1 1 0 1 {..
→2021.08.09
Coding/Algorithm
[C/C++] DFS/BFS 개념정리
BFS/DFS ⭐DFS 깊이 우선 탐색 정의 : 한 경로의 끝까지 최대한 깊숙히 탐색하다가 그 다음 경로로 이동한다. 장점 : 현재 경로의 노드만 기억하면 됨 -> 저장공간이 많이 필요하지않다. 단점 : 목표 노드까지 도달한 경로가 최단 경로라는 보장이 없다. 해가 없는 경로인 경우 : 끝까지 탐색하기 때문에 미리 정해둔 임의의 깊이까지만 탐색하고 해를 발견하지 못하면 가장 최근의 부모 노드로 돌아가는 백트래킹(Back Tracking) 을 이용해 다른 경로를 선택하여 진행한다. 구현 : 재귀 / 스택(stack) 의사 코드 Dfs(G, v): 스택 s를 생성한다. s.push(v) while (not is_empty(s)) do v = s.pop() if(v가 방문되지 않았으면) v를 방문되었다고 표시..
→2021.08.09

• 이전
• 1
• 다음