문돌이 Theo

설명 해를 찾는 도중에 '막히면' (즉, 해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 백트래킹 기법은 최적화 문제와 결정 문제를 해결 가능 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'가 답하는 문제 미로 찾기 n-Queen 문제 Map coloring 부분 집합의 합(Subset Sum) 문제 등 백트래킹과 깊이우선탐색과의 차이 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임. (Prunning 가지치기) 깊이우선탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단 깊이우선탐색을 가하기에는 경우의 수가 너무 많음 즉 N! 가지의 경우의 수를 가진 문제에 대해 깊..

설명 비선형 구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요 두 가지 방법 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS)] 깊이 우선 탐색 방법의 과정 시작 정점으로부터 한 방향으로 갈 수 있는 경로가 있는 깊이까지 탐색 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 후퇴 갈림길에서 다른 방향의 정점으로 탐색을 이어 진행 반복하여 모든 정점을 방문하는 순회방법 가장 마지막에 만났던 갈림길의 정점으로 되돌아가기 위해 후입선출 구조의 스택을 사용 DFS 알고리즘 # input # 7 8 (정점의 수, 간선의 수) # 1 2 1 3 2 4 2 5 4 6 5 6 6 ..

Memoization 설명 재귀함수로 구현한 알고리즘은 "엄청난 중복 호출이 존재"한다는 문제점이 존재 피보나치 수열의 Call Tree 메모이제이션(memoization)은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술 동적 계획법의 핵심이 되는 기술 Memoizaition 방법을 적용한 알고리즘은 아래와 같음 # Memoization memo = [0,1] def fibo1(n): if n >= 2 and len(memo) = 2 and len(memo)

함수 호출 설명 프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로, 후입선출 구조의 스택을 이용하여 수행순서 관리 함수 호출이 발생하면 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입 함수의 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)를 삭제(pop)하면서 프레임에 저장되어 있던 복귀주소를 확인하고 복귀 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 됨 함수 호출과 복귀에 따른 전체 프로그램의 수행 순서 재귀호출 설명 자기 자신을 호출하여 순환 수행되는 것 함수에서 실행해야 하는..

설명 스택의 특성 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 스택에 저장된 자료는 선형 구조를 갖음 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있음 마지막에 삽입한 자료를 가장 먼저 호출 - 후입선출 스택의 구현 (필요한 자료구조와 연산) 자료구조 : 자료를 선형으로 저장할 저장소 배열 사용 가능 저장소 자체를 스택이라 부름 스택에서 마지막 삽입된 원소의 위치를 top이라 부름 연산 삽입 : 저장소에 자료를 저장, 보통 push라고 칭함 삭제 : 저장소에서 자료를 호출, 꺼낸 자료는 삽입한 자료의 역순, 보통 pop이라고 칭함 스택이 공백인지 아닌지를 확인하는 연산 : isEmpty 스택의 top에 있는 원소를 반환하는 연산, peek 스택의 삽입/삭제 과정 스택의 push 알고리즘 d..

고지식한 알고리즘 (Brute Force) 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작 시간 복잡도 최악의 경우 모든 위치에서 패턴을 비교해야 하므로 O(MN)이 됨 비교횟수를 줄일 수 있는 방법은 무엇이 있을까? 예시 코드 p = 'is' # 찾을 패턴 t = 'This is a book~!' # 전체 텍스트 M = len(p) N = len(t) def BruteForce(p, t): i = 0 # t의 인덱스 j = 0 # p의 인덱스 while j < M and i < N: if t[i] != p[j]: i = i - j j = -1 i = i + 1 j = j + 1 if j == M: return i - M # 검색 성공 else: ret..

설명 저장되어 있는 자료로부터 k번째로 큰 혹은 작은 원소를 찾는 방법 최소값, 최대값, 중간값 등을 찾는 알고리즘을 의미하기도 함 선택 과정 셀렉션은 아래와 같은 과정으로 구성 정렬 알고리즘을 이용하여 자료 정렬 원하는 순서에 있는 원소 선택 k번째로 작은 원소를 찾을 때, 1번부터 k번째까지 작은 원소들을 찾아 배열의 앞쪽으로 이동, 배열의 k번째를 반환 시간 복잡도: O(kn) - k가 비교적 작을 때 유용 예시 def select(list, k): for i in range(0, k): minIndex = i for j in range(i+1, len(list)): if list[minIndex] > list[j]: minIndex = j list[i], list[minIndex] = list[m..

설명 검색이란 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 목적하는 탐색 키를 가진 항목을 찾는 것 탐색 키(search key): 자료를 구별하여 인식할 수 있는 키 검색의 종류 순차 검색 (sequentail search) 이진 검색 (binary search) 순차 검색 (Sequential Search) 일렬로 되어 있는 자료를 순서대로 검색하는 방법 가장 간단하고 직관적인 검색 방법 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행시간이 급격히 증가하여 비효율적 2가지 경우 정렬되어 있지 않은 경우 정렬되어 있는 경우 정렬되어 있지 않은 경우 검색 과정 첫 번째 원소부터 순서대로 ..

설명 유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아보시오. 예: [-7, -3, -2, 5, 8]의 경우 [-3, -2, 5]라는 부분집합이 참이 된다. 위와 같은 문제가 존재할 때, 완전검색 기법으로 접근해야 할 것이다. 우선 집합의 모든 부분집합을 생성하고, 각 부분집합의 합을 계산해야 한다. 부분집합의 수 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개 각 원소를 부분집합에 포함시키거나, 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 동일 {1, 2, 3, 4} 의 경우 2 X 2 X 2 X 2 = 16 총 16개의 부분집합이 존재 각 원소가 부분집합에 포함되었는지를 for..

설명 행과 열을 교환하여 얻는 행렬 즉, 주대각선을 축으로 하는 반사 대칭을 가하여 얻는 행렬 예시 # i : 행의 좌표, len(arr) # j : 열의 좌표, len(arr[0]) arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 3*3 행렬 for i in range(3): for j in range(3): if i [[1, 4, 7], [2, 5, 8], [3, 6, 9]]