나의 개발일지

문제 : https://www.acmicpc.net/problem/17202 DP 두 개의 번호를 풀이에 맞는 형태로 하나의 dp 리스트에 담는다. 점화식 : dp[i] = (dp[i] + dp[i+1]) % 10 dp.pop()으로 맨 뒤의 요소를 뺀다. 두 자리가 완성되면 종료, 출력 a = list(map(int, input())) b = list(map(int, input())) dp = [] for i in range(8): dp.append(a[i]) dp.append(b[i]) while len(dp) != 2: for i in range(len(dp)-1): dp[i] = (dp[i] + dp[i+1]) % 10 dp.pop() print(dp[0], end="") print(dp[1])

문제 : https://www.acmicpc.net/problem/24416 피보나치 수를 직접 재귀를 구현해서 풀면 시간초과가 뜬다. n에 해당하는 피보나치 수를 재귀로 구한 값과 재귀가 호출된 횟수는 같아서 dp로 얻은 값을 리턴함 n = int(input()) def dp_fibo(n): dp = [1, 1] cnt = 0 for i in range(2, n): dp.append(dp[i-2]+dp[i-1]) cnt += 1 return print(dp[n-1], cnt) dp_fibo(n)

문제 : https://www.acmicpc.net/problem/1477 이분탐색 n, m, l = map(int, input().split()) li = list(map(int, input().split())) li.append(0) # 처음 li.append(l) # 끝 li.sort() dist = [] # 휴게소 사이의 거리를 담을 배열 for i in range(1, len(li)): dist.append(li[i]-li[i-1]-1) # 시작이 1부터라서 거리 구하고 1을 뺀다 dist.sort() l, r = 1, l answer = 1001 while l m: # 개수가 많으면 l = mid + 1 # 크기를 늘린다. else: answer = min(answer, mid) # 가능한 값..

문제 : https://www.acmicpc.net/problem/9205 BFS (너비 우선 탐색) from collections import deque t = int(input()) def bfs(): n = int(input()) # 편의점 개수 homeX, homeY = map(int, input().split()) # 상근이 집 li = [] # 좌표 리스트 ck = [0] * (n+1) # 체크 리스트 for i in range(n): # 편의점 좌표 입력 받고 리스트에 추가 li.append(list(map(int, input().split()))) endX, endY = map(int, input().split()) # 페스티벌장 좌표 li.append([endX, endY]) # 페스티벌..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42628 힙(heap) 🔑 최솟값 제거는 heappop()을 사용 🔑 최댓값 제거를 위해 pop()을 했으나 힙 자료구조는 모든 원소를 정렬하지 않기 때문에 마지막 값이 최댓값이라는 보장이 없다. 🔑 그래서 최댓값을 구할 때는 sort()로 새롭게 정렬을 해주고 pop()을 했다. (정답 리턴 때도 마찬가지) from heapq import * def solution(operations): heap = [] for i in operations: if i[0] == "I": heappush(heap, int(i[2:])) # 숫자 부분만 슬라이싱, 형 변환 후 힙에 추가 elif i == "D..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42627 힙(heap) 🔑 현재 시간에 작업할 수 있는 작업들 중 소요 시간이 적은 작업을 찾기 🔑 현재 시간에 작업할 수 있는 작업이 없으면 먼저 들어온 요청 시간을 현재 시간으로 업데이트 🔑 우선순위 큐인 heapq에 작업을 추가하면 소요 시간이 적은 작업 순으로 자동 정렬이 일어남 from heapq import * def solution(jobs): # 정답, 처리한 작업 수, 현재 시간 answer, cnt, time = 0, 0, 0 heap = [] # 우선순위 큐 jobs.sort() # 요청 시간 기준으로 오름차순 정렬 while True: while cnt < len(job..

문제 : https://www.acmicpc.net/problem/2638 BFS from collections import deque n, m = map(int, input().split()) Map = [list(input().split()) for _ in range(n)] cnt = 0 for i in range(n): # 치즈 개수 세기 for j in range(m): if Map[i][j] == '1': cnt += 1 def bfs(): Q = deque([[0, 0]]) visit = [[0] * m for _ in range(n)] cheese = [[0] * m for _ in range(n)] while Q: zx, zy = [0, 0, 1, -1], [1, -1, 0, 0] x, ..

문제 : https://www.acmicpc.net/problem/7576 BFS deque의 popleft()를 쓰지않고 pop(0)으로 했을 때 시간초과가 뜬다. from collections import deque n, m = map(int, input().split()) tomato = [] for i in range(m): tomato.append(list(map(int, input().split()))) Q = deque([]) zero = 1 for i in range(m): # 4 for j in range(n): # 6 if tomato[i][j] == 1: # 익어있는 토마토들의 위치를 먼저 큐에 저장 Q.append([i, j]) if tomato[i][j] == 0: # 안익은게 있..