본문 바로가기

Coding test

 (123)
[백준/16922/파이썬] 로마 숫자 만들기 소스코드 n = int(input().strip()) lst = [] for i in range(n + 1): for j in range(n + 1 - i): for k in range(n + 1 - i - j): t = n - i - j - k total = i * 1 + j * 5 + k * 10 + t * 50 lst.append(total) print(len(set(lst))) 알고리즘 그냥 for문 3번돌리면 되는,,무식한 BF문제로 풀었다. 백트래킹으로 풀어보려 했지만 시간초과가 났다. simple is the best!
[백준/11048/파이썬] 이동하기 - DP 소스코드 n, m = map(int, input().split()) s = [] dp = [[0] * (m + 1) for i in range(n + 1)] for i in range(n): s.append(list(map(int, input().split()))) for i in range(1, n + 1): for j in range(1, m + 1): dp[i][j] = s[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) print(dp[n][m]) 알고리즘 DP는 점화식을 잘 세우면 되는것 같아요~ 이제 슬슬 깨닫게 되는것 같습니다. 1 2 3 6 5 7 7 8 9 12 11 10 이런 입력을 받았을 때 DP 리스트에는 다음과 ..
[백준/12026/파이썬] BOJ거리 소스코드 n = int(input()) boj = list(input()) big = 99999999 dp = [big]*(n) dp[0] = 0 def prev_block(x): if x == 'B': return 'J' elif x == 'O': return 'B' elif x == 'J': return 'O' for i in range(1,n): for j in range(i): if boj[j] == prev_block(boj[i]): dp[i] = min(dp[i],dp[j] + pow(i - j,2)) print(dp[n - 1] if dp[n - 1] != big else -1) 알고리즘 DP문제입니다. 아직 감이 완전히 잡히지는 않은것 같아요,,ㅜㅡㅜ 이번 문제는 B,O,J 순서대로 가면서..
[백준/12869/파이썬] 뮤탈리스크 소스코드 n = int(input()) scv = list(map(int, input().split())) scv.extend([0, 0]) dp = [[[0]*61 for _ in range(61)] for _ in range(61)] dp[scv[0]][scv[1]][scv[2]] = 1 comb = [(9, 3, 1), (9, 1, 3), (3, 9, 1), (3, 1, 9), (1, 9, 3), (1, 3, 9)] for i in range(60, -1, -1): for j in range(60, -1, -1): for k in range(60, -1, -1): if dp[i][j][k] > 0: for c in comb: i_ = i-c[0] if i-c[0] >= 0 else 0 j_ = j-..
[백준/6603/파이썬] 로또 소스코드 def dfs(depth, idx): if depth == 6: print(*out) return for i in range(idx, k): out.append(S[i]) dfs(depth + 1, i + 1) out.pop() while True: array = list(map(int, input().split())) k = array[0] S = array[1:] out = [] dfs(0, 0) if k == 0: exit() print() 알고리즘 사실 이 문제도 combinations를 이용해서 풀면 풀리는 문제인데 공부하는 입장이다보니 dfs를 이용하여 풀었습니다. dfs를 사용하여 깊이를 1씩 늘려가며 6개가 되면 출력하는 형태로 진행하였습니다. .ez~
[백준/11723/파이썬] 집합 소스코드 (시간초과가 났지만 맞는..) M = int(input()) S = [0]*21 for i in range (M): command = input().split() if command[0] == 'add': S[int(command[1])] = 1 if command[0] == 'remove': S[int(command[1])] = 0 if command[0] == 'check': print(S[int(command[1])]) if command[0] == 'toggle': S[int(command[1])] = ~ S[int(command[1])]+2 if command[0] == 'all': S = [1]*21 if command[0] == 'empty': S = [0]*21 알고리즘 요즘 DP..
[백준/10972/파이썬] 다음 순열 소스코드 n = int(input()) data = list(map(int, input().split())) for i in range(n-1, 0, -1): if data[i-1]
[백준/9095/파이썬] 1,2,3 더하기 - DP 소스코드 T = int(input()) for i in range (T): n = int(input()) dp = [0]*(n+1) if n == 1 : print(1) elif n == 2 : print(2) elif n == 3 : print(4) else : dp[1] = 1 dp[2] = 2 dp[3] = 4 for j in range(4,n+1) : dp[j] = dp[j-1] + dp[j-2] + dp[j-3] print(dp[n]) 알고리즘 현재 자료구조 과목만 수강을 해서 알고리즘에 대해 생소한 부분이 있다면 바로 DP인것 같아요. DP란 Dynamic Programming으로 동적프로그래밍이라고 하는데 계산값을 선언된 배열에 넣어줌으로서 많은 연산을 줄여주는 프로그래밍 기법입니다. 예를들..

티스토리툴바