Dp

2023년 9월 15일 알고리즘 문제풀이 문제 1 백준 11047 문제 링크 1차 시도 나의 생각 최소한의 동전을 사용하기 위해선 최대한 가치가 큰 동전을 많이 사용해야 한다. 이를 위해 입력받은 동전을 큐에 저장해 최대 힙을 사용하였다. 가장 큰 동전부터 가능한 갯수만큼 사용했다. 기존에는 이중 반복문을 사용해서 가장 큰 동전을 여러번 쓰도록 구현했지만 시간초과가 문제가 되었다. 따라서 몫과 나머지를 이용해서 한번만 실행되도록 바꾸었더니 통과되었다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys from heapq import heappush, heappop n, k = map(int, sys.stdin.readline().split()) coins = [] for _ in range(n): heappush(coins, -1*int(sys.stdin.readline())) cnt = 0 while k > 0 and coins: val = -1*coins[0] if k >= val: tmp = k//val cnt += tmp k %= val heappop(coins) print(cnt) 문제 2 백준 1541 문제 링크 ...

2023년 9월 7일 알고리즘 문제풀이 문제 1 백준 2748 문제 링크 1차 시도 나의 생각 기본적인 다이나믹 프로그래밍 문제였다. 재귀를 이용하면 시간초과가 되니 정의한 함수를 저장하는 배열을 만들어서 이를 참조하자. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys n = int(sys.stdin.readline()) dp = [0 for _ in range(n+1)] dp[1] = 1 def fibo(x): if x == 0: return dp[0] elif x == 1: return dp[1] else: if dp[x]: return dp[x] else: dp[x] = fibo(x-1) + fibo(x-2) return dp[x] print(fibo(n)) 문제 2 백준 1904 문제 링크 ...

2023년 8월 17일 알고리즘 문제풀이 문제 1 올바른 괄호 문제 링크 1차 시도 나의 생각 문자열을 앞부터 한글자씩 스택에 넣는다. 여는 괄호’(‘는 무조건 넣고, 닫는 괄호’)‘는 경우가 나누어진다. 스택에 마지막으로 들어가있는 원소가 여는 괄호면 합쳐서 올바른 괄호니 마지막에 들어간것을 pop해준다. 스택이 비어있으면 올바른 괄호가 아니라는 의미이다. 단어의 모든 글자를 순회했는데 아직 스택에 괄호가 남아있다면 올바르지 못한 괄호이다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 from collections import deque def solution(s): answer = True arr = list(s) q = deque() for i in range(len(s)): if arr[i] == '(': q.append(arr[i]) else: if not q or q[-1] != '(': return False elif q[-1] == '(': q.pop() continue if q: return False else: return answer 문제 2 디스크 컨트롤러 문제 링크 ...

2023년 8월 15일 알고리즘 문제풀이 문제 1 백준 1697 문제 링크 1차 시도 나의 생각 처음엔 재귀나 피보나치 등 여러 방법을 고민했다. 결국 다이나믹 프로그래밍으로 푸는게 적절하다고 생각했다. 맨처음 n에서 1초후 갈 수 있는 곳은 2n, n+1, n-1 이다. 이들을 큐에 저장하고 이들까지 도달하는데 걸린 시간도 같이 저장한다. 이 큐에서 하나씩 순회하며 2배한 좌표, +1, -1 한 좌표에 시간을 업데이트하고 큐에 다시 저장하는 것을 반복했다. 하지만 예시를 입력하면 올바른 정답이 나오지 않았다. 디버깅해봐야겠다. ...

1.개발 진행 및 완료상황 1주차 Python Algorithm 문제풀이 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 Quick sort를 이용하여 주어진 수를 오름차순으로 정렬하고 싶었다. 교과서로 Quick sort가 가장 빠르다고 읽어서, 그냥 가장 좋은 기능이겠거니 생각하였다. 코드도 복잡해지고 잘 안되어서 단순선택 정렬로 했다. 주어진 정수 정렬하여 출력하는 문제에서 메모리가 적게 주어졌다. 다른 문제들처럼 하니 메모리 초과 문제로 오답처리 되었다. 입력되는 수의 개수는 10만개 이상이였지만 주어지는 수의 크기는 1만 이하였기에 분명히 겹칠 가능성이 있을거라 생각했다. 그래서 1만1개짜리 리스트(인덱스와 그 위치가 나타내는 수를 일치시키기 위해서)를 만들어 각 수가 나올때마다 그 수를 인덱스로히는 리스트의 원소를 1씩 늘려준 후 각 인덱스값을 원소만큼 출력하도록 반복함수를 구성하였다. ...