알고리즘
-
알고리즘/백준 2021. 10. 24. 23:27
문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 a. 오답 및 시간 초과 import sys n = int(input()) data = [] for i in range(n): data.append([j for j in map(int, sys.stdin.readline().split())]) # 회의 시간이 짧은 순으로 정렬했음 -> 이러면 회의를 최대 갯수만큼 할 수 있을 거라고 생각했는데 # 반례 n=3, data = [[3,5],[1,4],[4,8]] data.sort(key=lambda x: x[1] - x[0]) # 회의실 사용 여부 _usage = [0 for i in range(max(x[1] for x..
-
알고리즘/백준 2021. 10. 24. 18:10
문제 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 a. 시간 초과 서류순위를 기준으로 오름차순 정렬을 수행한다 서류 순위가 1등인 이는 무조건 채용이 될 것이므로, [1: 지원자수]의 범위에 대하여 합격 여부를 확인한다 지원자보다 서류 순위가 높은 모든 이에 대하여, 면접 순위를 비교한다 서류/면접 순위가 모두 떨어지는 이를 합격자 명수에서 제외한다 해당 풀이의 경우 O(N^2)의 시간복잡도를 가지게 된다. 시간 초과로 실패 import sys T = int(input()) fo..
-
알고리즘/백준 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를 수행하며 최다 빈출 염기 서열을 ..
-
알고리즘/프로그래머스 2021. 10. 18. 21:34
문제 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 a. 시간 초과 풀이 범위 내의 index에서 최대 수를 구하는 것을 반복하는 방식으로 문제를 풀이하였다. 만들어야 하는 자리 수는 number의 길이 - k개이고, 가장 높은 자리의 숫자부터 차례로 결정하여 문자열을 얻어내야 한다 start_index = 0, size = (숫자의 길이) - (제거해야 할 숫자 k개) - 1 로 설정 k개를 제거할 때까지, 삭제 가능한 범위 내에서 최대 수를 구하여 answer 문자열에 추가하기를 반복 k개를 제거한 뒤, 선택해야 할 숫자의 갯수를 충족하지 못한 경우, 남은 수를 answer 문자열에 추가 def solution(number, k): """ start_idx: 탐색을 시작할 s..