All Good

전체 글287

Linear Equation & Linear System / Rank & det(A) Linear Equation 👐🏻 선형 방정식이란, 변수 $x_1, x_2, .. x_n$이 있고, $a_1x_1 + a_2x_2 + ... + a_nx_n = b$로 나타낼 수 있는 방정식을 뜻한다. (b와 계수 a_1, a_2, ~ a_n은 실수 또는 복소수) 👐🏻 위 equation은 이렇게도 표현 가능하다. $a^Tx = b$ $$a = \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{bmatrix}, x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}$$ Linear System 👐🏻 선형 시스템은 앞서 설명한 linear equation이 1개 이상 구성된 시스템을 뜻한다 👐🏻 예시) ID A B.. Math & Linear Algebra/Concepts 2023. 2. 1.
★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.
🔸Coordinate Compression🔸 intro / implementation 🔸 넓게 퍼져 있는 값들을 문제 해결을 위해 좌표 압축. (위 그림의 경우 -6~5까지의 퍼져 있는 수들을 차례대로 0 - 1 - 2 - 3 - 4로 나열 가능) 🔸 주의점: 주어진 수들의 크기가 중요치 않고, 크기 순서만이 문제 해결에 필요할 때 좌표 압축 진행 🔸 구현 ex) 랜덤 크기 순으로 나열된 A[1], A[2], A[3], .... A[n]을 좌표 압축 ① A[1], A[2], ... , A[n]를 정렬한 새로운 배열 B[] 생성 ② 필요 시 중복된 원소들을 제거(중복 카운트 중요치 않을 경우만) ③ 각 A[i]를 B[]에서 이분탐색하여 B[]에서의 A[i] index를 계산 🔸 쉽게 말하자면, 랜덤하게 배치된 다양한 크기의 숫자들을 index의 크기.. Computer Science/Algorithms 2023. 1. 24.
dataframe 꾸미기 🤲 pandas의 dataframe을 jupyter css 파일 코드를 고치거나 추가하면 입맛에 맞게 꾸밀 수 있다! 그 과정을 소개해봄 - 수정 후 - 🤲 jupyter notebook styling css 파일 총 2개를 수정했다. ① custom.css ② style.min.css 🤲 custom.css 🤲 설명에 의하면 overriding되는 동일구조 code의 최종 of 최종본을 선언할 때 쓰라는 안내문 🤲 .dataframe은 style.min에서 찾아도 없어서(ctrl+F5 단축키) custom.css에 깔끔히 썼다. .dataframe th{ background:#B7E0F0; font-weight: 600; border:3px solid white; } → tag는 dataframe ta.. Python/Pandas&Numpy 2023. 1. 22.
★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.
🫂 Prefix Sum intro ✊🏻 구간 합 문제는 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 계산하는 문제 유형을 뜻한다. ✊🏻 예를 들면, 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정했을 때, 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40인 90이 된다. ✊🏻 N개의 정수로 구성된 수열이 있고, M개의 query 정보가 주어진다. 각 query는 left와 right로 구성. 각 query에 대하여 [left, right] 구간에 포함된 데이터들의 합을 출력해야 한다. (수행 시간 제한은 O(N+M)) → 위 예와 접목하자면, 5개의 데이터 (N=5)로 구성된 수열에서 매번 새로운 query 구간마다 해당 합을 구한다면 시간 복잡도는 O(N.. Computer Science/Algorithms 2023. 1. 18.
Numpy fundamentals 2/2 🎅 numpy는 필수적으로 알아야 하는 library로, 수학 연산 관련해서 반드시 쓰이는 library. 옛날 포스팅에 이어서 numpy 관련 다양한 기능을 익혀보자! NumPy intro. + fundamentals 1/2 1. 개념 * NumPy = Numerical Python - Python에서 대규모 다차원 배열을 다룰 수 있게 도와주는 library * 데이터의 대부분은 숫자 배열로 볼 수 있기에 NumPy는 꼭 필요 - 이미지나 소리 등 실생활 대부분이 숫 sh-avid-learner.tistory.com 1. numpy 배열 생성 다양한 함수 * 배열 생성 및 초기화 함수 🎅 zeros() - 주어진 형태와 타입을 갖는 0으로 채워진 배열 반환 (지정된 shape 배열을 생성하고 모든 요.. Python/Pandas&Numpy 2023. 1. 16.
★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.
Regular Expression 💚 정규 표현식은 '패턴 매칭 기반으로 특정한 규칙을 가지는 문자열을 검색&분리하고 교체하는 강력한 기능을 제공하는 형식 언어' 💚 python에서는 re library를 import import re 1. re.search() & re.match() & re.fullmatch() 💚 re.match() checks for a match ONLY at the beginning of the string, whereas re.search() checks for a match anywhere in the string ※ re.match는 문자열 처음부터 매칭 / re.search는 문자열 일부분 매칭) ※ 💚 re.fullmatch() checks for entire string to be a match. ①.. Computer Science/Algorithms 2023. 1. 11.
★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.
Types of Binary Tree🌲 🌲priority queue 자료구조 포스팅에서 heap은 일종의 CBT(Complete Binary Tree) 형태로 구현된다고 언급한 적이 있다. priority queue - heap 1. concepts> ☝️ 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' ☝️ 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가 sh-avid-learner.tistory.com 🌲 여기서 다양한 종류의 Binary Tree에 대해 간단하게 알아보자. 🌲 Binary Tree란 tree 자료구조의 일종으로, 각 node의 자식 node는 최대 2개 존재하며, 이를 left & right child라고 부른다. ① representation) .. Computer Science/Data Structures 2023. 1. 10.
priority queue(binary heap) 1. concepts> ☝️ 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' ☝️ 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우 자료구조 추출되는 데이터 stack 가장 나중에 삽입된 데이터 queue 가장 먼저 삽입된 데이터 priority queue 가장 우선순위가 높은 데이터 ☝️ 우선순위 큐는 크게 두 가지 방법으로 구현 가능 ① 단순히 list로 구현 ② heap을 이용하여 구현 ※ heap을 사용해서, 단순히 먼저 들어오거나 나중에 들어온 순서가 아닌, 우선순위가 높은, 즉 최댓값 먼저, 아니면 최솟값 먼저 뽑을 수 있는 자료구조를 이용해 효율적인 시간 효율 내로 연산 진행.. Computer Science/Data Structures 2023. 1. 9.
★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.
🛝Dynamic Programming🛝 intro 🐥 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함. 따라서 완전탐색의 비효율적인 시간 복잡도 성능 한계점을 해결해준다. 또한 '다이나믹 프로그래밍 = 동적계획법'이라고도 부른다. (동적(dynamic) 할당(allocation) - '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'). DP 알고리즘을 활용한다면 여러 sub-problem 포함 모든 문제의 정답이 들어가는 메모리 미리 배치(이 때 여러 문제들의 결과를 저장하는 저장용 list는 dp-table). DP 알고리즘을 활용하기 위해서는 아래 두가지 조건을 만족해야 한다. ① 최적 부분 구조(Optimal Subst.. Computer Science/Algorithms 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.
bitmasking * intro> 💧 bitmask = '컴퓨터는 내부적으로 모든 자료를 이진수로 표현. 이 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법' (엄밀하게 자료구조는 아님) 💧 2진수 관련 bit 연산을 진행하면 웬만한 모든 연산의 time complexity가 $O(1)$로 표현되므로 매우 매우 유용하고 편리함! 💧 2진수와 10진수 간의 변환방법 (python) ① 10진수 → 2진수: bin() 함수 사용 (반환 결과 string) print(bin(100)) #0b1100100 #type 'str' ② 2진수 → 10진수 (1) 2진수가 0과 1로 구성된 숫자라면 앞에 0b를 붙이고 출력 (2) 2진수가 문자열 형태라면 int()에 문자열과 2를 지정해 변환 ※ bin의 결과가 문자열로 반환.. Computer Science/Algorithms 2022. 12. 20.
★Sorting Upper-Intermediate I - 6 Solved★ ★ 1138 한 줄로 서기 ★ N = int(input())highers = list(map(int,input().split()))[::-1]orders = []for higher in highers: orders.insert(higher,N) N -= 1print(*orders) 👫🏿 자신보다 키 큰 사람이 앞에 몇 명 있는 지 정보에 따라 줄을 선 순서대로 출력하는 문제→ 먼저 키가 큰 사람부터 앞에 자신보다 키 큰 사람의 정보에 따라 줄을 선다면(입력한 반대순 정렬 - 여기서는 [::-1] 사용), 이 정보는 곧 앞에 서 있는 사람의 명수가 되고, 곧 줄 line의 index가 되어 python insert() 함수를 사용해 차례대로 줄을 설 수 있다.★ 2108 통계학 ★ 🍭 최빈.. BOJ/🥈 2022. 12. 20.
★Number Theory Intermediate I - 17 Solved★ ★ 9613 GCD 합 ★ import sys input=sys.stdin.readline from itertools import combinations def gcd(a,b): #a0: a,b=b%a,a return b for _ in range(int(input())): ans = 0 pairs = list(combinations(list(map(int, input().split()))[1:], 2)) for pair in pairs: ans += gcd(pair[0], pair[1]) print(ans) 🦙 최대공약수 GCD를 구하는 알고리즘은 크게 아래와 같이 3가지로 나눌 수 있다. ① math module 내장함수 사용 ② 유클리드 호제법 사용 (별도 gcd 함수 따로 만들기 / 재귀) ③ 정.. BOJ/🥈 2022. 12. 13.
★Stack & Queue & Deque Intermediate I - 20 Solved★ ★ 10828 스택 ★ import sys N = int(sys.stdin.readline()) stack = []*N kinds = ['push', 'pop', 'size', 'empty', 'top'] for _ in range(N): order = sys.stdin.readline().split() kind = order[0] if kind == kinds[0]: stack.append(order[1]) elif kind == kinds[1]: if len(stack) > 0: print(stack[-1]) stack.pop() else: print(-1) elif kind == kinds[2]: print(len(stack)) elif kind == kinds[3]: print(0) if len(.. BOJ/🥈 2022. 12. 11.
★Recursion Intermediate - 2 Solved★ ★ 17478 재귀함수가 뭔가요? ★ N = int(input()) print('어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.') def CH(n): if n < 0: return print('_'*4*(N-n) + '"재귀함수가 뭔가요?"') if n != 0: print('_'*4*(N-n) + '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.') print('_'*4*(N-n) + '마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.') print('_'*4*(N-n) + '그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."') else: print('_'*4*(N-n) + .. BOJ/🥈 2022. 12. 11.
★Binary Search Intermediate I - 7 Solved★ 👩🏼‍🔬 binary-search의 핵심은 탐색 범위를 줄여, 원하는 target을 찾는 시간 복잡도를 $O(logN)$으로 줄인다는 데 있다. 👩🏼‍🔬 binary-search 간략 요약 ① 주어진 array, 찾고자 하는 target, 시작 start와 끝 end - 4개가 주어진다. ② start와 end의 중간점 mid를 구한다(짝수이면 소수점 절사) ③ mid가 가리키는 값이 target이면 끝! target보다 크다면 end를 mid-1로, target보다 작다면 start를 mid+1로 설정 ★ 13777 Hunt The Rabbit ★ ※ binary-search 유일 Bronze 문제이지만 Intermediate 포스팅에 넣음 ※ def binary_search(n,l,start,end).. BOJ/🥈 2022. 12. 7.
👀 Binary Search 👀 intro 🐧 순차 탐색 - 선형 탐색) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인 (가장 기본적인 형태 - 한 개씩 확인) 🐧 이진 탐색) 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색(시작점, 끝점, 중간점을 이용하여 탐색 범위 설정) ※ 이진 탐색은 순차 탐색에 비해 탐색 범위가 훨씬 줄어들기 때문에 시간 복잡도는 log시간을 보인다. Q. 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾기 0 - 2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 ① 시작점) index 0, 중간점) index 4, 끝점) index 9 → 중간점이 2개 존재한다면, 소수점은 제외한 앞부분을 설정한다 → 4가 중간점 기준 왼쪽에 존재.. Computer Science/Algorithms 2022. 12. 6.

티스토리툴바