Cherry & Cherish

문제 : 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 접근 : 우선순위 큐를 사용해서 문제를 풀 수 있다. 이 문제는 여러 개의 강의실을 사용할 수 있지만, 비슷한 유형의 정렬 그리디 문제 중 한 개의 강의실을 여러개가 나눠서 예약하는 경우에 대한 문제가 많다. 그런 문제들로 연습하고, 이 문제를 풀어보면 더욱 좋을 것 같다. (백준 1931 회의실 배정 / SWEA 화물도..

문제 : 웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다. 웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오. 접근 : 처음 접근 방법은 마감 짧은 것, 점수 높은 것 순서로 정렬하여, 짧은 것 중 점수가 높은 것 선별 후에 문제를 풀어야겠다고 생각했다. score.sort(key=lambda x: (x[0], -x[1])) 방식으로 정렬을 했는데, 다음날이 마감인 것 중 2순위가 오늘 처리할 것 보다 점수가 높은 경우에 대해서 예외처리를 해줄 수 없어서 실패했다. 그 ..

문제 : 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다. 문자열의 뒤에 A를 추가한다. 문자열을 뒤집고 뒤에 B를 추가한다. 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 접근 : 그리디는 접근이 오래걸리는 문제인 것 같다. 접근하면 코드는 금방 풀리는데, 문제를 이해하고 푸는 방법을 설정하기까지 고민을 했다. T리스트에서 A..

문제 : 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, ..

문제 : 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 접근 : count를 통해서 풀어보려고 했는데 시간초과가 나왔고, 연속하는 숫자를 세기 위해서 while 문을 추가로 만들어서 s(start)와 e(end)라는 투포인터를 만들어서 문제를 풀어봤다. 하지만 또 시간초과가 나왔다. 그래서 결국 문제에 대한 풀이를 찾아봤고, 파이썬 내장 모듈인 bisect에 대해서 알게 되었다. bisect는 파이썬에 내장되어있는 이진탐색 모듈이다. bisect_left(list, value)는 list에서 value가 들어갈 가장 왼쪽 인덱스, bisect_r..

문제 : 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 접근 : 제한 숫자가 크기 때문에 시간 초과가 어떻게 해도 난다. 이진 탐색을 활용해서 문제를 풀었다. 풀이 : import sys def binary_search (array, target, start, end): while start target : end = mid - 1 else : start = mid + 1 return None N = int(input()) arr = sorted(list(map(int, sys.stdin.readline().split()))) M = int(i..

문제 : 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.) 접근 : lambda를 활용하면 아주 손쉽게 풀 수 있다. arr에 추가할때, 알아보기 쉽도록, 국어 영어, 수학, 이름 순서로 append 했다. key=lambda x : (-x[0], x[1], -x[2], x[3])로 설정함으로서, 국어는 감소하고 영어는 증가하고, 수학은 감소하고..

문제 : 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 접근 : lambda를 활용해서 첫 번째 인자인 나이만 정렬하도록 했다. 정렬 문제는 출력 시 타입을 잘 확인해야 한다. 답은 맞는데 type 때문에 실패 처리된 케이스가 있었다. 풀이 : import sys n = int(sys.stdin.readline()) arr = [] for i in range(n): arr.append(list(sys.stdin.readline().split())) arr.sort(key=lambda x: int(x[0])) for i in range(n): print(ar..