본문 바로가기

Coding test

 (123)
[백준/1107/파이썬] 리모컨 - Brute force 소스코드 target = int(input()) ans = abs(100 - target) M = int(input()) if M: broken = set(input().split()) else: broken = set() for num in range(1000001): for N in str(num): if N in broken: break else: ans = min(ans, len(str(num)) + abs(num - target)) print(ans) 알고리즘 가능한 숫자 조합을 생각하여 문제를 푸려고 했는데 런타임에러가 자꾸 나서 다른 사람의 풀이를 참고했는데 그냥 무식하게 쭉 브루트 포스 알고리즘을 사용하여 풀면 되는 문제였다. 단순한게 또 먹히는 문제도 있는 걸 깨달았다.
[백준/1463/파이썬] 1로 만들기 - DP 소스코드 x = int(input()) dp = [0]*(x+1) dp[1] = 0 for i in range(2,x+1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i], dp[i // 3] + 1) if i % 2 == 0: dp[i] = min(dp[i], dp[i // 2] + 1) print(dp[x]) 알고리즘 DP문제는 많이 풀어봐서 이번 문제는 그리 어렵지는 않았다. 1이 되기 위해서 필요한 연산의 숫자를 구하는 것 이다. 2,3은 1에 2배,3배를 하면 된다. 4는 2까지 걸린 연산 횟수의 1번 더(2배) 하면 된다. 5는 4까지의 연산에 1번더(+1) 6은 2까지의 연산에 1번더(*2) 최소 횟수에 대해 전에 걸 불러와서 연산해 나가는 방..
[백준/6588/파이썬] 골드바흐의 추측 소스코드 import sys dp = [1] * (1000000 + 1) dp[0] = 0 dp[1] = 0 for i in range(2, 1001): #dp에 소수를 넣는 과정 (에라토스테네스의 체) if dp[i]: for j in range(i * i, 1000001, i): dp[j] = 0 def goldba(n): for i in range(2, n): if dp[i] and dp[n - i]: print(f'{n} = {i} + {n - i}') return 0 return 1 # 골드바흐 가설이 틀린걸 증명 해버림 while (1): try: n = int(sys.stdin.readline()) if n == 0: break if goldba(n): print("Goldbach's con..
[백준/16936/파이썬] 나3곱2 소스코드 N = int(input()) seq = list(map(int, input().split())) ans = [] for i in seq: can3 = 0 num = i while True: if i % 3 == 0: can3 += 1 i //= 3 else: break ans.append([can3, num]) ans.sort(key= lambda x: (-x[0], x[1])) for i in range(N): print(ans[i][1], end=' ') 알고리즘 list에 있는 숫자들이 모두 2와 3으로 이루어져 있는것을 보고 소인수 분해를 해봤다. 4 = 2^2 8 = 2^3 6 = 2 * 3 3 = 3 12 = 2^2 * 3 9 = 3^2 그리고 출력 결과를 보니깐 3을 인수로 많이 ..
[백준/14225/파이썬] 부분수열의 합 소스코드 N = int(input()) seq = list(map(int,input().split())) bf = [False] * 10000000 subsets = [[]] for num in seq: size = len(subsets) for y in range(size): bf[sum(subsets[y]+[num])] = True subsets.append(subsets[y]+[num]) for i in range (1,len(bf)): if bf[i] == False : print(i) break 알고리즘 1. 모든 가능한 부분 수열의 합을 구한다. 2. 존재를 체크하는 list 선언 후 수열의 합이 있으면 True를 선언한다. 3. 1부터 for 문을 돌면서 수열의 합으로 나타내지 못한 애 (F..
[백준/2468/파이썬] 안전영역 - DFS(재귀) 소스코드 import sys sys.setrecursionlimit(100000) N = int(sys.stdin.readline()) area = [list(map(int,sys.stdin.readline().split())) for _ in range(N)] #입력받기 dx = [-1,1,0,0] dy = [0,0,1,-1] def dfs(x,y,h): #범위내 조건을 만족하면 재귀 돌면서 실행 for i in range(4): nx = x + dx[i] ny = y + dy[i] if (0
[백준/7576/파이썬] 토마토 소스코드 from collections import deque m, n = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(n)] queue = deque([]) dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] res = 0 for i in range(n): for j in range(m): if matrix[i][j] == 1: queue.append([i, j]) def bfs(): while queue: x, y = queue.popleft() for i in range(4): nx, ny = dx[i] + x, dy[i] + y if 0
[백준/14500/파이썬] 테트로미노 소스코드 (틀린풀이) from collections import deque N,M = map(int,input().split()) tetro = [] for i in range(N): tetro.append(list(map(int,input().split()))) dx = [-1,1,0,0] dy = [0,0,-1,1] def bfs(x,y): queue = deque() queue.append((x,y)) #시작 지점 queue에 삽입 SUM = tetro[x][y] Max_place = () visited = [(x,y)] for _ in range (3): #테트로미노는 자기포함 4번 움직임 poly = queue.popleft() Max = 0 nlist = [] for i in range(4):..

티스토리툴바