친절한 도현씨 친절한 도현씨

★ 접근 적당히 큰 입력 값의 크기, 구해야 하는 모든 경우의 수들을 종합적으로 봤을 때 바로 다이나믹 프로그래밍을 떠올렸다. ★ 풀이 1. 비행을 할 때 한 지점에 도달할 수 있는 경우의 수는 이전 x좌표에서 아래에서 위로 올라온 것과 이전 x좌표에서 위에서 아래로 내려온 경우의 수를 합친 경우이다. 2. 1번이 전부이다.... 항상 dp가 그렇죠 뭐..... 점화식만 세우면 끝이니... 근데 이 정도로 간단할 줄은.... 그래도 골드4인데... 황당... - 코드 import sys input = sys.stdin.readline d,m = map(int,input().split()) dp = [[0] * 4001 for _ in range(4001)] dp[1][1] = 1 for i in rang..

★ 접근법 문제에서 우선순위가 높은 프로세스 기준 프로세스가 같다면 id가 작은 것이 우선이라고 했을 때 => 우선순위, 최대 십만크기 바로 heapq를 떠올렸다. ★ 풀이법 나머지 프로세스의 우선순위를 1 증가시키는 방법만 떠올린다면 말도 안되게 쉬운 문제이다. 그대로 구현하면 최대 백만 초 * 최대 십만 개의 프로세스이기 때문에 시간초과가 발생한다. 나머지 프로세스의 우선순위를 1 증가시키는 것이 아닌 자신의 프로세스를 1 감소시키는 것이다. 우선순위는 상대적이기 때문에 나의 우선순위를 1 감소시키면 자연스럽게 나머지 프로세스의 우선순위가 1 증가된 것처럼 보인다. - 코드 import sys,heapq input = sys.stdin.readline t,n = map(int,input().split..

★ 글을 쓰게 된 동기 (기억할 수 있다고 생각했지만 계속 까먹어 기록을 하기로 결정!) @Autowired를 쓰고 안 쓰고의 차이가 무엇이지라는 의문이 들었다. ★ 차이를 알아보자! 생성자에서 의존성 주입을 받을 때 예를 들어 public OrderServiceImpl(MemberRepository memberRepository, DiscountPolicy discountPolicy) { this.memberRepository = memberRepository; this.discountPolicy = discountPolicy; } 이런 코드가 존재할 때 다른 곳에서 MemberRepository와 DiscountPolicy를 주입받고 있다고 생각했다. ★ 하지만! 실상은 그렇지 않았다. @Autowi..

※ 접근법 n,m을 더했을 때 문자열의 최대 길이는 십만이고 s와t가 주어진다. 0과 1의 조합이 어떻게 이루어졌을 때 s와 t가 가장 적게 이동해서 값을 만들어낼까?..... 시간제한은 1초 떠오르는 것은 그리디 알고리즘 밖에 없었다. 그렇다면 이것을 어떻게 그리디하게 풀까? 처음 떠올렸던 것은 그냥 간단하게 1을 기준으로 더 적게 움직이는 쪽에서 상대방에게 1을 맞추자였다. 이렇게 하니 최소가 아니었다. 여기서!!! 멘붕에 빠져서 헤매다가 결국 친구에게 힌트를 물어봤고 친구는 거리를 좁힌다는 생각을 해보라고 했다. ★ 풀이 1. s,t의 1의 좌표를 새로운 s_data, t_data에 저장한다. 2. 순서대로 하나씩 꺼내 둘의 차이를 구해서 answer에 계속 더한다. 3. answer을 홀수,짝수 ..

★ 접근법 처음에 n의 최댓값은 10개이고 입력으로 주어지는 문자의 최대 길이는 8개, 구해야하는 답은 최댓값인 것을 봤을 때 모든 경우의 수를 유추하는 백트래킹, dp 마지막으로 백트래킹으로 풀 수 없을 것 같아서 그리디 알고리즘을 떠올렸다. ★ 틀린 풀이법 1. 각 문자가 등장하는 가장 큰 자릿수, 등장 횟수를 리스트로 만든다. 2. 첫 번째 값에 대해서 오름차순으로 정렬하고 두 번째 인자에대해서는 첫 번째 인자가 같다면 오름차순으로 정렬하게 했다. 3. 예제도 다 맞았고 게시판에 있는 딱 하나의 반례 빼고 모든 반례가 통과했다. ★ 딱 하나의 반례 10 ABB BC BC BC BC BC BC BC BC BC ★ 틀린 코드 n = int(input()) data = [] dic = dict() for..

● 접근법 d와n의 최대 길이는 300,000이다. 이중 반복문을 쓸 경우 무조건 시간 초과가 발생한다. 그렇다면 여기서 반복 한 번 만에 이 문제를 해결해야 한다는 것을 알 수 있다. ● 풀이법 1. 피자는 자신보다 지름이 작은 오븐 밑으로는 내려 갈 수 없다. 즉, 오븐은 내림차순 정렬(진짜로 sort(reverse = True) 하라는 뜻이 아니다.) 현재 오븐 칸 보다 바로 밑에 있는 칸의 지름이 더 크다면 현재 오븐 칸의 지름으로 밑에 있는 칸의 지름을 바꿔도 된다는 뜻이다. 2. 그 다음 피자를 집어넣을 때 위에서 집어넣으면 의미없는 반복들을 진행해야 하기 때문에 밑에서부터 넣어주면 반복 한번에 피자를 오븐에 넣을 수 있는 지에 대한 여부를 알 수 있게 된다. ● 코드 d,n = map(int..

● 접근법 - 입력에서 n의 최대 크기가 123,456인데 대략 최대 십이만 이라고 생각해보자. 시간 제한은 1초이고 파이썬으로 for문 여러개를 썼다가는 시간 초과가 발생할 것이 뻔하다. 그럼 어떻게 시간 안에 최소를 구해야 할까? 여기서 생각은 단순해진다. for문을 한 번만 써야한다. 그리고 여기서 어떻게 한 번에 minHP를 구해야 하지? 뒤에서 부터 가면 되지 않을 까라는 생각을 했지만 t가 2일 경우 공격력이 점차 증가해 몬스터를 빨리 물리치니 뒤에서부터 계산할 수 없다는 것을 깨닫는다. 그럼 남은 방법은 앞에서부터 출발하는 하나의 방법이 남는다. ● 풀이법 1. 누적된 데미지, 공격력을 위한 변수 td, ta를 만든다. 2. t가 1일 경우 td를 빼주고 매 반복마다 td의 최솟값을 갱신해준..

● 접근 방법 문제에서 상하좌우로 이동한다는 힌트를 줘서 bfs인 것을 알았고 격자의 크기가 50으로 크지 않았기 때문에 bfs로 풀기로 결정했다. ● 풀이법 문제에서 '다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.' 이런 말을 한다. 이 말을 보고 물을 먼저 움직여야겠다고 생각했다. 왜냐하면 물과 고슴도치는 동시에 움직이는 것이지만 물을 먼저 움직여놓고 도치가 움직인다고 했을 때 그 칸에 물이 있으면 즉, 물이 이동할 예정인 칸이었으면 도치가 해당 칸으로는 이동하지 못하기 때문이다. 그러나 유의해야 할 점은 필자는 여기서 많이 헤맸는데 임의로 물을 먼저 움직인다고 가정했을 뿐이지 도치와 물은 동시에 움직이는 것이다. 즉, 물을 먼저 움직여 도치가 있는 칸에 물이 들어왔다고 하더라도 사..