CS/알고리즘 (27) 썸네일형 리스트형 Chap 4. 그리디 알고리즘 그리디 알고리즘 그리디 알고리즘은 "최적화 문제를 해결하는 알고리즘" 최적화 (optimization) 문제 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 그리디 알고리즘은 (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 매 순간 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택 이러한 선택을 ‘근시안적’인 선택이라고 말하기도 함 전체를 끝까지 보는 것이 아니라 해당 시점에서 최적의 선택을 계속적으로 누적하여 마지막 결과까지 진행하는 방법이므로 "근시안적" 이라고 표현함 그리디 알고리즘 방법 = 근시안적인 선택으로 부분적인 최적해를 찾고, 이들을 모아서(축적하여) 문제의 최적해(전역 해)를 얻는다. [특징] (1) .. Chap3-4. 최근접 점의 쌍 찾기(Closest Pair) 3.4 최근접 점의 쌍 찾기 = 최근접 점의 쌍(closest pair)문제는 2차원 평면 상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제이다. ex) 기상 예보, 외판원 문제 등에서 사용 [가장 간단한 방법 구현] 모든 점에 대해서 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점을 찾는 방법 #include #include #include #include #define N 10 typedef struct { int x, y; }Point; void print(Point p[]) { for (int i = 0; i < N; i++) printf("[%d %d]", p[i].x, p[i].y); printf("\\n"); } double dist(Point p1, .. Chap3-2 퀵정렬(QuickSort) 3.2 퀵정렬 퀵 정렬은 분할 정복 알고리즘으로 분류하지만 분할할 수 없을 때까지 분할 후 합병이 아닌 분할 정복, 분할 정보의 과정을 반복하는 알고리즘 2개의 부분 문제로 분할, 각 부분 문제의 크기가 일정하지 않음(비균등 분할) -a = 2이고 b의 값은 정해지지 않음 퀵정렬 알고리즘의 아이디어 순환의 방법으로 과정이 수행된다. 배열의 원소 중 하나를 “피봇”이라는 이름으로 선정 피봇이 위치한 곳을 기준으로 작은 것은 피봇의 왼편으로 큰 것을 피봇의 오른편으로 보낸다. 피봇을 제외한 왼쪽 부분에서 새로운 피봇을 정하여 이 과정을 반복 왼쪽 부분에서 더 이상 정렬할 것이 없다면 오른쪽 부분에서 새로운 피봇을 찾아 이 과정을 반복한다. 피봇 피봇을 기준으로 오른쪽 왼쪽이 다 정렬되면 피봇의 자리는 고정된.. Chap3-1. 합병 정렬(MergeSort) 합병 정렬 = 입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 절반으로 감소하는 분할 정복 알고리즘 중 대표 -순환문의 형태로 정렬을 한다. -2개의 부분 문제를 합병하면서 정렬하는 알고리즘 [ 설명 ] 정렬과 탐색 알고리즘이 제일 중요하다. 가장 효율적으로 원하는 것을 찾는 것이 매우 중요 정렬 알고리즘은 구현의 복잡도에 따라 단순한 알고리즘, 복잡으로 나눌 수 있다. -단순한 알고리즘 = 순차적으로 찾아다니면서 한다(1씩 감소하면서 정렬) ex) 문제의 크기가 1씩 감소하는 중첩된 반복문을 통해 크기를 비교한다. → 시간 복잡도를 따지면 n * n의 시간 복잡도임 -복잡한 알고리즘 = 단순보다는 효율적이다. - 합병 정렬 로그 선형으로 가기 때문에 n의 제곱보단 효율적이라고 할 수 있다 . .. Chap 3. 분할 정복 알고리즘 분할정복 알고리즘 : 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘 부분 해(분할)를 취합( =정복)하여 원래 문제의 해를 얻음 부분문제와 부분해 더 이상 분할할 수 없을 때까지 분할한다. → 분할한 문제들의 해를 취합 → 부분 취합을 다시 취합 (1) 분할 과정 [상황] 입력 = n 분할 = n을 3개로 분할 각각 분할된 부분 문제의 크기 = n/2 *질문 = 여기서 n을 3개로 분할한 것이므로 각각 분할된 부분 크기는 n/3이 아닌가? ⇒ n이라는 전체 크기를 3등분하여 반으로 나눈다는 의미 3등분을 전체에 대한 것이 아니라 전체의 반의 반이 하나의 등분으로 생각하면 된다. [ 이를 일반화 하면 ] 입력 = n 분할 = n을 b개로 분할 각각 분할된 부분 문제의 크기 = n/a.. Ch2. 알고리즘 2.1 알고리즘이란 : 문제를 해결하기 위한 단계적인 절차 또는 방법 입력이 주어지고 → 알고리즘 수행 → 결과 도출 알고리즘의 일반적 특성 입력이 존재 결과값이 존재(출력) 정확성문제 해결의 과정이 논리적이고 정확해야 한다. 주어진 입력에 대해 올바른 해를 주어야 함 수행성알고리즘에 모호한 표현(ambiguity)이 있다면 알고리즘을 프로그래밍을 할 수 없게 된다. 알고리즘의 각 단계는 컴퓨터에서 수행 가능 유한성제한된 개수의 명령 단계를 거쳐서 반드시 언젠가는 종료되어야 한다. 유한 시간 내에 종료되어야 한다. 효율성 문제 해결 과정이 비교했을 때 좀 더 효율적일수록 가치가 높다. 일반성 같은 타입의 문제가 들어온다면 해당 알고리즘을 항상 적용할 수 있어야 함 확장성함수의 특성과 비슷 동일한 입력이 .. Ch 1. 알고리즘의 첫걸음 알고리즘의 유래 -“알콰리즈미”라는 사람의 이름으로부터 유래 -최초의 알고리즘 = 유클리드의 최대공약수 알고리즘 (몫과 나머지의 성격을 이용하여) 알고리즘이란? : 문제를 해결하기 위한 단계적인 절차 -효율적인 알고리즘 고안이 중요 = 최소한의 시간과 비용이 드는 것(시간 복잡도와 공간 복잡도를 최소화시키는 알고리즘) 알고리즘 기술 방법 -알고리즘이라는 것은 문제를 해결하는 방법을 고안하는 것뿐만 아니라 약속된 방법을 통해서 절차를 기술하는 것까지가 알고리즘이다. 기술 방법 = 자연어, flow chart, 의사코드 등 의사코드가 가장 일반적 (프로그래밍 코드와 매우 유사) 모든 문제를 그때 그때마다 구현까지 하려면 복잡한 문제는 구현하는데까지 드는 비용이 매우 높을 것이다. 그 전단계까지인 의사코드를 .. 이전 1 2 3 다음
