All Good

BOJ80

★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.
★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 ans print(factorial(N)//(factorial(K)*factorial(N-K))) 💋 일단 이항계수 nCk는 (n!)/(k!(n-k)!)로 나타낼 수 있고, 팩토리얼 함수(for문 사용)를 만들어 세 함수의 반환을 이용했다. .. BOJ/🥉 2023. 8. 9.
★Sorting Advanced I - 5 Solved★ ★ 1083 소트 ★ import sys input=sys.stdin.readline N=int(input()) arr=list(map(int,input().split())) S=int(input()) for i in range(N): subarray_max = max(arr[i:i+S+1]) if arr[i] != subarray_max: subarray_max_index = arr.index(subarray_max) for j in range(subarray_max_index-i): arr[subarray_max_index-j], arr[subarray_max_index-j-1] = arr[subarray_max_index-j-1], arr[subarray_max_index-j] S-=(subarra.. BOJ/🥇 2023. 7. 28.
★Math & Geometry Upper-Beginner II - 19 Solved★ ★ 15818 오버플로우와 모듈러 ★import sysinput=sys.stdin.readlineN,M=map(int,input().split())nums=list(map(int,input().split()))ans=1for num in nums: ans*=(num%M)print(ans%M) 🤙 매우 큰 수에의 나머지를 구하는 건 큰 수 자체에 오버플로우 발생 가능성이 존재. 🤙 따라서 모듈러 연산을 활용! (A*B)%X = ((A%X)*(B%X))%X → 연산도중도중 곱해지는 수의 모듈러 결과를 구해 큰 수가 나오지 않게 과정 도중에 방지★ 16483 접시 안의 원 ★ print(round((int(input())/2)**2)) 🤙 아래의 그림으로 한 번에 설명된다★ 22938 백발백준하는 .. BOJ/🥉 2023. 4. 6.
★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.
★BFS&DFS Intermediate I - 17 Solved★ DFS / BFS ① DFS(Depth-First Search) ⚡️ 먼저 DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 ⚡️ 스택 자료구조(또는 재귀함수)를 이용하며, 구체적인 동작 과 sh-avid-learner.tistory.com 🙆‍♂️ 그래프로 표현되는 여러 상황에서, 각 node의 visited 유무를 따질 때 그래프 탐색 방법에 따라 DFS / BFS로 나뉨 🙆‍♂️ 깊이있게 먼저 탐색하자면 DFS / 가까운 것 먼저 탐색하자면 BFS 🙆‍♂️ DFS / BFS 모두 딱! 3가지의 준비물 필요 ※ 이 때 DFS는 stack 사용 / BFS는 queue를 사용하므로 BFS 사용 시 deque import ※ ① 2차원 graph (각 node별로.. BOJ/🥈 2023. 2. 17.
★Combinatorics Intermediate I - 3 Solved★ ★ 2407 조합 ★ import math n,m=map(int,input().split()) print(math.factorial(n) // (math.factorial(n-m) * math.factorial(m))) 👻 위 공식만 정확히 알고 있으면 끝! ★ 9375 패션왕 신해빈 ★ import sys input=sys.stdin.readline for _ 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: fashion[clothes[1]]+=1 else: fashion[clothes[1]] = .. BOJ/🥈 2023. 2. 16.
★Set/Map Intermediate I - 13 Solved★ ★ 1620 나는야 포켓몬 마스터 이다솜 ★ import sys input=sys.stdin.readline pokemon={} N,M=map(int,input().strip().split()) for i in range(N): pokemon[input().strip()]=i+1 pokemon_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 - 4 Solved★ 😻 이분탐색 알고리즘을 적용해야 함을 인지하는 부분이 제일 중요하다. 이분탐색을 풀어야 하는 문제의 판별법은 ① 노가다성이 들어간다. 일단, 내가 원하고자 하는, 무언가를 일일이 문제의 조건을 충족해가며 비교해가는 과정이 들어간다면 이분탐색 또는 매개변수 탐색 유형임을 고려해보자 ② ~자르기와 같은 주어진 최소, 최대 일렬로 나열된 줄에서 범위를 줄여가며 최종 target(point일 수도 있고, 주어진 범위의 길이일 수도 있다)을 찾는 문제라면 이분탐색을 고려해보자 ★ 1654 랜선 자르기 ★ import sys input=sys.stdin.readline K,N=map(int,input().split()) ls=[int(input())for _ in range(K)] start,end=1,max(ls.. BOJ/🥈 2023. 2. 9.

티스토리툴바