All Good

BOJ80

★정렬 최상급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 - 8 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 - 5 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) 🤽🏻‍♂️ 두 원의 위치 관계에 따른 두 원 교점의 개수 🤽🏻‍♂️ 두 원의 위치 관계는 크게 6가지로 나뉜다. 🤽🏻‍♂️ 두 원의 중심 사이의 거리를 기준으로 6가지를 자세하게 .. 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.
★Prefix Sum 중급 - 5문제()★ 🐰 누적합 유형은 주로 어려운 난이도 다양한 알고리즘 유형의 답을 구하는 과정에서 많이 사용된다. 단독으로 사용되는 경우만 일부 문제를 골라 정리해봄 ★ 11441 합 구하기 ★ import sys input=sys.stdin.readline N=int(input()) B=[] a=0 for i in map(int,input().split()): a+=i B.append(a) for _ in range(int(input())): a,b=map(int,input().split()) if a==1:print(B[b-1]) else:print(B[b-1]-B[a-2]) 🐰 누적합을 구하기 위한 구간을 만든 뒤, 구간 B에서 원하는 구간만큼 바로 indexing으로 B[b-1] - B[a-2] 연산해주면 완료!.. BOJ/🥈 2023. 1. 18.
★Math Beginner IV - 22 Solved★ ★ 2914 저작권 ★ A,I=map(int,input().split()) print(A*(I-1)+1) 🔢 올림해서 결과를 내기 때문에 I-1을 곱한다음 1을 더하면 된다. ★ 15923 욱제는 건축왕이야!! ★ ans=0 N=int(input()) l=[] for _ in range(N): x,y=map(int,input().split()) l.append((x,y)) for i in range(N): if i==0: x0,y0=l[N-1][0],l[N-1][1] else: x0,y0=l[i-1][0],l[i-1][1] x1,y1=l[i][0],l[i][1] if x0==x1:ans+=(abs(y0-y1)) else:ans+=(abs(x0-x1)) print(ans) 🔢 누적해서 거리합을 더해나가면 .. BOJ/🥉 2023. 1. 16.
★PQ 중상급 - 6문제()★ 🧠 priority queue를 구현하기 위한 heap 관련 여러 문제는 기존 자료구조(stack, queue, deck)보다 더 복잡한 tree구조로, 중급 이하의 문제는 없다. 중상급 이상부터 여러 문제를 풀며 적응해보자 🧠 priority queue 관련 개념 포스팅 참고 priority queue - (binary) heap tree 1. concepts> ☝️ 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' ☝️ 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가 sh-avid-learner.tistory.com ★ 1927 최소 힙 ★ import sys import heapq input=sys.stdin.readline .. BOJ/🥈 2023. 1. 11.
★DP Advanced I - 4 Solved★ ★ 2591 숫자카드 ★ n=input()l=len(n)if l==1:print(1)else: dp=[0]*l #dp-table initialization - dp[0], dp[1] dp[0]=1 front_two=int(n[:2]) if front_two =4: dp[i]=0 else: dp[i]=dp[i-2] print(dp[-1]) 👄 dp-table을 전형적인 dp 유형 답게 update하는 유형이나, 맨 마지막 숫자가 0일 경우의 예외를 처리하는 dp 유형! 👄① 길이가 1인 경우 - 숫자 1개로 이루어진 카드 1개 - dp[0] = 1 ② 길이가 2인 경우(1) 앞.. BOJ/🥇 2023. 1. 8.
★Stack & Queue & Deque Upper-Intermediate I - 11 Solved★ ★ 1874 스택 수열 ★ import sys input = sys.stdin.readline stack,sequence,ans = [],[],[] cur = 0 for _ in range(int(input())): sequence.append(int(input())) sequence = sequence[::-1] while len(sequence) != 0: popped = sequence.pop() if popped > cur: for i in range(cur+1,popped+1): stack.append(i) ans.append('+') cur = popped if popped == stack[-1]: stack.pop() ans.append('-') else: ans = [] break if l.. BOJ/🥈 2023. 1. 8.
★Bitmasking Intermediate I - 3 Solved★ 🔟 bitmasking 연산은 매우 빠른 연산으로 O(1)의 time complexity를 보이는 경우가 많아 많이 쓰이는 기법 중 하나 🔟 다만, 0과 1을 이용한 2진수 연산이기 때문에 컴퓨터가 실제로 연산하는 하드웨어적인 성격이 들어가므로 단순 연산보다 좀 더 신경을 써야 함 🔟 아래 개념 정리 링크 참조 ☀️bitmasking☀️ * intro> 💧 bitmask = '컴퓨터는 내부적으로 모든 자료를 이진수로 표현. 이 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법' (엄밀하게 자료구조는 아님) 💧 2진수 관련 bit 연산을 진행 sh-avid-learner.tistory.com 🔟 특히 집합 관련 연산을 사용할 때 bitmasking 기법이 많이 쓰인다. 여러 문제를 통해서 적응하도록.. BOJ/🥈 2023. 1. 5.
★DP Upper-Intermediate I - 15 Solved★ ★ 2579 계단 오르기 ★ # dp 1차원 배열import sysinput=sys.stdin.readlineN=int(input())S=[0]for _ in range(N):S.append(int(input()))if N==1:print(S[1])elif N==2:print(S[1]+S[2])elif N==3:print(S[3]+max(S[1],S[2]))else: dp=[0]*(N+1) dp[1]=S[1] dp[2]=S[1]+S[2] dp[3]=S[3]+max(dp[1],S[2]) for i in range(4,N+1): dp[i]=S[i]+max(dp[i-2],dp[i-3]+S[i-1]) print(dp[-1]).. BOJ/🥈 2023. 1. 3.
★DP Intermediate I - 20 Solved★ ★ 17202 핸드폰 번호 궁합 ★ A=list(input()) B=list(input()) l=[] for i in range(8):l.extend((int(A[i]),int(B[i]))) while len(l)>2: L=len(l) for j in range(L-1):l[j]=(l[j]+l[j+1])%10 del l[-1] print(*l,sep='') ★ 16395 파스칼의 삼각형 ★ n,k=map(int,input().split()) d=[0]*n d[0]=1 if n==1:print(1) else: for i in range(1,n): new=[] new.append(1) for j in range(i-1): new.append(d[i-1][j]+d[i-1][j+1]) new.append(1) .. BOJ/🥈 2022. 12. 22.

티스토리툴바