반응형 학부공부/Algorithm_알고리즘14 07. Divide and Conquer(1) 안녕하세요. 오늘은 Divide and Conquer. 한국어로는 분할정복이라고 불리는 알고리즘을 소개할까 합니다. 정말 유명한 알고리즘입니다. 다만, Search, DP, Greedy에 비해는 등장빈도가 조금 낮다고 할 수 있습니다. 분할하고 정복하기 분할 : 주어진 문제를 여러개의 부분 문제로 나눈다 정복 : 분할된 문제를 푼다. 이때 문제의 크기가 작아지면 풀기 쉽다는 것을 이용한다. 분할정복 문제 자체는 등장빈도가 조금 낮을 수 있다고 말씀드렸지만, 분할이라는 접근은 매우 유용하기 때문에 다른 자료구조나 알고리즘의 basic이 되는 경우가 많습니다. 정복을 설명하면서 문제의 크기가 작아지면 풀기 쉽다는 것을 이용한다고 말씀드렸는데요. Resursive function의 base case처럼 바로 .. 2021. 11. 18. 06. Greedy Algorithm(2) Greedy Technique 01. Greedy Technique suggests constructing a solution to an optimization problem through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached On each step, the choice made must be(Feasible, i.e., it has to satisfy the problem’s constraints, locally optimal, i.e., it has to be the best local choi.. 2021. 11. 18. 05. Greedy Algorithm(1) 안녕하세요. 오늘은 Greedy Algorithm. 한국어로는 탐욕적 기법이라고 하는 알고리즘을 소개할까 합니다. DP와 함께 굉장히 유명한 알고리즘인데요. 개념 자체는 이해하기 쉽습니다. 하지만 어려운 문제도 많은만큼 마스터는 어려운 파트죠. 탐욕적 기법은 말 그대로 탐욕적으로 당장 눈에 보이는 것 중에 가장 맛있어 보이는 부분(이익) 만 취하겠다는 것입니다. 물론 이런 방법이 통하지 않는 경우도 있습니다. 도시락 데우기, 파일 합치기 등은 탐욕적 기법이 통하는 유명한 문제입니다. 이런 경우는 여러 번의 선택이 모두 잘못되지 않아야 합니다. 즉, 눈 앞에 보이는 것에 대해서 취한 전략이 그 이후에도 계속 성립해야 한다는 것입니다. 많은 문제들이 딱보고 그리디라고 판단하기는 어려운데요. 쉽게 반례가 떠오.. 2021. 11. 18. 04. Brute-force Search(2) Brute Force and Exhaustive Search 01. Brute Force A straightforward approach to solving a problem, usually directly based on the problem’s statement and definitions of the concepts involved “just do it!” the brute-force strategy is the one that is easiest to apply Examples: Computing 𝒂^𝒏(𝒂>𝟎, 𝒏 a nonnegative integer) : multiplying 1 by 𝑎 𝑛 times Computing 𝒏! The consecutive integer checking algo.. 2021. 11. 16. 03. Brute-force Search(1) 완전 탐색. 모든 경우를 다 생각하는 것입니다. 수학을 배울 때 끔찍한 기억이 떠오르는군요. 분명히 뭔 이야기를 하는지는 알겠는데 간단하게 풀자니 자신이 없어서 모든 경우를 다 고려해서 문제를 풀었던 기억 말입니다. 물론 완전탐색으로 원하는 시간 안에 다 풀리진 않습니다. 우리가 시간복잡도라는 것을 고안한 이유죠. https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 위의 문제가 좋은 예시가 될 수 있겠네요. 입력값이 최대 10만이죠. 모든 구간에 시도하면 1.. 2021. 11. 2. 02. 빅오 표기법, 시간복잡도, 공간복잡도(2) Fundamentals of the Analysis of Algorithm Efficiency 01. A general framework for analyzing algorithm efficiency Two kinds of efficiency: Time efficiency, also called time complexity, indicates how fast an algorithm in question runs. Space efficiency, also called space complexity, refers to the amount of memory units required by the algorithm in addition to the space needed for its input and outp.. 2021. 10. 27. 이전 1 2 3 다음 반응형
