오늘의 문제: 1374. 강의실오늘도 딱봐도 그리디 문제다. 그리고 그리디 문제 중 가장 유명한 문제격인 강의실 배정과 비슷한 문제로 보인다. 오늘도 그리디적 사고를 해보려고 한다.아이디어: 한 수업이 끝나고 가장 빨리 시작하는 수업을 바로 배정한다.어차피 문제에서 구해야 하는 것은 동시에 최소 몇개의 강의실이 필요한가 이다. 즉 퍼즐을 맞추듯이 하면 되는거 아닌가? 그래서 그냥 한 가지 케이스만 존재하는게 아닌가? 하는 생각이 들었다. 근데 알고리즘 분류에 우선순위 큐가 존재한다… 우선순위 큐도 무엇인지 알아놔야 하는 것일까? 일단 풀어보기로 했다. 강의 번호는 필요없어 보이니 대충 버리고 시작했다.처음 시작한 강의의 끝나는 시간을 저장함 → 해당 시간이 되기 전에는 빼지 않음.import heapqn..

오늘의 문제: 2212. 센서문제를 대충 읽어봤을 때는 그래프인가? 그리디인가? 확신이 서지 않았다. 우선 그리디 문제는 저번 문제 풀었던 거처럼 차분히 하나하나 정리하며 읽어보기로 했다.센서는 N개 설치하였고, K개의 집중국을 설치했다.집중국은 수신 가능 영역이 따로 있고, 센서들은 하나의 집중국이라도 닿아야 한다.입력으로 주어지는게 센서이다 보니 집중국의 수신 가능 영역 길이의 합이 어떤 걸 뜻하는지를 먼저 생각해야 겠다 싶었다. 일단 이쯤됐으면 그리디 문제라는 건 바로 파악이 되긴 했다.결국 문제를 푸는 걸 포기하고 검색했다…아이디어: 각 센서 사이의 거리를 먼저 계산하자.집중국이 설치된 지점은 따로 거리가 계산되지 않는다. 따라서 각 지점에 설치했을 때, 어느 지점에 설치하는 게 손해인지를 확인하..

오늘의 문제: 31926. 밤양갱오늘도 보자마자 그리디라는 생각이 들었다. 하지만 문제를 보아하니 실수하기 좋아보여서 어떤 사고 흐름을 가져야 하는지를 명확하게 해야겠다는 생각이 들었다. 사실 이게 애드 혹 문제라는 데 왜 애드 혹인가 처음에는 몰랐더니 단순 계산으로 해결돼서 그런게 아닐까 싶다.사고의 흐름N = 1 일 때는 daldidal 까지의 코스트 6daldidalgo 까지의 코스트는 8이후 추가되는 daldidan의 코스트 2따라서 N = 1일 때의 코스트 10n=int(input())def Nparser(n: int): i=0 while n: n//=2 i+=1 return iprint(Nparser(n)+9)이후 복사를 해나갈 수 있는 양이 2배씩 커..

오늘의 문제: 2847. 게임을 만든 동준이단순한 그리디 문제로 보인다. 사고의 흐름을 먼저 정리해보기로 했다.배열을 순회하기 편하도록 반대로 정렬하여 접근한다.현재 있는 위치의 값을 저장하고, 다음 값으로 넘어간다.저장한 값보다 탐색한 값이 작아지도록 값을 빼준다.빼는 값들의 합이 정답이다.이렇게만 접근한다면 문제없이 해결할 수 있을 것이라는 생각이 든다.n=int(input())l=[int(input()) for i in range(n)]l.reverse()value=l[0]del l[0]sum=0for i in l: if value>i: value=i else: temp=i-value+1 sum+=temp value=i-tempprint(..

오늘의 문제: 13417. 카드 문자열카드를 순서대로 순회하여 가장 사전 순으로 빠르도록 만드는게 미션이다. 문제는 딱 봐도 그리디인 것으로 보이고, 이제 아이디어를 떠올려야 한다.아이디어: 순회하며 만나는 대로 판단하여 배치한다그냥 단순하게 하나하나 돌면서, 맨앞에 있는 것과 비교하여 빠르면 앞으로, 아니면 뒤로 보내는 작업을 한다. 이유는 단순히 느릴 경우 앞으로 보내는게 손해가 되기 때문이다. 정말 그리디에 충실한 해결 방법인듯.from collections import dequet=int(input())for i in range(t): n=int(input()) l=input().split() r=deque() r.append(l[0]) del l[0] for i ..

오늘의 문제: 14916. 거스름돈오늘은 거스름돈을 계산하는 문제이다. 사실 거스름돈이 서로가 배수/약수 관계라면 단순 계산이 가능하겠지만 2원짜리 동전과 5원짜리 동전이기 때문에 무조건 거스름돈이 크다고 개수가 많지는 않다. 다만 문제 알고리즘 분류를 봐서도 알 수 있듯이 DP를 활용하여 해결하는 것이 가능하다. 거스름돈이 2씩 커질 때마다 1, 5씩 커질 때마다 1을 추가하는 배열을 만들면 선형시간으로 해결할 수 있는 것이다. 하지만 내가 예전에 풀었던 방식을 보면 아주 단순하게 수식으로 해결했다. 기본적으로 가장 거스름돈의 개수가 적을 때가 답이기에 무조건 5원을 우선적으로 내는게 맞긴하기에 그걸 우선적으로 생각한 수식이다.n=int(input())k=n%5if n in [1, 3]: print(-..

오늘의 문제: 7569. 토마토오늘 문제는 그래프의 대표적인 문제인 토마토이다. 토마토가 두 가지 버전이 있는데 그중에 3차원 형식으로 이루어진 문제이다. 3차원에서 그래프 탐색을 해야한다는 게 이 문제의 핵심이다. 확실히 3차원이 되다보니 아이디어가 쉽게 떠오르지 않아서 오늘은 검색 찬스를 쓰게 되었다… 아무래도 일반적인 그래프 탐색 방식이 아니라 그런지 쉽지 않았다. 노드와 간선으로 이루어진 그래프였으면 풀 수 있지 않았을까 싶기도 하다.from collections import dequem,n,h=map(int,input().split())graph=[[[*map(int,input().split())] for i in range(n)] for j in range(h)]visit=[[[-1]*m fo..

오늘의 문제: 25195. Yes or yes오늘 문제는 보자마자 큰일 났다는 생각이 제일 먼저 들었다. 그래프 관련된 문제 중 골드4면 꽤나 어려울 거라 생각해서 약간 시간을 잡아먹겠다는 생각이 들었다. 그래봤자 크게 어렵지 않겠지라는 생각으로 우선 풀어봤다.아이디어: 곰곰이를 만나지 않고 종료되면 틀리지 않을까.그래프 탐색을 종료하는 방법에 대해서 생각을 해봤을 때, (1) 곰곰이를 만나게 되면 그 경로는 앞으로 검사하지 않는다. (2) 곰곰이를 만나지 않고 경로 탐색이 종료될 경우 답은 yes가 된다.라는 대원칙을 가지고 시작해보려 한다.from collections import dequeimport sysinput=sys.stdin.readlinen,m=map(int,input().split())..