지민 개발 블로그

문제 풀이:이 문항은 dp문항이다. 처음에 input을 arr list를 만들어 따로 받았는데, 그럴 필요가 없었다.arr로 따로 만들게 된 이유는, 이때까지 풀었던 몇 가지 dp 문항들이 min(dp[i-1] + arr[i],dp[i]) 이런식으로 자꾸 비교하면서 들어오길래 이상하게 생각없이 arr를 무작정 만들었었다. 그런데 해결이 안되니, 근본적인 이유는, 그냥 R일 때 G일 때 B일 때를 모두.. dp로 해보면 된다는 점이었음. '모두'라 함은 작을 수 있는 가능성이 있는 경우를 뜻함. 그래서, 시작이 무엇이니에 따라서 case가 3가지가 나오고 그때마다 그냥 가장 적게 드는 값을 탐색하다보면 답이 나온다. 코드:N = int(input())dp = []for _ in range(N):    dp..

미로 찾기 문항은 BFS를 이용했을 때 매우 효과적으로 해결할 수 있다.Why? : BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다.그러므로 (1,1)지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다. 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다. from collections import deque# N, M을 공백으로 구분하여 입력받기n, m = map(int,input().split())# 2차원 리스트의 맵 정보 입력받기graph = []for i in range(n):    graph.append(list(map(int,input())))# 이동할 네 방향 정의(상,하,좌,우)dx = [-1,1,0,..

알고리즘 분류)이분탐색, 매개 변수 탐색*매개 변수 탐색(Parametric Search): 이분 탐색을 사용하여 조건을 만족하는 최대값을 구하는 방법이다.*Parametric Search의 Detail은 https://stopmin.tistory.com/31 여기 정리해 놨음. Solution)이진탐색의 정의에 맞게 일단 비교해야 하는 값들을 sorted해서 House에 정리해줬다.start, end 포인트를 1과 가장 멀리 떨어져있는 집 사이의 거리로 설정했다. 그리고 이제 while (start 일단 기준점이 필요하다. house[0]을 기준으로 삼고, 일단 최소 거리 1이니 count = 1로 잡는다.그리고 for문을 돌린다. 집의 개수까지 돌리는데 만약 집의 거리가 기준점+중간값 보다 크거나 같..

이진탐색이 시간초과 해결의 Point였다. 처음에 이 문제를 우당탕탕 풀었을 때는 Case의 답 중 가장 큰 값에서 -1씩 해서 모두 돌려보는 과정으로 이 문제를 해결해보았다. 그러나 시간초과가 나왔다. 다른사람들 코드를 구경하다보니, start,end,mid가 있길래 '어 이거 이진탐색문항이구나..' 깨닫게 되었다. 알고보니 이진탐색을 활용하면 빠르게 풀이되는 문항이었다.이진탐색은 https://stopmin.tistory.com/28 에 간단하게 정리해두었다! 내가 처음 짠 코드들은 둘 다 순차탐색을 활용한 코드였기에 시간초과가 나올 수 밖에 없었다.  내가 처음 짠 2개의 시간초과 코드들)import sysK, N = map(int,sys.stdin.readline().split())string =..

보호되어 있는 글입니다.