2021/알고리즘 3

알고리즘 강의 3주차 - 그리디 알고리즘

그리디 (Greedy) 알고리즘 최적화 문제를 해결하기 위한 알고리즘 (입력) 데이터 간의 관계를 고려하지 않음 최소 신장 트리 (Minimum Spanning Tree) 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 최단 경로 (Shortest Path) 문제 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제 다익스트라 (Dijkstra) 최단 경로 알고리즘이 대표적 그리디 알고리즘은 최적화 문제를 해결하기 위한 알고리즘, 가능한 값중 최대, 최소값을 찾는문제 근시안적인 선택으로 부분적인 최적 해를 찾고, 모아서 최적 해를 찾는다. 번복하지 않는다. 단순한 특성을 보임. 제한적인 알고리즘 동전 거스름돈 -..

2021/알고리즘 2021.10.12

알고리즘 강의 2주차 - 분할 정복, 합병 정렬

분할 정복 - 주어진 문제를 더이상 나눌 수 없을 때까지 나누고, 나누어진 문제를 각각 풀어 답을 얻는 알고리즘 규칙은 정해져있지 않고 개발자의 창의력, 독창성, 경험에 달려있다 분할 정복 알고리즘을 설계하는 요령 분할 - 2개이상의 하위문제로 나눈다 정복 - 하위문제가 여전히 분할 가능하다면 하위집합에 대해 분할을 다시 수행, 아니라면 하위 문제를 푼다. 결합 - 위 두 과정에서 정복된 답을 취합한다. 부분문제 - 분할된 입력에 대한 문제 부분해 - 부분 문제의 해 문제해 - 부분해를 취합 합병 정렬 Merge Sort n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할 각각의 부분문제를 재귀적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복) 합병 정렬의 시간 복잡도 (층수)xO(n) ..

2021/알고리즘 2021.10.08

알고리즘 강의 1주차

알고리즘 첫걸음 ~ 알고리즘을 배우기 위한 준비 순차탐색의 개념 10개의 숫자 중 가장 큰 숫자를 찾는 방법 - 첫번째 숫자와 두번째 숫자를 비교하여 더 큰 수를 저장 > 저장된 값과 다음 값을 비교해가며 찾는 방법 이진탐색 오름차순으로 정렬된 숫자들을 반으로 나누어 비교하고, 또 반으로 나누어 탐색 그리디 알고리즘 거스름돈 문제 730원을 거슬러 줄 때 가장 이상적인 동전 갯수 => 6개 한붓그리기 문제 가짜 동전 찾기 문제 가장 오래된 알고리즘 최대공약수 알고리즘 알고리즘 표현 방법 자연어 순서도 Flow Chart 의사 코드 Pseudo Code (일반적으로 사용) 컴퓨터 프로그래밍 언어 알고리즘 분류 문제 해결 방식에 따른 분류 분할정복 알고리즘 - 주어진 문제를 나눌 수 없을 때까지 나누어 답을..

2021/알고리즘 2021.10.08