Algorithm & Problem Solving/그리디 알고리즘(Greedy)
-
[백준 1461] 도서관 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 2. 10. 16:18
www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치 www.acmicpc.net 문제풀이 N, M, arr : 입력값 negative, positive : 음수, 양수 리스트 distance : 책의 원래 위치까지 가야하는 최소 걸음 수 리스트 음수와 양수를 나누고, 절대값이 큰 것부터 M개씩 나눈 후, 그 중 절대값이 가장 큰 수 만큼 움직이면 된다. 가장 절대값이 큰 거리의 경우는 돌아오지 않아야 하는 예외를 처리해주어야 한다. 1. 음수, 양수로 나누기 - 절대값이 큰..
-
[백준 19639] 배틀로얄 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 2. 5. 20:59
www.acmicpc.net/problem/19639 19639번: 배틀로얄 첫 번째 줄에 X, Y, M (0 ≤ X, Y ≤ 100,000, 2 ≤ M ≤ 100,000)이 주어진다. M은 짝수다. 다음 X개의 줄에는 i번째 사람과 싸웠을 때 잃게 되는 체력이 주어진다. 이 수는 0 이상 M / 2 이하의 정수이다. www.acmicpc.net 문제풀이 X, Y, M : 입력값 damage : 싸웠을 때 잃게 되는 체력 heal : 아이템을 먹었을 때 얻게 되는 체력 max_M : 초기 M 현재 체력(M) 이 초기 M (max_M) // 2 이하일 경우 포션을 먹고, max_M // 2 초과일 경우 적들과 싸우는 방식의 그리디 알고리즘으로 해결할 수 있다. 1. 현재 M 값 확인하기 - M max_M ..
-
[백준 4889] 안정적인 문자열 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 2. 5. 02:11
www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 문제풀이 stack을 이용해 안정적이지 않은 경우 ans를 증가하는 방식으로 해결할 수 있다. 1. 현재 문자가 '{' 이면 stack에 append하기 2. 현재 문자가 '}' 이면 stack 에서 pop하기 - stack 이 비어있을 경우 안정적이지 않은 경우이므로 ans 증가 - 이 경우 안정적이지 않은 '}' 를 바꿔줘야 하므로 '{'를 stack에 append 3. stack 이 남아있을 경우, s..
-
[백준 2258] 정육점 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 2. 4. 16:54
www.acmicpc.net/problem/2258 2258번: 정육점 첫째 줄에 두 정수 N(1≤N≤100,000), M(1≤M≤2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는 www.acmicpc.net 문제풀이 N, M : 입력값 arr : (가격, 무게) 리스트 weight : 현재까지의 무게 same : 가격이 동일한 고기일 경우, 해당 가격만큼 결과에 더해주기 위한 변수 실버1 문제인데, 생각보다 많이 까다로운 그리디 알고리즘 문제였다. 처음에 우선순위 큐를 이용해 해결하려 하였는데, 계속 틀렸습니다를 받아서 결국 정답코드를 참고하였다. 생각보다 단순하게 생각하면 쉽게 해결할..
-
[백준 1041] 주사위 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 30. 02:02
www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 문제풀이 N, arr : 입력값 ans : 보이는 5면 합의 최소값 min_lists : 1, 2, 3 면의 주사위의 최소값 개인적으로 굉장히 어려운 문제였다 ㅠㅠ.. 주사위와 같은 기하적인 문제 생각하는 것이 너무 어렵다... 만들어지는 완성체는 큐브 모양인데, 큐브에서 각각의 블록이 보일 수 있는 면은 1, 2, 3 개 중 하나이다. 면이 1개 보이는 블록 개수 : 4 * (N - 2..
-
[백준 1263] 시간 관리 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 30. 00:37
www.acmicpc.net/problem/1263 1263번: 시간 관리 첫째 줄에 일의 수 N이 입력되고 다음 N(1≤N≤1,000)개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti(1≤Ti≤1,000)와 Si(1≤Si≤1,000,000)가 입력된다. www.acmicpc.net 문제풀이 N : 입력값 arr : i번째 작업의 (완료시간, 작업이 걸리는 시간) 작업의 완료 시간을 기준으로 가장 늦게 완료해도 되는 작업부터 시작해서 다른 일들의 작업 시간을 탐색하면서 시작 시간을 갱신하는 그리디 알고리즘으로 해결할 수 있다. 1. 작업의 완료 시간을 기준으로 역순으로 정렬하기 2. 첫 번째 작업의 최대 시작 시간을 시작으로 나머지 작업들 확인하기 - i번째 일을 끝마쳐야 하는 시간이 현재 시간보..
-
[백준 1715] 카드 정렬하기 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 28. 00:36
www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제풀이 N : 입력값 hq : 우선순위 큐 우선순위 큐를 이용해 가장 적은 두 수를 빼가면서 정답(ans)에 더해주면 된다. 어렵지 않은 그리디 알고리즘 문제이다. 1. 우선순위 큐에 입력하기 2. hq의 크기가 1이 될때까지 hq 안의 가장 작은 두 수를 빼면서 ans에 더해준다. - 더한 수를 다시 hq에 넣어준다. 코드 import sys import heapq if __name__ == ..
-
[백준 1744] 수 묶기 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 22. 23:08
www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제풀이 N, arr : 입력값 minus_cnt, plus_cnt, zero_cnt : 음수, 양수, 0 개수 그리디 알고리즘 문제인데, 극강의 하드코딩으로 해결하였다... 분명히 더 효율적인 방법이 많이 존재할 것이다. 예외 테스트케이스를 생각하면서 짜다보니 코드가 길어졌고, 결국 하드코딩이 되어버렸다...ㅠㅠ 1. 음수, 양수, 0 개수 세주기 2. 음수 계산하기 - 음수 개수가 짝수일 경우 짝지어서 곱..