알고리즘

1학기 동안 진행될 알고리즘 실습 과목의 수업 진행 경과를 작성해보도록 하겠습니다. Visual Studio(VSC 아님)를 사용하신다고 하셔서 맥 유저인 저는 어쩔 수 없이 실습실 PC를 이용해야 합니다. 그거야 힘든 일이 아니죠. 하지만 저는 OT 당일날 똥컴 자

What is Algorithm? '문제(Problem)'를 해결하는 단계별 절차를 체계적으로 기술한 것 하나의 문제에 대해 다양한 솔루션이 존재 솔루션에 따라 성능의 차이가 존재 (시간 성능, 공간 성능) ⠀⠀ 문제의 요구 조건 입력(Input)과 출력(Output)으로 명시할 수 있다. -> 알고리즘은 입력으로부터 출력을 만드는 과정...

정렬이 중요한 이유 컴퓨팅 작업에서 가장 많은 시간을 차지하는 것은 저장과 검색 정렬된 데이터의 검색은 $$O(log$$ $$n)$$, 정렬되지 않은 데이터의 검색은 $$O(n)$$ $$n$$이 큰 경우 정렬 시간의 차이로 인한 컴퓨팅 효율의 차이 역시 매우 크게 변화 Selection Sort Algorithm 리스트에서 가장 큰 원소를 찾는다. ...

분할 정복. 사실 이 개념도 자료구조에서 다뤘었지만, 복습 차원에서 다시 살펴보자. Algorithm 입력을 2개 또는 그 이상의 작은 입력으로 분리 나누어진 입력이 쉽게 처리될 수 있는 크기면 처리, 그렇지 않으면 다시 분리 필요시, 처리된 각각의 작은 입력값을 결합하여 하나의 결과 생성 ⠀⠀ Merge Sort에서의 Divide and Co...

Dynamic Programming Divide and Conquer와 마찬가지로 문제의 Instance를 작게 분리 작은 Instance부터 Bottom-Up 형태로 계산한 결과를 배열(또는 테이블)에 저장하고 상위 Instance 계산 시 사용 Divide and Conquer를 사용할 때, 분해된 Sub Instance 간에 상호 관련이 있을 경우 비...

Chained Matrix Multiplication Matrix Multiplication 세 개 이상의 행렬곱을 수행한다면 계산 순서에 따라 곱셈 횟수가 달라짐 Goal : 곱셈 횟수가 가장 적은 곱셈 순서 결정 Brute-Force algorithm: Exponential Time Principal of Optimality 성립 → Dyn...

Greedy Algorithm Greedy Approach 현재 상태에서 최적의 다음 상태를 선택하는 접근 방법 이전 선택을 고려하지 않고 미래의 선택도 고려 X Greedy라는 부정적인 단어를 사용했지만 매우 효율적이고 쉽게 결과를 만들 수 있는 방법 Instance를 더 작은 Instance로 분리할 필요 X Selection - Fe...

Scheduling Scheduling: 실행 시간이 서로 다른 Job들을 실행할 때 'Time in the System'을 최소화 하는 Job 실행 순서를 정하는 것 Time in the System: Job이 실행될 때 까지의 대기 시간과 Job의 실행 시간의 합 과거에 Disk Scheduling, Elevator Scheduling 등에 사용...

Graph Coloring m-Coloring Problem Graph의 각 Node를 서로 다른 m개의 색을 사용해서 칠하되 인접한 Node는 색이 서로 달라야 함 m의 값에 따라 달라지는 별개의 문제 Graph가 주어졌을 때 m = 2이면 Solution이 없는 경우가 많다. Graph Coloring Graph Coloring의 주요 Applicat...

Branch and Bound Backtracking Algorithm과 마찬가지로 State Space Tree를 사용하지만 Traversing 순서를 다르게 적용 차이점 Tree Traversal 제한 X (Breadth-First or Best-First) Optimization Problem에만 사용 Tree의 각 Node에서 Bound를 검...