득이공간

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 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) ..

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 3-1 * Dynamic Programming - Multistage decision proccess * Dynamic - multistage, time-varying * Programming - 훈련과 병참지원을 위한 military schedule의 optimal program을 구하는 방법을 program이라고 했음. * 동적계획 - divide-and-conquer 알고리즘은 하향식(top-down) 해결법 - dynamic programming은 상향식(bottom-up approach) 해결법 - 작은 문제 -> 큰 문제 순서로 해결한다. - 인덱스를 조정해서 중복된 계산을 피한다. - 작..

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 2-1 * 분할정복(Divide-and-Conquer)식 설계 전략 - 분할(Divide) : 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다. - 정복(Conquer) : 나눈 작은 문제를 각각 해결한다. - 통합(Combine) : (필요하다면) 해결된 해답을 모은다. - 이러한 문제 해결 방법을 하향식(top-down) 접근방법이라고 한다. * 이분검색(binary search) : 재귀적방식 - 문제 : 크기가 n인 정렬된 배열 S에 x가 있는가? - 입력 : 양수 n, 배열 S[1..n], 키 x - 출력 : x가 S의 어디에 있는지의 위치. 만약 없으면, 0. index locati..

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 1-1 * 알고리즘 기원 - 페르시아의 수학자, 천문학자, 지리학자 알코와리즘 * 알고리즘 - 문제를 해결할 수 있는 잘 정의된(well defined) 유한(finite) 시간 내에 종료되는 계산적인(computational) 절차(procedure) - 확률적(probabilistic) 알고리즘은 무작위성을 포함한다. * 알고리즘 사용 예시 - 자율주행, 인공지능, 로봇, 메타버스, 암호화폐, NFT * 알고리즘 학습 목표 - Design(설계), Analysis(분석), Computational Complexity(계산복잡도), Application Capability(응용력) * 문제 분야 -..

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 9장. 다이나믹 프로그래밍 9-1. 다이나믹 프로그래밍 📌 9-1. 다이나믹 프로그래밍 * 다이나믹 프로그래밍 - 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 알고리즘 * 다이나믹 프로그래밍 특징 - 큰 문제를 작은 문제로 나눈다. - 작은 문제들이 반복되어 나타나고 사용되며 작은 문제들의 결과는 항상 같다. - 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하고 추후 테이블을 재사용할 수 있다. = 메모이제이션 기법 - 바텀-업(반복문), 탑-다운(재귀함수)로 구현 가능하다. *..

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 8장. 조합 8-1. 조합 📌 8-1. 조합 * 조합 - nCr: n개의 숫자에서 r개를 뽑는 경우의 수 - nCr = n! / (n-r)! r! * 순열 - nPr: n개의 숫자에서 r개를 뽑아 순서를 고려해 나열할 경우의 수 - nPr = n! / (n-r)! * 조합 동작 원리 1. 특정 문제 가정 2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 고려 - ex. 5C3 = 4C3 + 4C2, 점화식으로 표현: D[5][3] = D[4][2] + D[4][3] 3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출 - D[i][j] = ..