he_is_me의 등록된 링크

 he_is_me로 등록된 네이버 블로그 포스트 수는 101건입니다.

프로그래머스 - 징검다리 [내부링크]

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를 구성하여 우위에 있는 것을 결과로서 출력한다.

백준1300 - k번째 수 [내부링크]

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

백준 1926 - 그림 [내부링크]

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

백준 2800 - 괄호 제거 [내부링크]

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

백준 5670 - 휴대폰 자판 [내부링크]

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

백준 20210 - 파일 탐색 [내부링크]

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

프로그래머스 - 124 나라의 숫자 [내부링크]

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로 만든다.

백준 1949 - 우수 마을 [내부링크]

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]은 미포함

백준 2578 - 빙고 [내부링크]

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

백준15724 - 주지수 [내부링크]

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

백준 13913 - 숨바꼭질4 [내부링크]

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리스트를 만들어 해당 경로의 이전 위치를 담는다.이후 거꾸로 탐색해가며 경.......

백준 14621 - 나만 안되는 연애 [내부링크]

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

백준 14938 - 서강 그라운드 [내부링크]

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

백준 14442 - 벽 부수기2 [내부링크]

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

백준 15989 - 1,2,3 더하기 4 [내부링크]

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

백준 1305 - 광고 [내부링크]

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알고리즘으로 테이블을 구성하고 입력 문자열의 길이에서 접미사의 길이를 빼주면 된다.

백준 2749 - 피보나치 수3 [내부링크]

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)가 된다.이를 활용해 문제를 해결하였다.

백준 2470 - 두 용액 [내부링크]

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 감소

백준 1939 - 중량제한 [내부링크]

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

백준 1253 - 좋다 [내부링크]

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

백준 2512 - 예산 [내부링크]

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

트라이(trie) 자료구조 [내부링크]

문자의 효율적 탐색을 위한 트리형태의 자료구조 루트부터 트리를 타고 가 리프에 다달으면 해당 경로의 문자가 저장되어 있음을 의미 사용이유 단순 문자 비교들 통한 탐색의 시간 복잡도는 높기에 효율적인 탐색을 위해 사용 시간 복잡도 생성: 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.......

백준 1647 - 도시 분할 계획 [내부링크]

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

트라이(trie) 자료구조2 [내부링크]

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

백준 14725 - 개미굴 [내부링크]

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

백준 16172 - 나는 친구가 적다(Large) [내부링크]

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

백준 1826 - 연료 채우기 [내부링크]

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 보유하고 있는 연료가 목적지 보다 적을 때 현재 보유하고 있는 연료로 갈 수 있는 거리 범위의 거리와 연료를.......

백준 12764 - 싸지방에 간 준하 [내부링크]

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]에 담긴 값(종료시간) 보다 시작 시간이 이상인 값이 있다면 컴퓨터.......

백준 9935 - 문자열 폭발 [내부링크]

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 하는 방식으로 해결

백준 5052 - 전화번호 목록 [내부링크]

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쉬운문제였는데 풀어보기도 전에 시간초과를 생각하느라 쓸데없이 고민했던것 같다.

백준 1958 - LCS3 [내부링크]

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에서 추가

백준 4358 - 생태학 [내부링크]

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

백준 1701 - Cubeditor [내부링크]

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의 값은 감소시킨다. 이때 두 값이 같.......

백준 1786 - 찾기 [내부링크]

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

백준 16916 - 부분 문자열 [내부링크]

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

백준 12018 - Yonsei TOTO [내부링크]

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 가장 많은 과목을 신청하기 위해선 마일리지가 적.......

백준 2109 - 순회 강연 [내부링크]

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을 구성한다. 주어진 날짜에 강연을 하는게 아닌 안에 강연을.......

백준 10775 - 공항 [내부링크]

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

백준 1789 - 수들의 합 [내부링크]

12345n = int(input())for i in range(1,4294967295): if n < (i*(i+1))//2: print(i-1) exit()cs 가우스의 덧셈공식을 이용해 초과하는 값이 나오면 i-1 출력

백준 16953 - A->B [내부링크]

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) 출력

1715 - 카드 정렬하기 [내부링크]

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개를 비교하는 것이다. 루프에서 매번 정렬 후 처리하는 것보다 효율적인 처리를 위해 최소힙을 구성하였다.

백준 11000 - 강의실 배정 [내부링크]

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에 넣는다.시작 시간이 늦은 값이 나오면 비교하던 종료시간을 빼고 새로운 종료 시.......

백준 2468 - 안전 영역 [내부링크]

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

백준 7562 - 나이트의 이동 [내부링크]

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

백준 2644 - 촌수 계산 [내부링크]

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를 출력하는 알고리즘

백준 10451 - 순열 사이클 [내부링크]

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 루프를 돌며 사이클 내의 노드 방문 체크.숫자의 사이클을 탐색하려는.......

백준 10026 - 적록 색약 [내부링크]

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

백준 1707 - 이분 그래프 [내부링크]

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

백준 1463 - 1로 만들기 [내부링크]

요구사항 숫자 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,.......

개미 전사 (dp) [내부링크]

요구사항 숫자 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].......

백준 1343 - 폴리오미노 [내부링크]

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]

백준 1978 - 소수 찾기 [내부링크]

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 에라토스테네스의 체

백준 1543 - 문서 검색 [내부링크]

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로 나눈 후 계산

백준 11501 - 주식 [내부링크]

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 주가를 거꾸로 보면서 더 작은 값이 나오면 이득이 남을 의미하기에 차액을 더해준다.

백준 14241 - 슬라임 합치기 [내부링크]

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 값 추가 시 정렬

백준 9009 - 피보나치 [내부링크]

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

백준 1497 - 통나무 건너뛰기 [내부링크]

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칸 떨어진 통나무는 옆에 놓이는 통나무가 된다.

백준 1202 - 보석 도둑 [내부링크]

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]) # 보.......

백준 10799 - 쇠막대기 [내부링크]

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

백준 1904 - 01타일 [내부링크]

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

백준 1929 - 소수 구하기 [내부링크]

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)에 해당하는 값 만을 출력

백준 11053 - 가장 긴 증가하는 부분 수열 [내부링크]

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

백준 1912 - 연속합 [내부링크]

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

백준 4948 - 베르트랑 공준 [내부링크]

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 배열 구성.이후 해당 범위에 대한 소수 존재 수 출력

백준 6603 - 로또 [내부링크]

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

백준 1149 - RGB거리 [내부링크]

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 중에 최소 비용이 되면 된다.

백준 9251 - LCS [내부링크]

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]에 넣는다. .......

백준 1759 - 암호 만들기 [내부링크]

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

백준 11726 - 2xn 타일링_DP [내부링크]

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

백준 2579 - 계단오르기_DP [내부링크]

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

백준 2193 - 이친수_DP [내부링크]

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

백준 11727 - 2xn 타일링2_DP [내부링크]

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

백준 9461 - 파도반 수열 [내부링크]

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

SWEA 2357 - September 9 [내부링크]

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

SWEA 2072 - 홀수만 더하기 [내부링크]

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

SWEA 1204 - 최빈수 구하기 [내부링크]

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 내의 최빈수와 빈도수를 튜플형태로 내림차순 출력

SWEA 1859 - 백만 장자 프로젝트 [내부링크]

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

SWEA 9658 - 유효숫자 표기 [내부링크]

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

백준 1966 - 프린터 큐 [내부링크]

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가 시작점을 설정하고 그래프를 탐색해 나가듯이 대기실 안에 있는 모든 ...