one Book a Day

별찍기 같은 경우 분할 정복의 대표적 문제다. 분할 : 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..

처음에 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 = ..

문자열에 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..

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..

n = int(input()) lst = list(map(int, input().split())) # 원소 제외 없는 결과, 원소 하나 제외한 결과 dp = [[0, 0] for _ in range(n)] # 초깃값 : 나자신 or 나를 제외한 경우. dp[0] = [lst[0], -999999999] for i in range(1, n): # 끊고 출발하거나 이전에꺼에 덧붙히거나. dp[i][0] = max(dp[i - 1][0] + lst[i], lst[i]) # 이전까지의 합에 나를 제외한 경우.(+0이 생략된 값을 이어붙힘), 이전까지의 합에 나를 붙힌경우(생략x) # => 앞에서 -가 생략이 됐고 그게 최적이라면 dp[i-1][1]+lst[i]가 더 커야하고 아니라면 # 앞의 생략이 최적이 아니..

시간초과 및 메모리초과 때문에 10트정도 했다. 원소를 1개씩 가지고 있는 집합들을 합치고 어떤 원소가 이미 같은 집합으로 합쳐져있는지 확인하는 Union-Find구현문제이다. import sys input = sys.stdin.readline sys.setrecursionlimit(100000) n,m = map(int,input().split()) parent = [i for i in range(n+1)] def Union(a,b): a = Find(a) b = Find(b) if a>b: parent[a] = b else: parent[b] = a def Find(u): if parent[u]==u: return u parent[u] = Find(parent[u]) return parent[u] f..

array의 P들은 같은 gi에 동시에 존재 할 수 없고 교집합도 있을 수 없다. 되도록이면 gi에 도킹하는 것이 효율적이고 불가능하면 gi-1에 도킹하는 식으로 설계한다. 도킹을 완료하면 이전 트리와 union을 통해 통합된 tree로 도킹 가능한 G를 parent node로 관리한다. import sys input = sys.stdin.readline G = int(input()) P = int(input()) parent = [i for i in range(G+1)] def find(v): if parent[v] == v: return v parent[v] = find(parent[v]) return parent[v] def union(a, b): a = find(a) b = find(b) pare..

system = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" #10진법이면 9 까지, 36진법이면 Z까지 표현된다 N, B = map(int, input().split()) answer = '' while N != 0: # N을 B로 나눈 나머지를 마지막칸에 채움(1의자리)(36진법이면 나머지 = 36진법중 2번째 숫자) answer += str(system[N % B]) #위치로 진법 변환 # N을 B로 나눈 몫이 N이 된다. N //= B print(answer[::-1]) 변환은 결국 dictionary or list or 문자열로 1:1 매칭. key값, index를 무엇으로 잡을것이냐부터 시작.