# Coding (78) 썸네일형 리스트형 [백준 / 15686] 치킨 배달 - Python https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨집을 M개만큼 골라아한다 -> 조합(combination) 치킨집 M개를 고른 모든 경우를 계산해준다. def combi(N, start, end, prev=[]): all_set = [] numList = [i for i in range(start, end)] for i in numList: temp = prev[:] temp.append(i) if N == 1: all.. [보기 쉬운 Algorithm] 냅색(Knapsack) 알고리즘 - Python 냅색 알고리즘은 DP(Dynamic Programming)의 한 종류로 많이 쓰이는 방식 중 하나이다. 가방문제에 가장 많이 등장한다! 가방에 담을 수 있는 무게 제한이 있고, 각각의 물건은 무게와 가치가 있다. 가방의 무게를 초과하지 않게 물건을 많이 담아 최고 가치를 가지게 하는 문제이다. for i in range(1, n+1): for j in range(1, k+1): w = thing[i][0] # 물건의 무게 v = thing[i][1] # 물건의 가치 if j < w: # 현재 무게가 물건 보다 작다면 table[i][j] = table[i-1][j] # 위의 값을 그대로 else: table[i][j] = max(table[i-1][j], table[i-1][j-w]+v) https://.. [백준 / 12865] 평범한 배낭 - Python https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 냅색 알고리즘(Knapsack Algorithm) (처음에는 재귀함수로 다 모든 경우를 계산해서 시간이 너무 오래 걸렸다.) n, k = map(int, input().split()) table = [[0]*(k+1) for _ in range(n+1)] thing = [[0, 0]] for i in range(n): thing.a.. [백준 / 9251] LCS - Python https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net s1 = input() s2 = input() s1_len = len(s1) s2_len = len(s2) table = [[0 for _ in range(s2_len+1)] for _ in range(s1_len+1)] for i in range(1, s1_len+1): for j in range(1, s2_len+1): if s1[i-1] == s2.. [백준 / 1034] 램프 - Python https://www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 램프는 열 단위로 불이 켜지고, 행에 있는 불의 개수를 세는 거다. 열 단위로 불이 켜지므로 A행과 B행의 램프의 순서가 같다면 둘은 같이 켜질 것이고, 둘이 다르면 다르게 켜질 것이다. 따라서 같은 램프 구조를 가지고 있는 행의 개수를 세면 되는 문제였다. (정말로 간단하게 생각해도 되는 문제였다. 처음에는 재귀함수로 풀었는데 계속 시간초과가 나왔다.) 하지만, 짝수인 경우 껐다켰다 하면.. [백준 / 1013] Contact - Python https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 반례 101 -> NO 1000000000000000 -> NO 100000000000001111111111111 -> YES 100111001 -> YES def algo(num): fail = False l = len(num) i = 0 first = False last = True while i < l: if first: if num[i] == '0': pass elif num[i.. [백준 / 10974] 모든 순열 - Python https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net def func(arr, ans=''): l = len(arr) if l == 1: ans += str(arr.pop()) print(ans) else: for i in range(l): temparr = arr[:] tempans = ans+str(temparr.pop(i))+' ' func(temparr, tempans) n = int(input()) arr = [i for i in range(1, n+1)] func(arr) [백준 / 13305] 주유소 - Python https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 1. 앞에 가격보다 뒤의 가격이 크면 앞의 가격으로 사는 것이 좋다. 따라서 뒤의 가격이 더 크면 앞의 값중 제일 작은 값으로 바꾼다. 2. 뒤에서부터 거꾸로 가면서 가격이 더 커지면 뒤에서 해당 도시까지 온 거리를 해당 기름 값으로 계산해준다. n = int(input()) dis = list(map(int, input().split())) cost = list(map(int, i.. 이전 1 2 3 4 5 6 7 8 ··· 10 다음
