1. 트리의 순회 이 문제는 트리의 preorder와 inorder가 주어졌을 때 이 정보를 가지고 postorder을 생성하는 문제이다. preorder는 각 서브트리의 루트를 먼저 출력한다. 따라서 preord[0]은 이 트리의 루트가된다. inorder는 서브트리의 왼쪽끝쪽을 조사한다음 서브트리의 루트를 출력한다음 오른쪽을 조사한다. 즉, 트리의 루트가 출력될때 이미 이 루트의 왼쪽 부분은 탐색을 마친 상태이다. 트리의 루트의 오른쪽은 오른쪽 서브 트리이다. 위의 각 순회의 특성을 이용하여 재귀적으로 함수를 구현하면 답을 쉽게 얻을 수 있다. 이 코드의 시간복잡도는 r 과 for문에 지배된다 for문은 각 단계에서 대략 n번 수행되고 r = n이므로 O(N^2)의 시간 복잡도를 가진다. 1 2 3 ..

1. 완전 탐색 이 문제는 주어진 문자열 입력에 대해 중복된 부분 문자열의 개수를 센다음 k개 이상의 중복 문자열 중에서 가장 긴 부분 문자열을 찾는 문제이다. 하지만 부분 문자열을 전부 만들어서 카운트하면 시간안에 수행이 불가능하다. 2. 공통 접두사의 최대 길이 사용 접미사 배열을 만들고 공통 접두사의 최대 길이를 계산하면 시간안에 해결할 수 있다. 이 때 중요한 것은 k개를 더한것과 비교하는 것이다. 이는 k번째 접미사와 접두사가 일치하지않으면 0이되기 때문에 이는 완활히 작동된다. 다음은 책에있는 코드이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39..

1. 문자열 이 문제는 KMP알고리즘을 사용하면 간단하게 풀 수 있다. 아래 코드는 좀 복잡하게 구현하였는데, 사실 첫 상태와 비교하는게 아니라 이전 상태랑 비교하면 더 깔끔한 코드가 될 것이다. 또한 A를 시계방향으로 i만큼 돌린 결과가 B일때 이는 B를 반시계방향으로 i만큼 돌린 결과가 A라는 것을 이용하면 더 직관적 일 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include #include #include usi..

1. 문자열 현대의 컴퓨터의 많은 양의 데이터들은 거의 문자열이다. 때문에 문자열을 다루는 문제와 자료 구조는 전산학의 중요한 연구 주제이다. 문자열 검색 문제를 위한 kmp알고리즘과 문자열 처리의 스위스 칼이라고 할 수 있는 자료 구조 접미사 배열(suffix array)에 대해 알아보자. - 문자열 = S - 문자열의 길이 = |S| - 문자열 S의 i 번 = S[i] - 부분 문자열(substring) = S[i,..j] - 접두사(prefix) = 0번부터 특정 문자까지의 문자열 S[0..a] - 접미사(suffix) = 특정 문자에서 부터 끝까지의 문자열 S[b...] 2. 단순한 문자열의 검색 문자열이 A, B가 있을 때 문자열 A가 문자열 B의 부분 문자열로 포함하는지 확인하고 부분 문자열의..

1. 크리스마스 인형 이 문제는 두가지의 문제를 풀어야한다. 선물상자의 인덱스 0~n 주문한번: a번 박스 부터 b번 박스까지 구매 1. 산타가 아이들에게 같은양의 선물을 주고 남은 나머지가 0인 상자의 구간의 개수 2. 산타가 아이들에게 띄엄 띄엄 주문해서(중복x) 주문한번당 아이들에게 나머지 없이 나누어주는 최대의 주문 수 2. 1번 문제 1번문제에서 이 문제는 부분 구간의 부분합을 구해야한다는 것을 알 수 있다. psum[a] = 0~a 까지의 합 order(a, b) = a 에서 b까지 주문하고 총 인형의 개수 라고 하자. 아이들한테 남는거 없이 선물하므로, order(a, b) % child == 0 이 되어야함을 알 수 있다. order(a, b) = psum[b] - psum[a-1] ord..

1. 비트 마스크 문제 부울 배열들을 비트 마스크 로 풀어내는 문제이다. 과목 => 선수과목 학기 => 과목 학기마다 선수과목이 포함되어 있는지 확인하고. 강의를 들을 수 있는 과목을 선택하여 조합 탐색하면 쉽게 답을 구할 수 있다. tmpSelect = semester[j] & (~select); => 이번 학기에 들을 수 있는 수업중 이미 수강한것은 제외시킨다. => 최상위 비트또한 반전되어 없어진다. => 모든학생이 이번 학기에 들을 수 있는 강의들 if((tmpSelect&(1