득이공간

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net #include using namespace std; int Tree[10001]; void DFS(int Current, int End) { if (Current > End) { return; } int Mid = End + 1; for (int i = Current + 1; i Tree[Current]) { Mid = i; break; } } DFS(Current + 1, Mid - 1); DFS(Mid, End); cout Tree[i]; if..

2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net #include using namespace std; int Max[2][3]; int Min[2][3]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; int A, B, C; cin >> A >> B >> C; Max[0][0] = A; Max[0][1] = B; Max[0][2] = C; Min[0][0] = A; Min[0][1] = B; Min[..

4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net #include #include #include #include #include using namespace std; typedef pair star; typedef tuple edge; vector Stars; vector EdgeList; int Root[100]; float MakeDistance(const star& A, const star& B) { float AX = A.first, AY = A.second; float BX = B.first, BY =..

2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net #include #include #include using namespace std; list Neighbors[1001]; int Entries[1001]; bool Visited[1001]; queue SQ; int Solution[1000]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, M; cin >> N >> M; for (i..

2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net #include #include using namespace std; const int Infinite = INT_MAX; const int MoveCost[5][5] = { { 0, 2, 2, 2, 2 }, { 0, 1, 3, 4, 3 }, { 0, 3, 1, 3, 4 }, { 0, 4, 3, 1, 3 }, { 0, 3, 4, 3, 1 } }; int DP[100000][5][5]; void Init() { for (int i..

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 8-1 * 키의 비교만으로 검색하는 경우 하한 * 검색(Searching) 문제 - n개의 키를 가진 배열 S와 어떤 키 x가 주어졌을 때, x = S[i]가 되는 첨자 i를 찾는다. - 만약 x가 배열 S에 없을 때는 오류로 처리한다. * 이분(이진) 검색 알고리즘 - 배열이 정렬이 되어 있는 경우 시간복잡도가 W(n) = lgn + 1이 되어서, 매우 효율적인 알고리즘이라고 할 수 있다. - 키의 비교만으로 검색을 수행하는 경우에는 이분 검색 알고리즘 보다 더 좋은 알고리즘은 존재할 수 없다. * 검색의 결정트리(decision tree) - 큰 마디(내부마디) : 키와 각 아이템을 비교하는 마디..

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 7-1 * 계산복잡도(Computational Complexity) - 얼마나 많은 계산을 해야지 문제가 풀릴 것인가 * 알고리즘의 분석 - 어떤 특정 알고리즘의 효율(efficiency)을 측정 - 시간복잡도(time complexity) - 공간복잡도(space/memory complexity) * 문제풀이 접근하는 2가지 방법 - 문제를 푸는 더 효율적인 알고리즘을 개발 - 더 효율적인 알고리즘 개발이 불가능함을 증명 * 문제의 분석 - 일반적으로 "계산복잡도 분석"이란 "문제의 분석"을 지칭 - 어떤 문제에 대해서 그 문제를 풀 수 있는 모든 알고리즘의 효율의 하한(lower-bound)을 결..

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 6-1 * Backtracking은 상태공간을 이동, Branch-and-Bound는 bound함수를 통해 가장 좋은 해를 찾음 * 최소화 문제 - 최소 거리의 트래킹코스를 찾는다. * 최대화 문제 - 최대 가치의 보물을 찾는다. * 분기한정법 특징 - 되추적 기법과 같이 상태공간트리를 구축해서 문제를 해결한다. - 최적의 해를 구하는 문제(optimization problem)에 적용할 수 있다. - 최적의 해를 구하기 위해서는 모든 해를 다 고려해 봐야하므로 트리의 마디를 순회(traverse)하는 방법에 구애 받지 않는다. * 분기한정법 원리 1. 각 마디를 검색할 때 마다, 그 마디가 유망(p..

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 5-1 * 트리 방문(tree traversal) 1. preorder : 자신->좌측->우측 2. inorder : 좌측->자신->우측 3. postorder : 좌측->우측->자신 4. level order : 깊이 순서 * 깊이 우선 검색 (depth-first search) - 뿌리마디(root)가 되는 마디(node)를 먼저 방문한 뒤, 그 마디의 모든 후손마디(descendant)들을 차례로 (보통 왼쪽에서 오른쪽으로) 방문한다. (= preorder tree traversal) void depth_first_tree_search(node v) { node u; visit v; for (e..

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 4-1 * 탐욕적 알고리즘 - 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택한다. - 그 순간의 선택은 그 당시(local)에는 최적이지만 그 결과들을 모아서 최종적인(global)해답을 만들었다고 해서 그 해답이 궁극적으로 최적이라는 보장이 없다. 따라서 탐욕적인 알고리즘은 항상 최적의 해답을 주는지 반드시 검증해야 한다. * 설계 절차 - 1. 선정 과정 (selection procedure) : 현재 상태에서 가장 좋으리라고 생각되는(greedy) 해답을 찾아서 해답모음(solution set)에 포함시킨다. - 2. 적정성 점검 (feasibility check) ..