12345678910111213141516171819202122232425262728def solution(distance, rocks, n): answer = 0 st = 0 ed = distance rocks.sort() while st <= ed: mid = (st+ed)//2 cnt = 0 r = 0 for rock in rocks: if rock - r < mid: cnt += 1 else: r = rock if cnt > n: break if cnt > n: ed = mid - 1 else: answer = mid st = mid + 1 return answer print(solution(25, [2, 14, 11, 21, 17], 2))cs mid를 정하고 해당 기준을 사용했을 때, 바위가 n개 이상 제거될 수 없기에 n개 이상이 되면 end를 줄이고 n개 이하의 바위를 제거하면 start를 키우며 최대의 mid를 찾는 과정
123456789101112131415161718import heapq def solution(n, works): answer = 0 if sum(works) < n: return answer work = [-i for i in works] heapq.heapify(work) for _ in range(n): heapq.heappush(work,heapq.heappop(work)+1) for w in work: answer += w**2 return answerColored by Color Scriptercs works n result[4, 3, 3] 4 12 예제에서 n=4 (남은 시간)일 때, 남은 작업량이 [4,3,3]이면 최소화된 야근 지수(남은 시간 제곱 합)는 2^2 + 2^2 + 2^2우선 n보다 works의 합이 적다면 애초에 야근할 필요가 없기에 0를 리턴. 그게 아니라면 따로 처리해줄 필요가 있다.문제가 (1. 효율성)을 요하고 제곱하는 수의 크기를 줄이는 것.......
123456789101112def solution(money): l = len(money) dp = [money[0]] + [0]*(l-1) dp2 = [0] + [0]*(l-1) for i in range(1,l): dp[i] = max(dp[i-1], dp[i-2]+money[i]) dp2[i] = max(dp2[i-1], dp2[i-2]+money[i]) return max(dp[-2],dp2[-1]) print(solution([1, 2, 3, 1]))cs 첫번째 집의 도둑질 여부에 따라 답이 달라진다. (첫번째 집을 도둑질 하는 경우, 마지막 집은 갈 수 없기에 제외)이에 2개의 dp를 구성하여 우위에 있는 것을 결과로서 출력한다.
12345678910111213141516171819import sysn = int(sys.stdin.readline())k = int(sys.stdin.readline())st = 1ed = k ans = 0while st <= ed: mid = (st+ed)//2 tmp = 0 for i in range(1,n+1): tmp += min(mid//i, n) if tmp >= k: ans = mid ed = mid-1 else: st = mid+1 print(ans)cs
1234567891011121314151617181920212223242526from collections import defaultdict def solution(table, languages, preference): pref = defaultdict(int) for i in range(len(languages)): pref[languages[i]] = preference[i] score = defaultdict(int) for t in table: t = list(map(str, t.split())) for i in range(1,len(t)): if pref[t[i]]: score[t[0]] += pref[t[i]] * (len(t)-i) answer = sorted(score.items(), key=lambda x:(-x[1],x[0]))[0][0] return answer print(solution(["SI JAVA JAVASCRIPT SQL PYTHON C#", "CONTENTS JAVASCRIPT JAVA PYTHON SQL C++", "HARDWARE C C++ PYTHON JAVA JAVASCRIPT", "PORTAL JAVA JAVASCRI.......
12345678910111213141516from itertools import permutations def solution(word): vowel = ["A","E","I","O","U"]*5 dic = [] for i in range(1,6): for j in list(permutations(vowel,i)): dic.append("".join(j)) dic = sorted(list(set(dic))) return dic.index(word)+1 print(solution("AAAAE"))cs permutaitions로 모든 생성 가능한 조합을 생성,사전순으로 정렬 후 위치를 찾았는데 비효율적인것 같다.
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요. 1234567891011121314151617181920212223242526272829303132333435363738394041424344from collections import defaultdictimport heapq de.......
1234567891011121314151617181920212223242526272829303132333435363738import sysfrom collections import deque def bfs(i,j): global max_val dimension = 1 q = deque() q.append([j,i]) while q: x,y = q.popleft() for dx,dy in (0,1),(0,-1),(1,0),(-1,0): nx,ny = x+dx, y+dy if 0 <= nx < m and 0 <= ny < n: if graph[ny][nx] == 1 and visit[ny][nx] == 0: visit[ny][nx] = 1 q.append([nx,ny]) dimension += 1 if dimension > max_val: max_val = dimension n, m = map(int, sys.stdin.readline().split())graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]visit = [[0]*m for _ in range(n.......
123456789101112131415161718192021222324252627from itertools import combinationsimport sys,copy txt = list(sys.stdin.readline().rstrip())n = []idx = [] for i,j in enumerate(txt): if j == '(': txt[i] = "" n += [i] if j == ')': txt[i] = "" idx += [[n.pop(),i]] ans = set()for i in range(len(idx)): for j in combinations(idx,i): tmp = copy.deepcopy(txt) for k,l in j: tmp[k] = "(" tmp[l] = ")" ans.add("".join(tmp)) for i in sorted(ans): print(i)cs enumerate로 문자열의 인덱스 위치를 i, 캐릭터를 j좌측 괄호가 나오면 문자를 지우고 위치를 n에 저장우측 괄호가 나오면 문자를 지우고 인덱스로 괄호 쌍의 위치를.......
123456789101112131415161718192021222324252627from itertools import combinationsfrom collections import defaultdict def solution(orders, course): answer = [] for c in course: tmp2 = [] for o in orders: tmp = combinations(sorted(o),c) tmp2 += tmp menus = defaultdict(int) for t in tmp2: menus["".join(t)] += 1 if not menus: continue cnt = max(menus.values()) if cnt <= 1: continue for i,j in menus.items(): if j == cnt: answer.append("".join(i)) return sorted(answer)cs course를 바탕으로 order에 들어 있는 값으로 조합 생성값과 빈도수를 menus에 저장각 코스의 수당 최대 빈도의 요리를 찾는다(1명이하의.......
1234567891011121314151617181920212223242526272829303132333435363738394041424344def solution(new_id): # step1,2 rev = "" for i in range(len(new_id)): x = new_id[i] if x.isdigit() or x == "_" or x == "-" or x == "_" or \ x.islower() or x == ".": rev += x elif x.isupper(): rev += chr(ord(x)+32) # step3 rmv = rev[0] for i in range(1,len(rev)): if rev[i] == "." and rev[i] == rev[i-1]: continue else: rmv += rev[i] # step4 if len(rmv): if rmv[-1] == ".": rmv = rmv[:-1] if len(rmv): if rmv[0] == ".": rmv = rmv[1:] # step5 if not len(rmv): rmv = "a" # step6 if len(rmv) >= 16: rmv = rmv[:15] if len(r.......
123456789101112131415161718192021222324def solution(files): renamed = [] cnt = -1 for f in files: re = "" tmp = "" c = 0 cnt += 1 for i in f: if i.isdigit(): tmp += i c = 1 elif not c: re += i.upper() else: break renamed.append([re,int(tmp),cnt,f]) r = sorted(renamed, key=lambda x: (x[0],x[1],x[2])) ans = [] for x in r: ans.append(x[3]) return ansColored by Color Scriptercs files에서 파일명을 가져오며 파일명 내의 캐릭터들을 살펴본다.숫자면 tmp에 저장하고 c를 true로 만든다c가 false이면 re에 문자를 re에 저장c가 true인데 문자가 들어오면 조건을 탈출한다.-> 위 과정에서 생성한 문자(head), 숫자(nu.......
12345678910111213141516171819202122232425262728293031323334353637383940414243import sys,heapqinput = sys.stdin.readline def dijkstra(st, dest): q = [] heapq.heappush(q,[0,st]) distance[st] = 0 while q: dist, node = heapq.heappop(q) if distance[node] >= dist: for i in graph[node]: cost = dist + i[1] if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q,[cost, i[0]]) if distance[dest] == int(1e9): return False return True n,m = map(int, input().split())graph = [[] for _ in range(n+1)] for i in range(1,n+1): tmp = list(input().split()) for j in range(len(tmp)): if tmp[j] == "0": .......
123456789101112131415161718192021222324252627282930313233import sysfrom collections import defaultdict try: while True: n = int(sys.stdin.readline()) dic = defaultdict(list) words = [] for i in range(n): word = sys.stdin.readline().rstrip() words.append(word) tmp = "" for w in word: if tmp != "" and w not in dic[tmp]: dic[tmp].append(w) tmp += w ans = [] for word in words: cnt = 1 tmp = "" for w in word: if len(word) == 1: break tmp += w if len(dic[tmp]) > 1 or tmp != word and tmp in words: cnt += 1 ans.append(cnt) print("{:.2f}".format(sum(ans)/n)) except: exit()Colored by Color Scriptercs.......
123456789101112131415161718192021222324252627282930313233343536373839import sys n = int(sys.stdin.readline())words = []for i in range(n): txt = sys.stdin.readline().rstrip() tmp = "" tmp2 = [] for j in range(len(txt)): if txt[j].isdigit(): tmp += txt[j] elif txt[j].isupper(): if tmp: cnt = tmp.count("0") tmp2.append(0) tmp2.append(int(tmp) + cnt * 0.01) tmp = "" tmp2.append(1) tmp2.append(ord(txt[j])) else: if tmp: cnt = tmp.count("0") tmp2.append(0) tmp2.append(int(tmp) + cnt * 0.01) tmp = "" tmp2.append(1) tmp2.append(ord(txt[j])-31.5) if tmp: cnt = tmp.count("0") tmp2.append(0) tmp2.append(.......
12345678910111213141516171819def solution(n): answer = '' while n: x = 0 tmp = n%3 if not tmp: x = 1 tmp = 4 if n < 3: answer += str(tmp) break n //= 3 n -= x answer += str(tmp) return answer[::-1] cs 1,2,4 즉 3개의 숫자를 표현하기 위해 3진법 사용 대신 3으로 나누어 떨어지는 경우 몫을 -1 하고 나머지를 4로 만든다.
12345678910111213141516171819202122232425import sys def dfs(v): visit[v] = 1 dp[v][0] = nums[v] for i in graph[v]: if not visit[i]: dfs(i) dp[v][0] += dp[i][1] dp[v][1] += max(dp[i][0], dp[i][1]) n = int(sys.stdin.readline())nums = [0] + list(map(int, sys.stdin.readline().split()))graph = [[] for _ in range(n+1)]for _ in range(n-1): a,b = map(int, sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a) dp = [[0]*2 for _ in range(n+1)]visit = [0 for _ in range(n+1)]dfs(1) print(max(dp[1][0],dp[1][1]))cs dfs + dp dp[n][0]는 자신을 포함dp[n][1]은 미포함
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556import sysfrom collections import defaultdict def check(): cnt = 0 tmp = [0,0] for i in range(5): tmp2 = [0,0] for j in range(5): tmp2[0] += bingo[i][j] tmp2[1] += bingo[j][i] if tmp2[0] == 5: cnt += 1 if tmp2[1] == 5: cnt += 1 tmp[0] += bingo[i][i] tmp[1] += bingo[i][4 - i] if tmp[0] == 5: cnt += 1 if tmp[1] == 5: cnt += 1 if cnt >= 3: return 1 else: return 0 dic = defaultdict(int)bingo = [[0]*5 for _ in range(5)] r = c = 0for _ in range(5): nums = list(map(int, sys.stdin.readline().split.......
1234567891011import sys n,m = map(int, sys.stdin.readline().split())sector = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]k = int(sys.stdin.readline())for _ in range(k): xy = list(map(int, sys.stdin.readline().split())) asw = 0 for i in range(xy[0]-1, xy[2]): asw += sum(sector[i][xy[1]-1:xy[3]]) print(asw)Colored by Color Scriptercs 단순 구현으로 범위 값을 합산하였는데 시간 초과 123456789101112131415import sys n, m = map(int, sys.stdin.readline().split())sector = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]k = int(sys.stdin.readline()) dp = [[0] * (m+1) f.......
12345678910111213141516171819202122232425262728293031from collections import dequeimport sys def bfs(): q = deque() q.append(n) while q: x = q.popleft() if x == k: break for y in x-1, x+1, x*2: if 0 <= y <= 100000 and visit[y] == -1: q.append(y) visit[y] = x n, k = list(map(int, input().split()))visit = [-1] * 100001visit[n] = -2 bfs() ans = []while k != -2: ans.append(k) k = visit[k] ans.reverse()print(len(ans)-1)print(' '.join(map(str, ans)))cs bfs로 평범하게 q에 경로를 같이 담으면 메모리 초과가 발생한다. 이에 visit리스트를 만들어 해당 경로의 이전 위치를 담는다.이후 거꾸로 탐색해가며 경.......
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748import sys,heapq def union(x,y): x = find(x) y = find(y) if x != y: parent[y] = x def find(x): if parent[x] == x: return x else: parent[x] = find(parent[x]) return parent[x] n, m = map(int, sys.stdin.readline().split())gender = list(map(str, sys.stdin.readline().split()))gender.insert(0,0)q = []for _ in range(m): u,v,d = map(int, sys.stdin.readline().split()) if gender[u] != gender[v]: heapq.heappush(q, [d,u,v]) parent = [int(i) for i in range(n+1)] ans = 0cnt = 0while q: c, a, b = heapq.heappop(q) if find(a.......
12345678910111213141516171819202122232425262728293031323334353637383940import sys,heapq def dijkstra(st): q = [] heapq.heappush(q, [0,st]) distance[st] = 0 while q: dist, node = heapq.heappop(q) if distance[node] >= dist: for v in graph[node]: cost = dist + v[1] if cost < distance[v[0]]: distance[v[0]] = cost heapq.heappush(q,[cost,v[0]]) n,m,r = map(int, sys.stdin.readline().split())items = [0] + list(map(int, sys.stdin.readline().split()))graph = [[] for _ in range(n+1)]distance = [int(1e9)] * (n+1)for _ in range(r): a,b,l = map(int, sys.stdin.readline().split()) graph[a].append([b,l]).......
1234567891011121314151617181920212223242526272829import sysfrom collections import deque def bfs(): q = deque() q.append([0,0,0]) visit = [[[0] * (k+1) for _ in range(m)] for _ in range(n)] visit[0][0] = [1] * (k+1) while q: x,y,z = q.popleft() dist = visit[y][x][z] if x == m-1 and y == n-1: return visit[y][x][z] for dx,dy in (0,1), (1,0), (0,-1), (-1,0): nx,ny = x+dx, y+dy if 0 <= nx < m and 0 <= ny < n and not visit[ny][nx][z]: if graph[ny][nx] == "0": visit[ny][nx][z] = dist + 1 q.append([nx,ny,z]) elif z < k: visit[ny][nx][z+1] = dist + 1 q.append([nx,ny,z+1]) return -1 n,m,.......
123456789101112import sys dp = [1,1,2,3] + [0] * 9997for i in range(4, 10001): dp[i] = dp[i-1] + (dp[i-2]-dp[i-3]) if i % 3 == 0: dp[i] += 1 for _ in range(int(sys.stdin.readline())): n = int(sys.stdin.readline()) print(dp[n])cs
12345678910111213141516def solution(lottos, win_nums): zeros = 0 wins = 0 for i in lottos: if i == 0: zeros += 1 continue if i in win_nums: wins += 1 if wins == 0: if zeros == 0: return ([6,6]) return ([7-zeros,6]) return ([7-(zeros+wins), 7-wins])cs
1234567891011121314151617def solution(enroll, referral, seller, amount): answer = [0] * (len(enroll)) graph_dict = dict(zip(enroll, range(len(enroll)))) for i in range(len(seller)): man = seller[i] price = amount[i] * 100 while True: node_num = graph_dict[man] div = price // 10 answer[node_num] += price - div price = div man = referral[node_num] if man == "-": break if div == 0: break return answerColored by Color Scriptercs
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051def rotate(y1,y2,x1,x2,graph): r = y1 c = x1 cnt = 0 tmp = graph[r+1][c] min_val = tmp while True: tmp2 = graph[r][c] graph[r][c] = tmp tmp = tmp2 if tmp < min_val: min_val = tmp if c == x2 and r == y1: cnt = 2 elif c == x2 and r == y2: cnt = 1 elif c == x1 and r == y2: cnt = 3 if cnt == 0: c += 1 elif cnt == 1: c -= 1 elif cnt == 2: r += 1 else: r -= 1 if r == y1 and c == x1: break return graph, min_val def solution(rows, columns, queries): answer = [] graph = [[0]*columns for _ in range(rows)] cnt.......
12345678910111213141516171819202122232425262728293031323334353637import sysfrom collections import defaultdict def dfs(st): visit[st] = 1 order.append(st) ans[st] += time[st] for i in graph[st]: if visit[i] == 0: visit[i] = 1 ans[i] += ans[st] dfs(i) n = int(sys.stdin.readline())graph = [[] for i in range(n+1)]visit = [0] * (n+1)ans = [0] * (n+1)order = [] time = defaultdict(int)st = 0 for i in range(1, n+1): tmp = list(map(int, sys.stdin.readline().split())) if len(tmp) == 2: st = i else: for j in range(1,len(tmp)-1): graph[tmp[j]].append(i) time[i] = tmp[0] dfs(st) for i in order: print(ans[.......
1234567891011121314151617import sys def make_table(): j = 0 table = [0] * len(txt) for i in range(1,len(txt)): while j and txt[i] != txt[j]: j = table[j-1] if txt[i] == txt[j]: j += 1 table[i] = j print(len(table) - table[-1]) l = int(sys.stdin.readline())txt = sys.stdin.readline().rstrip()make_table()cs kmp알고리즘으로 테이블을 구성하고 입력 문자열의 길이에서 접미사의 길이를 빼주면 된다.
123456789101112131415161718import sys n = int(sys.stdin.readline())m = 10 ** 6p = 15 * (10 ** 5)fibo = [0,1] if n < 2: print(fibo[n]) exit() for i in range(2,p): fibo.append((fibo[i-1]+fibo[i-2])%m) if i == n: print(fibo[n%p]) exit() print(fibo[n%p])cs 피보나치 수를 나눌 때 나머지는 항상 주기를 갖으며 이를 피사노 주기라 한다.주기의 길이를 p라고 하고 나누는 수를 m(= 10^k, (k>2))라 할 때, p는 항상 15 * 10^(k-1)을 성립한다.문제의 출력에서 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력하라 하였기에 m은 10^6이 되고 p는 15 * (10^5)가 된다.이를 활용해 문제를 해결하였다.
12345678910111213141516171819202122import sys def search(nums): global cnt st = 0 ed = n-1 while st < ed: tmp = nums[st]+nums[ed] if abs(tmp) < cnt[0]: cnt = [abs(tmp), nums[st], nums[ed]] if tmp < 0: st += 1 else: ed -= 1 n = int(sys.stdin.readline())nums = list(map(int, sys.stdin.readline().split()))cnt = [sys.maxsize,0,0]search(sorted(nums))print(cnt[1], cnt[2])cs 초기 값은 수의 최소, 최대. 이 합의 절대 값이 작다면 카운터 갱신합이 음수면 left point 증가, 양수면 right point 감소
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152import sysfrom collections import deque def bfs(w): q = deque() q.append(ans[0]) visit = [0] * (n+1) visit[ans[0]] = 1 while q: x = q.popleft() if x == ans[1]: return 1 for i,j in graph[x]: if j >= w and not visit[i]: visit[i] = 1 q.append(i) return 0 def search(): cnt = 1 st = 1 ed = 1000000000 while st <= ed: mid = (ed+st)//2 tmp = bfs(mid) if tmp == 1: cnt = mid st = mid + 1 else: ed = mid - 1 print(cnt) n,m = map(int, sys.stdin.readline().split())graph = [[] for _ in range(n+1)] for _ in ra.......
12345678910111213141516171819202122232425262728293031import sys def search(i): global cnt target = nums[i] nums.pop(i) st = 0 ed = l - 2 while st < ed: val = nums[st] + nums[ed] if val == target: nums.insert(i, target) cnt += 1 return elif val < target: ed -= 1 else: st += 1 nums.insert(i, target) cnt = 0n = int(sys.stdin.readline())nums = list(map(int, sys.stdin.readline().split()))nums.sort(reverse=True)l = len(nums)[search(i) for i in range(l)] print(cnt)Colored by Color Scriptercs 가능한 모든 경우의 수를 찾는게 아니므로 발견시 cnt+=1, return
12345678910111213141516171819202122232425import sys n = int(sys.stdin.readline())nums = list(map(int, sys.stdin.readline().split()))m = int(sys.stdin.readline()) st = 0ed = max(nums) while st <= ed: mid = (st+ed)//2 cnt = 0 for i in nums: if i > mid: cnt += mid else: cnt += i if cnt > m: ed = mid -1 else: st = mid + 1 print(ed)Colored by Color Scriptercs
문자의 효율적 탐색을 위한 트리형태의 자료구조 루트부터 트리를 타고 가 리프에 다달으면 해당 경로의 문자가 저장되어 있음을 의미 사용이유 단순 문자 비교들 통한 탐색의 시간 복잡도는 높기에 효율적인 탐색을 위해 사용 시간 복잡도 생성: O(len(string) + total_num(string)) 탐색: O(len(string)) ex) ba, abcd, ac ba 첫 문자는 b이다. trie자료구조에는 아무 정보가 없기에 루트의 child로 b추가 b의 child가 없기에 b에 a를 추가 abcd 루트의 child에 a가 없기에 루트의 child로 a추가 a의 child로 존재하는 b는 trie에 없기에 a의 child로 b추가 c를 b의 child로 추가 d를 c로 child로 추가 ac 루트의 child에 a가 존재하므로 a의 c.......
123456789101112131415161718192021222324252627282930313233343536373839404142import sys, heapq def union(x,y): x = find(x) y = find(y) if x != y: parent[y] = x def find(x): if parent[x] == x: return x else: parent[x] = find(parent[x]) return parent[x] q = []n, m = map(int, sys.stdin.readline().split())for _ in range(m): a, b, c = map(int, sys.stdin.readline().split()) heapq.heappush(q, [c,a,b]) parent = [int(i) for i in range(n+1)] ans = []cnt = 0while q: c, a, b = heapq.heappop(q) if find(a) == find(b): continue union(a, b) ans.append(c) cnt += 1 if cnt == n - 1: break print(sum(ans) - ans[-1]).......
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889class Node: def __init__(self,key,data=None): self.children = {} self.key = key self.flag = data# 노드의 정보를 담을 class Node 선언# 자식 노드의 정보 dictionary 형태로 선언# key: 해당 노드의 문자 정보가 들어간다# flag: 해당 노드의 전체 문자 정보를 가지고 있어# 끝나는 위치를 판단할 수 있게 하는 flag역할을 한다. class Trie: def __init__(self): self.root = Node(None) # 루트 노드의 정보를 Node를 호출해 초기화 def insert(self,strin.......
12345678910111213141516171819202122232425262728293031323334353637import sys class Node: def __init__(self, key, data=None): self.children = {} self.key = key self.flag = data class Trie: def __init__(self): self.root = Node(None) def insert(self, string): cur = self.root for char in string: if char not in cur.children: cur.children[char] = Node(char) cur = cur.children[char] cur.flag = string def start(self,n,cur): if n == 0: cur = self.root for c in sorted(cur.children.keys()): print("--"*n, c, sep="") self.start(n+1, cur.children[c]) n = int(sys.stdin.readline())trie = Trie() for _ in range(.......
1234567891011121314151617181920212223242526272829303132333435import sys def make(): j = 0 table = [0] * len(pattern) for i in range(1, len(pattern)): while j and pattern[i] != pattern[j]: j = table[j-1] if pattern[i] == pattern[j]: j += 1 table[i] = j return table def kmp(): j = 0 for i in range(len(string)): while j and string[i] != pattern[j]: j = table[j-1] if string[i] == pattern[j]: if j == len(pattern)-1: print(1) exit() else: j += 1 print(0) string = sys.stdin.readline()string = "".join([i for i in string if not i.isdigit()])pattern = sys.stdin.readline()table = make()kmp()Colored by Co.......
1234567891011121314151617181920212223242526import sys, heapq n = int(sys.stdin.readline())q = [] for _ in range(n): a,b = map(int, sys.stdin.readline().split()) heapq.heappush(q,[a,b])target, fuel = map(int, sys.stdin.readline().split()) cnt = 0bucket = []while fuel < target: while q and q[0][0] <= fuel: tmp = heapq.heappop(q) heapq.heappush(bucket, [-tmp[1], tmp[0]]) if not bucket: cnt = -1 break tmp = heapq.heappop(bucket) fuel -= tmp[0] cnt += 1 print(cnt)Colored by Color Scriptercs 보유하고 있는 연료가 목적지 보다 적을 때 현재 보유하고 있는 연료로 갈 수 있는 거리 범위의 거리와 연료를.......
123456789101112131415161718192021222324252627import sys, heapq q = []n = int(sys.stdin.readline())for _ in range(n): P,Q = map(int, sys.stdin.readline().split()) heapq.heappush(q, [P,Q]) cnt = 0com = [0] * nnum = [0] * nwhile q: tmp = heapq.heappop(q) for i in range(len(com)): if com[i] <= tmp[0]: if com[i] == 0: cnt += 1 com[i] = tmp[1] num[i] += 1 break print(cnt) for i in num: if i: print(i,end= " ")cs 컴퓨터의 종료시간을 담는 com과 컴퓨터 별 사용자의 대수를 체크하기 위한 num배열과 컴퓨터의 수를 담는 cnt를 초기화 한다.com[i]에 담긴 값(종료시간) 보다 시작 시간이 이상인 값이 있다면 컴퓨터.......
123456789101112131415161718import sys txt = sys.stdin.readline().rstrip()b = list(sys.stdin.readline().rstrip())stack = [] for t in txt: stack.append(t) if len(stack) < len(b): continue if stack[-len(b):] == b: del stack[-len(b):] if stack: print("".join(stack)) else: print("FRULA") Colored by Color Scriptercs 처음에는 while과 find()로 index위치를 찾아 제거하는 형태로 작성했으나 시간초과. 두번째 stack을 사용하며 string slicing하여 스택을 초기화 하는 형태로 작성했으나 이 또한 시간초과세번째 stack을 사용하며 문자를 list화 하여 del 하는 방식으로 해결
1234567891011121314import sys, heapq def print_(nums): for i in range(len(nums)-1): if nums[i] == nums[i+1][0:len(nums[i])]: return "NO" return "YES" t = int(sys.stdin.readline())for _ in range(t): n = int(sys.stdin.readline()) nums = [sys.stdin.readline().rstrip() for _ in range(n)] print(print_(sorted(nums)))cs 전화번호를 입력 받고 정렬(접두사 비교를 위해)함수에서 접두사를 찾으면 return NO, else return YES쉬운문제였는데 풀어보기도 전에 시간초과를 생각하느라 쓸데없이 고민했던것 같다.
12345678910111213141516import sys seq1 = sys.stdin.readline().rstrip()seq2 = sys.stdin.readline().rstrip()seq3 = sys.stdin.readline().rstrip()dp = [[[0]*(len(seq3)+1) for _ in range(len(seq2)+1)] for _ in range(len(seq1)+1)] for i in range(1,len(seq1)+1): for j in range(1,len(seq2)+1): for k in range(1,len(seq3)+1): if seq1[i-1] == seq2[j-1] == seq3[k-1]: dp[i][j][k] = dp[i-1][j-1][k-1] + 1 else: dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]) print(dp[-1][-1][-1])Colored by Color Scriptercs 추가된 seq에 대한 값만 기존 LCS에서 추가
123456789101112131415import sysfrom collections import defaultdict cnt = 0tree = defaultdict(int)while True: tmp = sys.stdin.readline().rstrip() if not tmp: break tree[tmp] += 1 cnt += 1 tree = sorted(tree.items())for name, num in tree: print("%s %.4f" % (name,num/cnt*100))cs
kmp알고리즘 문자열을 검색할 때 brute force하게 검색한다면 문자열의 길이 l, 패턴의 길이 p일 때, 최악의 경우 시간복잡도는 O(l*p)가 된다. 이를 보완하기위해 일치하지 않는 부분이 발생하면 불일치 전까지는 다시 비교하지 않는 알고리즘이 kmp이다. O(l+p) kmp는 접두사와 접미사의 개념이 사용된다. 문자열 abacaaaba가 있다면 접두사 aba 접미사 aba 접두사와 접미사가 일치하는 최대 길이를 찾아야한다. 일치하는 길이에 대해 점프가 가능하다. 두 포인터가 i = 1, j = 0으로 시작한다면 두 값이 일치하면 i의 위치에 j+1을 넣은 후 i,j의 값을 증가시키고 일치하지 않는다면 i의 값만 증가시키고 j의 값은 감소시킨다. 이때 두 값이 같.......
12345678910111213141516171819202122232425262728293031323334353637383940import sys def kmp_table(): j = 0 table = [0] * len(word) for i in range(1, len(word)): while j > 0 and word[i] != word[j]: j = table[j-1] if word[i] == word[j]: j += 1 table[i] = j return table def kmp(): j = 0 global cnt table = kmp_table() for i in range(len(txt)): while j > 0 and txt[i] != word[j]: j = table[j-1] if txt[i] == word[j]: if j == len(word) - 1: cnt += 1 val.append(i - len(word) + 2) j = table[j] else: j += 1 txt = sys.stdin.readline().replace("\n", "")word = sys.stdin.readline().replace("\n", "")val =.......
1234567891011121314151617181920212223242526272829303132import sys def make_table(): j = 0 table = [0] * len(word) for i in range(1,len(word)): while j and word[i] != word[j]: j = table[j-1] if word[i] == word[j]: j += 1 table[i] = j return table def kmp(): table = make_table() j = 0 for i in range(len(txt)): while j and txt[i] != word[j]: j = table[j-1] if txt[i] == word[j]: if j == len(word) - 1: print(1) exit() else: j += 1 print(0) txt = sys.stdin.readline().replace("\n","")word = sys.stdin.readline().replace("\n","")kmp()Colored by Color Scriptercs kmp로 해결.패턴이 발견되면 print, exit
12345678910111213141516171819202122232425262728import sys, heapq n, m = map(int, sys.stdin.readline().split())q = [] for _ in range(n): p, l = map(int, sys.stdin.readline().split()) mil = list(map(int, sys.stdin.readline().split())) heapq.heapify(mil) for _ in range(len(mil)-l): heapq.heappop(mil) heapq.heappush(q, [len(mil)-l, mil, l]) cnt = 0for _ in range(len(q)): tmp = heapq.heappop(q) if tmp[2] > len(tmp[1]): m -= 1 if m < 0: break cnt += 1 else: m -= heapq.heappop(tmp[1]) if m < 0: break cnt += 1 print(cnt)Colored by Color Scriptercs 가장 많은 과목을 신청하기 위해선 마일리지가 적.......
123456789101112131415161718192021222324252627282930import sys, heapqfrom collections import defaultdict def move(day): for _ in range(day): if day == 0: return 0 if not dic[day]: dic[day] = 1 return day else: day -= 1 return 0 dic = defaultdict(int)n = int(sys.stdin.readline())q = [] for _ in range(n): p, d = map(int, sys.stdin.readline().split()) heapq.heappush(q,[-p,d]) ans = 0while q: tmp = heapq.heappop(q) if move(tmp[1]): ans -= tmp[0] print(ans)Colored by Color Scriptercs 가장 많은 강연 비용을 구하기에 강연비용을 기준으로 max heap을 구성한다. 주어진 날짜에 강연을 하는게 아닌 안에 강연을.......
12345678910111213141516171819202122232425262728293031import sys g = int(sys.stdin.readline())p = int(sys.stdin.readline())gi = []parent = [int(i) for i in range(g+1)] def find(n): if parent[n] == n : return n else: parent[n] = find(parent[n]) return parent[n] def union(x,y): x = find(x) y = find(y) if x!=y: parent[y] = x gi = [int(sys.stdin.readline()) for _ in range(p)] ans = 0for n in gi: tmp = find(n) if tmp == 0: break ans += 1 union(tmp-1,tmp) print(ans)Colored by Color Scriptercs
12345n = int(input())for i in range(1,4294967295): if n < (i*(i+1))//2: print(i-1) exit()cs 가우스의 덧셈공식을 이용해 초과하는 값이 나오면 i-1 출력
1234567891011121314151617181920212223from collections import dequea,b = map(int, input().split())q = deque()q.append((a,1))ans = [] while q: value = q.popleft() if value[0] * 2 <= b: q.append((value[0]*2, value[1]+1)) if value[0] * 2 == b: ans.append(value[1]+1) value = (int(str(value[0]) + "1"), value[1]) if value[0] <= b: q.append((value[0],value[1]+1)) if value[0] == b: ans.append(value[1]+1) if not ans: print(-1)else: print(min(ans))cs 끝에 1을 추가한 값과 2를 곱한 값이 b를 넘지 않는다면 q에 추가, 여러 경우가 발생할 수 있기에 min(answer) 출력
1234567891011121314import heapqn = int(input())cards = []for _ in range(n): heapq.heappush(cards, int(input())) summation = 0while len(cards) > 1: x = heapq.heappop(cards) y = heapq.heappop(cards) summation += x + y heapq.heappush(cards, x + y) print(summation)cs 가장 적은 비교는 최소의 값 2개를 비교하는 것이다. 루프에서 매번 정렬 후 처리하는 것보다 효율적인 처리를 위해 최소힙을 구성하였다.
12345678910111213141516171819import sys,heapqn = int(sys.stdin.readline())times = []end = []for _ in range(n): s, t = map(int, sys.stdin.readline().split()) heapq.heappush(times,[s,t])times.sort() tmp = []heapq.heappush(tmp, times[0][1])for i in range(1,n): if tmp[0] > times[i][0]: heapq.heappush(tmp, times[i][1]) else: heapq.heappop(tmp) heapq.heappush(tmp,times[i][1]) print(len(tmp))Colored by Color Scriptercs tmp에 초기값으로 수업 종료 시간을 넣는다. 수업 종료 시간보다 시작 시간이 이른 값에 대해 종료시간을 tmp에 넣는다.시작 시간이 늦은 값이 나오면 비교하던 종료시간을 빼고 새로운 종료 시.......
123456789101112131415161718192021222324252627282930313233from collections import dequeimport sys n = int(sys.stdin.readline())graph = [list(map(int,sys.stdin.readline().split())) for _ in range(n)] def bfs(i,j,k,visit): q = deque() q.append((k,j)) visit[j][k] = 1 while q: x,y = q.popleft() for dx,dy in (0,1),(0,-1),(1,0),(-1,0): nx, ny = x+dx, y+dy if nx < 0 or nx >= n or ny < 0 or ny >= n: continue if visit[ny][nx] == 0 and graph[ny][nx] > i: q.append((nx, ny)) visit[ny][nx] = 1 ans = []for i in range(max(map(max,graph))): cnt = 0 visit = [[0] * n for _ in range(n)] for j in ra.......
12345678910111213141516171819202122232425262728293031323334from collections import dequeimport sys def bfs(fr,to,cnt): q = deque() q.append((fr[1],fr[0],0)) visit = [[0] * l for _ in range(l)] while q: x, y, c = q.popleft() for dx, dy in dir: nx, ny = x + dx, y + dy if nx < 0 or nx >= l or ny < 0 or ny >= l: continue if visit[ny][nx] == 0: q.append((nx, ny, c+1)) visit[ny][nx] = 1 if nx == to[1] and ny == to[0]: cnt.append(c+1) return min(cnt) dir = [(-2,1),(-1,2),(1,2),(2,1),(-2,-1),(-1,-2),(2,-1),(1,-2)] for _ in range(int(sys.stdin.readline())): l = int(sys.stdin.readline()) fr .......
12345678910111213141516171819202122232425import sys def dfs(v): visit[v][0] = 1 for i in graph[v]: if visit[i][0] == 0: visit[i][1] = visit[v][1] + 1 dfs(i) n = int(sys.stdin.readline())a,b = map(int, sys.stdin.readline().split())visit = [[0] * 2 for _ in range(n+1)]graph = [[] for _ in range(n+1)] for _ in range(int(sys.stdin.readline())): fr,to = map(int, sys.stdin.readline().split()) graph[fr].append(to) graph[to].append(fr) dfs(a) if visit[b][1]: print(visit[b][1])else: print(-1)Colored by Color Scriptercs 두 사람 중 한 사람 부터 탐색을 시작해 다른 사람 까지의 depth를 출력하는 알고리즘
1234567891011121314151617181920212223242526import syssys.setrecursionlimit(2000) def dfs(v): visit[v] = 1 for i in graph[v]: if visit[i] == 0: dfs(i) for _ in range(int(sys.stdin.readline())): n = int(sys.stdin.readline()) nums = [[i[0]+1, i[1]] for i in enumerate(map(int, sys.stdin.readline().split()))] visit = [0] * (n+1) graph = [[] for _ in range(n+1)] for i in nums: graph[i[0]].append(i[1]) graph[i[1]].append(i[0]) cnt = 0 for i in range(1,len(nums)+1): if visit[i] == 0: cnt += 1 dfs(i) print(cnt)Colored by Color Scriptercs 루프를 돌며 사이클 내의 노드 방문 체크.숫자의 사이클을 탐색하려는.......
12345678910111213141516171819202122232425262728293031323334353637383940import sysfrom collections import deque def bfs(i,j,c): q = deque() q.append((i,j)) visit[i][j] = 1 while q: y,x = q.popleft() for dx,dy in (0,1),(0,-1),(-1,0),(1,0): nx,ny = x +dx, y + dy if 0 <= nx < n and 0 <= ny < n: if visit[ny][nx] == 0: if c == 1: if graph[y][x] == "G": graph[y][x] = "R" if graph[ny][nx] == "G": graph[ny][nx] = "R" if graph[ny][nx] == graph[y][x]: q.append((ny, nx)) visit[ny][nx] = 1 def call(c): cnt = 0 for i in range(n): for j in range(n): if visit[i][j] == 0: cnt += 1 bfs(i, j,c) print.......
12345678910111213141516171819202122232425262728293031323334353637383940import syssys.setrecursionlimit(10000000) def prt_ans(): for i in range(1,v+1): for j in graph[i]: if visit[i][1] == visit[j][1]: return "NO" return "YES" def dfs(vertex): visit[vertex][0] = 1 ans.append(vertex) for i in graph[vertex]: if visit[i][0] == 0: visit[i][1] = not visit[vertex][1] dfs(i) k = int(sys.stdin.readline())graph = []visit = []ans = [] for _ in range(k): ans = [0] v, e = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(v+1)] visit = [[0]*2 for _ in range(v+1)] for _ in range(e): fr, to = .......
요구사항 숫자 n이 주어질때 1로 만드는 최소의 연산을 구하여라. 제약 조건 입력은 1 ~ 10^6의 정수가 된다.가능한 연산은 /3, /2, -1 이다. 1234567891011n = int(input())dp = [0, 0, 1, 1] + (pow(10,6) - 3) * [0] for i in range(4, n + 1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i],dp[i//3] + 1) if i % 2 == 0: dp[i] = min(dp[i],dp[i//2] + 1) print(dp[n])cs\ 문제 해결의 접근 dp 문제이기에 우선 점화식을 찾기 위해 접근하였다.1: [1], cnt = 02: [2,1], cnt = 13: [3,1], cnt = 14: [4,2,1], cnt = 25: [5,4,2,1], cnt = 36: [6,2,1], cnt = 27: [7,6,2,1] cnt = 38: [8,4,2,1] cnt = 39: [9,3,1] cnt = 210: [10,.......
요구사항 숫자 n과 숫자 list가 주어질 때 최대 합을 구하여라. 제약 조건 인덱스의 값을 연속적으로 더할 수 없다. 1234567n = int(input())k = list(map(int, input().split()))dp = [k[0],k[1]] + [0]*(n-2)for i in range(2,n): dp[i] = max(dp[i-1], dp[i-2]+k[i]) print(dp[-1])cs 문제 해결의 접근 dp 문제이기에 우선 점화식을 찾기 위해 접근하였다.예제 입력 [1 3 1 5]를 보면 연속된 값을 갖지 못하기에 dp[0] = 1(k[0]), dp[1] = 3(k[1])으로 고정이 된다. 그리고 dp[2]에 올 수 있는 값은 k[1]을 갖는다면 k[2]는 가질 수 없고 k[0]를 갖는다면 k[2] 또한 가질 수 있다.이를 식으로 표현하면 dp[2] = dp[1] or dp[2] = dp[0] + k[2].......
12345678910111213141516board = input().split(".")ans = "" for i in board: if i == "": ans += "." continue if len(i) % 2 == 1: print(-1) exit() cnt = [len(i) // 4, len(i) % 4 // 2] ans += "AAAA" * cnt[0] + "BB" * cnt[1] + "." print(ans[:-1])Colored by Color Scriptercs "."으로 문자열을 구분해주고 리스트에 공백이 있다면 "."을 더해주었다.마지막 점을 출력하지 않기 위해 [:-1]
1234567891011121314n = int(input())nums = list(map(int,input().split()))eratos = [0,0,1] + [1]*998for i in range(2,1001): if eratos[i] == 0: continue for j in range(2 * i,1001,i): eratos[j] = 0 cnt = 0for i in nums: if eratos[i] == 1: cnt += 1print(cnt)cs 에라토스테네스의 체
123456789doc = input()word = input()doc2 = doc.split(word)cnt = 0 for t in doc2: cnt += len(t) print((len(doc) - cnt) // len(word))cs doc를 찾고자하는 word로 나눈 후 계산
1234567891011121314t = int(input())for _ in range(t): n = int(input()) nums = list(map(int, input().split())) cnt = 0 tmp = nums.pop() for i in reversed(range(n-1)): if nums[i] <= tmp: cnt += tmp - nums[i] else: tmp = nums[i] print(cnt)cs 주가를 거꾸로 보면서 더 작은 값이 나오면 이득이 남을 의미하기에 차액을 더해준다.
123456789101112n = int(input())slime = list(map(int, input().split()))slime.sort()cnt = 0 while len(slime) > 1: a , b = slime.pop(0), slime.pop(0) slime.append(a+b) cnt += a*b slime.sort() print(cnt)cs 값 추가 시 정렬
123456789101112131415161718192021t = int(input()) case = []for _ in range(t): case.append(int(input())) fibo = [0,1]for _ in range(2,46): fibo.append(fibo[-2]+fibo[-1]) for n in case: ans = [] while n: for i in range(46): if fibo[i] <= n: tmp = fibo[i] n -= tmp ans.insert(0,tmp) print(" ".join(str(i) for i in ans))cs
123456789101112t = int(input())for i in range(t): n = int(input()) l = list(map(int, input().split())) l = sorted(l,reverse=True) ans = 0 for j in range(n-2): ans = max(ans,l[j]-l[j+2]) print(ans) Colored by Color Scriptercs 가장 적은 차이를 만드는 방법은 가장 큰 값을 가운데 놓고 그 다음 큰 값을 양옆에 쌓아가는 방식이다.이에 역순으로 정렬하게 되면 배열에서 2칸 떨어진 통나무는 옆에 놓이는 통나무가 된다.
12345678910111213141516171819202122232425262728293031323334353637383940import heapqimport sysn,k = map(int, sys.stdin.readline().split())info = []w = [] for _ in range(n): m,v = map(int,sys.stdin.readline().split()) heapq.heappush(info, [m,v]) for _ in range(k): w.append(int(sys.stdin.readline()))w.sort# ex) input: 1 65, 5 23, 2 99 ans = 0tmp = []for _ in range(k): b = heapq.heappop(w) # 1) b = 2, info = [[1,65], [5,23], [2,99]] # 2) b = 10, info = [[5,23]] while info and b >= info[0][0]: # 보석의 정보가 존재하고 가방에 담길 수 있는 보석이 있는 경우에만 heapq.heappush(tmp, -info[0][1]) # 보.......
1차 코드 (시간초과) O(n^2) 123456789101112131415161718192021222324252627282930313233from collections import defaultdictbkt = input()cut = []stick = []cnt = [0,0]bracket = [(bkt[0],0)]for i in range(1, len(bkt)): bracket.append((bkt[i], i)) if bkt[i] == ")" and bkt[i-1] == "(": cut.append([i-1,i])cnt = 1while bracket: if bracket[cnt][0] == ")" and bracket[cnt-1][0] == "(": tmp = [] tmp.append(bracket.pop(cnt)[1]) tmp.insert(0,bracket.pop(cnt-1)[1]) if tmp not in cut: stick.append(tmp) cnt = 0 cnt += 1 freq = defaultdict(int)for i in cut: for j in stick: if j[0] <= i[1] <= j[1]: freq[(j[0].......
12345n = int(input())dp = [1,2,3]for i in range(3, n+1): dp.append((dp[i-2] + dp[i-1])%15746)print(dp[n-1])cs
123456789101112131415n, m = map(int, input().split())eratos = [1] * (m+1)eratos[0] = 0eratos[1] = 0answer = [] for i in range(2,m+1): if eratos[i]: answer.append(i) for j in range(2*i, m+1, i): eratos[j] = 0 for i in answer: if i >= n: print(i)cs 에라토스테네스의 체 1. 구하고자 하는 모든 수를 나열한다. (eratos 리스트에서 2~m에 해당하는 값 = 1)2. 2는 소수이므로 answer에 2를 넣는다.3. 자기 자신을 제외한 2의 배수를 모두 0으로 만든다.4. 이후 0이 아닌 값이 나오면 해당 값을 answer에 넣고 배수들을 0으로 만든다.5. answer에서 범위(n <= value <= m)에 해당하는 값 만을 출력
12345678910n = int(input())arr = list(map(int, input().split()))dp = [0]*n for i in range(n): for j in range(i): if arr[i] > arr[j] and dp[i] < dp[j]: dp[i] = dp[j] dp[i] += 1print(max(dp))Colored by Color Scriptercs
123456n = int(input())arr = list(map(int, input().split()))dp = [0] * nfor i in range(n): dp[i] = max(dp[i-1]+arr[i], arr[i])print(max(dp))cs
1234567891011121314151617181920212223242526272829answer = []def decimal(n): m = 2*n eratos = [1]*(m+1) eratos[0] = 0 eratos[1] = 0 for i in range(2,m+1): if eratos[i]: answer[i] = 1 for j in range(2*i, m+1, i): eratos[j] = 0 nums = []while True: num = int(input()) if num == 0: break nums.append(num) answer = [0] * (max(nums)*2 + 1)decimal(max(nums)) for i in nums: result = 0 for j in range(i+1,2*i+1): if answer[j] == 1: result += 1 print(result)cs 값을 전부 받고 이 중 가장 큰 값을 에라토스테네스의 체 알고리즘으로 answer 배열 구성.이후 해당 범위에 대한 소수 존재 수 출력
123456789101112131415161718from itertools import combinations while True: nums = list(map(int, input().split())) n = nums.pop(0) if n == 0: break nums = list(combinations(nums,6)) for i in range(n): nums[i] = tuple(sorted(list(nums[i]))) nums = sorted(nums) for i in nums: print(" ".join(map(str, i))) print()Colored by Color Scriptercs
12345678910111213n = int(input())dp = [[0]*n for _ in range(3)] for i in range(n): for idx, val in enumerate(map(int, input().split())): dp[idx][i] = val for i in range(1, n): dp[0][i] += min(dp[1][i - 1], dp[2][i - 1]) dp[1][i] += min(dp[2][i - 1], dp[0][i - 1]) dp[2][i] += min(dp[1][i - 1], dp[0][i - 1]) print(min(dp[0][-1],dp[1][-1],dp[2][-1]))cs dp[n][i]는 dp[][i-1]과 다른 rgb color 중에 최소 비용이 되면 된다.
123456789101112seq1 = input()seq2 = input()dp = [[0]*(len(seq2)+1) for _ in range(len(seq1)+1)] for i in range(1,len(seq1)+1): for j in range(1,len(seq2)+1): if seq1[i-1] == seq2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i][j-1], dp[i-1][j]) print(dp[-1][-1])Colored by Color Scriptercs 입력: ACAYKP CAPCAK 0 C A P C A K 0 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 1 1 2 2 2 A 0 1 2 2 2 3 3 Y 0 1 2 2 2 3 3 K 0 1 2 2 2 3 4 P 0 1 2 3 3 3 4 공백의 표를 만들고 seq1[i] 와 seq2[j]에 같은 값이 있다면 이전 dp값에 1을 더하고값이 다르다면 dp[:j] 와 dp[:i] 범위의 dp에서 큰 값을 dp[i][j]에 넣는다. .......
1234567891011121314151617from itertools import combinationsn,c = map(int, input().split())words = input().split()vowels = ["a","e","i","o","u"]words.sort()words = list(combinations(words,n)) for i in words: cnt = [0, 0] for j in i: if j in vowels: cnt[0] += 1 else: cnt[1] += 1 if cnt[0] > 0 and cnt[1] > 1: print("".join(i)) Colored by Color Scriptercs 조합을 생성해 조건이 맞는 암호만 print
1234567891011n = int(input())if n <= 3: print(n) exit() dp = [0]dp.append(1)dp.append(2)for i in range(3,n+1): dp.append(dp[i-1] + dp[i-2])print(dp[-1]%10007)cs
1234567891011121314n = int(input())score = [0]*300for i in range(n): score[i] = int(input())dp = [0]*300dp[0] = score[0]dp[1] = score[0]+score[1]dp[2] = max(score[0]+score[2],score[1]+score[2]) for i in range(3,n): dp[i] = max(dp[i-2]+score[i],dp[i-3]+score[i]+score[i-1]) print(dp[n-1]) Colored by Color Scriptercs
12345n = int(input())dp = [0,1]for i in range(2,n+1): dp.append(dp[i-2] + dp[i-1])print(dp[-1])cs
12345n = int(input())dp = [0,1]for i in range(2,n+1): dp.append(dp[i-2] + dp[i-1])print(dp[-1])cs
1234567n = int(input())nums = [int(input()) for i in range(n)]dp = [0,1,1,1,2,2]for i in range(6,max(nums)+1): dp.append(dp[i-1] + dp[i-5])for i in nums: print(dp[i])cs
123456789T = int(input()) for test_case in range(1, T + 1): num = int(input()) if "9" in str(num): print('#{} {}'.format(test_case, "Yes")) else: print('#{} {}'.format(test_case, "No")) Colored by Color Scriptercs
1234567 nums = map(int, input().split()) sum = 0 for i in nums: if int(i) % 2 == 1: sum += int(i) print('#{} {}'.format(test_case,sum)) Colored by Color Scriptercs
12345678import collections T = int(input())for test_case in range(1, T + 1): print("#",end="") print(int(input()),end=" ") data = list(map(int, input().split())) print('#{} {}'.format(test_case,collections.Counter(data).most_common()[0][0]))cs collections.Counter(data).most_common() : 데이터 list 내의 최빈수와 빈도수를 튜플형태로 내림차순 출력
1234567891011121314151617for i in range(int(input())): cnt = 0 summation = 0 n = int(input()) price = list(map(int, input().split())) for j in reversed(price): if not cnt: cnt = j continue if j <= cnt: summation += cnt - j else: cnt = j print("#%d %d" % (i+1,summation))cs
123456789101112t = int(input())for i in range(1,t+1): num = input() n = round(float(num[:3])/10) if n >= 100: n /= 100 num = int(num) * 10 else: n /= 10 d = len(str(num))-1 print("#%d %.1f*10^%d" % (i,n,d) )cs
1234567891011121314151617181920t = int(input())for i in range(1,t+1): n, m = map(int, input().split()) doc = list(map(int,input().split())) for i in range(n): doc[i] = (doc[i],i) result = [] while doc: pri = max(doc) tmp = doc.pop(0) if pri[0] == tmp[0]: result.append(tmp) else: doc.append(tmp) for i in range(n): if result[i][1] == m: print(i+1) breakcs
문제 해결의 접근 각 노드가 양방향으로 연결되어 있고 가중치를 지닌다. 하나의 source로부터 2개의 destination을 찾아가지만, 특정 경로까지 합승(같이 이동함)이 가능함을 고려해야 한다. 그렇다면 모든 노드를 순차적으로 순회하며 해당 노드까지의 비용을 계산하고 그 노드부터 각각의 destination까지의 비용을 더해서 그 값이 가장 적은 경우를 생각하자. 문제에서 합승하지 않은 경우의 비용이 더 적다면 합승하지 않아도 됨을 명시하였는데, 이는 비용 중에서 start 노드부터 start 노드까지 이동 후 각 destination을 찾아가는 경우와 같기에 따로 처리하지 않아도 된다. 1234567891011121314151617181920212223242526272829303132333.......
12345678910111213141516171819202122232425262728293031323334353637def solution(play_time, adv_time, logs): tmp = list(map(int,play_time.split(":"))) play_time_sec = tmp[0]*3600 + tmp[1]*60 + tmp[2] tmp = list(map(int,adv_time.split(":"))) adv_time_sec = tmp[0]*3600 + tmp[1]*60 + tmp[2] total_time = [0 for _ in range(play_time_sec+1)] for i in logs: i = i.split("-") start = list(map(int, i[0].split(":"))) end = list(map(int,i[1].split(":"))) start = start[0]*3600 + start[1]*60 + start[2] end = end[0]*3600 + end[1]*60 + end[2] total_time[start] += 1 total_time[end] -= 1 for i in range(1, play_tim.......
def solution(s): answer = [] for i in range(1,len(s)+1): data = [] tmp = "" for j in range(len(s)): tmp += s[j] if len(tmp) == i: data.append(tmp) tmp = "" if len(tmp): data.append(tmp) tmp = "" data.append([]) cnt = 1 check = data[0] tmp2 = "" for j in range(1,len(data)): if len(data) == 1: break if data[j] == check: cnt +=1 else: if cnt == 1: tmp2 += check check = data[j] else: tmp2 += str(cnt) + check check = data[j] cnt = 1 answer.append(len(tmp2)) return min(answer) Colored by Color Scriptercs
12345678910111213141516171819202122232425262728293031323334import copy def solution(key, lock): l = len(lock) k = len(key) lock_array = [[0]*(k*2+l) for _ in range(k*2+l) ] for i in range(k, k+l): for j in range(k, k+l): lock_array[i][j] = lock[i-k][j-k] cnt = 0 while cnt < 4: for i in range(len(lock_array) - k): for j in range(len(lock_array) - k): tmp_lock = copy.deepcopy(lock_array) for o in range(k): for p in range(k): tmp_lock[o+i][p+j] += key[o][p] cnt2 = 0 for o in range(k,k+l): for p in range(k,k+l): if tmp_lock[o][p] == 0 or tmp_lock[o][p] == 2: cnt2 = 1 break if cnt2 == 1: break i.......
12345678910111213141516171819def solution(n): tri = [[0 for _ in range(1, i+1)] for i in range(1, n+1)] x, y = -1, 0 num = 1 for i in range(n): for j in range(i,n): if i % 3 == 0: x += 1 elif i % 3 == 1: y += 1 else: x -= 1 y -= 1 tri[x][y] = num num += 1 return sum(tri, []) Colored by Color Scriptercs
123456789101112import copy def solution(s): answer = [0,0] n = copy.deepcopy(s) while len(n) > 1: tmp = "".join(n.split("0")) answer[0] += 1 answer[1] += len(n) - len(tmp) n = bin(len(tmp))[2:] return answercs
12345678910111213141516171819def solution(record): answer = [] info = dict() rec = [] msg = {"Enter":"님이 들어왔습니다.", "Leave":"님이 나갔습니다."} for r in record: tmp = r.split() if tmp[0] == "Leave": rec.append((tmp[0],tmp[1])) else: info[tmp[1]] = tmp[2] if tmp[0] == "Change": continue rec.append((tmp[0],tmp[1])) for r in rec: answer.append(info[r[1]]+msg[r[0]]) return answerColored by Color Scriptercs dictionary 형태로 uid에 대한 닉네임 정보 갱신
1234567891011121314151617181920212223242526def solution(lines): times = [] for l in lines: tmp = l.split() end = tmp[1].split(":") process = float(tmp[2][:-1]) * 1000 end = int(end[0]) * 3600000 + int(end[1]) * 60000 + \ float(end[2]) * 1000 start = end - process + 1 times.append((start,end)) answer = 0 for time in times: fr = [time[0], time[1]] to = [time[0] + 999, time[1] + 999] cnt = 0 cnt2 = 0 for t in times: if t[0] <= to[0] and t[1] >= fr[0]: cnt += 1 if t[0] <= to[1] and t[1] >= fr[1]: cnt2 += 1 answer = max(answer,cnt,cnt2) return answerColored by Color Scriptercs 시간을 mi.......
문제를 해결의 접근 일반적인 bfs가 시작점을 설정하고 그래프를 탐색해 나가듯이 대기실 안에 있는 모든 ...