본문 바로가기

공부

 (39)
[방송대 알고리즘]해 탐사 알고리즘 해 탐사 알고리즘 되추적 알고리즘 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) ..
운영체제 - 교착상태 정리 (방송통신대학교 운영체제) 교착상태 필요조건 상호배제 점유대기 비선점 환형대기 상호배제 프로세스들이 자원에 대한 배타적인 통제권을 요구 적어도 하나 이상의 자원은 공동 사용될 수 없음 즉, 필요로 하는 자원을 다른 프로세스가 점유하고 있으면 반드시 대기해야 함 점유대기 프로세스가 이미 다른 자원을 할당받아 배타적으로 점유하고있는 상황에서 다른 프로세스가 점유하고 있는 자원이 해제되기를 기다리는 상호아 비선점 프로세스에 할당된 자원은 그 프로세스가 사용을 마치고 스스로 반환하기 전에 제거되지 않음 즉, 다른 프로세스에 의해서는 해제되지 않음 환형 대기 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 환형을 이루며 대기 자원할당 그래프 정점 V = P U R P: 프로세스 R: 자원 Q(p,r): 요구간선, p가 r을 요구함 S(..
알고리즘 2018년도 기말 기출문제 풀이 - 방송대, 방송통신대학교 알고리즘 알고리즘 2018 1번. 교재 및 강의에서 다루어지지 않은 알고리즘 기하 알고리즘 정렬 알고리즘 - 버블, 선택, 삽입, 셸, 합병, 퀵, 힙, 계수, 기수 유전 알고리즘 - 외판원 문제의 근삿값 구하기 욕심쟁이 알고리즘 - 동전 거스름돈, 배낭, 최소신장트리, 최단경로, 작업스케줄링, 작업선택, 허프만 코딩 정답: 1번 2번. 주어진 문제를 컴퓨터로 해결하려고 한다. 이를 위한 명령어들이 만족해야 할 조건과 거리가 먼 것은? 모든 명령은 컴퓨터에서 수행 가능해야 한다. 각 명령은 단순하고 명확해야 한다. 한정된 수의 단계를 거친 후에는 반드시 종료해야 한다. 외부 입력이 반드시 존재해서 하나 이상의 출력을 생성해야 한다. → 외부 입력이 반드시 존재할 필요는 없다. 정답 : 4번 3번. 최대 개수의 노..
기하변환 기하변환 기하변환: 물체의 위치나 방향, 크기 등을 바꾸는 기하학적 변환 기본 2차원 변환 1. 2차원 이동변환 점의 2차원 이동변환 변화량 t일 때 P' = P + T x' = x + t_x y' = y + t_y 물체의 이동변환 삼각형이 이동시, 삼각형을 구성하는 모든 꼭지점이 변화량 T만큼 이동해야함 2. 2차원 크기변환 원점을 기준으로 한 2차원 크기변환 변화량 s일 때 P' = SP x' = s_x * x + 0y y' = 0x + s_Y * y 임의 고정점을 기준으로 한 크기변환 임의 고정점 f를 원점인것처럼 계산 3. 2차원 회전변환 2차원 평면에서의 각도와 좌표의 관계 x = r cos a y = r sin a 2차원 회전행렬 동차좌표계와 기본 2차원 변환 행렬 1. 동차좌표와 기하변환 동..
[방송대 알고리즘]정렬 알고리즘 정렬 알고리즘 1. 정렬의 개념 내부 정렬: 정렬할 데이터 전체가 속도가 빠르고 무작위 접근이 가능한 주기억장치에 있는 경우에 사용되는 정렬 방식 비교 기반 정렬 알고리즘: 데이터의 키값 전체를 직접적으로 비교하여 어떤 값이 큰지 또는 작은지를 결정하여 정렬을 수행하는 방식의 알고리즘 안정적 정렬 알고리즘: 동일한 값을 같는 데이터가 여러 개 있을 때 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 방식의 정렬 알고리즘 제자리 정렬: 데이터를 정렬함에 있어서 입력 데이터를 저장한 공간 이외에 별도로 필요한 저장 공간이 상수 개를 넘지 않는 정렬 알고리즘 내부 정렬 알고리즘 비교 기반 알고리즘 데이터의 값을 직접적으로 비교해서 정렬하는 알고리즘 키값의 비교 횟수를 가지고 성능을 판단함 버블, 선택,..
[방송대 알고리즘]그리디 알고리즘 ※ 방송대 교재의 예제를 참고하여 작성하였습니다. 디테일한 내용은 교재를 참고 바랍니다. 그리디 알고리즘 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택함으로써 전체적인 최적해를 구함 동적 프로그래밍 방법과의 공통점 최적화 문제 해결에 주로 사용 최적성의 원리가 적용된 방법 차이점 동적 프로그래밍 방법은 항상 전체적인 최적해를 구함 욕심쟁이 알고리즘은 각 단계에 대해서 하나의 최적해만 고려, 전체적인 최적해를 구하지 못할 수 있음 그리디의 한계 가장 좋은 바지, 가장 좋은 넥타이, 가장 좋은 자켓을 입는다고 가장 멋쟁이라고 할 수 있는가? 동전문제 그리디로 해결하기 위해서 다음 크기 동전이 이전 크기 동전의 배수여야함 일반적인..

티스토리툴바