one Book a Day

뭔가 요새 DFS로 풀릴것 같으면 DFS하는 습관이 생겼다. import sys input = sys.stdin.readline N = int(input()) A = list(map(int,input().split())) check = [False] * 1200 ans = [] v = 0 cnt = 0 def DFS(v,cnt): if v>=N-1: ans.append(cnt) return if A[v]==0: return for i in range(1,A[v]+1): if not check[v+i] and not v+i>N-1: check[v+i] = True DFS(v+i,cnt+1) check[v+i] = False check[0]=True DFS(0,0) print(min(ans) if ans e..

별찍기 같은 경우 분할 정복의 대표적 문제다. 분할 : n=3인 경우로 분할 정복 : n=3인 경우를 해결. (매개변수로 받아오는 값만 어떻게 처리해야 동일한 패턴이 나올까 고민하면됨) 병합 : n=3인 경우의 결과값을 다음 순서에 넣어 확장시키면 재귀적인 프렉탈구조를 만들수 있다. # 분할 정복 알고리즘 / 분할, 정복, 합치기. # 정복 # star 배열을 통해 새 matrix를 생성해 반환하는게 목적. # 반복문에서 3*len(star)로 별이 그려지는 모든 배열을 검사하며 len(star) # 즉 최초 n의 크기에 따라 빈칸 " "을 추가적으로 삽입하는 방식을 차용한다. # (n=9일때 3으로 나눠 몫이 1인 index = 1 요소의 가운데 ) def conquer(n): matrix=[] for..

말 그대로 큰 문제를 재귀적으로 쪼개어 나간 다음 하위문제들의 결과를 조합 해 원래 문제의 결과를 도출하는 방식. 분할 -> 정복 -> 조합 3단계로 이루어지며 대표적으로 병합 정렬 알고리즘을 볼 수 있다. def F(X): # 정복 if F(X)가 간단해졌을 때: return F(X)계산값(int or list or str) else: # 분할 X를 left와 right로 분할. F(left)와 F(right)를 호출 # 조합 return F(left)와 F(right)로 F(x)를 구하는 관계식(재귀) 추후 최적 부분구조(Optimal Substructure)에도 연관 됨. 예제로 연산 문자열이 들어갔을 때 괄호를 치는 경우의 수에 따른 계산값 리스트를 구하는 함수. 각 연산자를 만남에 따라 좌우를 ..

처음에 6으로 나눠떨어져야 한다는 조건 못봐서 실패. 그리고 한참 디버깅코드 안빼고 왜 실패하지?? 고민하다 결국 ans디버깅 코드 넣어논거 발견하고 해결. 코드 더 줄일 수 있을 것 같지만 그냥 제출. matrix = [input() for _ in range(5)] N = (len(matrix[0])//4)+1 zero = ['***','* *','* *','* *','***'] one = [' *',' *',' *',' *',' *'] two = ['***',' *','***','* ','***'] three = ['***',' *','***',' *','***'] four = ['* *','* *','***',' *',' *'] five = ['***','* ','***',' *','***'] s..

처음엔 ord chr 쓰는줄 알았는데 도저히 그쪽으론 설계가 안돼서 노가다로 풂. 문제 함정은 testcase는 하나 띡 놓고 실상은 입력이 겁나 많이 들어간다는 것. 때문에 while로 무한 반복에 try except까지 써서 멈출 수 있게 해줘야 정답처리가 된다. moem = ['a','i','y','e','o','u'] zaem = ['b','k','x','z','n','h','d','c','w','g','p','v','j','q','t','s','r','l','m','f'] # 무한입력. try except while 1: try: S = input() ans = "" for i in range(len(S)): if S[i].lower() in moem: if S[i].isupper(): k = ..

1. find 2. 여러개 탐색. a = str1.find(str2) print a while str1[a+1:].find(str2) != -1: a = str1[a+1:].find(str2) + a + 1 print a 3. re 모듈의 finditer(b,a) for a in re.finditer(str2,str1) : print a.start() start()는 시작위치 반환, end()는 끝위치 반환 4. A.startswitth(a,b) a문자가 A문자열의 b위치에서 시작되면 True반환. 5. A.endswith(a,b) =>보통 b위치에 find(a)를 넣어 True강제반환하게끔 가능.

문자열에 str처리해서 더하면 되는것을.. list만드는 병에 걸려서.. 문제 보자마자 중복없는 순열에 DFS넣을때마다 부등호 바꿔주는 조건. N과M(12)까지 다 풀었다면 아이디어 자체는 어렵지 않다. n = int(input()) inequality = input().split() check = [False] * 10 max, min = "", "" def possible(i, j, k): if k == '': return i > j return True def DFS(depth, s): global max, min if depth == n + 1: if not len(min): min = s else: max = s return for i in range(10): if not check[i]: if..

중복을 허용하지 않는다. 리스트(튜플) -> 셋 -> 리스트로 중복제거 가능. 순서가 없다. 고로 인덱싱이 불가능하다. s = set()로 정의 그럼 어디쓰냐? 1. 교집합 s1 & s2 2. 합집합. s1 | s2 =si.union(s2) 3. 차집합. s1-s2 =s1.difference(s2) 사용가능한 메소드는 add(), update(list) /// remove(), pop()

itertools라이브러리 combinations모듈과 permutations모듈을 통해 손쉽게 순열과 조합을 구할 수 있다. 이때 만들어진 순열,조합은 튜플형태로 리스트에 담겨서 반환된다. [(0,1,2),...] 조합 from itertools import combinations arr = [0, 1, 2, 3, 4, 5] print(list(combinations(arr, 3))) 순열 from itertools import permutations arr = [0, 1, 2, 3, 4, 5] print(list(permutations(arr, 3))) 재귀 기본적인 아이디어는 DFS,백트래킹과 유사하다. combination([0,1,2,3],2) = ([0],combination([1,2,3],1..

n,m = list(map(int,input().split())) s = [] def dfs(): if len(s)==m: print(' '.join(map(str,s))) return for i in range(1,n+1): if i not in s: s.append(i) dfs() s.pop() dfs() 어렵지 않다. 조건에 맞는 배열을 탐색, 출력하는 것이므로 dfs로 탐색 출력을 진행. n,m = list(map(int,input().split())) s = [] def dfs(start): if len(s)==m: print(' '.join(map(str,s))) return for i in range(start,n+1): if i not in s: s.append(i) dfs(i+1) s.p..