알고리즘12 [ps 팁] 문제의 입력 제한값으로 알고리즘 유추하기 https://claremont.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-ep1-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B8%B0%EB%B3%B8-%EC%A7%80%EC%8B%9D%EB%93%A4 [자료구조] ep1) 자료구조 기본 지식들ㅇ다차원 배열- 3차원 배열 - 4차원 배열 ㅇ빅오(Big O) 표기법: 연산의 횟수를 대략적(점근적)으로 표기"최악의 case 실행시간을 고려한다" [예시](1) 7n-2: O(n)(2) 3n^3 + 20n^2 + 5: O(n^3)(3) 3log(n) + logclaremont.tistory.com 일반적으로 연산을 10^8 번 하면 1초다10^8 = 1초이 원리를 이용해.. 2024. 10. 23. [알고리즘] ep4+) 연쇄법 구현 문제) 크기 M인 해시테이블에 여러 개의 키 값을 입력받아 저장하고, 연쇄법을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오 [구현 조건]- 해시테이블은 크기가 M인 배열로 동적 할당한다.- 입력 키는 중복이 없는 자연수다.- 키 x에 대한 해시함수 h(x) = x % M 을 사용한다.- 삽입 시 충돌이 발생하는 경우, 해당 버켓 리스트의 맨 앞에 삽입한다. [입력]- 해시테이블의 크기 M을 입력받는다.- 삽입(i), 탐색(s), 삭제(d), 인쇄(p) 명령어를 순서에 상관없이 반복하여 입력받는다. i x> : 키 x를 해시테이블에 삽입s x> : 키 x가 해시테이블에 존재하는지 탐색d x> : 키 x가 해시테이블에 존재하면 삭제p : 해시테이블에 저장된 키들을 순서대로 인쇄(입출력 예시 참.. 2024. 7. 19. [알고리즘] ep3++) AVL 트리 구현 AVL 트리 구현종료(q) 명령 때까지 삽입(i), 탐색(s), 삭제(d), 인쇄(p), 명령을 반복 입력받아 수행i : 입력 에 대한 노드 생성 및 트리에 삽입d : 입력 가 트리에 존재하면 해당 노드 삭제 후 삭제된 키를 출력, 없으면 ‘X’를 출력s : 입력 가 트리에 존재하면 해당 키를 출력, 없으면 ‘X’를 출력 p: 현재 트리를 전위순회로 인쇄q: 프로그램 종료 주의: 중복 키가 없는 것으로 전제한다. 문제를 단순화하기 위해, 키만 존재하고 원소(element)는 없는 것으로 구현한다. main 함수는 반복적으로 명령을 입력받기 전에 빈(empty) 이진탐색트리를 초기화해야 한다 – 즉, 외부노드 1개로만 구성된 이진트리를 말한다. 힌트: 트리 노드 삭제 시, 삭제할 노드 w의 자식 중 하나.. 2024. 7. 17. [알고리즘] ep3+) 이진탐색트리(BST) 구현 BST(이진탐색트리) 구현종료(q) 명령 때까지 삽입(i), 탐색(s), 삭제(d), 인쇄(p), 명령을 반복 입력받아 수행i : 입력 에 대한 노드 생성 및 트리에 삽입d : 입력 가 트리에 존재하면 해당 노드 삭제 후 삭제된 키를 출력, 없으면 ‘X’를 출력s : 입력 가 트리에 존재하면 해당 키를 출력, 없으면 ‘X’를 출력 p: 현재 트리를 전위순회로 인쇄q: 프로그램 종료 주의: 중복 키가 없는 것으로 전제한다. 문제를 단순화하기 위해, 키만 존재하고 원소(element)는 없는 것으로 구현한다. main 함수는 반복적으로 명령을 입력받기 전에 빈(empty) 이진탐색트리를 초기화해야 한다 – 즉, 외부노드 1개로만 구성된 이진트리를 말한다. 힌트: 트리 노드 삭제 시, 삭제할 노드 w의 자식.. 2024. 7. 17. [알고리즘] 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. [알고리즘] 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. 이전 1 2 다음
