문돌이 Theo

설명 그래프를 탐색하는 방법에는 크게 두 가지가 있음 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS) 너비우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 인접한 정점들에 대해 탐색한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용 BFS는 아래와 같은 순서로 탐색 BFS 알고리즘 def BFS(G, v): # 그래프 G, 탐색 시작점 v visited = [0] * n # n : 정점의 개수 queue = [] # 큐 생성 queue.append(v) # 시작점 v를 큐에 삽입 while..

설명 초기 공백 상태 : front = rear = 0 Index의 순환 front와 rear의 위치가 배열의 마지막 인덱스인 n-1을 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함 이를 위해 나머지 연산자를 사용 front 변수 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠 삽입 위치 및 삭제 위치 원형 큐의 연산 과정 원형 큐의 구현 # 원형 큐에서 front와 rear의 초기값은 0 front, rear = 0, 0 # Index의 순환을 위해서 front와 rear은 n-1 다음에 0으로 이동해야함 # 이를 위해 나머지 연산자 mod()를 사용 # 삽입 def enQueue(item): global ..

큐 설명 큐(Queue)의 특성 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조 선입선출구조(FIFO : First In First Out) 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입(First in)된 원소는 가장 먼저 삭제(First Out) 큐의 선입선출 구조 큐의 사용을 위해 필요한 주요 연산 큐의 연산 과정 선형 큐 1차원 배열을 이용한 큐 큐의 크기 = 배열의 크기 front : 저장된 첫 번째 원소의 인덱스 rear : 저장된 마지막 원소의 인덱스 상태 표현 초기 상태 : front = rear = -1 공백 상태 : front = rear 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 ..

설명 퀵 정렬은 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법 합병정렬과 동일? - 다르다 합병정렬은 그냥 두 부분으로 나누는 반면, 퀵정렬은 분할할 때, 기준키 중심으로 작은 값과 큰 값을 위치 각 부분 정렬이 끝난 후, 합병정렬은 '합병'이란 후처리 작업 진행, 퀵정렬은 필요하지 않음 알고리즘 def quickSort(arr, begin, end): if begin < end: p = partition(arr, begin, end) quickSort(arr, begin, p-1) quickSort(arr, p+1, end) def partition (arr, begin, end):..

설명 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘 퀵 정렬, 합병 정렬로 대표되는 정렬 알고리즘 문제와 고속 푸리에 변환 문제가 대표적 설계 전략 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눔 정복(Conquer) : 나눈 작은 문제를 각각 해결 통합(Combine) : (필요하다면) 해결된 해답을 모음 거듭 제곱 (Exponentiation) O(n) # 반복문을 이용한 거듭제곱 def Iterative_Power(x, n): result = 1 for i in range(1, n+1): result *= x return result O(logn) # 분할 정복을 이용한 거듭제곱 def Recursive_Power(x, n): if n == 1: r..

설명 해를 찾는 도중에 '막히면' (즉, 해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 백트래킹 기법은 최적화 문제와 결정 문제를 해결 가능 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 '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..