All Good

전체 글 - Table of Contents288

★Greedy Upper-Advanced I - 1 Solved★ ★ 1700 멀티탭 스케줄링 ★ ❤️‍🔥 Optimal Page Replacement 알고리즘에서 콘센트에 처음으로 꼽는 page fault 횟수를 제외한 page fault의 횟수를 최소화하는 문제 ❤️‍🔥 ① 콘센트 채우기 → ② 콘센트에 존재하지 않는 첫 기기 등장하면(page fault 상황) (1) 이미 채운 기기 중 아예 존재하지 않는 기기가 있다면 해당 기기와 교체 (2) 없다면 콘센트 기기의 index 확인해 가장 나중에 등장하는 기기와 교체(greedy) import sys input=sys.stdin.readline N,K=map(int,input().split()) names=list(map(int,input().split())) ans=0 ps=[0]*N #power_strip in.. BOJ/🥇 2023. 10. 18.
Optimal Page Replacement Algorithm intro ▶ 운영체제 메인 메모리에 존재하지 않는 새로운 page가 있을 때 page fault가 발생. ▶ page fault가 발생할 때, existing page와 newly needed page replacement 진행 ▶ 이 때, page fault의 횟수를 최소화한 알고리즘이 Optimal Page Replacement Algorithm ▶ page hit & fault algorithm ▶ "when page fault, pages are replaced which would not be used for the longest duration of time in the future" ▶ ① referred page가 이미 main memory에 존재한다면, page hit count 1 증.. Computer Science/Algorithms 2023. 10. 18.
★BF Advanced I - 3 Solved★ ★ 14500 테트로미노 ★ import sys input=sys.stdin.readline N,M=map(int,input().split()) tetris=[] for _ in range(N): tetris.append(list(map(int,input().split()))) ans=0 for i in range(N): for j in range(M): #1x4 if j BOJ/🥇 2023. 10. 6.
C1W2 - Logistic Regression as a Neural Network 1. Binary Classification ★ Logistic Regression is an algorithm for binary classification ex) an input of an image(represented in 3 RGB matrices: 3 x 64 x 64; if 64 x 64 pixels) → output 1 (cat) vs 0 (non cat) ★ in binary classification, our goal is to learn a classifier(x → y), to predict whether this is a cat image or non-cat image(whether y is 1 or 0) ★ Notation: ① A single training example is.. Deep Learning/Fundamentals 2023. 9. 6.
★Greedy Advanced I - 4 Solved★ ★ 1744 수 묶기 ★ import sys input=sys.stdin.readline N=int(input()) arr=[int(input()) for _ in range(N)] ans=0 pos,neg,zero,one=[],[],[],[] for n in arr: if n==0: zero.append(0) elif n==1: one.append(1) elif n>0: pos.append(n) else: neg.append(n) #1. don't tie ones ans+=len(one) #2.tie pos(from the biggest) pos.sort(reverse=True) for i in range(0,len(pos),2): if i==len(pos)-1:ans+=pos[i] else:ans+=.. BOJ/🥇 2023. 8. 30.
★Greedy Intermediate II - 4 Solved★ ★ 2012 등수 매기기 ★ import sys input=sys.stdin.readline N=int(input()) ans,i=0,1 for x in sorted([int(input()) for _ in range(N)]): ans+=abs(x-i) i+=1 print(ans) 💲 greedy 알고리즘은 직관적으로 optimal solution의 모음 → 전체 최적 solution이라 생각하고 진행하는 경우가 많다. 💲 greedy 관점 분석 : 개별 상황) 각자 예상한 등수에 실제 등수 부여, 그리고 불만도 구하기 : 종합 상황) 불만도의 합 / 최적의 종합 상황) 불만도의 합이 최소 ★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 먼저 예.. BOJ/🥈 2023. 8. 20.
🚡Next Permutation / Previous Permutation Intro 1) Next Permutation ★ Combinatorics 조합론에서 흔히 볼 수 있는 대표 알고리즘 중 하나로, print the lexicographically next greater permutation of the given array. If there does not exist any greater permutation, then print the lexicographically smallest permutation of the given array. ★ 배열에 여러 수가 정렬되어 있다면, 사전 순으로 그 다음 수, 즉 현재 수보다 크되 큰 수 중 가장 작은 수를 구하는 알고리즘. 현재 수보다 큰 수가 존재하지 않는다면 permutation 중 가장 작은 수를 구함. ★ 예를 들.. Computer Science/Algorithms 2023. 8. 16.
★Combinatorics Upper-Intermediate I - 4 Solved★ ★ 2697 다음수 구하기 ★ import sys input=sys.stdin.readline def next_permutation(n,l): #ex) n = [3,2,1] i = l-2 while i>=0 and n[i]>=n[i+1]: i-=1 if i>=0: j=l-1 while n[j] =0 and n[i] >= n[i+1]: i-=1 if i>=0: j = l-1 while n[j] =0 and l[i]>=l[i+1]: i-=1 if i>=0: j=N-1 while l[j] nK+1=33 if nums>32: print(0) else: ans=[] for three_in_pair in combinations(MBTIs,3): x,y,z=three_in_pair[0],three_in_pair[1].. BOJ/🥈 2023. 8. 16.
★Regular Expression 중상급 - 2문제()★ ★ 정규표현식(Regular Expression)은 어떻게 쓸 수 있는 지 함수를 적절히 사용 / 정규표현식 문법을 알면 된다 ★ 9342 염색체 ★ import re,sys input=sys.stdin.readline for _ in range(int(input().strip())): chromosome = input().strip() if re.match('^[ABCDEF]?A+F+C+[A,B,C,D,E,F]?$',chromosome): print('Infected!') else: print('Good') 🦖 정규표현식 문법 차례대로 작성하자면! ① 문자열은 {A, B, C, D, E, F} 중 0개 또는 1개로 시작해야 한다 → ^[ABCDEF]? ② 그 다음에는 A가 하나 또는 그 이상 있어야 한.. BOJ/🥈 2023. 8. 14.
★Set/Map Upper-Intermediate I - 2 Solved★ ★ 2910 빈도 정렬 ★ import sys input=sys.stdin.readline N,C=map(int,input().split()) freq=dict() message=list(map(int,input().split())) order=1 for n in message: if n not in freq: freq[n] = [1, order] order += 1 else: freq[n][0] += 1 freq_sorted = sorted(freq.items(), key=lambda x:(-x[1][0],x[1][1])) for x in freq_sorted: for _ in range(x[1][0]): print(str(x[0]),end=' ') 🧑🏻‍🎨 hash table의 key값은 고유한 숫자.. BOJ/🥈 2023. 8. 11.
★Combinatorics Upper-Beginner - 4 Solved★ ★ 15439 Vera and Outfits ★ N=int(input()) print(N*N-N) 🥽 옷을 입을 수 있는 총 가짓수는N tops와 N pants의 조합 N*N가짓수. 여기서 똑같은 색깔끼리의 조합 총 N개만 제외해야 하므로 답은 N*N-N ★ 11050 이항계수 1 ★ N, K = map(int, input().split()) def factorial(n): ans = 1 for i in range(1,n+1): ans = ans * i return ans print(factorial(N)//(factorial(K)*factorial(N-K))) 💋 일단 이항계수 nCk는 (n!)/(k!(n-k)!)로 나타낼 수 있고, 팩토리얼 함수(for문 사용)를 만들어 세 함수의 반환을 이용했다. .. BOJ/🥉 2023. 8. 9.
👐 Primality Test ※ 소수(Prime Number) = 1과 자기 자신으로만 나누어지는 수 ※ 1. 약수의 개수 👐 ① 2~(N-1) 까지 모두 돌렸을 때 나머지가 0이 아니다 ② 약수의 개수가 2 def isPrime1(N): for i in range(2,N): if N%i == 0: return False return True def isPrime2(N): cnt = 0 for i in range(1,N+1): if N%i == 0: cnt += 1 if cnt == 2: return True else: return False → 위 두 풀이는 모두 O(N) 모든 범위를 돌며 일일이 확인 2. O(N^(1/2)) 👐 ③ 탐색 범위 N^(1/2)으로 줄이기 → 위와 동일하되 시간복잡도 O(N^(1/2)). 나누어지는 .. Computer Science/Algorithms 2023. 8. 8.

티스토리툴바