알고리즘/백준
-
알고리즘/백준 2021. 10. 24. 16:52
문제 12845번: 모두의 마블 영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다. 이번 이 www.acmicpc.net 풀이 레벨이 제일 큰 카드를 기준으로 골드의 값을 업데이트해나가면 되는 greedy 문제이다. a. 풀이 1) 가장 레벨값이 큰 카드를 찾는다 2) 1)에서 얻은 카드의 (왼쪽,오른쪽) 카드 중 레벨값이 더 작은 것을 먼저 흡수한다 3) 골드값을 업데이트하고, 흡수한 카드를 list에서 제거한다 4) 카드가 1개만 남을 때까지 1)~3)을 반복 수행한다 n = int(input()) data = [i for i in map(int, input().split()..
-
알고리즘/백준 2021. 10. 24. 16:18
문제 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 수식의 합이 최소가 되도록 계산해야 하는 문자열 greedy 문제이다. a. 풀이 수식의 합이 최소가 되기 위해서는 - 연산자 뒤의 부분 수식의 값이 최대가 되어야 한다. 따라서 - 연산자를 기준으로 parsing을 수행했다. 수식에 + 연산자만 남아있다면 남아있는 수를 모두 더하고 break - 연산자가 존재한다면, 해당 index 이후의 부분수식(_data)을 수식(data)에서 제거한 뒤 부분 수식에 대한 합연산을 수행하는 것을 반복 dat..
-
알고리즘/백준 2021. 10. 23. 20:50
문제 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 수를 묶는 규칙을 모두 고려해야 하는 greedy 문제이다 a. 반례 처음에는 음수/양수/0에 대한 경우를 나누지 않고, 단순 오름차순 정렬 후 구간별로 최대합(_add) or 최대곱(_mul)을 구하여 더해주는 방향으로 접근하였으나 일부 테스트 케이스에 대해 실패하였다.. 반례를 찾아보니, 이 소스코드는 0 또는 음수에 대한 합/곱의 예외를 고려하지 못한다는 것을 발견했다 5 4 -1 0 1 2 작성했던 소스코드는 다음과 같다 n = int(inp..
-
알고리즘/백준 2021. 10. 23. 00:56
문제 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 어떤 플러그를 빼야 하는가에 대하여 Greedy하게 접근해야 했다. a. 반례 처음에는 단순히 기기의 사용 횟수를 기준으로 스케줄링을 하였는데, 이 방법으로 접근하면 사용 순서에 따른 우선순위가 고려되지 않게 된다. 따라서 가장 마지막에 쓰일 기기 플러그부터 제거하는 스케줄링 방식으로 다시 접근하여 해결하였다. 3 14 1 4 3 2 5 4 3 2 5 3 4 2 3 4 2 15 3 2 1 2 1 2 1 2 1 3 3 3 3 3 3 b. 최종 풀이 1...
-
알고리즘/백준 2021. 10. 22. 20:47
문제 https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 풀이 문자열을 순회하며 각 위치에서([0,m)) 가장 많이 사용된 물질(A, C, G, T)를 구하고, 그에 따른 hamming distance의 누적합을 구하면 된다. Greedy 보다는 Brute-Force에 가까운 것 같다. 1. 입력받은 DNA를 사전순으로 정렬 2. 입력받은 DNA에 대해 for loop를 수행하며 최다 빈출 염기 서열을 ..