본문 바로가기

Algorithm Problem

(95)

Candy Tribulation Problem: https://atcoder.jp/contests/abc432/tasks/abc432_c C - Candy TribulationAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 문제 요약작은 사탕과, 큰 사탕 두 종류의 사탕이 있다.작은 사탕의 한 개 무게는 X, 큰 사탕의 한 개 무게는 Y일 때,N명에게 동일한 무게의 사탕을 분배하려고 한다. N명이 받은 큰 사탕은 몇 개인가?단, 각각 받을 수 있는 최대 사탕 갯수는 모두 다르다. 예시1)입력설명(의미)3 6 83명, X = 6, Y = 811 10 13각..

Truck Driver Problem: https://atcoder.jp/contests/abc430/tasks/abc430_c C - Truck DriverAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 문제 요약'a' 와 'b'로만 이루어진 문자열S가 주어진다. (e.g. abbaaabaaba)문자열 S에서, 'a'가 A개 이상이고, 'b'가 B미만인 부분 문자열의 갯수를 구하여라. 예시1)SabbaaabaabaA4B2정답: 3부문 문자열1 (4, 8): aaaba부분 문자열2 (4, 9): aaabaa부분 문자열3 (5, 9): aabaa..

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 ..

이전 1 2 3 4 ··· 12 다음

티스토리툴바