분할 정복(Divide-and-Conquer) 알고리즘이란 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘이다. 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 이들의 해를 취합하여 원래 문제의 해를 얻는다. 분할된 입력에 대한 문제를 부분 문제(subproblem)라고 하고, 부분 문제의 해를 부분해라고 한다. 부분 문제는 더 이상 분할할 수 없을 때까지 계속 분할한다. 분할 횟수: log₂n 일반적으로 부분 문제들의 해를 취합하여 큰 부분 문제의 해를 구한다. 합병 정렬 (Merge Sort) 입력이 2개의 부분 문제로 분할, 부분문제의 크기가 ½로 감소하는 분할 정복 알고리즘이다. - 합병 정렬 알고리즘 MergeSort(A,p,q) 입력: A[p]~A[q] 출..
Algorithm/자료구조
자료구조란 자료를 효율적으로 사용하기 위해 자료를 조직화한 것이다. 구조 정의, 삽입 동작, 삭제 동작 등을 정의해야 한다. 자료구조의 종류 선형 자료구조 배열(array), 연결 리스트(linked list) 스택(stack), 큐(queue) 비선형 자료구조 트리(tree), 그래프(graph) 순차 자료구조 자료들의 논리적 순서와 물리적 순서가 일치한다. 배열('같은 자료형'을 가진 자료들을 메모리에 연속적으로 저장하는 방식)의 삽입과 삭제를 사용한다. 연결 자료구조 배열이 가지는 메모리 사용의 비효율성을 해결한다. 연결 리스트(다음 자료의 위치를 자료가 가지고 있는 방식, 노드와 링크로 구성)를 사용한다. typedef struct _node { int key; // 정수형 key 필드를 사용하여..
알고리즘이란 문제를 해결하는 단계적 절차 또는 방법이다. 알고리즘에는 입력이 주어지고, 알고리즘은 수행한 결과인 해(또는 답)를 출력한다. 알고리즘의 특성 정확성: 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다. (안정적 정확성) 수행성: 알고리즘의 각 단계는 컴퓨터에서 수행 가능하여야 한다. (잘 정의된 동작 명령) 유한성: 알고리즘은 일정한 시간 내에 종료되어야 한다. 효율성: 알고리즘은 효율적일수록 그 가치가 높아진다. 최초의 알고리즘 가장 오래된 알고리즘은 기원전 300년경 유클리드(Euclid)의 최대공약수 알고리즘이다. 유클리드 호제법이라고도 부른다. - 유클리드의 최대공약수 알고리즘 2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다는 성질을 이..
알고리즘이란 문제를 해결하기 위한 단계적인 절차를 의미한다. 주어진 문제에 여러 종류의 알고리즘이 있을 수 있으나, 보다 효율적인 알고리즘을 고안하는 것이 매우 중요하다. 1. 최대 숫자 찾기 mission: 다음 카드들 중에 가장 큰 숫자를 찾는다. - 순차 탐색 (Sequential Search) 카드를 한 장씩 차례대로 읽어 가며 찾는 방법이다. 2. 임의의 숫자 찾기 mission: 다음 카드들 중에 임의의 숫자(ex. 85)를 찾는다. - 순차 탐색 (Sequential Search) - 이진 탐색 (Binary Search) 오름차순으로 정렬된 데이터를 반으로 나누고, 나누어진 반을 다시 반으로 나누고, 이 과정을 반복하여 원하는 데이터를 찾는 탐색 알고리즘이다. 3. 동전 거스름돈 missi..
