All Good

전체 글 - Table of Contents332

★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]*nd[0]=1if n==1:print(1)else: for i in range(1,n): new=[] new.append(1) for j in range(i-1): new.append(d[.. 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  🐤 대표적인 재귀 문제 → return 종료 조건 코드 + 함수 넣는 코드 2개 사이사이에 어떻게 코드 넣을 지 디자인만 잘하면 됨★ 4779 칸토어 집합 ★def draw(s,e): if (s+1)==e: return else: length=(e-s) step=(length//3) lines[s+step:s+step*2]=[' ']*(step) draw(s,s+step) draw(s+step*2,e)while 1: try: .. BOJ/🥈 2022. 12. 11.
★Binary Search Intermediate I - 9 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.
understanding pesudo-code of QuickSort 🦢 백준 퀵 정렬 대표 문제 모음) 추후 🦢 퀵 정렬 concepts 포스팅) 추후 🦢 QuickSort pseudo-code quick_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p < r) then { q Computer Science/Algorithms 2022. 12. 5.

티스토리툴바