1. 시간 queue 모듈과 deque모듈을 이용하여 풀었을 때 queue모듈은 시간초과가 났고 deque모듈은 통과되였다. 기본적으로 두 모듈 모두 알고리즘은 똑같다. 2. 소스코드 (1) queue(시간초과) queue로 while문을 돌리기 위해선 매 반복마다 while(not q.empty()) 연산을 수행해야 하는데, 이것때문에 시간이 오래 걸린것으로 보인다 import queue N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(map(int,list(input())))) q=queue.Queue() q.put((0,0,0)) cL=[[[0,0] for i in range(M)] for j in range(N)] cL[0][..

1. 풀이 bfs로 풀어야 한다 Q. 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 2. 소스코드 import queue N,K=map(int,input().split()) q=queue.Queue() time=0 q.put(N) visitedL=[0]*100001 visit..

N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 1. dfs from collections import deque from copy import deepcopy N,M=map(int,input().split..

Q. 각각의 시계추의 무게가 주어질 때 ( ex) weight=[3, 1, 6, 2, 7, 30, 1] ) 시계추로 잴 수 없는 가장 작은 양의 정수는? 1. 풀이 오름차순으로 정렬된 weight를 앞에서 누적하여 더해가며, 다음으로 큰 숫자보다 그 합이 작을때 stop => 더이상 더할것이 없으므로 2. 소스코드 def solution(weight): weight.sort() length=len(weight) s=1 for i in range(length): if s

1. 풀이 (1) 현재 가지고 있는 기름으로 방문가능한 모든 주유소 중에 가장 기름을 많이 넣을 수 있는 주유소를 후보에 추가한다. (이때 후보주유소는 힙으로 관리한다. 게속 추가하고 매회 최댓값을 추출해야 하기 때문) (2) 후보(heap)에서 최댓값을 추출한다. (이때 방문횟수를 +1) * 만약 방문할 주유소가 없으면 답은 -1 2. 소스코드 import heapq import sys from collections import deque N=int(input()) point=[] for i in range(N): a,b=map(int,sys.stdin.readline().rstrip().split()) point.append([a,b]) L,P=map(int,input().split()) point...

1. 풀이 dp[i][j] : i에서 j문자열까지 만들 수 있는 길이 중 최대 dp[i][j]를 구하기 위해선 아래 두가지를 고려해주면 된다. ​ (1) (A[i]==a and A[j]==t) or (A[i]==g and A[j]==c) 인경우 dp[i+1][j-1]+2 => 양끝이 조건에 만족하면 KOI유전자 (2) dp[i][j]=max(dp[i][j-s]+dp[i+j+1-s][j] (k: 1~j-i)) => () + ()가 가능(각조합에서 최댓값 찾기) 2. 소스코드 A=input() size=len(A) dp=[[0 for j in range(size)] for i in range(size)] for j in range(1,size): for k in range(size-j): dp[k][j + ..