본문 바로가기

전체 글

 (152)
탐욕 알고리즘 (Greedy algorithm) 탐욕 알고리즘은 주어진 순간에 가장 최적의 경우를 선택하는 알고리즘이다.다시 말해, 현재 단계 관점에서 최선의 결정을 선택하는 것이다.따라서 지역적으로 최적을 선택하는 것이기 때문에, 문제에 따라, 최선의 접근법이 아닐 수도 있다.  만약 탐욕 알고리즘은 최선의 해를 내놓는다면, 보통 동적 프로그래밍(dynamic programming)이나 완전 탐색보다 빠르다.반대로, 최선의 해를 내놓지 못한다면, 동적 프로그래밍이나 완전 탐색이 최적의 접근법이 될 수 있다. 예시) 동전 교환문제주어진 동전을 가지고, 주어진 금액을 지불할 수 있는 최소 동전 개수를 찾는 문제.동전: [1, 2, 5]지불 금액: 6결과: 동전(1) 1개, 동전(5) 1개 이 문제는 동전이 어떻게 주어지냐에 따라, 그리디 알고리즘이 최적..
Lesson 16. Gready algorithm - TieRopes 1. 문제There are N ropes numbered from 0 to N − 1, whose lengths are given in an array A, lying on the floor in a line. For each I (0 ≤ I We say that two ropes I and I + 1 are adjacent. Two adjacent ropes can be tied together with a knot, and the length of the tied rope is the sum of lengths of both ropes. The resulting new rope can then be tied again.For a given integer K, the goal is to tie the ..
Lesson 16. Gready algorithm - MaxNonoverlappingSegments 1. 문제Located on a line are N segments, numbered from 0 to N − 1, whose positions are given in arrays A and B. For each I (0 ≤ I Two segments I and J, such that I ≠ J, are overlapping if they share at least one common point. In other words, A[I] ≤ A[J] ≤ B[I] or A[J] ≤ A[I] ≤ B[J].We say that the set of segments is non-overlapping if it contains no two overlapping segments. The goal is to find th..
Lesson 15. Caterpillar method - MinAbsSumOfTwo #5 이미 100%를 달성했지만, 좀 더 좋은 코드로 만들어보자. 1. 문제에 대한 고찰이 문제에서 요구하는 값은 결국 0이다.물론 0이 나올지 안나올지는 알 수 없으나, 나오고 안나오고의 문제는 접어두고, 단순히 최적의 해가 무엇이냐 하면 0이다.즉, 절대값이 0에 가까워 지도록, 계산해야할 값들을 선택하면 된다. 예시)left      rightA[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]-10-78912131415 A[0] + A[7] = (-10) + 15 = 5 5는 0보다 크다 →  0에 더 가깝게 만들기 위해서는 최대값을 더 작게(right - 1) 만들어야 한다. A[0] + A[6] = (-10) + 14 = 4 4는 0보다 크다 →  0에 더 가깝게 만들기 위해서는 최대값을 더 ..
Lesson 15. Caterpillar method - MinAbsSumOfTwo #4 (속도 개선-3) 1. 속도 개선 아이디어지금까지 모든 반복문은 항상 시작위치가 정해져 있었다.최소값: 0번째부터 시작최대값: (N - 1)번째부터 시작 그런데 꼭 이렇게 끝에서부터 검색을 해야 할까? Vector A의 요소들 간에 값 차이가 매우 클수도 있지만, 만약 매우 오밀조밀하다면?처음부터 다시 찾지 말고, 이전에 찾은 최소 값을 기준으로 검색하는 것이 더 빠르다. 예시)A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]-10-78912131415 A[0] + A[7] = |(-10) + 15| = 5A[0] + A[6] = |(-10) + 14| = 4A[0] + A[5] = |(-10) + 13| = 3A[0] + A[4] = |(-10) + 12| = 2 A[0] + A[3] = |(-10) + 9| ..
Lesson 15. Caterpillar method - MinAbsSumOfTwo #3 (속도 개선-2) 1. 속도 개선 아이디어Vector A에서 음수와 양수를 분리해보자.'음수 + 음수', '양수 + 양수'와 같은 불필요한 연산을 줄일 수 있다.또한 Vector A가 음수 혹은 양수로만 구성되어 있을 경우, 정렬을 통해 별도 검색없이 바로 결과를 도출할 수 있다.(음수로만 구성되어 있을 경우, return (최대값 * 2) * -1)(양수로만 구성되어 있을 경우, return (최소값 * 2))  2. 코드 (C++)최소값을 찾는 로직은 이전과 동일하다.#include int solution(vector &A) { vector positive_numbers = {}; vector negative_numbers = {}; //split the positive and negative ..
Lesson 15. Caterpillar method - MinAbsSumOfTwo #2 (속도 개선-1) 1. 속도 개선 아이디어정렬을 통해 계산 횟수를 줄일 수 있다.데이터가 오름차순으로 정렬되어 있으면최소값 ----------------- 최대값 순으로 나열되어 있다. index i는 0번째(최소값)에서 시작하고,index j는 n-1번째(최대값)에서 시작해서, j 값을 줄여가면서(j--) 절대값을 찾는다면,index i에서의 최소값을 구할 수 있다.특히, 절대값이 어느 순간 커진다면, 중간에 탐색을 멈출 수 있다. 예시)A[0]A[1]A[2]A[3]A[4]A[5]A[6]-108910111213 A[0] + A[6] = |(-10) + 13| = 3A[0] + A[5] = |(-10) + 12| = 2A[0] + A[4] = |(-10) + 11| = 1 A[0] + A[3] = |(-10) + 10| ..
Lesson 15. Caterpillar method - MinAbsSumOfTwo #1 1. 문제Let A be a non-empty array consisting of N integers.The abs sum of two for a pair of indices (P, Q) is the absolute value |A[P] + A[Q]|, for 0 ≤ P ≤ Q For example, the following array A:A[0] = 1A[1] = 4A[2] = -3has pairs of indices (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2).The abs sum of two for the pair (0, 0) is A[0] + A[0] = |1 + 1| = 2.The abs sum of two for the pair (0, 1) is A[0]..

티스토리툴바