All Good

전체 글 - Table of Contents287

★Math & Geometry Advanced I - 1 Solved★ ★ 1011 Fly me to the Alpha Centauri ★import sysinput=sys.stdin.readlinefor _ in range(int(input())): x,y=map(int,input().split()) diff=y-x closest_root=int(diff**(1/2)) if diff == (closest_root**2): print(closest_root*2-1) elif (diff-(closest_root**2)) 🍋 kn은 kn-1 / kn / kn+1 중 한 개만 가능 + 맨 앞과 맨 뒤의 거리 step은 1만 가능하다는 조건 하에 수학 규칙성을 찾는 문제→ y-x를 diff라고 한다면, 중복된 step 간격 없이 오름차순 -.. BOJ/🥇 2024. 4. 27.
🏘️Euler Sieve intro 🏘️ 소수 판정법으로 유명한 에라토스테네스의 체(Sieve of Eratosthenes)를 개선한 '오일러의 체(Euler Sieve)'에 대해서 소개한다. 에라토스테네스의 체는 소수 판별 시간 복잡도가 O(nloglogn)임이 알려져 있고, 이를 개선한 오일러의 체 시간 복잡도는 단 선형 시간만에 O(n)으로 판별이 가능하다. 🏘️ 에라토스테네스의 체의 시간 복잡도가 선형 시간(O(n))이 될 수 없는 이유는 합성수 210을 들면 쉽게 알 수 있다. 210은 2x3x5x7로 나타낼 수 있는데, 에라토스테네스의 체에 의해서는 2x3x5x7 / 2x3x5x7 / 2x3x5x7 / 2x3x5x7 와 같이 각각 빨간색 숫자일 때 210이 합성수임을 중복해서 알려주고 있다. 🏘️ 따라서, 이를 단 한.. Computer Science/Algorithms 2024. 4. 21.
🥐Counting Sort orders ① 정렬할 데이터 준비 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 ○ 이 때, 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 list를 생성 ○ ② 왼쪽부터 데이터를 하나씩 확인하며 데이터의 값과 동일한 index의 데이터를 1씩 증가시킨다. ③ 오름차순 결과를 확인하기 위해 각 원소의 계수가 저장된 list를 왼쪽 끝부터 돌려 해당 데이터의 값만큼 반복해 인덱스를 출력한다. - 출력 결과 - 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 about Counting Sort 🥐 특정한 조건이 부합할 때만 사용할 수 있으나 매우 빠르게 동작하는 정렬 알고리즘. (*특정한 조건: 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용) 🥐 .. Computer Science/Algorithms 2024. 4. 17.
🗼Tower of Hanoi intro 🗼 유명한 '하노이의 탑' 알고리즘에 대해 소개한다. 3개의 기둥이 있고, 다양한 크기의 n개의 원판(원판의 크기는 모두 다르다)이 존재한다. 퍼즐을 시작하기 전에는 한 기둥에 n개의 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 아래 3가지 조건을 만족 시키면서 다른 기둥으로 옮겨서 다시 쌓는 퍼즐이다. ① 한 번에 1개의 원판만 옮길 수 있다. ② 가장 위에 있는 원판만 이동할 수 있다. ③ 큰 원판이 작은 원판 위에 있어서는 안된다. 이 때, 최소 이동횟수로 맨 왼쪽 기둥에서 맨 오른쪽 기둥으로 n개의 원판을 순서에 맞추어서 쌓아주면 된다 example demo (n=3) 🗼 n=3일 때 Hanoi Tower를 쌓아보자! 🗼 Hanoi Tower 문제는 크게 아래 3가지 순서로 진.. Computer Science/Algorithms 2024. 4. 9.
➕Merge Sort orders ★ 원소를 개별적으로 나누고, 병합하는 두 과정이 수반되는 정렬 ★ (아래 과정 ②는 divide / ③은 merge) (따라서 merge sort는 나누고 + 합치고 두 과정) ① 정렬할 데이터 준비 (오름차순 가정) 7 3 1 5 6 4 2 ② 본격적인 merge sort를 하기에 앞서서 각각 원소가 1개씩만 있게끔 recursive하게 array를 절반으로 쪼갠다 (recursion 적용) 7 3 1 | 5 6 4 2 → 7 | 3 1 | 5 6 | 4 2 → 7 | 3 | 1 | 5 | 6 | 4 | 2 ③-1) 두 개씩 쪼개는 루트의 역 방향으로 작은 원소를 앞에, 큰 원소를 뒤에 놓는다. (1) 3 1 에서 3 | 1로 쪼갰으므로 1 3으로 정렬 (2) 5 6 에서 5 | 6으로 .. Computer Science/Algorithms 2024. 4. 6.
★Implementation&Simluation Upper-Advanced I - 1 Solved★ ★ 19237 어른 상어 ★ import sys input=sys.stdin.readline from collections import deque N,M,k=map(int,input().split()) #NxNsize / M sharks / smell limit k trace=[] smell=[[0]*N for _ in range(N)] sharks=deque() shark_ds_priorities=[] #shark_ds dx,dy=['?',-1,1,0,0],['?',0,0,-1,1] num_of_sharks=M for i in range(N): l=list(map(int,input().split())) trace.append(l) for j in range(N): if l[j] != 0: sharks... BOJ/🥇 2024. 3. 3.
★Stack & Queue & Deque Advanced I - 1 Solved★ ★ 9935 문자열 폭발 ★ import sys input=sys.stdin.readline s=list(input().rstrip()) explode=list(input().rstrip()) explode_length=len(explode) ans=[] for x in range(len(s)): ans.append(s[x]) if s[x] == explode[-1]: if explode_length BOJ/🥇 2024. 2. 24.
🍡 Two Pointers intro 🍡 two pointers란 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 이중 for문으로 돌리면 i=0일때의 정보를 i=1일 때 전혀 쓰이지 않지만, two pointers는 i=0일 때의 작업이 i=1일 때의 작업에 쓰인다. 과거 정보를 기억한 채로 효율적이게 index를 O(N)으로 움직이는 알고리즘. 이분탐색 문제를 투포인터로도 풀 수 있는 경우가 많고, 그 반대도 많다. two pointers는 O(N)으로, 각각의 모든 case를 일일이 점검할 필요 없이, 일부 case는 점프하는 경우만 풀이가 가능. explanation 🍡 위와 같은 배열이 있다고 할 때, a일때 b~i를 돌고 / b일 때 c~i를 도는.. Computer Science/Algorithms 2024. 2. 11.
★Two-Pointers Advanced I - 7 Solved★ ★ 15961 회전 초밥 ★ import sys input=sys.stdin.readline from collections import defaultdict N,d,k,c=map(int,input().split()) kinds=[int(input()) for _ in range(N)] y,ans,cnt,freq=0,0,0,defaultdict(int) for x in range(N): while cnt BOJ/🥇 2024. 2. 11.
★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.
🦜 Pigeonhole Principle intro 🦜 총 19개의 구멍이 있는 비둘기집에서 20마리의 비둘기가 들어가려고 할 때, 적어도 한 곳의 비둘기집에는 적어도 2마리 이상의 비둘기가 반드시 있을 수 밖에 없다는 원리. ① theorem I: 각 구멍에 A마리의 비둘기가 평균적으로 들어가 있다면, A가 정수가 아니라면, 적어도 한 곳에는 ceil(A)마리의 비둘기가 있다는 뜻. 나머지 비둘기 집에는 최대 floor(A)마리의 비둘기가 있다. ② theorem II: n+1개의 물건을 n개의 상자에 넣으려고 할 때, 적어도 한 개 이상의 상자에는 2개 이상의 물건을 넣을 수 밖에 없다. 🦜 generalization ①) 만약 Kn+1마리의 비둘기가 n개의 비둘기집에 들어가려고 할 때, (Kn+1)/n은 K + 1/n이므로 적어도 한 곳의.. Computer Science/Algorithms 2024. 2. 2.
★Implementation&Simluation Advanced I - 5 Solved★ ★ 21610 마법사 상어와 비바라기 ★ import sys input=sys.stdin.readline from collections import deque N,M=map(int,input().split()) baskets=[] for _ in range(N): baskets.append(list(map(int,input().split()))) moves=[] for _ in range(M): moves.append(tuple(map(int,input().split()))) clouds=deque([[N-2,0],[N-2,1],[N-1,0],[N-1,1]]) #(1) clouds moving dx,dy=[0,-1,-1,-1,0,1,1,1],[-1,-1,0,1,1,1,0,-1] for move in mo.. BOJ/🥇 2024. 1. 28.

티스토리툴바