본문 바로가기

🚗 Major Study (Bachelor)/🟨 Algorithm20

알고리즘 5주차 월요일 강의 Greedy Algorithm Dynamic Programming is Blind 뭔가 잘 보이지 않는 상태에서 푸는 문제의 느낌이라는 것. matrix chain이나 LCS같은 경우의 Time Complexity는 다음과 같다. 세타라고 표현을 해야 한다. (정정 필요) LCS의 경우 M과 N이 order가 비슷하다고 하면 세타 M^2까지 가능할 수 도 있다. 비교적 차수가 높게 나온다. 왜 그런가? Optimal solution을 계산할 때 선택이 굉장히 여러가지가 존재한다. 그 선택이 어느게 옳은 선택인지 모든 경우의 수를 고려해야 하기 때문이다. Example: MCM 맨처음 (1,6)에 있는 것 중 최적의 값을 위해서 총 5번의 곱셈을 계산하게 된다. 그 중 최적의 값인 노란색이 채택이 된다. .. 2022. 4. 4.

알고리즘 4주차 목요일 오픈북, 텍스북과 슬라이드(PDF로 가지고 있는 사람은 안된다). Master Theorem 을 어느 정도 주려고 한다. P3는 행렬을 곱하는 방법을 나타내고 있다. Divide and Conquer는 시간이 더 오래 걸린다. 똑같은 Subproblem을 계속 해서 풀어서 시간이 오래 걸린다. 세타N으로 표현하려면 정확이 N 번 만 실행되어야 하는데 Worst case와 Best case에 해당하는 것처럼 다양하게 되면 빅오를 사용하는 것이 좋다. Loop 이 있으면 Loop 만 봐도 된다. Memorization 방식도 Recursion을 하지만 저장하지 않은 부분에 대해서만 call하므로 동일하다. 2022. 3. 24.

알고리즘 4주차 월요일 강의 2022. 3. 24.

알고리즘 4주차 월요일 강의 Optimal Substructure 각각의 점을 찍으면 세로의 좌표부터 가로의 좌표로 가는 최단 거리를 나타내게 된다. Diagonol 한 것은 자기 자신에 대해 대응하므로 0으로 채워져있다. (1,3) 부터는 두가지 방법이 존재한다. 괄호를 할 수 있는 경우의 수로 나뉠 수 있다. 마지막 Solution은 (1,6)에 위치하게 된다. (3,6)의 경우, A3부터 A6까지 곱할 수 있는 경우를 생각해보자. Sub Problem에 대한 Solution이 존재해야 하고 그것들이 Optimal 해야 한다. Optimal Solution을 구할 때 이 전의 Sub Problem의 Solution은 Optimal 하다는 가정을 가지고 계산을 하므로 다시 계산하지 않아도 되는 Bottom up 방식이다. Opti.. 2022. 3. 20.

알고리즘 3주차 목요일 강의 Master Theorem 으로 풀 수 없는 경우도 존재한다. 엡실론은 1/1000도 되고 1도 되고 굉장히 많은 숫자도 성립한다. 2022. 3. 17.

알고리즘 3주차 월요일 강의 Exercise1 행렬 곱하기 문제: Iterative solution 이 사용된다. A와 B가 각각 nxn 행렬이라고 가정. 3번부터 7번까지가 곱하게 되는 과정. 3개의 for loop으로 구성되어 있다. 7번 라인에서 곱하게 된다. C 행렬은 A의 row와 B의 column을 모두 곱하게 되는 과정이 있다. Time Complexity를 구하는 것은 for loop이면 구하기 쉽다. 세타 n^3이다. 그냥 n^3이라고 표현하면 안된다. Exercise 2 Divide and conquer로 풀게 되면 Recur로 하게 된다. C라는 매트릭스를 반반 4등분을 진행한다. A와 B도 마찬가지로 Divide를 진행한다. C라는 매트릭스는 A와 B 매트릭스 그룹으로 곱하게 된다. Element를 하나 남길 .. 2022. 3. 14.

알고리즘 2주차 목요일 0으로 수렴해야 한다. 들어가는 위치는 빅오 로그 n이랑 스퀘어 n 사이에 들어가는 것이 맞다. 빅오의 정의만 알면 바로 답할 수 있는 문제.... 2. 빅오에서 = 라는 표시는 포함관계에 해당하므로 수학적 표시와 다르다. 3. set 을 더하게 되면 가장 큰 order만 남으므로 True가 된다. 4. 빅오로 표현을 바꾸어도 충분히 맞긴 하지만 알고리즘이 주어지고 세타, 빅오로 표현이 가능하다면 세타 표현이 더 좋다. 5. 스몰 오의 경우 자신과 동일한 차수가 존재하면 성립할 수 없다. 1. max tree 를 만족하지 않는다. 2. Max tree 는 만족하지만 52 55에서 max 관계를 만족하지 않는다. 3. max heap 을 만족한다. Nearly Binary Tree 이면 되기 때문에 Com.. 2022. 3. 10.

알고리즘 2주차 월요일 강의 알고리즘 Growth of Functions function이 어떻게 자라는가. Time complexity에 관한 것을 배우는 과이다. 물론 더불어서 Space complexity도 분석하게 된다. 알고리즘이 어떤 문제를 푸는데 걸리는 시간이 있는데 어떤 order(차원)에서 적용이 되는지를, 효율성을 간단하게 보여주는 것이다. Input size N이 무한대로 갔을 때 A, B 알고리즘 어느 것이 더 오래걸리는 지를 범주화하자는 것이다. 물론 어떤 INput이 들어가는지에 따라서 차이가 있겠지만 어떤 급인지를 간단하게 보여주는 테크닉이 되겠다. Growth of Function N = 2일 때 N = 3일 때 이런 자세한 것을 다루지 않고 무한대로 갔을 때 어떻게 되는지에 대한 수학적 수식을 이용해서.. 2022. 3. 9.

알고리즘 1주차 월요일 강의 문제에 대한 알고리즘을 어떤 식으로 분석할지 이미 알고 있는 알고리즘으로 분석하는 시간 Unsorted List 에서 record 하나를 선택해서 Sorted List에 넣는다. 방바닥에 1부터 100까지 적혀져있는 숫자가 있고 카드 숫자가 안보인다고 가정하자. 만약 누가 정렬해서 1부터 100까지 정렬해서 가져오라고 하면 어떻게 할 것 인가? 대부분 임의의 카드 하나를 선택하는데 이는 이미 정렬된 값이고 다음 카드가 첫 번째 숫자보다 크면 오른손 작으면 왼손으로 넣는다. 같은 방법으로 위치시키면 왼손과 오른손에 카드가 정렬돼서 위치할 것이다. 노란색은 Sorted List이고 오른쪽은 Unsorted List이다. Bar가 그 사이를 구분한다고 하면 맨 왼쪽에 있는 Element는 Sorted List.. 2022. 3. 1.

알고리즘 1주차 월요일 HW 마다 배점은 다를 수 있다. 시험과 Quiz는 오프라인으로 진행할 것. 프로그래밍 HW이 아닌 Written Homework는 Late 허용을 하지 않는다. 2022. 2. 28.

이전 1 2 다음

티스토리툴바