study/algorithm (3) 썸네일형 리스트형 [탐색의 종류] 완전탐색/이분탐색/깊이우선탐색/너비우선탐색 1) 완전탐색: 브루트 포스라고도 불리며 컴퓨터의 빠른계산 성능을 활용하여 가능한 모든 경우의 수를 탐색풀리지 않는 문제는 없으나 효율성 관점에서 최악.. - 완전탐색 구현방법ㆍ 반복문ㆍ 재귀함수(완전탐색 외에도 동적계획법, 백트래킹, 탐욕법에서도 사용)# 반복문으로 구현def solution(trump): for i in range(len(trump): if trump[i] == 8: return i return -1 # 재귀함수로 구현def solution(trump, loc): if trump[loc] == 8: return loc else: return solution(trump, loc+1) 2) 이분탐색이진검색이라고도 표현하며 오름.. 시간복잡도(Big-O) 시간복잡도를 표기하는 방법Big-O(빅-오) ⇒ 상한 점근Big-Ω(빅-오메가) ⇒ 하한 점근Big-θ(빅-세타) ⇒ 그 둘의 평균위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법Big-O빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.“최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.Big-O 표기법은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’를 표기하는 방법이다. 표기 예시형태O(1)상수O(log n)로그O(n)선형O(n log .. 백트래킹 백트래킹?현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 즉 이름 그대로 방금 왔던 길을 되짚어가는, backtrack1 하는 알고리즘이다. Promising : 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크한다.Pruning (가지치기): 해당 트리에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지치기를 한다. 해를 구하는 도중 해가 아니어서 막히면 막히기 전으로 다시 돌아가서 해를 찾는 기법가상의 트리에서 해를 구하기 위해 부모 노드에서 자식 노드까지 뻗어나간다. 만약 해당 노드가 조건에 맞지 않는다면 다시 부모노드로 돌아간다.해.. 이전 1 다음
