분류 전체보기
-
알고리즘/백준 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..
-
Develop/DevOps 2021. 10. 23. 16:41
AWS Community Day Online 2021 세션 수강! 인터넷 기반의 컴퓨팅을 Cloud라고 정의한다 1. AWS Network VPC (virtual Private Cloud) AWS 계정 전용의 가상 데이터 센터 (네트워크가 분리되어 있는 개인의 사설 network 센터 개념) region에 종속적 region 당 다수의 vpc 생성 가능 계정당 생성 가능한 vpc의 개수는 한정이 되어 있음 enterprise 환경에서는 다수의 vpc를 이용하는 경우가 다수 소규모 app의 경우 단일 vpc가 유리할 수도 있다! 1. 사용할 IP 범위 대역 구하기 CIDR notation 사용 ex) 172.16.0.0/16 (IP/subnet) 2. VPC 내부의 subnet 생성 subnet은 AZ에 ..
-
알고리즘/백준 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를 수행하며 최다 빈출 염기 서열을 ..