문제   이 문제에 대한 해결방법을 계속 고민하다 보면 dp를 사용해 주어야 할 것같은 느낌이 온다.이전의 평범한 배낭 문제와 비슷한데 그거보다 쉬운버전이라고 생각해주면 된다  일단 dp 문제 이기 때문에 점화식을 세워 주어야 하는데 우리가 구해야하는 것은 최소가 되는 동전의 개수라는 것을 명심해서이것을 기준으로 dp를 작성해주면 된다.  일단dp를 초기 설정할 때 k가 10000이하 이므로 가장 많은 동전의 개수인 10001로 초기화 해주거나 양의 무한대로 값을 설정해주어도 된다. 그리고 원소의 개수는 k+1로 해주면 된다. 왜냐하면 가치가 i 일때 최소가 되는 동전의 개수를 구해줄 것이므로 k가치 까지의 dp를 구해주면 되기 때문이다. inf = float('inf')dp = [inf] * (k+1..

문제  이 문제는 단순히 구현을 하는 것 보다도 어떻게 최적화된 방식으로 구현을 하느냐가 중요한 것 같다 처음에 단순구현한 코드는 시간초과가 발생했다 단순구현한 코드n = int(input())tops = list(map(int,input().split()))answer = [0] * ndef find(i,tops): for j in range(i-1,0,-1): #i보다 높이가 높아서 신호를 받은 탑이 있다면 리턴 if tops[j] >= tops[i]: print(tops[j],tops[i]) return j+1 return 0for i in range(n): answer[i] = find(i,tops)for i in r..

문제  일단 이 문제는 다리 위, 대기중인 트럭을 stack으로 생각하여 풀어주면 되는 문제이다. 매 초마다 다리위의 위치가 한칸씩 이동하는데 이때 최대무게를 넘도록 트럭이 들어가는 경우에만 예외처리 해주면 된다.그리고 계산은 대기중인 트럭이 없을 때까지를 기준으로 해주면 된다.  bridge = [0] * bridge_length  이런 식으로 다리를 다리길이만큼 0으로 채워 한칸씩으로 생각해주고 대기중인 트럭에서 조건에 맞는 다면 넣어주고 아니라면 넣지 않은채로 다리 내부의 위치가 한칸씩 이동한다고 생각해주면 된다. 전체코드def solution(bridge_length, weight, truck_weights): answer = 0 bridge = [0] * bridge_length ..

문제   이 문제는 전형적인 stack 문제다.  앞의 작업이 현재 날짜를 기준으로 출시가 불가능 하다면 뒤의 작업이 출시가능해도 출시할 수 없는 시스템이라고 이해하면 된다. 일단 각 작업이 며칠을 기준으로 출시가 가능한지 구해서 stack에 저장해두었다 이때 유의할 점은 progresses 배열을 역순으로 순회하면서 저장해야 앞의 작업이 stack의 제일 윗부분에 쌓일 수 있다는 것이다. #각 작업이 며칠 뒤 배포가 가능한지 저장 이때 앞의 작업이 나중에 쌓이도록 역순으로 저장 for i in range(len(progresses)-1,-1,-1): tmp = (100-progresses[i]) // speeds[i] if (100-progresses[i]) % speed..

문제    이 문제에서 가장 유의해야할 점은 주어진 값들의 제한 범위이다.문제를 보면 알 수 있듯이 무려 n이 10억이하의 숫자이다 이 부분을 꼭 유의해서 풀이를 찾아야한다  그렇기때문에 이분탐색 을 사용하여 문제를 해결해주었다.   이분탐색이란? 자료의 중간값(mid)이 원하는 target값인지 비교해주면서 mid가 target이 아니라면 대소비교를 통하여 범위를 조정해가면서 target을 찾는 알고리즘이다.   하지만 이 문제에서 mid값을 어떤걸로 주어야하는 지에 대한 부분이 어려웠다times 배열을 정렬해서 중간값을 준다해도 나누어 떨어질때를 구하는 것이기 때문에 times 내의 요소들의 순서가 우리가 구하고자하는 값의 순서와는 다르기 때문에 중간값으로 둘 수 없다.  해결방법  left = 1#..

문제  일단 이 문제를 보고 먼저 진입지점이 제일 작은순 그리고 그다음으로는 진출 지점이 작은 순으로 정렬을 해준 후에 겹치는 범위에 대해 필요한 카메라 개수를 계산하면 되겠다고 생각했다. 정렬routes.sort(key = lambda x:[x[0],x[1]])  먼저 이렇게 정렬을 수행 해준 후에 start, end 로 진입, 진출 범위의 값을 저장해 해당 범위를 벗어나는 경로를 만나면 start, end를 업데이트 해주어 다음에 카메라를 둘 지점에 대해서 구하도록 해주었다.  나의 코드def solution(routes): answer = 1 routes.sort(key = lambda x:[x[0],x[1]]) start = routes[0][0] end = routes[0]..

문제  문제를 요약하자면 최대 2명이하의 사람을 한 대의 보트에 담는데 보트의 무게제한을 넘지 않으면서 전부를 태울 수 있는 보트의 개수 최솟값을 구하는 문제이다. 처음 생각한 방법은 일단 사람을 무게순으로 정렬을 한뒤 맨앞과 맨뒤 이 두개의 시작점부터 중간점으로 나아가는 방식으로 개수를 구해주려고 했다 초기코드(오답)def solution(people, limit): answer = 0 people.sort(reverse = True) s = 0 e = len(people)-1 while(s  하지만 하나의 테스트케이스에서 실패가 뜨고 효율성측면에서 실패가 떴다.. 그래서 이 방법을 기본토대로 큐를 사용해서 해결해줘야겠다는 생각이 들었다.   정답코드 (큐 사용)from co..

문제  이전의 도착지를 다시 출발지로 설정하여 재귀를 통해 문제를 해결해줄 수 있으므로 bfs보다는 dfs를 통해서 문제를 해결해주는게 적절한 문제이다. 이때 알파벳의 순서가 앞서는 경로를 우선시 해주므로 재귀함수를 실행하기전에 sort() 내장함수를 통해 정렬을 해주고가능한 경로가 2개이상인 경우도 있기때문에 이에대한 처리 또한 해주어야 한다.  나의  코드def solution(tickets): answer = [] #알파벳 순서가 앞서는 경로 먼저 방문하기 위해 처리 tickets.sort(key = lambda x:(x[0],x[1])) visited = [False] * len(tickets) def dfs(pre, path): #마지막에 하나 더 ..

문제     문제를 접하고서 경로를 찾는 것 자체는 최단경로 찾을 때처럼 해결해주면 될 것같은데 주어진 직사각형의 테두리만 따라서 경로를 찾아주는 것이 구현하기 너무 까다롭다는 생각이 들었다.   그리고 결국 이 부분은 구글링을 통해 도움을 얻었다. 이 부분을 해결할 때 크게 3가지의 단계가 필요하다 1. 사각형 내부에 포함되는 부분은 0으로 처리2. 경계선에 해당되는 부분은 1로 처리3. 좌표를 2배로 키워준다 (왜냐하면 ㄷ 자와 같은 형태의 경로를 탐색할때 ㅁ으로 인식될 수 있으므로 이를 방지하고자 좌표의 크기를 2배로 키워줌)  이 3가지 단계를 적용한 코드는  from collections import dequedef solution(rectangle, characterX, characterY, ..

문제  이 문제는 주어진 단어를 한개의 알파벳만 변환해주면서 target이라는 단어와 같도록 변환을 해주는데 이때 변환을 하는데 필요한 "최소" 단계 수를 구해주는 문제이다. 최소 단계를 구하는 문제이기때문에 bfs를 사용하여 문제를 풀어주었다. 이때 queue 를 사용해서 문제를 풀어주는데 queue에 다음에 들어갈 단어와 단계까지 같이 넣어주면 된다. 나의 코드from collections import dequedef solution(begin, target, words): answer = 0 #변환할 수 없는 경우 if target not in words: return answer return bfs(begin, target, words) def bfs..