본문 바로가기

Algorithm Problem

 (92)
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]..
Lesson 15. Caterpillar method - CountTriangles 1. 문제An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if it is possible to build a triangle with sides of lengths A[P], A[Q] and A[R]. In other words, triplet (P, Q, R) is triangular if 0 ≤ P   - A[P] + A[Q] > A[R],  - A[Q] + A[R] > A[P],  - A[R] + A[P] > A[Q].For example, consider array A such that:A[0] = 10A[1] = 2A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 12There are fou..

티스토리툴바