본문 바로가기
반응형

탐욕 알고리즘11

[Python] 프로그래머스 택배 배달과 수거하기(탐욕 알고리즘) 이번 문제는 Level2 문제입니다. 탐욕 알고리즘을 사용하면 풀 수 있는 문제입니다. 문제의 링크입니다. https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제는 등간격을 가지는 집들이 택배사를 기점으로 있을 때, 각각의 집에서 요청한 택배의 개수와 수거품들을 최소한의 거리 이동으로 모두 처리하는 문제입니다. 그림에서와 같이 왼쪽에 택배사가 있고, 여러 집들이 1의 거리를 사이로 위치하고 있습니다. 택배차에는 실을 수 있는 택배 상자의 개수가.. 2023. 4. 16.
[C/C++] 백준 #2156 포도주 시식(탐욕 알고리즘) 이번 문제는 탐욕 알고리즘의 범주로 놓아야할 것 같아서, 탐욕 알고리즘이라고 적기는 했지만, 문제에서 추천하는 알고리즘은 동적 계획법입니다. 동적 계획법이 더 맞을 수도 있겠죠. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 제가 생각한 알고리즘은 다음과 같습니다. \(fc_0\)은 현재 와인을 선택하지 않았을 때, 최대값입니다. \(fc_1\)은 이전 와인은 선택하지 않았지만, 현재 와인은 선택한 경우입니다. .. 2023. 4. 10.
[C/C++] 백준 #1912 연속합(탐욕 알고리즘) 주어진 수열에 대해서 연속합의 최대값을 찾는 것이 이번 문제입니다. 모두 다 양수라면 다 합친 것이 최대값이 될겁니다. 이와 비슷하게, 이번 알고리즘은 처음부터 차례대로 더해서 음수가 되지 않는 이상 양수 상태이면, 그것을 유지하는 것이 관건입니다. 알고리즘은 아주 간단합니다. 1. 현재의 합이 양수라면, 다음 수를 합한다. 2. 현재의 합이 음수이면, 현재의 합은 다음 수가 된다. 3. 현재의 합이 현재까지의 최대값보다 크다면, 최대값을 갱신한다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //-------------------------------------- // baekjoon #1912 - Sequential Sum // - by Aubrey Choi // - created at 20.. 2022. 11. 2.
[C/C++] 백준 #1744 수 묶기(탐욕 알고리즘) 이 문제는 탐욕 알고리즘으로 풀기에 괜찮은 문제입니다. 수열이 주어지면 그 수를 다른 수와 묶어서 곱한 후 더하거나 수 자체를 더하는 방법을 사용합니다. 한번 사용된 수는 다시 사용될 수 없습니다. 그리고 모든 수가 참여되어야 합니다. 이렇게 했을 때 최대의 합을 구하는 것이 문제입니다. 예를 들어서 ( 3, -2, 5, -7, 0 ) 이 있다고 한다면, (-2 * -7) + (3 * 5) + 0을 하면 가장 최대수를 얻게 됩니다. 원리는 간단합니다. 0 이하의 수와 1보다 큰 수들, 그리고 1의 갯수를 구합니다. \(1a = a\)이므로 1은 곱하기보다는 자기 자신으로 더하는 것이 더 큰 수가 됩니다. ( 2, 3, 5, 7 ) 이렇게 4개의 수가 있다면, 가장 큰 값을 얻기 위해서는 큰수끼리 곱해나가.. 2022. 10. 8.
[C/C++] 백준 #1715 카드 정렬하기(탐욕 알고리즘) 이번 문제는 카드 정렬하기이고요. 이 문제는 정렬된 여러개의 카드 더미가 있을 때, 모두 다 정렬하기 위해서 어떤 순으로 혼합(Merge)를 하는 것이 좋을까입니다. 각각 n과 m개의 카드를 가지고 있는 두 더미를 혼합을 하기 위해서는 \(O(n+m)\)의 비교횟수와 이동횟수를 가지고 있다는 것은 잘 알려져 있습니다. 실제 이동 횟수는 \(n+m\)번이 됩니다. 이 문제에서는 혼합을 하는 과정을 구현하는 것은 아닙니다. 정렬을 하기 위해서는 우리는 두 더미를 혼합하게 되는데, 혼합하는 순서에 따라서 전체적인 이동 횟수가 달라지게 됩니다. 더하기 연산을 할 때, 그 결과값을 모두 더하는 것과 같습니다. 3, 5, 7, 9 개의 카드가 있는 더미를 생각한다면, 1) 3 + 5 = 8 --> 총 이동횟수 : .. 2022. 10. 1.
728x90

티스토리툴바