All Good

BOJ88

★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 - 23 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.
★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.
★정렬 최상급1 - 1문제()★ 🏅 플래티넘 이상의 난이도는 각 문제의 접근방향 뿐만 아니라, 사고과정 흐름까지 최대한 리마인드하는 방식으로 기억하자! 🏅 정렬관련 포스팅 하단 참조 🏅 정렬에는 정말 많은 알고리즘이 있다. 플래이상의 난이도급 문제에서 정렬을 어떤 방식으로 접근하는 지 알아보자 ★ 2220 힙 정렬 ★ import math n = int(input()) if n==1:print(1) elif n==2:print(2,1) elif n==3:print(3,2,1) else: arr = [3,2,1] for i in range(n-3): end=int(math.log(i+3,2)) idx=len(arr)-1 for _ in range(end): arr[idx],arr[(idx-1)//2]=arr[(idx-1)//2],arr[.. BOJ/🏅 2023. 2. 7.
★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.

티스토리툴바