본문 바로가기

알고리즘

 (8)
완전탐색, 동적계획법, 탐욕법 1. 완전탐색, BFS, DFS : 모든 선택지 탐색하는 방법. 하나의 문제를 작은 sub 문제로 쪼개서 재귀로 풀 수 있는 경우 多 2. 동적계획법 : 완전 탐색처럼 해결하나, 중복되는 sub 문제를 한번만 계산되도록 memoization을 활용하는 문제 3. 탐욕법 : 한 문제를 작은 문제로 쪼개서 재귀로 푸는 것은 완전탐색, 동적계획법과 동일하나, 각 단계마다 당장 가장 좋은 방법만 선택 ① 여러 부분 문제로 나누기 ② 어떤 우선 순위로 선택할지 결정 (손으로 몇 개 풀면서) ③ 답이 항상 최적해인지, 각 단계에서 최적해가 전체 최적해를 만드는지 생각
백준_BruteForce_부분수열의 합 [Python] from itertools import combinations n, s = map(int, input().split()) arr = list(map(int, input().split())) cnt = 0 for k in range(1, n+1): combs = combinations(arr, k) ## 먼저 이렇게 객체를 만들어 저장하고 for comb in combs: # 나중에 for문을 돌려야함 if sum(comb) == s: cnt += 1 print(cnt)
백준_BruteForce_분해합 n = input() n = int(n) def getsSum(num): sSum = num while(num >= 1): sSum += (num % 10) num = num // 10 return sSum flag = False for i in range(n): if getsSum(i) == n: print(i) flag = True break if flag == False: print(0)
백준_BruteForce_로또 import numpy as np def dfs(start, depth): if depth == 6: for i in combination: print(i, end=' ') print() return ## 6개 다 안채워진 경우 for i in range(start, n): combination[depth] = lotto[i] dfs(i+1, depth+1) while(1): inp = input() if inp == '0': break case = inp.split() n = int(case[0]) lotto = [int(i) for i in case[1:]] combination = np.zeros(6, dtype='int') dfs(start=0, depth=0) print() python으로 작성..
백준_BruteForce_연구소 잘 모르겠다. 예제 코드 잘 돌아가고, 다른 코드랑 비교해도 다른게 없어보이는데 :(런타임에러가 어디서 나는지 찾아주시면 감사하겠습니다ㅠㅠ import numpy as np import sys import copy ans = 0 n = m = 0 viruslist = [] arr = [] safelist = [] ## DFS로 바이러스 퍼트리고, 안전구역 넓이 구하기 def spread_virus(copyed_arr, queue): dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] visit = list() while queue: node = queue.pop(0) # (1,5) if node not in visit: visit.append(node) copyed_arr[node[0]]..
백준_BruteForce_퇴사 n = int(input()) n_ = n t = [] p = [] while(n_ > 0): splited = input().split() t.append(int(splited[0])) p.append(int(splited[1])) n_ -= 1 def fun(psum, i): if i > n: return 0 if i == n : return psum return max(fun(psum+p[i], i+t[i]), fun(psum, i+1)) print(fun(0, 0))
백준_BruteForce_일곱 난쟁이 key = [] for i in range(9): key.append(int(input())) def findtwo(key): for i in range(len(key)): for j in range(len(key)): if i == j: continue if sum(key) - key[i] - key[j] == 100: return (key[i], key[j]) del1, del2 = findtwo(key) key.remove(del1) key.remove(del2) key = sorted(key) for k in key: print(k)
백준_BruteForce_한수 def check(n): numlist = [] while(True): numlist.append(n % 10) n = n // 10 if n == 0: break numlist.reverse() diff = 0 for i in range(len(numlist)-1): if i == 0: diff = numlist[i+1] - numlist[i] continue new_diff = numlist[i+1] - numlist[i] if diff != new_diff: return False return True n = int(input()) cnt = 0 for num in range(1,n+1): if check(num): cnt += 1 print(cnt)

티스토리툴바