All Good

BOJ88

★Tree Advanced I - 1 Solved★ ★ 1068 트리 ★ import sysinput=sys.stdin.readlineN=int(input())l=list(map(int,input().split()))tree=[[] for _ in range(N)]visited=[[] for _ in range(N)]start_node = 51ans = 0def dfs(tree, visited, delete_node, start_node): global ans visited[start_node] = True if len(tree[start_node]) == 0: #leaf-node ans += 1 else: len_child = len(tree[start_node]) if len_child == .. BOJ/🥇 2023. 12. 22.
★Tree Upper-Intermediate I - 3 Solved★ ★ 1991 트리 순회 ★ import sys input=sys.stdin.readline def pre_order(node): print(node, end='') if tree[node][0] != '.': pre_order(tree[node][0]) if tree[node][1] != '.': pre_order(tree[node][1]) def in_order(node): if tree[node][0] != '.': in_order(tree[node][0]) print(node, end='') if tree[node][1] != '.': in_order(tree[node][1]) def post_order(node): if tree[node][0] != '.': post_order(tree[node].. BOJ/🥈 2023. 12. 19.
★BFS&DFS Advanced I - 13 Solved★ ★ 7576 토마토 ★ import sysinput=sys.stdin.readlinefrom collections import dequeM,N=map(int,input().split())graph=[]starts=[]depths=[[0]*M for _ in range(N)]visited=[[False]*M for _ in range(N)]def BFS(graph, depths, starts, visited): queue = deque(starts) dx,dy=[0,0,-1,1],[-1,1,0,0] while queue: v = queue.popleft() for i in range(4): nx,ny=v[0]+dx[i],v[1]+dy[i] .. BOJ/🥇 2023. 12. 15.
★BF Upper-Intermediate I - 2 Solved★ ★ 2503 숫자 야구 ★ import sysfrom itertools import permutationsinput=sys.stdin.readlineN=int(input())pos=list(permutations(['1','2','3','4','5','6','7','8','9'],3))idxs=[n for n in range(len(pos))]def get_strike_ball(a,b): strike=0 for x,y in zip(a,b): if x==y: strike+=1 return (str(strike),str(len(a+b)-len(set(a+b))-strike))for _ in range(N): num,S,B=input().split() didxs=[] .. BOJ/🥈 2023. 10. 26.
★Greedy Upper-Advanced I - 1 Solved★ ★ 1700 멀티탭 스케줄링 ★ ❤️‍🔥 Optimal Page Replacement 알고리즘에서 콘센트에 처음으로 꼽는 page fault 횟수를 제외한 page fault의 횟수를 최소화하는 문제 ❤️‍🔥 ① 콘센트 채우기 → ② 콘센트에 존재하지 않는 첫 기기 등장하면(page fault 상황) (1) 이미 채운 기기 중 아예 존재하지 않는 기기가 있다면 해당 기기와 교체 (2) 없다면 콘센트 기기의 index 확인해 가장 나중에 등장하는 기기와 교체(greedy)import sysinput=sys.stdin.readlineN,K=map(int,input().split())names=list(map(int,input().split()))ans=0ps=[0]*N #power_strip initia.. BOJ/🥇 2023. 10. 18.
★BF Advanced I - 3 Solved★ ★ 14500 테트로미노 ★ import sysinput=sys.stdin.readlineN,M=map(int,input().split())tetris=[]for _ in range(N): tetris.append(list(map(int,input().split())))ans=0for i in range(N): for j in range(M): #1x4 if j 🎢 테트리스 4개 size로 나누어 분석 : 1~3번은 모양 그대로 확인 / 4번과 5번은 각각 8개의 테트리스 모양 구현 🎢 직접 위 모든 경우의 수 따져 최댓값 update★ 1107 리모컨 ★ import sysinput=sys.stdin.readlinefrom itertools import produ.. BOJ/🥇 2023. 10. 6.
★Greedy Advanced I - 5 Solved★ ★ 1744 수 묶기 ★ import sysinput=sys.stdin.readlineN=int(input())arr=[int(input()) for _ in range(N)]ans=0pos,neg,zero,one=[],[],[],[]for n in arr: if n==0: zero.append(0) elif n==1: one.append(1) elif n>0: pos.append(n) else: neg.append(n)#1. don't tie onesans+=len(one)#2.tie pos(from the biggest)pos.sort(reverse=True)for i in range(0,len(pos),2): if i==len(pos)-1:ans+=pos[i] els.. BOJ/🥇 2023. 8. 30.
★Greedy Intermediate II - 11 Solved★ ★ 2012 등수 매기기 ★ import sysinput=sys.stdin.readlineN=int(input())ans,i=0,1for x in sorted([int(input()) for _ in range(N)]): ans+=abs(x-i) i+=1print(ans) 💲 greedy 알고리즘은 직관적으로 optimal solution의 모음 → 전체 최적 solution이라 생각하고 진행하는 경우가 많다. 💲 greedy 관점 분석: 개별 상황) 각자 예상한 등수에 실제 등수 부여, 그리고 불만도 구하기: 종합 상황) 불만도의 합 / 최적의 종합 상황) 불만도의 합이 최소 ★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 먼저 .. BOJ/🥈 2023. 8. 20.
★Combinatorics Upper-Intermediate I - 4 Solved★ ★ 2697 다음수 구하기 ★ import sysinput=sys.stdin.readlinedef next_permutation(n,l): #ex) n = [3,2,1] i = l-2 while i>=0 and n[i]>=n[i+1]: i-=1 if i>=0: j=l-1 while n[j]  ✋ next_permutation★ 5360 Next Permutation ★ def next_permutation(n,l): i = l-2 while i >=0 and n[i] >= n[i+1]: i-=1 if i>=0: j = l-1 while n[j]  ✋ next_permutation★ 1.. BOJ/🥈 2023. 8. 16.
★Regular Expression Upper + Intermediate - 3 Solved★ ★ 9342 염색체 ★ import re,sysinput=sys.stdin.readlinefor _ in range(int(input().strip())): chromosome = input().strip() if re.match('^[ABCDEF]?A+F+C+[A,B,C,D,E,F]?$',chromosome): print('Infected!') else: print('Good') 🦖 정규표현식 문법 차례대로 작성하자면!① 문자열은 {A, B, C, D, E, F} 중 0개 또는 1개로 시작해야 한다 → ^[ABCDEF]?② 그 다음에는 A가 하나 또는 그 이상 있어야 한다 → A+③ 그 다음에는 F가 하나 또는 그 이상 있어야 한다 → F+④ 그 다음에는 C가 하나 또는 그 이상 있어.. BOJ/🥈 2023. 8. 14.
★Set/Map Upper-Intermediate I - 3 Solved★ ★ 2910 빈도 정렬 ★ import sysinput=sys.stdin.readlineN,C=map(int,input().split())freq=dict()message=list(map(int,input().split()))order=1for n in message: if n not in freq: freq[n] = [1, order] order += 1 else: freq[n][0] += 1freq_sorted = sorted(freq.items(), key=lambda x:(-x[1][0],x[1][1]))for x in freq_sorted: for _ in range(x[1][0]): print(str(x[0]),end=' ') .. BOJ/🥈 2023. 8. 11.
★Combinatorics Upper-Beginner - 4 Solved★ ★ 15439 Vera and Outfits ★ N=int(input())print(N*N-N) 🥽 옷을 입을 수 있는 총 가짓수는N tops와 N pants의 조합 N*N가짓수. 여기서 똑같은 색깔끼리의 조합 총 N개만 제외해야 하므로 답은 N*N-N★ 11050 이항계수 1 ★ N, K = map(int, input().split())def factorial(n): ans = 1 for i in range(1,n+1): ans = ans * i return ansprint(factorial(N)//(factorial(K)*factorial(N-K))) 💋 일단 이항계수 nCk는 (n!)/(k!(n-k)!)로 나타낼 수 있고, 팩토리얼 함수(for문 사용)를 만들어 세 .. BOJ/🥉 2023. 8. 9.

티스토리툴바