Leta Learns

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 꽤 많이 헤맸다. 처음엔 '(', ')' 에 대해서 투 포인터로 문제를 풀어야 하나? 싶어서 일단 입력받은 식을 해체했다. 수 따로 연산자 따로 리스트를 만들고 나면 어떻게든 되겠지~ 라는 생각으로 일단 식을 해체했는데 하고나니 어떻게 해야 할 지 모르겠어서 문제를 제대로 이해하기 위해 노력했다. 식의 값이 최솟값이 되기 위해서는 뺄셈을 기준으로 식을 나누는 게 가장 중요했다. 뺄셈이 ..

문제 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 문제가 이해가 안 돼서 한참 멍 때렸다. 테이프 길이가 L이고 좌우로 0.5씩 간격을 주어야 하므로 L-1 만큼을 막을 수 있다. 물이 새는 곳을 리스트로 받아 정렬한 후 물이 새기 시작하는 곳을 갱신한다. 현재 새는 곳보다 시작점이 큰 경우에는 이미 테이프로 막고 있는 것이기 때문에 고려할 필요가 없다. 따라서 시작점이 현재 새는 곳보다 작은 경우에만 시작점을 갱신하고 횟수..

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 이중 for문 안 쓰려고 슬라이싱 했다. ㅋㅋ import sys input = sys.stdin.readline n = int(input()) time = list(map(int, input().split())) time.sort() w = 0 #대기시간 for i in range(n): wait = time[:i+1] w += sum(wait) print(w)

문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 끝나는 시간 기준으로 정렬한 후에 시작하는 시간 기준으로도 정렬해주어야 한다는 거 깜빡해서 틀렸다. ㅋㅋ 그리디 기본 문제 좋아 import sys input = sys.stdin.readline n = int(input()) meet = [list(map(int, input().split())) for _ in range(n)] meet.sort(key=lambda x:(x[1], x[0])) t = 0 #time cnt = 0 for i in range(n): if t

문제 https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 어제 조금 정신 없는 상태에서 풀었더니 제출도 못하고 예제부터 틀렸었다. 어제는 일이 생겨서 다른 거 하다가 다시 못 풀어서 오늘 마저 풀었다. 어제 푼 코드를 보니 그냥 뭐 말도 안 되는 코드길래 ㅋㅋ 싹 다 갈아 엎었다. n: 리스트에 있는 점수의 개수. p: 랭킹 리스트의 개수. n = 10, p = 5의 경우, 리스트에 10개(n)의 점수가 있어도 랭킹 리..

문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 1700번에 비하면 쉬운 문제였다. (실버1) 순위를 입력받는 거라서 1이 좋은 건데 처음에 5가 좋은 거라고 착각했다. 문제 다시 읽어보다가 깨닫고 수정했다. 람다를 이용해서 서류 순위, 면접 순위 기준으로 다중 정렬을 했는데, 동석차가 없으니 서류 기준으로만 정렬하고 서류 1위면 일단 채용한다. (cnt = 1) 서류 1위의 면접 순위를 first 변수에 넣고 for..

문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 그리디 오랜만에 풀어서 어려웠다... 골드1이기도 했고...... 구조를 잡는 것부터 어려웠다. 빈 콘센트가 존재하는 경우 플러그를 꽂고, 이미 해당 기기가 꽂혀있는 경우에는 다시 꽂지 않아야 한다. 콘센트가 꽉 차 있고, 해당 기기가 꽂혀있지 않은 경우에는 두 가지를 고려해야 한다. 멀티탭에 꽂혀있는 기기들 중 이후에 재사용하는 기기가 없는 경우 재사용하는 기기가 있는 경우 1번의 경우 재..

문제 https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 예제는 잘 돌아가는데 시간초과가 나서 며칠동안 고군분투했던 문제.. 그냥 문제가 귀여워서 재밌어 보이길래 시도한 건데 푼 사람도 많이 없어서 구글링해도 시간초과 해결하는 법을 찾을 수 없었다.. 같이 스터디하는 친구도 시간초과 났었는데 해결한 후 본인 알고리즘 설명해준 거 듣고 나도 비슷한 방식으로 접근해봤다. 우선, 당근 맛의 최댓값을 가지려면..

문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 회의실 배정 문제를 제외하면 그리디는 처음 풀어본 것 같다. 정해진 틀이 있는 게 아니라 알고리즘 생각하고 구현하는 느낌이라서 풀면서 내가 지금 그리디로 잘 풀고 있는 게 맞나? 의문이 들었다. 가장 큰 동전부터 사용하기 위해서 입력받은 동전의 가치들을 역순으로 정렬한 후 for문을 사용하여 가능한 동전 수를 구하였다. 어쨌든 ..

그리디 알고리즘 공부 2021.06.29 - [HUFS/Algorithm] - Greedy Algorithm (그리디, 욕심쟁이 알고리즘) Greedy Algorithm (그리디, 욕심쟁이 알고리즘) 1. Greedy Algorithm : 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 Greedy 알고리즘은 최적해를 구하는 상황에서 사용하는 방법이다. 여러 경우 중 하나를 선택할 때 그 상황에서 가장 좋다고 letalearns.tistory.com 예제는 맞는데 시간 초과가 난다. 이중 for문을 사용해서 그런 것으로 추정되는데 이중 for문 안 쓰고 푸는 방법이 도무지 생각나지 않는다. 코드 길이라도 줄여보려고 다른 방식으로 코드를 하나 더 작성했으나 이것도 이중 for문을 사용해서인지 시간 초과..