본문 바로가기

Algorithm Problem

 (93)
Security 2 Problem: https://atcoder.jp/contests/abc407/tasks/abc407_c C - Security 2AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 문제 요약특별한 기능을 가진 버튼 A, B가 있다.입력된 값(input)을 만들기 위해서는, A,B 버튼을 최소 몇 번 사용해야 하는가? 초기값: 빈 문자열(S)버튼A: S에 0을 더한다버튼B: S의 모든 문자에 1을 더한다 예시)S: 1984버튼A: 19840버튼B: 20951 모든 문자는 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)로..
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]..

티스토리툴바