BOJ/🥈40

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

★Divide & Conquer Upper-Intermediate I - 9 Solved★ ★ 2630 색종이 만들기 ★import sysinput=sys.stdin.readlineN=int(input())W,B=0,0confetti=[]def is_check(arr): side=len(arr) if all(arr[i][j] == 0 for i in range(side) for j in range(side)): return 'W' elif all(arr[i][j] == 1 for i in range(side) for j in range(side)): return 'B' else: return 0def get_confetti(arr,l,W,B): if l == 1: if arr[0][0] == 0: W+=1 .. BOJ/🥈 2023. 3. 20.

★Number Theory Upper-Intermediate I - 9 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개) → 아래와 같이 10의 지수승으로 나열할 수 있다... BOJ/🥈 2023. 2. 28.

★BFS&DFS Intermediate I - 20 Solved★ 🙆‍♂️ 그래프로 표현되는 여러 상황에서, 각 node의 visited 유무를 따질 때 그래프 탐색 방법에 따라 DFS / BFS로 나뉨 🙆‍♂️ 깊이있게 먼저 탐색하자면 DFS / 가까운 것 먼저 탐색하자면 BFS 🙆‍♂️ DFS / BFS 모두 딱! 3가지의 준비물 필요 ※ 이 때 DFS는 stack 사용 / BFS는 queue를 사용하므로 BFS 사용 시 deque import ※ ① 2차원 graph (각 node별로 연결된 node의 번호가 list로 저장됨)② visited 여부 1차원 list (최종적으로 방문되었는 지 확인)③ 시작 node★ 1260 DFS와 BFS ★ import sysinput = sys.stdin.readlinefrom collections import dequ.. BOJ/🥈 2023. 2. 17.

★Combinatorics Intermediate I - 5 Solved★ ★ 2407 조합 ★import mathn,m=map(int,input().split())print(math.factorial(n) // (math.factorial(n-m) * math.factorial(m)))👻 위 공식만 정확히 알고 있으면 끝! ★ 9375 패션왕 신해빈 ★import sysinput=sys.stdin.readlinefor _ in range(int(input())): n=int(input()) fashion={} if n==0: print(0) else: for _ in range(n): clothes=input().split() if clothes[1] in fashion: .. BOJ/🥈 2023. 2. 16.

★Set/Map Intermediate I - 14 Solved★ ★ 1620 나는야 포켓몬 마스터 이다솜 ★ import sysinput=sys.stdin.readlinepokemon={}N,M=map(int,input().strip().split())for i in range(N): pokemon[input().strip()]=i+1pokemon_list=list(pokemon.keys())for _ in range(M): problem=input().strip() if problem.isalpha():print(pokemon[problem]) else:print(pokemon_list[int(problem)-1]) 😽 포켓몬 번호를 말하면 포켓몬 이름을 출력하고, 반대로 포켓몬 이름을 말하면 포켓몬 번호를 출력하는, 즉 두 가지 정보 포켓몬.. BOJ/🥈 2023. 2. 15.

★Binary Search Upper-Intermediate I - 6 Solved★ 😻 이분탐색 알고리즘을 적용해야 함을 인지하는 부분이 제일 중요하다. 이분탐색을 풀어야 하는 문제의 판별법은 ① 노가다성이 들어간다. 일단, 내가 원하고자 하는, 무언가를 일일이 문제의 조건을 충족해가며 비교해가는 과정이 들어간다면 이분탐색 또는 매개변수 탐색 유형임을 고려해보자 ② ~자르기와 같은 주어진 최소, 최대 일렬로 나열된 줄에서 범위를 줄여가며 최종 target(point일 수도 있고, 주어진 범위의 길이일 수도 있다)을 찾는 문제라면 이분탐색을 고려해보자★ 1654 랜선 자르기 ★ import sysinput=sys.stdin.readlineK,N=map(int,input().split())ls=[int(input())for _ in range(K)]start,end=1,max(ls) #0.. BOJ/🥈 2023. 2. 9.

★Greedy Upper-Intermediate I - 9 Solved★ ★ 11497 통나무 건너뛰기 ★ 🦒 문제를 이해하고 idea를 생각하는 게 중요! 🦒 인접한 두 통나무 높이 차의 최댓값을 최소화하는 문제① 즉, 최소화하기 위해서는 인접한 두 통나무간의 높이 차가 최소화되어야 한다② 서로간의 높이 차를 최소화하려면, 가장 큰 통나무부터 순서대로 $h_1, h_2, h_3, h_4, .... h_n$으로 정렬한 뒤, $h_1$을 정중앙에, 그 다음 $h_2, h_3$를 양옆에, $h_4, h_5$를 그 다음 양 옆에 차례대로 배치하면, 서로 간의 높이 차를 최소화할 수 있다. 🦒 greedy의 생명은 시간 단축! 매우 많은 풀이를 보며 시간 단축을 문제의 특성에 맞게 code로 고쳐가며 진행해보자 - 352ms - ① 위 그림에 맞게 제일 높은 통나무를 가운데 중.. BOJ/🥈 2023. 1. 27.

★Math & Geometry Upper-Intermediate I - 6 Solved★ ★ 1002 터렛 ★ for _ in range(int(input())): x1, y1, r1, x2, y2, r2 = map(int, input().split()) d = (x1-x2)**2 + (y1-y2)**2 if d > (r1+r2)**2: print(0) elif d == (r1+r2)**2: print(1) elif (r1+r2)**2 > d > (r1-r2)**2: print(2) else: if r1!=r2: if d == (r1-r2)**2: print(1) else:print(0) else:print(-1) 🤽🏻‍♂️ 두 원의 위치 관계에 따른 두 원 교점의 개수 🤽🏻‍♂️ .. BOJ/🥈 2023. 1. 26.

★Coordinate Compression Upper-Intermediate - 3 Solved★ ★ 18870 좌표 압축 ★ 👨🏽‍🏫 좌표 압축 구현은 먼저 정렬로 새로운 배열을 만든 다음 → 중복 제거 → 그리고 index를 계산하는 3개의 step으로 진행 👨🏽‍🏫 마지막 세 번째 step을 시간단축을 위해 어떤 기법을 쓰는 지에 따라 상황별로 소요 시간을 다르게 계산할 수 있다. ① 이분탐색 bisect_left() 계산 풀이 from bisect import bisect_left import sys input=sys.stdin.readline N=int(input()) l=list(map(int,input().split())) B=sorted(set(l)) ans=[] for i in l: ans.append(bisect_left(B,i)) print(*ans) → step 1) 정렬로 B[.. BOJ/🥈 2023. 1. 24.

이전 1 2 3 4 다음

티스토리툴바