1. DFS란? - DFS 는 깊이 우선 탐색 을 말합니다. - 루트 노드에서 시작하여, 해당 노드들의 자식을 우선적으로 탐색합니다. * 미로찾기로 예시를 들면, 한 방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게 되면 다시 가까운 갈림길로 되돌아 와서 다시 탐색을 진행하는 것과 유사합니다. Q. 깊이우선 탐색을 하면 순서가 어떻게 될까요? A. 0-1-3-4-2-5-6 1) 특징 > 모든 노드를 탐색할 때 좋은 방법입니다. > BFS보다 좀 더 간단하지만 느립니다. 2) 알고리즘 구현 방법 DFS의 결과 : 1 - 2 - 3 - 5 - 4 -6 ⓐ 재귀함수 이용 #include #include using namespace std; bool visited[10]; //방문했던 노드를 기억하는..
Algorithm/Study
1. 완전탐색 1) 개념 : 말 그대로 가능한 모든 경우의 수를 다 탐색하는 것 2) 방법 ⓐ 브루트 포스(Brute-Force) : 영어를 번역하면 무차별 대입이라는 뜻이다. ⓑ 비트마스크(BitMask) : 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법 ⓒ 순열 ⓓ BFS(너비우선탐색) ⓔ 백트래킹 : DFS에 가지치기를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법 2. 해결방법 1) 주어진 문제를 선형 구조로 구조화 2) 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색 3) 구성된 해를 정리 EX) 10의 약수구하기 - 10의 약수가 될 수있는 모든 자연수를 구조화 (1,2,3,4,5,6,7,8,9,10} - 탐색을 이..
1. 시간복잡도 1) 의미 : 알고리즘이 동작하는데 걸리는 시간을 대략적으로 나타냄 🔎 코드는 최대한 간결하고 빠르게 작동하는 것을 원칙으로 한다. 2) 표기법 ⓐ O(Big O) : 시간의 상한 값(최악의 성능일 때 걸리는 시간) ⓑ θ(theta) : 오와 오메가의 중간(평균) ⓒ Ω(omega) : 시간의 하한 값(최고의 성능일 때 걸리는 시간) - 보통 빅 O표기법을 씀 이유 : 알고리즘이 최악일 때 어떤 성능을 지녔는지 판단해야 사용유무를 판단할 수 있기 때문! (어떠한 알고리즘이 최소 1의 속도가 걸린다고 해도 최악의 경우 N속도가 걸리면 무의미 함) 3) 대표적인 시간복잡도 - O(1) : 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다. - ..
