나의 개발일지

문제 : https://www.acmicpc.net/problem/6443 🔑 DFS, 백트래킹 딕셔너리에 알파벳 개수를 저장한다 ex) {a : 2, b : 1, c: 1} 알파벳이 있으면(값이 0이 아니면)문자열에 추가, 딕셔너리에서 값을 내리고 다음 재귀로 간다. 1. a 2. aa 3. aab 4. aabc 알파벳 다 썼으니까 출력하고 리턴 후 사용했던 알파벳 개수 다시 증가 (다른 순서로 다시 사용해봐야 함) 2. aa 3. aac 4. aacb 반복 .... n = int(input()) def dfs(dict_s, l, s): if l == len(s): print(s) return for i in dict_s: if dict_s[i]: dict_s[i] -= 1 dfs(dict_s, l, ..

문제 : https://www.acmicpc.net/problem/2251 🔑 물통의 이동 경우의 수 6가지 C → A C → B B → A B → C A → B A → C one, two, three = map(int, input().split()) answer = [] m = max(one, two, three) chk = [[[0] * (m+1) for _ in range(m+1)] for _ in range(m+1)] def dfs(a, b, c): if chk[a][b][c] == 1: return if a == 0: answer.append(c) chk[a][b][c] = 1 if c > (one - a): # C -> A dfs(one, b, c - (one - a)) else: dfs(a ..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/17678 🔑 마지막 운행 셔틀 마지막 운행 셔틀에 자리가 남으면? 마지막 운행 시간에 맞춰서 오기 자리가 있다면 제일 마지막 시간에 딱 맞춰가도 탈 수 있기 때문 마지막 운행 셔틀에 자리가 없으면? 제일 마지막에 도착한 사람보다 1분 일찍 오기 이 버스를 놓치면 회사 못 간다. 무조건 마지막에 도착한 사람보다 1분 일찍 와서 기다리자 def solution(n, t, m, timetable): start_time = 540 # 첫 셔틀 시간 end_time = 540 + (n - 1) * t # 마지막 셔틀 도착 시간 for i in range(len(timetable)): # 시간 분으로 ..

문제 : https://www.acmicpc.net/problem/22944 🔑 BFS 우산을 들고 있을 때, 안 들고 있을 때의 계산 처리 우산을 들고 있으면 우산의 내구도만 내리고 다음 칸에 체력 저장 우산을 안 들고 있으면 체력을 내리고 다음 칸에 체력 저장 방문했던 곳은 현재 체력이 높을 때만 이동 (우산 때문에, 방문했던 곳의 체력보다 현재 체력이 더 많을 수 있어서) import sys from collections import deque input = sys.stdin.readline n, h, d = map(int, input().split()) MAP = [list(input()) for _ in range(n)] start, end = [], [] visit = [[0] * n for ..

문제 : https://www.acmicpc.net/problem/2667 🔑 BFS 지도를 돌면서 1을 만나면 bfs 실행한다. 방문했으면 지도에 1을 0으로 바꾼다. 이때 집의 수도 같이 센다. 연결된 단지를 모두 탐색했으면 bfs 종료되고 단지 수를 올린다. from collections import deque n = int(input()) danji = [list(map(int, input())) for _ in range(n)] total_danji = 0 danji_list = [] def bfs(i, j): mx, my = [0, 0, 1, -1], [1, -1, 0, 0] q = deque([(i, j)]) danji[i][j] = 0 cnt = 1 while q: x, y = q.popl..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/150370 🔑 년.월.일을 일 수로 변환 한 달 = 28일로 고정이기 때문에 쉽게 변환 가능 약관 종류에 대한 유효 기간은 딕셔너리로 저장 유효 기간도 일 수로 변환해서 저장 ex) "A 6" = "A" : 168 오늘 날짜 >= 개인정보 수집 날짜 + 약관 유효 기간 약관 만료일이 지났으면 파기 끝 def day(d): # 년월일 -> 일 d = list(map(int, d.split("."))) d = d[0] * 336 + d[1] * 28 + d[2] return d def solution(today, terms, privacies): answer = [] today = day(tod..

문제 : https://www.acmicpc.net/problem/11404 🔑 플로이드-워셜 알고리즘 (On³) 🔥 점화식 graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) i → j 로 가는 비용보다 i → k 를 거쳐 k → j 로 가는 비용이 더 적은지 확인 (i → k → j) 2차원 리스트(그래프) 행 = 출발지 열 = 도착지 graph[행][열] = 비용 (초기 값 INF) ex) 1번 노드에서 2번 노드로 가는 비용이 5 : graph[1][2] = 5 이 문제에서 1로 시작하지 않고 0부터 시작한 이유 n(도시 개수)가 1개일 때 인덱스 에러 발생함 import sys input = sys.stdin.readline n = int(in..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/72413 🔑 다익스트라 1번 풀이 : 모든 노드를 시작점으로 n번의 다익스트라를 호출 n → s + n → a + n → b 비용의 최솟값을 찾는다. 최대 n이 200이므로 굉장히 느림 (최대 200번의 다익스트라 호출), 최대 14677.97ms 2번 풀이 : s, a, b를 시작 지점으로 총 3번의 다익스트라 호출 s → n + a → n + b → n 비용의 최솟값을 찾는다. n이 몇이든 다익스트라는 3번만 호출하면 되기 때문에 굉장히 빠름, 최대 230.38ms 모든 노드를 시작점으로 n번의 다익스트라 호출 from collections import defaultdict from he..