빙글빙글 돌아가는 맷돌

직접 푼 것으로 틀릴 수 있음 주의 I. Red Black Tree: 1. 다음을 해결하여라 ① RedBlack tree에 A,L,O,R,I,T,H,M이 차례대로 insertion되는 과정을 나타내시오 ② ①에서 완성된 RedBlack tree에서 A,L,O,R,I,T,H,M이 차례대로 deletion되는 과정을 나타내시오 2. 다음을 해결하여라 ① RedBlack tree에 S,O,F,T,W,A,R,E이 차례대로 insertion되는 과정을 나타내시오 ② ①에서 완성된 RedBlack tree에서 S,O,F,T,W,A,R,E 이 차례대로 deletion되는 과정을 나타내시오 II. 2-3 트리 1. 다음과 같은 2-3 트리가 있다. 다음과 같은 동작이 순서대로 이루어질 때 2-3 트리 모양을 각각 그리..

2) T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1)+1 여기서, T(n-1)은 n-1개의 원반을 옮기는데 필요한 이동 횟수입니다. 1은 n번째 원반을 옮기는 횟수입니다. 따라서, T(n)은 T(n-1)의 두 배에 1을 더한 값과 같습니다. 3) 점화식 T(n) = 2^n - 1을 풀면 T(n)은 얼마인지 구할 수 있습니다. 여기서, ^는 거듭제곱을 나타냅니다. 따라서, T(n)은 2^n - 1입니다. (0 표기법 사용)

재귀적 해법은 중복 호출 문제가 발생할 수 있다 -e.g. 피보나치 →동적 프로그래밍을 하면 해결할 수 있다. 동적 프로그래밍의 적용 요건 ①최적 부분 구조 -큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함된다 ②재귀호출시 중복 -재귀적 해법으로 풀면 같은 문제에 대한 재귀 호출이 심하게 중복된다. 1) 행렬 경로 문제 -양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동한다 -이동 방법 (제약조건) ① 오른쪽이나 아래쪽으로만 이동할 수 있다 ② 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다 -목표 :행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최대가 되도록 한다 2) 돌 놓기 -3×N 테이블의 각 칸에 양 또는 음의 정..

가정: 상호배타적 집합만을 대상으로 하기에 교집합은 없다 Make-Set(x): 원소 x로만 이루어진 집합을 생성 Find-Set(x): 원소 x를 가지고 있는 집합을 알아냄 Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합 표현방법 : 연결리스트, 트리 1) 연결 리스트 -같은 집합의 원소들은 하나의 연결 리스트로 관리 -연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼음 [정리 1] 연결 리스트를 이용해 표현되는 배타적 집합에서 무게를 고려한 Union을 사용할 때, m번의 Make-Set, Union, Find-Set 중 n번이 Make- Set이라면 이들의 총 수행 시간은 O(m + n log n)이다. 2)트리 -같은 집합의 원소들은 하나의 트리로 관리 -자식 노드..

레코드 record -개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 (예) 사람의 레코드 주민번호, 이름, 집주소, 집 전화번호, 직장 전화번호, 필드 field -레코드에서 각각의 정보를 나타내는 부분 (예) 위 사람의 레코드에서 각각의 정보를 나타내는 부분 검색키 search key 또는 키 key - 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 -키는 하나의 필드로 이루어질 수도 있고, 두 개 이상의 필드로 이루어질 수도 있음 검색 트리 search tree -각 노드는 규칙에 맞도록 하나씩의 키를 갖고 있음 -키를 통해 해당 레코드가 저장된 위치를 알 수 있음 검색 트리 종류 ①자식 노드 수 -K진 검색 트리: 자식이 최대 k개 -이진 검색 트리(2개)/ 다진 검색 ..

1) i번 작은 수 찾기 -배열 A[p..r]에서 i번째 작은 원소를 찾는다 -선택 알고리즘의 수행 시간 범위 Ω(n): n개의 원소 각각을 한 번씩 보아야 함 O(nlogn): 정렬한 후 i 번째 원소를 고름 ∴nlogn~n -Quicksort 기반

정렬 알고리즘 -대부분 O(n^2) ~ O(nlogn) -기초 정렬 알고리즘 → 평균적으로 O(n^2) ; 선택, 버블, 삽입 정렬(이미 정렬된 상태일때는 삽입 O(n)) -고급 정렬 알고리즘 → 평균적으로 O(nlogn) : 퀵, 힙, 병합 정렬(퀵은 worst case일때 O(n^2)) -input이 특수한 성질을 만족하는 경우에는 O(n) sorting도 가능 Ⅰ. 기초 정렬 알고리즘 1) 선택정렬 -최대원소 찾기 → 최대원소와 맨 오른 쪽 원소 교환 → 맨 오른쪽 원소 제외 -하나의 원소만 남을 때 까지 반복 2) 버블 정렬 - 인접한 두 원소를 비교하면서 제일 큰 원소를 끝자리로 옮김 3) 삽입 정렬 -이미 정렬되어 있는 i개 짜리 배열에 하나의 원소를 더 더하여 i+1개 짜리 배열을 만드는 과..

알고리즘이란 -문제 해결 절차를 체계적으로 기술한 것 -문제 요구 조건 : 1) 입,출력 명시 2) 입력으로 출력 만드는 과정 알고리즘 분석 -해당 알고리즘이 자원(소요시간, 메모리 등)을 얼마나 소모하는지 -시간 분석 : 1) 최악/평균의 경우 2) 어느정도 입력에 어느 정도 시간이 필요한 지 짐작 3)입력 크기 대해 시간이 어떤 비율로 소요되는지로 표현 재귀 = 자기호출, 어떤 문제 안에 크기만 다를 뿐 같은 성격의 작은 문제들이 포함되어 있는 것 = factorial, 점화식 점근석 알고리즘 분석 -크기가 작은 문제는 알고리즘 효율성이 중요하지 않음 -크기가 충분히 큰 문제는 알고리즘 효율성 중요함 -입력의 크기가 춤분히 큰 경우에 대한 분석 - Ο, Ω, Θ, ω, ο 표기법 1) O( g(n) ..