반응형 알고리즘6 연결 구조 연결구조1흩어진 데이터를 링크로 연결해서 관리함 연결구조의 리스트연결된 구조의 리스트 2용량이 고저오디어 있지 않음 3중간에 자료를 삽입하거나 삭제하기 용이함4n번쨰 항목에 접근하는데 O(n)의 시간이 소요됨노드(node) - 데이터 필드(data field) - 하나 이상의 링크 필드(link field)헤드포인터(head pointer) 연결 리스트의 종류1단순연결 리스트(singly linked list)2원형연결 리스트(circular linked list)3이중연결 리스트(doubly linked list)단순연결 리스트 연결되 스택 노드클래스 class Node: #단순연결 리스트를 위한 노드 클래스 .. 2024. 6. 7. 그리디 알고리즘 1.부분 배낭(Knapsack)문제 1.배낭(Knapsack)문제 *n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 때, 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제 2.부분 배낭(Fractional Knapsack)문제 *원래 배낭 문제는 물건을 통째로 배낭에 넣어야 되지만, 부분 배낭 문제는 문건을 부분적으로 담는 것을 허용함 -단위 무게 강 가장 값나가는 물건을 배낭에 넣고 계속해서 그 다음으로 값 나가는 물건을 넣음 -만일 그다음으로 값나가는 문건을 통째로 배낭에 넣을 수 없게 되면 부분적으로 배낭에 담음 예제 문제 시간 복잡도 O(nlogn) 2.집합 커버(Cover)문제 n개의 원소를 가진 집합인 U가 있고, U의 부분집합들.. 2024. 4. 9. 분할 정복 알고리즘 1.선택 문제 *선택 문제 해결을 위한 간단한 방법 ex)n개의 숫자들 중에서 k번쨰로 작은 숫자를 찾는 문제 1)최소 숫자를 k번 찾음 -단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거함 -최악의 경우 시간 복잡도 O(kn) 2)숫자들을 정렬한 후, k번쨰 숫자를 찾음 -최악의 경우 시간 복잡도 O(nlogn) 2.최근접 점의 쌍 찾기 문제 *2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한쌍의 점을 찾는 문제 분할정복 알고리즘 적용 평면 판을 반으로 나누고 각판에 가까운 점을 구하고 두점중 가장 가까운 점으 거리로 x 값으로 두고 x값 사이의 점들의 거리를 구하고 판과 판사이의 가장 가까운 점을 구한다 시간 복잡도 => O(nlog²n) 3.분할 정복을 적용하는데 있어.. 2024. 4. 9. 분할 정복 알고리즘의 분류 분할 정복 알고리즘 1. 합병 정렬, 최근점 점의 쌍 찾기 *문제가 2개로 분ㄴ할되고, 부분문제의 크기가 1/2로 감소하는 알고리즘 2. 퀵정렬 *문제가 2개로 분할, 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘 3.선택 문제 알고리즘 *문제가 2개로 분할, 그중에 1개의 부분 문제는 고려할 필요 없으며 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘 합병정렬 알고리즘 (Merge Sort) *입력이 2개의 부분문제로 분할, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘 1.n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할 함 2. 각각의 부분문제를 재귀적으로 합병 정력함 3. 2개의 정렬된 부분을 합병하여 정렬(정복)함 퀵 정렬(Quick Sort) *문제를 2개의 부.. 2024. 4. 3. 알고리즘의 특성 및 최초의 알고리즘 알고리즘 *문제를 해결하는 단계적 절차 또는 방법 *입력이 주어지고, 알고리즘을 수행한 결과인해(또는 답)를 출력 알고리즘의 일반적 특성 1.정확성 -주어진 입력에 대해 올바른 해를 주어야함 2.수행성 -각 단계는 컴퓨터에서 수행 가능하여야 함 3.유한성 -일정한 시간 내에 종료되어야 함 4.효율성 효율적일수록 그 가치가 높아짐 최초의 알고리즘 기원전 300년경 유클리드(Euclid)의 최대공약수 알고리즘 최대공약수 *2개 이상의 자연수의 공약수들 중에서 가장 큰 수 유클리드 알고리즘 입력: 정수 a, b (단, a>=b>=0) 출력 a와 b의 최대 공약수 if b = 0, return a return Euclid(b, a mod b) return Euclid(b, a%b) 알고리즘 표현 방법 *일반적으.. 2024. 4. 3. 알고리즘의 첫걸음 알고리즘이란? -문제를 해결하기 위한 단계적인 절차 ex) 요리법과 유사 단계적인 절차를 따라 하면 요리가 만들어지듯이, 알고리즘도 단계적인 절차를 따라 하면 주어진 문제의 답을 주기 때문임 주어진 문제에 대해 여러 종류의 알고리즘이 있을 수 있음 -보다 효율적인 알고리즘을 고안하는 것이 매우 중요함 1. 순차탐색(Sequential Search)알고리즘 *카드를 한 장씩 차례대로(주어진 순서대로) 읽어 가며 찾는 방법 -카드의 숫자를 하나씩 비교하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며 진행하는 방법 -마지막 카드의 숫자를 본 후에, 머릿속에 기억된 가장 큰 숫자가 적힌 카드를 바닥에서 찾음 2이진탐색(Binary Search)알고리즘 *중간 숫자부터 비교해가며 찾는 방법 3그리디(Greedy.. 2024. 4. 3. 이전 1 다음 반응형
