BOJ/🥈36

★Two-Pointers Upper-Intermediate I - 5 Solved★ ★ 3273 두 수의 합 ★ import sys input=sys.stdin.readline n=int(input()) l=list(map(int,input().split())) X=int(input()) #array l.sort() #two-pointers x,y=0,n-1 ans=0 while x X y-=1 print(ans) 🍡 오름차순 정렬 뒤, x를 배열 왼쪽 끝 / y를 배열 오른쪽 끝에 배치. l[x]+l[y]가 X보다 클 경우, x를 아무리 오른쪽으로 이동해도 X보다 클 수 밖에 없음. 따라서 y를 왼쪽으로 이동 / l[x]+l[y]가 X라면 정답 찾음! ans+=1 한 뒤, l[x]와 l[y]는 이제 X 나오는 연산에 필요 없으므로 x 오른쪽 이동, y 왼쪽 이동 / l[x]+l[y]가.. BOJ/🥈 2024. 2. 11.

★Backtracking Upper-Intermediate I - 9 Solved★ ★ 15663 N과 M (9) ★ import sys input=sys.stdin.readline N,M=map(int,input().split()) nums=list(map(int,input().split())) nums.sort() num,visited=[],[False]*N def track(): if len(num)==M: print(*num) else: last=0 for i in range(len(nums)): if not visited[i] and last!=nums[i]: visited[i]=True num.append(nums[i]) last=nums[i] track() num.pop() visited[i]=False track() ★ 15664 N과 M (10) ★ import sys .. BOJ/🥈 2024. 1. 20.

★Backtracking Intermediate I - 10 Solved★ ★ 15649 N과 M (1) ★ N,M=map(int,input().split()) ans=[] def track(): if len(ans) == M: #completed print(*ans) else: for x in range(1,N+1): if len(ans) == 0 or x not in ans: ans.append(x) track() ans.pop() #backtrack track() 🙃 backtracking 포스팅 참조 ★ 15650 N과 M (2) ★ N,M=map(int,input().split()) ans=[] def track(): if len(ans) == M: #completed print(*ans) else: for x in range(1,N+1): if len(ans) == .. BOJ/🥈 2024. 1. 18.

★Implementation&Simulation Upper-Intermediate I - 3 Solved★ ★ 2564 경비원 ★ import sys input=sys.stdin.readline w,h=map(int,input().split()) diameter = (w+h)*2 loc=[] ans=0 for _ in range(int(input())): d,l=map(int,input().split()) if d == 3: loc.append(l) elif d == 2: loc.append(l+h) elif d == 4: loc.append(h*2+w-l) else: #d==1 loc.append(h*2+w*2-l) d,l=map(int,input().split()) if d == 3: me = l elif d == 2: me = l+h elif d == 4: me = h*2+w-l else: #d==1 m.. BOJ/🥈 2024. 1. 8.

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

★BF Upper-Intermediate I - 2 Solved★ ★ 2503 숫자 야구 ★ import sys from itertools import permutations input=sys.stdin.readline N=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=[] for i in idxs: p.. BOJ/🥈 2023. 10. 26.

★Greedy Intermediate II - 4 Solved★ ★ 2012 등수 매기기 ★ import sys input=sys.stdin.readline N=int(input()) ans,i=0,1 for x in sorted([int(input()) for _ in range(N)]): ans+=abs(x-i) i+=1 print(ans) 💲 greedy 알고리즘은 직관적으로 optimal solution의 모음 → 전체 최적 solution이라 생각하고 진행하는 경우가 많다. 💲 greedy 관점 분석 : 개별 상황) 각자 예상한 등수에 실제 등수 부여, 그리고 불만도 구하기 : 종합 상황) 불만도의 합 / 최적의 종합 상황) 불만도의 합이 최소 ★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 먼저 예.. BOJ/🥈 2023. 8. 20.

★Combinatorics Upper-Intermediate I - 4 Solved★ ★ 2697 다음수 구하기 ★ import sys input=sys.stdin.readline def 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] =0 and n[i] >= n[i+1]: i-=1 if i>=0: j = l-1 while n[j] =0 and l[i]>=l[i+1]: i-=1 if i>=0: j=N-1 while l[j] nK+1=33 if nums>32: print(0) else: ans=[] for three_in_pair in combinations(MBTIs,3): x,y,z=three_in_pair[0],three_in_pair[1].. BOJ/🥈 2023. 8. 16.

★Regular Expression 중상급 - 2문제()★ ★ 정규표현식(Regular Expression)은 어떻게 쓸 수 있는 지 함수를 적절히 사용 / 정규표현식 문법을 알면 된다 ★ 9342 염색체 ★ import re,sys input=sys.stdin.readline for _ 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가 하나 또는 그 이상 있어야 한.. BOJ/🥈 2023. 8. 14.

★Set/Map Upper-Intermediate I - 2 Solved★ ★ 2910 빈도 정렬 ★ import sys input=sys.stdin.readline N,C=map(int,input().split()) freq=dict() message=list(map(int,input().split())) order=1 for n in message: if n not in freq: freq[n] = [1, order] order += 1 else: freq[n][0] += 1 freq_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=' ') 🧑🏻‍🎨 hash table의 key값은 고유한 숫자.. BOJ/🥈 2023. 8. 11.

★DAC 중상급1 - 3문제()★ 🍴 DAC 분할정복 문제는 주로 재귀를 사용해 여러 개의 sub-problem을 돌리고 차례차례 해결해나가는 경우가 많다. 중상급 이상의 난이도부터 차례대로 탐색해보자! 🍴 아래 DAC 이론 포스팅 참조 Divide&Conquer(DAC) intro> 🍻 분할(Divide)하고 정복(Conquer)하는 이 알고리즘은 문제를 풀 때의 접근 방식으로 분할 → 정복 → 결합 크게 세 단계로 진행된다. 🍻 ① 분할(Divide): 주어진 문제를 더 작은 여러 개의 sub-pr sh-avid-learner.tistory.com ★ 2630 색종이 만들기 ★ import sys input=sys.stdin.readline N=int(input()) W,B=0,0 confetti=[] def is_check(arr).. BOJ/🥈 2023. 3. 20.

★Number Theory Upper-Intermediate I - 8 Solved★ ★ 1850 최대공약수 ★import mathA,B = map(int, input().split())ans = ''.join(['1']*math.gcd(A,B))print(ans) 👑 1의 개수 A와 B의 최대공약수만큼 1이 나열되어 있는 수가 최대공약수. 최대공약수 성질 / 유클리드 호제법을 사용해 이를 증명해보자 ※ 1이 a개 있는 수와 1이 b개 있는 수의 최대공약수는 1이 gcd(a,b)개 있는 수 (a≥b)※ - 증명 - → 1이 a개 있는 수를 $S_a$, 1이 b개 있는 수를 $S_b$라고 하면$$S_a = \underbrace{111 ... 111}$$(1이 a개)$$S_b = \underbrace{111 ... 111}$$(1이 b개) → 아래와 같.. BOJ/🥈 2023. 2. 28.

이전 1 2 3 다음

티스토리툴바