본문 바로가기

파이썬18

[S1] 백준 1992 - 쿼드트리 (Python3) https://www.acmicpc.net/problem/1992💡 해결방법분할정복 알고리즘을 적용해 해결했다.👀 풀이풀이 설명🧾코드# BOJ 1992N = int(input())grid = [input() for _ in range(N)]def sol(N, r=0, c=0): color = grid[r][c] for i in range(r, r+N): for j in range(c, c+N): if color != grid[i][j]: # 모두 같은 색이 아니라면 # 조건에 나온 순서대로 4분할로 쪼갠다. return '('+ sol(N//2, r, c) + sol(N//2, r, c + N//2) +.. 2024. 11. 10.
[Python] Dictionary 초기화, setdefault() setdefault를 언제 쓸까?Python에서 그래프를 Dictionary로 생성할 때에 귀찮은 점이 하나 있다.바로 Dictionary에서 새로운 key를 만들 때는 초기화를 해주어야 한다는 점이다.문제 코드,,N, M = map(int,input().split())G = {}for _ in range(M): p, k = map(int,input().split()) if p not in G: # 조건을 만들어서 초기화하기 G[p] = [k] else: G[p] += [k] if k not in G: # 양방향 그래프에선 이런 조건-초기화를 두 개 만들어야 한다. G[k] = [p] else: G[k] += [p]print(G)>> {1:.. 2024. 10. 3.
[이것이 코딩 테스트다] 효율적인 화폐 구성 - 다이나믹 프로그래밍 이 문제는 대학교 1학년 때 공부했던 이산수학에서 다룬 문제여서 금방 풀 수 있었다.그때 문제도 마찬가지로 2와 3의 화폐로 모든 화폐를 표현할 수 있냐는 문제였던 것 같다.2, 3, 2+2, 2+3, 3+3, ... 1 이하의 정수를 제외한 모든 화폐를 표현할 수 있었다. 문제의 입력 조건으로는 최대 입력이 100이라서 O(n^2) 으로도 충분하다. 그래서 2중 for문을 채택했다. 최소 화폐 단위가 2, 3, 7이라고 가정하자. 그러면a[i]를 위 화폐 단위로 만들 수 있을 때, a[i](최소 화폐 개수)는 min(a[i], a[i - 2]+1, a[i - 3]+1, a[i - 7]+1) 이다.이것은 이해를 돕기위해 세운 약간 어거지(?) 점화식이다. 실제로는 각 화폐 단위를 하나 씩만 비교하여 따진.. 2024. 9. 6.
[S3] 백준 1463 - 1로 만들기(Python) https://www.acmicpc.net/problem/1463 풀이👀1부터 X까지 반복문으로 1회 순환한다.i (1에 대해서 dp[i]라 할 때, dp[i]는 1에서 출발하여 주어진 조건을 만족하며 i를 만들기 위해 필요한 연산 최소 횟수이다.그러면dp[i]는 (dp[i-1], dp[i//2], dp[i//3], dp[i//5]) 중에서 최솟값을 찾은 다음, +1을 한 값으로 결정난다.코드💻# 1로 만들기X = int(input())dp = [10**7] * (X+1)dp[1] = 0for i in range(2, X+1): dp[i] = dp[i-1] + 1 if i%2 == 0: dp[i] = min(dp[i//2] + 1, dp[i]) if i%3 == 0: .. 2024. 9. 5.
[G5] 백준 1916 - 최소비용 구하기 (Python3) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 해결방법 다익스트라 알고리즘을 이용한다. 풀이👀 입력에서 버스 이동에 대한 정보를 제공해주고 있다. 순서대로 [출발점, 도착점, (출발->도착)비용] 이다. 각 지점에서는 연결 된 다른 점들로 이동할 수 있다. 이 이동에서 비용이 발생한다. 그런데 이동을 하면서 출발점과 도착점이 같지만 중간에 우회하는 경로를 달리하여 그 비용(결과)를 저렴하게 할 수 있다. 하지.. 2023. 1. 30.
[S4] 백준 4949 - 균형잡힌 세상 (Python3) https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 이 문제보다 한 단계 쉬운 문제는 백준 9012번: 괄호라고 생각한다. 이 문제를 풀고나서 이 문제를 푸는 것을 추천한다. 해결방법 스택을 활용하는 문제이다. bracket 이라는 리스트 변수에 여는 괄호("(", "[")를 담고, 닫는 괄호(")", "]")가 나올 때마다 bracket의 원소를 pop 해주는 방식으로 문제를 풀었다. 코드 while (string:=inpu.. 2023. 1. 14.
[Python] 백준 5430 - AC https://www.acmicpc.net/problem/5430 해결방법 문제에 나와있는 대로 따르면 충분히 풀 수 있는 문제이긴 하다. 하지만 곧이곧대로 따르기만 하면 여러 가지 문제로 해결이 불가능하다. 코드 tc = int(input()) for _ in range(tc): command = input() arr_len = int(input()) input_raw_arr = input() raw_arr = list(map(str, input_raw_arr)) raw_arr.pop(0); raw_arr.pop(-1) arr = (''.join(raw_arr)).split(',') error = False # True: 에러 on, False: 정상작동중 head = True # True: 앞부터 읽.. 2022. 5. 29.
[Python] 백준 6068 - 시간 관리하기 https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1=0: suc_all = True for i in range(works): if start + task[i][0] > task[i][1]: t -= 1 start = t suc_all = False break; start += task[i][0] # t일 때 모든 순회를 통과하면? # 그게 정답 if suc_all: print(t) break if t task[k][1]: task[i], task[k] = task[k], task[i] elif task[i][1] == task[k][1]: if task[i][0] > .. 2022. 5. 20.