본문 바로가기

Computer Science/알고리즘30

[알고리즘] ep3+) 이진탐색트리(BST) 구현 BST(이진탐색트리) 구현종료(q) 명령 때까지 삽입(i), 탐색(s), 삭제(d), 인쇄(p), 명령을 반복 입력받아 수행i : 입력 에 대한 노드 생성 및 트리에 삽입d : 입력 가 트리에 존재하면 해당 노드 삭제 후 삭제된 키를 출력, 없으면 ‘X’를 출력s : 입력 가 트리에 존재하면 해당 키를 출력, 없으면 ‘X’를 출력 p: 현재 트리를 전위순회로 인쇄q: 프로그램 종료  주의: 중복 키가 없는 것으로 전제한다. 문제를 단순화하기 위해, 키만 존재하고 원소(element)는 없는 것으로 구현한다. main 함수는 반복적으로 명령을 입력받기 전에 빈(empty) 이진탐색트리를 초기화해야 한다 – 즉, 외부노드 1개로만 구성된 이진트리를 말한다. 힌트: 트리 노드 삭제 시, 삭제할 노드 w의 자식.. 2024. 7. 17.
[알고리즘] ep3) 탐색트리 ㅇ이진탐색트리(BST, Binary Search Tree): 노드의 왼쪽 가지에는 노드보다 작은 값들만 있고, 노드의 오른쪽 가지에는 노드보다 큰 값들만 있도록 구성 내부노드에 (key, value)쌍을 저장하며 그림으로는 간단히 노드에 key만 표시한다(왼쪽 및 오른쪽 부트리 또한 각각 이진탐색트리이다) // 재귀버전int binarySearch(int* arr, int lowIdx, int highIdx, int key) { if (lowIdx > highIdx) { if (highIdx key) { // 중간값이 키값보다 큰 경우, 왼쪽 절반을 탐색 return binarySearch(arr, lowIdx, midIdx - 1, key); } else if (a.. 2024. 7. 11.
[알고리즘] ep2) 사전(dictionary) ㅇ사전(dictionary) ADT: 탐색 가능한 형태의 (key, value)쌍 항목들의 모음을 모델링주로 해시 테이블(hash table)과 이진 검색 트리(BST)로 구현하며, 이때 각 키는 유일해야 한다 -> 유일키 - 직접응용: 연락처, 카드 사용승인, 인터넷주소 맵핑 e.g. www.sejong.ac.kr을 128.148.34.101로 맵핑 - 간접응용: 알고리즘 구현, 자료구조 구현  유일키(unique key): 한 개의 키에 대해 하나의 데이터만 존재e.g. 학번, 계좌, ID중복키(duplicate key): 한 개의 키에 대해 여러 개의 데이터가 존재e.g. 이름, 나이, 계좌개설일자  [두 종류의 사전]- 무순사전 ADT- 순서사전 ADT [사전 구현에 따른 탐색 기법]    "컴퓨.. 2024. 7. 11.
[알고리즘] ep1-6+) 퀵정렬의 다양한 버전 (출력형식)Limit         결정적1           결정적3              무작위1           무작위31        X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 100    X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 500   X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 1000  X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX(참고: X.XXXXXXXX는 측정된 cputime in milliseconds).   [주요 함수들의 설계 가이드라인]global integer n = 100000global array Limits = {1, 100, .. 2024. 7. 10.
[알고리즘] ep1-4+) O(n + klog(n))의 힙정렬 문제: 중복이 있을 수 있는 n개의 정수들로 이루어진 무순리스트 L을 구축 후, k번째 작은 원소를 O(n + klog(n)) 시간에 찾아 인쇄하라  프로그램 요구사항:findKthSmallest(L, n, k)중복이 있을 수 있는 n개 정수 원소들로 이루어진 리스트 L의 원소 가운데 k-번째로 작은 원소를 찾아내 반환한다.buildList(n, min, max)난수함수를 이용하여 min ~ max 사이의 중복이 있을 수 있는 정수 n개의 무작위, 무순리스트를 만들어 반환한다.리스트는 1D 배열 또는 단일연결리스트 가운데 하나를 자유롭게 선택하여 구현한다.main()buildList(10, 1, 100)을 호출하여 1과 100 사이의 정수 10개로 이루어진 리스트를 만들어 L에 저장한다.정수들 사이를 공.. 2024. 7. 10.
[알고리즘] 정렬 알고리즘 선택 매뉴얼 ㅇ버블정렬 - 실무에서는 아예 사용하면 안된다"제자리 + stable" O(n^2)   ㅇ선택정렬: 우선순위 큐 (무순 리스트로 구현)"제자리 + unstable" O(n^2): 느리다 - 소규모 입력에 적합   ㅇ삽입정렬: 우선순위 큐 (순서 리스트로 구현)"제자리 + stable" O(n^2): 느리다 - 소규모 입력에 적합  ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ  ㅇ힙정렬: 우선순위 큐 (힙으로 구현)"제자리 + unstable" O(nlog(n)): 빠르다 - 대규모 입력에 적합   ㅇ병합정렬: 분할통치"제자리 X + stable" O(nlog(n)): 빠르다 - 초대규모 입력 + stable 결과에 적합   ㅇ퀵정렬: 분할통치"제자리 + unstable".. 2024. 7. 7.
[알고리즘] ep1-6) 퀵정렬(quick sort) ㅇ퀵정렬(quick sort): 분할통치법에 기초한 정렬 알고리즘"제자리 + unstable" O(nlog(n))※ 최악의 시간 복잡도: O(n^2) (이미 정렬된 리스트에서 항상 최악의 피벗을 선택하는 경우) 이름에서 알 수 있듯이 복잡하지만 매우 효율적인 알고리즘이다 일각에서는 이렇게 지칭한다 '살아있는 레전드' *피벗(pivot): 기준점1. 피벗을 기준점으로 잡는다2. 피벗보다 작으면 왼쪽에, 피벗보다 크면 오른쪽에 둔다3. 왼쪽과 오른쪽을 각각 정복한다  [분할 함수(partition 함수) 과정]  다양한 피봇 선정 방식 -> 다양한 퀵소트 버전    (참고)퀵정렬 트리: quickSort의 실행을 이진트리로 보이기이진트리의 각 노드는 quickSort의 재귀호출을 표현하며 다음을 저장- 실행.. 2024. 7. 7.
[알고리즘] ep1-5) 병합정렬(merge sort) ㅁ분할정복법 == 분할통치법(Divide and Conquer): 문제를 작은 부분으로 나누어 해결한 후, 그 결과를 결합하여 전체 문제를 해결하는 방법e.g. 병합정렬, 퀵정렬, 이진탐색, 하노이탑   ㅇ병합정렬 = 합병정렬(merge sort): 비교 기반의 정렬 알고리즘 중 하나로, 분할 정복 기법을 사용"제자리 X + stable" O(nlog(n))폰 노이만이 개발했으며 stable 특성 때문에 실무에서 많이 사용된다  병합(merge) 예시 - 연결리스트로 구현한 merge 함수     (참고)      합병정렬 트리: mergeSort의 실행을 이진트리로 보이기이진트리의 각 노드는 mergeSort의 재귀호출을 표현하며 다음을 저장한다- 실행 이전의 무순리스트 및 분할- 실행 이후의 정렬리스.. 2024. 7. 5.
[알고리즘] ep1-4) 힙정렬(heap sort) 복습하고 오자!https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep1-3-%ED%9E%99heap [알고리즘] ep1-3) 힙(heap)*완전 이진 트리(Complete Binary Tree): 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리 ㅁ힙(heap): 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 완전 이진 트claremont.tistory.com    ㅇ힙정렬(heap sort): 힙을 이용하여 정렬하는 방식"제자리 + unstable" O(nlog(n)) 1. 원소들을 전부 힙에 삽입한다.2. 힙의 루트는 남은 수들 중에서 최솟값(or 최댓값)을 가지므로 루트를 출력하고 힙에.. 2024. 7. 4.

티스토리툴바