BOJ/🥈36

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

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

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

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

이전 1 2 3 다음

티스토리툴바