본문 바로가기

공부/알고리즘(이론)

 (8)
[방송대 알고리즘]해 탐사 알고리즘 해 탐사 알고리즘 되추적 알고리즘 DFS로 해를 찾아다니다가 앞쪽에 더 이상 해가 없으면 왔던 길을 되돌아가서 다른 길을 찾아보는 방법 상태 공간 트리 주어진 입력으로 만들어 낼 수 있는 모든 후보해를 리프 노드로 갖는 트리 내부 노드는 각 후보해를 만들어 가는 부분 후보해를 나타냄 특징 다항 시간 알고리즘이 없지만 정확한 해를 구해야 하는 경우에 적용 저울 문제, 0-1 배낭 문제 → O(2^n) 시간 복잡도 분석과는 별개로 실제 동작 시 빠른 수행 결과를 보이는 경우가 많음 분기한정 알고리즘 최적화 문제에 대한 상태 공간 트리를 각 노드의 한정값을 이용하여 탐색 하는 방법 한정값: 현재 노드로 만들 수 있는 해의 상항이나 하한, 혹은 둘 다 한정값이 그 순간의 최적해보다 좋은 경우에만 탐색 후보로 보..
[방송대 알고리즘]근사 알고리즘 근사 알고리즘 1. 기본 개념 튜링 기계 컴퓨터의 이론적 모델 구성 요소 → 테이프, 기호, 헤드, 상태, 규칙 무한한 길이의 테이프, 유한한 개수의 기호와 상태, 상태와 기호에 따른 헤드의 동작을 정해둔 규칙 현재 상태와 읽은 기호에 따라 헤드가 테이프의 기호를 쓰거나 좌우로 이동 결정론적 튜링 기계 테이프의 위치를 바꾸거나 쓰인 기호를 바꿀 때 한 가지 상태로만 변경 가능 순차 처리 컴퓨터와 비슷 비결정론적 튜링 기계 하나 이상의 상태로 바뀔 수 있거나 혹은 바뀔 상태가 없을 수 있음 연산 결과가 상황에 따라 달라질 수 있는 연산을 수행 병럴 처리 컴퓨터와 비슷 다항 시간 알고리즘 알고리즘 수행 시간이 입력 크기 n에 대한 다항식으로 표현 O(1), O(logn), O(n^2) 등등.. O(2^n)같..
[방송대 알고리즘]탐색 알고리즘 탐색의 개념 여러 데이터 중에서 원하는 값을 가진 데이터를 찾는 것 데이터 형태 → 리스트, 트리, 그래프 등 순차탐색 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법 배열의 연산 삽입 연산 n번째 인덱스에 내가 삽입하고 싶은 원소를 추가하고 배열의 크기를 1 증가시킴 삭제 연산 n번째 인덱스의 원소를 삭제하고, 마지막 원소를 삭제한 인덱스에 대입한 후 배열의 크기를 1 감소시킴 연결리스트의 연산 삽입 연산 원하는 데이터를 추가하고 포인터를 연결함 삭제 연산 원하는 데이터를 삭제하고 삭제된 앞 노드와 뒤 노드의 포인터를 연결함 성능분석 탐색 실패의 경우 → 항상 n번 비교 탐색 성공의 경우 → 최소 1번 ~ 최대 n번 비교 → 탐색의 성능은 O(n) ..
알고리즘 2018년도 기말 기출문제 풀이 - 방송대, 방송통신대학교 알고리즘 알고리즘 2018 1번. 교재 및 강의에서 다루어지지 않은 알고리즘 기하 알고리즘 정렬 알고리즘 - 버블, 선택, 삽입, 셸, 합병, 퀵, 힙, 계수, 기수 유전 알고리즘 - 외판원 문제의 근삿값 구하기 욕심쟁이 알고리즘 - 동전 거스름돈, 배낭, 최소신장트리, 최단경로, 작업스케줄링, 작업선택, 허프만 코딩 정답: 1번 2번. 주어진 문제를 컴퓨터로 해결하려고 한다. 이를 위한 명령어들이 만족해야 할 조건과 거리가 먼 것은? 모든 명령은 컴퓨터에서 수행 가능해야 한다. 각 명령은 단순하고 명확해야 한다. 한정된 수의 단계를 거친 후에는 반드시 종료해야 한다. 외부 입력이 반드시 존재해서 하나 이상의 출력을 생성해야 한다. → 외부 입력이 반드시 존재할 필요는 없다. 정답 : 4번 3번. 최대 개수의 노..
[방송대 알고리즘]정렬 알고리즘 정렬 알고리즘 1. 정렬의 개념 내부 정렬: 정렬할 데이터 전체가 속도가 빠르고 무작위 접근이 가능한 주기억장치에 있는 경우에 사용되는 정렬 방식 비교 기반 정렬 알고리즘: 데이터의 키값 전체를 직접적으로 비교하여 어떤 값이 큰지 또는 작은지를 결정하여 정렬을 수행하는 방식의 알고리즘 안정적 정렬 알고리즘: 동일한 값을 같는 데이터가 여러 개 있을 때 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 방식의 정렬 알고리즘 제자리 정렬: 데이터를 정렬함에 있어서 입력 데이터를 저장한 공간 이외에 별도로 필요한 저장 공간이 상수 개를 넘지 않는 정렬 알고리즘 내부 정렬 알고리즘 비교 기반 알고리즘 데이터의 값을 직접적으로 비교해서 정렬하는 알고리즘 키값의 비교 횟수를 가지고 성능을 판단함 버블, 선택,..
[방송대 알고리즘]그리디 알고리즘 ※ 방송대 교재의 예제를 참고하여 작성하였습니다. 디테일한 내용은 교재를 참고 바랍니다. 그리디 알고리즘 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택함으로써 전체적인 최적해를 구함 동적 프로그래밍 방법과의 공통점 최적화 문제 해결에 주로 사용 최적성의 원리가 적용된 방법 차이점 동적 프로그래밍 방법은 항상 전체적인 최적해를 구함 욕심쟁이 알고리즘은 각 단계에 대해서 하나의 최적해만 고려, 전체적인 최적해를 구하지 못할 수 있음 그리디의 한계 가장 좋은 바지, 가장 좋은 넥타이, 가장 좋은 자켓을 입는다고 가장 멋쟁이라고 할 수 있는가? 동전문제 그리디로 해결하기 위해서 다음 크기 동전이 이전 크기 동전의 배수여야함 일반적인..
[방송대 알고리즘]분할정복 알고리즘 ※ 방송대 교재의 예제를 참고하여 작성하였습니다. 디테일한 내용은 교재를 참고 바랍니다. 분할정복 알고리즘 순환적으로 문제를 푸는 하향식 접근 방법 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 이 해들을 결합해서 원래 문제의 해를 구하는 방식 분할된 작은 문제는 서로 독립적, 순환적 분할 및 결과 통합이 가능 분할된 작은 문제는 원래 문제와 동일 분할정복 방법의 처리 과정 분할: 주어진 문제를 여러 개의 작은 문제로 분할 정복: 작은 문제를 순환적으로 분할, 더 이상 분할되지 않을 정도로 크기가 충분히 작다면 순환호출 없이 작은 문제의 해를 구함 결합: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 ..
[방송대 알고리즘]동적 프로그래밍 ※ 방송대 교재의 예제를 참고하여 작성하였습니다. 디테일한 내용은 교재를 참고 바랍니다. 동적 프로그래밍 상향식 접근 방법으로 소문제를 이용하여 보다 큰 크기의 문제를 해결하는 방법 동적 프로그래밍 방법을 적용하려면 최적성의 원리를 적용해야함 최적성의 원리: 주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다. 피보나치 수 동적 프로그래밍을 이용하면 O(n) 연쇄 행렬 곱셈 문제 행렬의 곱셈에 결합법칙이 성립됩을 이용 n개의 행렬을 곱하는 최적의 순서는 n개의 행렬의 어떤 부분집합을 곱하는 최적의 순서를 포함 C(i,j) → i,j 범위 내의 최소의 코스트 크기가 nxm 인 행렬과 mxk인 행렬을 곱하면 필요한 연산 수는 nmk 이다! P(i,j) → 최적의 곱셈 순서를 알기 위한..

티스토리툴바