All Good

전체 글 - Table of Contents288

🦜 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.
★Backtracking Upper-Advanced I - 1 Solved★ ★ 9663 N-Queen ★ #n-queens #place n queens (not placed in the same row / col / diagonal dir) def track(x): global ans if x == N: #finished ans+=1 return else: for ny in range(N): if v1[ny] == v2[x+ny] == v3[x-ny] == False: v1[ny] = v2[x+ny] = v3[x-ny] = True track(x+1) v1[ny] = v2[x+ny] = v3[x-ny] = False N=int(input()) ans=0 v1=[False]*(N) #horizontal 0~(N-1) v2=[False]*(2*N-1) #diagonal (right.. BOJ/🥇 2024. 1. 24.
★Backtracking Advanced I - 3 Solved★ ★ 7490 0 만들기 ★ import sys input=sys.stdin.readline def track(nums,exp,start): if start == len(nums)+1: res=eval(exp) if res == 0: ans=[] for i in range(len(exp)): if i>=1 and exp[i-1].isdigit() and exp[i].isdigit(): ans.extend([' ',exp[i]]) else: ans.append(exp[i]) print(*ans,sep='') else: #needs to be added for x in [' ','+','-']: if x == ' ': exp+=str(start) track(nums,exp,start+1) exp=exp[:-1.. BOJ/🥇 2024. 1. 21.
★Backtracking Upper-Intermediate I - 9 Solved★ ★ 15663 N과 M (9) ★ import sys input=sys.stdin.readline N,M=map(int,input().split()) nums=list(map(int,input().split())) nums.sort() num,visited=[],[False]*N def track(): if len(num)==M: print(*num) else: last=0 for i in range(len(nums)): if not visited[i] and last!=nums[i]: visited[i]=True num.append(nums[i]) last=nums[i] track() num.pop() visited[i]=False track() ★ 15664 N과 M (10) ★ import sys .. BOJ/🥈 2024. 1. 20.
★Backtracking Intermediate I - 10 Solved★ ★ 15649 N과 M (1) ★ N,M=map(int,input().split()) ans=[] def track(): if len(ans) == M: #completed print(*ans) else: for x in range(1,N+1): if len(ans) == 0 or x not in ans: ans.append(x) track() ans.pop() #backtrack track() 🙃 backtracking 포스팅 참조 ★ 15650 N과 M (2) ★ N,M=map(int,input().split()) ans=[] def track(): if len(ans) == M: #completed print(*ans) else: for x in range(1,N+1): if len(ans) == .. BOJ/🥈 2024. 1. 18.
🙃 Backtracking intro 🙃 backtracking이란, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 구현력을 필요로 한다. 현재에서 나올 수 있는 모든 경우의 수를 모아 둔 decision space를 만들고, decision space의 각 부분마다 뻗어 나가며 그 다음으로 나오는 deicision space에서 계속해서 뻗어나가며 탐색. 만약 뻗어나간 결과 문제 상황에 맞지 않으면, 그 자리에서 중단하고 다시 뒤로 후퇴하면서 올라가 또 다른 경우의 수로 뻗어나가며 탐색. 🙃 즉, 요약하자면 재귀적으로 가능한 모든 case를 incrementally하게 탐색해나가면서 해당 문제 조건에 만족하지 않는 경우는 이전으로 돌아가(backtrack) 계속 솔루션을 찾는 기법(결론: 백트래킹은 그냥 .. Computer Science/Algorithms 2024. 1. 18.
👔 fashionMNIST Classifier before building a classification model ① check the version & load fashionMNIST data & load the training, test split of the fashionMNIST dataset : fashionMNIST dataset is a collection of grayscale 28x28 pixel clothing images. Each image is associated with a label as shown in this table import tensorflow as tf print(tf.__version__) #2.15.0 # Load the Fashion MNIST dataset fmnist = tf.keras.dataset.. Deep Learning/Experiments 2024. 1. 15.
🧿 Dijkstra's (Shortest Path) Algorithm intro 🧿 다익스트라 알고리즘이란 '방향 그래프 또는 무방향 그래프에서 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘'이다. 플로이드 알고리즘은 모든 정점 쌍 사이의 최단 거리를 일일이 구하는 알고리즘. 플로이드 알고리즘은 음수인 간선 존재는 괜찮지만 음수인 사이클이 있을 때만 문제이나, 다익스트라는 음수인 가중치를 가지는 간선이 있으면 아예 사용 불가능. 음수인 간선이 있다면 벨만포드 알고리즘 사용. 또한 정확한 최단거리가 아닌 근사치를 원할 경우 A* 알고리즘을 사용함. 다익스트라는 네트워크에서도 많이 사용. 🧿 일명 '최단 경로 알고리즘' 중 하나로, 최단 경로 문제 상황은 (1) 한 지점에서 다른 한 지점까지의 최단 경로 (2) 한 지점에서 다른 모든 지점까지의 최단 .. Computer Science/Algorithms 2024. 1. 14.
★Implementation&Simulation Upper-Intermediate I - 3 Solved★ ★ 2564 경비원 ★ import sys input=sys.stdin.readline w,h=map(int,input().split()) diameter = (w+h)*2 loc=[] ans=0 for _ in range(int(input())): d,l=map(int,input().split()) if d == 3: loc.append(l) elif d == 2: loc.append(l+h) elif d == 4: loc.append(h*2+w-l) else: #d==1 loc.append(h*2+w*2-l) d,l=map(int,input().split()) if d == 3: me = l elif d == 2: me = l+h elif d == 4: me = h*2+w-l else: #d==1 m.. BOJ/🥈 2024. 1. 8.
🥪Array & Linked List 1. Array 🥪 Array(배열)는 메모리 상에 원소를 연속하게 배치한 자료구조를 뜻한다. O(1)에 k번째 원소를 확인/변경 가능하다. 또한 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양(overhead)가 거의 없으며, 메모리 상에 데이터들이 붙어 있어서 cache hit rate가 높다. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다. ※ array에서의 cache hit rate가 높은 이유? : 데이터가 연속해서 배치되어 있으므로 cache 입장에서 array 내의 인근 데이터까지 cache block에 load 하므로 임의의 array 내의 원소 접근 시 인근 원소 역시 cache에 있을 확률이 높다. 그리고 반복적으로 동일한 array 내의 원소를 접근한다면 cac.. Computer Science/Data Structures 2024. 1. 8.
★DP Expert(Easy) I - 4 Solved★ ★ 14003 가장 긴 증가하는 부분 수열 5 ★ import sysinput=sys.stdin.readlineN=int(input())A=list(map(int,input().split()))#binary searchdef binary_search(l, i, x): start,end=0,len(l)-1 while start ⛹️ LIS의 길이와 내용을 O(nlogn) 시간 복잡도 이내로 구하는 교과서 문제. LIS의 길이는 ans_num list에서 binary search로 update하며 내용 추가. LIS의 내용은 ans_i list에서 앞선 binary search로 삽입되는 원소의 index를 update하며 거꾸로 최댓값부터 1이 될때까지 해당 되는 inde.. BOJ/🏅 2024. 1. 7.

티스토리툴바