전체 글
-
검색트리(SearchTree)과외 - 알고리즘/과제 2018. 9. 6. 18:37
treeInsertContents이진 검색 트리(BST)에서 주어진 입력에 대하여 다음과 같이 treeInsert 함수로 원소를 재귀적으로 삽입 할 때 treeInsert 함수가 호출 되는 횟수를 출력하라. treeInsert(r, x){ if(t = NIL) ket[r] = x; left[r] = NIL; right[r] = NIL; return r; if(x < ket[t]) left[t] = treeInsert(left[t], x); return t else right[t] = treeInsert(right[t], x); return t; }Input첫 줄에는 BST에 삽입해야 하는 원소의 개수 n(1x; switch(cmd){ case 'I': tree.treeInsert(x); break; ca..
-
선택(Select)과외 - 알고리즘/과제 2018. 9. 6. 18:36
SelectContents정렬반을 졸업한 소년 빌게이츠는 정렬과는 다른 새로운 문제를 만났다. 문제는 n개의 원소가 아무런 규칙 없이 저장된 배열에서 i번째 작은 원소를 찾는 것이다. 이러한 문제를 다루는 알고리즘을 선택 알고리즘이라 하는데 평균적으로 선형시간(O(n))이 걸리는 선택 알고리즘은 다음과 같다. select(A[], p, r, i) //배열 A[p..r]에서 i번째를 찾는다.{ if(p == r) return A[p]; q = partition(A, p, r); //QuickSort에서 partition과 같음 k = q - p + 1; if(i k) return select(A, q + 1, r, i -..
-
정렬(Sort)과외 - 알고리즘/과제 2018. 9. 6. 18:35
Selection-SortContents소년 빌게이츠는 학원에서 알고리즘 수업에서 선택정렬을 배웠다. 학원 선생님이 말하길 제일 큰 원소를 찾아서 뒤로 옮기면 정렬이 된다고 했다. 학원 선생님이 전수해준 비기는 다음과 같다. 1. A[1..k]중 가장 큰 원소를 찾는다. 2. 가장 큰 원소를 A[k]와 바꾼다. (매번의 반복 마다 swap은 한번만 일어나야한다.) 3. 배열의 크기가 n이라고 할 때, k = n 부터 k = 2 까지 위 과정을 반복한다. 소년 빌게이츠는 수행 시간을 측정하기 위해 1번에서 최대값을 찾기 위해 수행하는 비교 횟수를 다음의 조건에 따라 측정하기로 했다. 여러분이 해야하는 일은 소년 빌게이츠를 도와 선택정렬의 비교 회수를 출력하면 된다. 선택정렬은 소년 빌게이츠가 배운대로 구현..
-
백준 1701 CubeditorAlgorithm/BOJ(백준) 2018. 9. 6. 16:28
문제 링크 : https://www.acmicpc.net/problem/1701※선행해야 할 알고리즘 : KMP Algorithm Algorithm부분 문자열마다의 pattern_table을 생성하여 그 중 값이 가장 큰 것을 return 한다.(해당 내용 : KMP Algorithm 참고) 1. 여기서 말하는 "부분 문자열" 마다의 의미는 예제 입력 "abcdabcabb"을 기준으로 다음과 같다. (1) abcdabcabb (부분 문자열 1) (2) bcdabcabb (부분 문자열 2) (3) cdabcabb (부분 문자열 3) . . . (10) b (부분 문자열 10) 2. "pattern_table"의 의미는 다음과 같다.문자열의 모든 부분 문자열의 접미사와 접두사가 같은 문자열의 문자 개수들을 ..
-
알고리즘 학습 방법Algorithm/이론 2018. 9. 6. 14:58
※ 알고리즘 학습 방법 순서도(커리큘럼) 1. 알고리즘과 입/출력2. 자료구조 1- 큐/스택/데크- 문자열3. 다이나믹 프로그래밍 14. 알고리즘 수학 1- GCD/LCM- 소수5. 정렬6. 그래프 1- 정의와 표현방법- 탐색 (DFS/BFS)- 모델링7. 트리 1- 순회- 저장- 트리와 관련한 알고리즘8. 그리디9~10. 분할 정복- 이분 탐색- 머지 소트/퀵 소트- 가장 가까운 두 점11~12. 완전 탐색- 비트마스크- 순열- 부르트 포스- 백트래킹13. 자료구조 2- 스택 2- 서로소 집합(Disjoint-Set)- 힙과 힙 소트- 이진 탐색 트리 (BST)14. 다이나믹 프로그래밍 2 15. 수학 2- 분할 정복- 이항 계수- 카탈란 수- 오일러 피 함수- 확장 유클리드 알고리즘16. 그래프 2-..