All Good

전체 글287

★Coordinate Compression Advanced - 2 Solved★ ★ 18869 멀티버스 II ★ import sys input=sys.stdin.readline from collections import defaultdict M,N=map(int,input().split()) cu_list,ans=[],0 def get_compressed_coordinate(l): sort_l = sorted(set(l)) cd = {sort_l[i]: i for i in range(len(sort_l))} x = [cd[n] for n in l] return x for _ in range(M): universe=list(map(int,input().split())) compressed_universe = get_compressed_coordinate(universe) cu_list.. BOJ/🥇 2023. 12. 28.
★Tree Advanced I - 1 Solved★ ★ 1068 트리 ★ import sys input=sys.stdin.readline N=int(input()) l=list(map(int,input().split())) tree=[[] for _ in range(N)] visited=[[] for _ in range(N)] start_node = 51 ans = 0 def dfs(tree, visited, delete_node, start_node): global ans visited[start_node] = True if len(tree[start_node]) == 0: #leaf-node ans += 1 else: len_child = len(tree[start_node]) if len_child == 1: #one child node child .. BOJ/🥇 2023. 12. 22.
2️⃣Bipartite Graph intro 2️⃣ Bipartite Graph(이분 그래프)란, 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로 칠할 수 있는 graph를 뜻한다. 2️⃣ a graph in which the vertices can be divided into two disjoint sets, such that no two vertices within the same set are adjacent. In other words, it is a graph in which every edge connects a vertex of one set to a vertex of the other set. : 즉, graph 내의 모든 간선은 두 가지 다른 색깔의 정점으로 무조건 연결되어 있어야 하고, 반대로 말하.. Computer Science/Algorithms 2023. 12. 21.
★Tree Upper-Intermediate I - 3 Solved★ ★ 1991 트리 순회 ★ import sys input=sys.stdin.readline def pre_order(node): print(node, end='') if tree[node][0] != '.': pre_order(tree[node][0]) if tree[node][1] != '.': pre_order(tree[node][1]) def in_order(node): if tree[node][0] != '.': in_order(tree[node][0]) print(node, end='') if tree[node][1] != '.': in_order(tree[node][1]) def post_order(node): if tree[node][0] != '.': post_order(tree[node].. BOJ/🥈 2023. 12. 19.
🌳 Binary Tree 🌳 theory 🌳 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 : Binary Tree is defined as a tree data structure where each node has at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. 🌳 트리 관련 용어 ① root node: 부모가 없는 최상위 노드 ② leaf node: 자식이 없는 노드 ③ size: 트리에 포함된 모든 노드의 개수 ④ depth: 특정 노드에서 루트 노드부터의 거리(즉 위 1번 노드의 깊이는 0, 2번 노드의 깊이는 1) ⑤ h.. Computer Science/Data Structures 2023. 12. 19.
★BFS&DFS Advanced I - 10 Solved★ ★ 7576 토마토 ★ (최단경로) import sys input=sys.stdin.readline from collections import deque M,N=map(int,input().split()) graph=[] starts=[] depths=[[0]*M for _ in range(N)] visited=[[False]*M for _ in range(N)] def BFS(graph, depths, starts, visited): queue = deque(starts) dx,dy=[0,0,-1,1],[-1,1,0,0] while queue: v = queue.popleft() for i in range(4): nx,ny=v[0]+dx[i],v[1]+dy[i] if 0 BOJ/🥇 2023. 12. 15.
★BF Upper-Intermediate I - 2 Solved★ ★ 2503 숫자 야구 ★ import sys from itertools import permutations input=sys.stdin.readline N=int(input()) pos=list(permutations(['1','2','3','4','5','6','7','8','9'],3)) idxs=[n for n in range(len(pos))] def get_strike_ball(a,b): strike=0 for x,y in zip(a,b): if x==y: strike+=1 return (str(strike),str(len(a+b)-len(set(a+b))-strike)) for _ in range(N): num,S,B=input().split() didxs=[] for i in idxs: p.. BOJ/🥈 2023. 10. 26.
★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.
set() & dict() - 집합과 맵 🏄🏽‍♂️ 대표 자료구조 '집합'과 '맵'이 있다. 두 개의 자료구조는 매우 효율적인 자료구조로 특별히 python에서 어떻게 코드로 구현하고, 관련 여러 연산 기능 및 time complexity까지 자세히 알아보자! 🏄🏽‍♂️ 시간복잡도 계산 상 효율적인 코드를 작성하기 위해 집합과 맵이라는 자료구조를 활용하는 경우가 많다(특히 어려운 PS 문제!) 각 자료구조의 특징을 정확히 알아보자 Sets overview "unordered collection of data types that is iterable, mutable and has no duplicate elements. The order of elements in a set is undefined though it may consist of va.. Computer Science/Data Structures 2023. 8. 3.
🪴Insertion Sort orders ★ 앞쪽에 있는 원소들이 이미 정렬되어 있다고 가정하고, 뒤 쪽에 있는 원소를 앞쪽에 있는 원소들 중에 들어갈 적절한 위치를 판단하고 삽입 ★ ① 정렬할 데이터 준비 (오름차순 가정) → 맨 왼쪽 첫번째 데이터 7은 그 자체로 정렬이 되었다고 판단하고, 두번째 데이터인 5가 7의 왼쪽으로 갈지, 오른쪽으로 갈지 판단(=5가 왼쪽의 어느 파트에 들어갈 지 판단) 7 5 9 0 3 1 6 2 4 8 ② 오름차순을 가정하였으므로 5가 7의 왼쪽으로 이동하겠다고 판단! 5 7 9 0 3 1 6 2 4 8 ③ 이어서 9가 어떤 위치로 들어갈 지 판단 → 9의 경우는 5의 왼쪽으로 들어갈 지, 5와 7사이에 들어갈 지, 아니면 7 오른쪽으로 들어갈 지 들어갈 수 있는 3개의 후보 중에서 판단 → 맨 왼.. Computer Science/Algorithms 2023. 7. 28.
★Sorting Advanced I - 5 Solved★ ★ 1083 소트 ★ import sys input=sys.stdin.readline N=int(input()) arr=list(map(int,input().split())) S=int(input()) for i in range(N): subarray_max = max(arr[i:i+S+1]) if arr[i] != subarray_max: subarray_max_index = arr.index(subarray_max) for j in range(subarray_max_index-i): arr[subarray_max_index-j], arr[subarray_max_index-j-1] = arr[subarray_max_index-j-1], arr[subarray_max_index-j] S-=(subarra.. BOJ/🥇 2023. 7. 28.
🥭Selection Sort orders ★ 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꿈 (오름차순 정렬 가정) ★ ① 정렬할 데이터 준비 (7 5 9 0 3 1 6 2 4 8) ② 처리되지 않은 데이터(7부터 8 전체) 중 가장 작은 0을 선택해 맨 앞의 7과 바꾼다. 7 5 9 0 3 1 6 2 4 8 (0과 7을 바꾼다) 0 (5 9 7 3 1 6 2 4 8) ③ 처리되지 않은 데이터(위 괄호 5부터 8) 중 가장 작은 1을 선택해 가장 앞의 5와 바꾼다. 0 5 9 7 3 1 6 2 4 8 (1과 5를 바꾼다) 0 1 (9 7 3 5 6 2 4 8) ④ 처리되지 않은 데이터가 맨 오른쪽 1개가 있을 때까지 반복한다(맨 마지막 1개의 데이터는 자동 정렬됨) 0 1 2 3 4 5 6 7 8.. Computer Science/Algorithms 2023. 7. 26.
C Basics 5/ (열혈 프로그래밍) 😙 점점 C언어 기초가 끝나간다. 다차원 배열부터 포인터의 포인터, void 포인터까지 16장부터 20장까지의 내용을 다룬다. 16. 다차원 배열 ① 2차원 배열 / 선언 / 접근 / sizeof ex) 세로가 3, 가로가 4인 int형 2차원 배열 선언은 int arr1[3][4]; (세로가 3, 가로가 4인 2차원 배열) ex) 여러 배열의 형태 → sizeof 연산자를 사용하면 2차원 배열의 크기를 계산할 수 있다. 세로 길이 x 가로 길이 x 자료형 크기로 배열의 크기가 나온다. #include int main(void) { int arr1[3][4]; int arr2[7][9]; printf("arr1 size: %d\n",sizeof(arr1)); //arr1 size: 48 printf("a.. C/Fundamentals 2023. 7. 26.
C Basics 4/ (열혈 프로그래밍) 🫡 네번째 포스팅부터는 C언어 심화 개념을 본격적으로 나간다! 점점 흥미있어지는 C언어! 두 번째 파트 11장부터 15장까지 정리했다. 11. 1차원 배열 ① 배열이란? → 다수의 데이터를 저장하고 처리하는 경우 유용하게 사용할 수 있는 것. 여러 개의 변수를 저장할 필요 없이, 한 번에 많은 수의 변수 선언 및 저장 가능! ② 1차원 배열 선언 & 접근 → 필요한 것: 배열이름, 자료형, 길이정보 ex) int arr1[7]; : int형 변수 4개로 이루어진 배열을 만들고, 그 배열의 이름은 arr1로 한다는 뜻이다. int형 변수 4개가 나란히 선언되었고, 실제로 배열을 이루는 요소들(변수들)의 주소 값을 확인 해보면 나란히 배치되어 있다. ex) float arr2[10]; double arr3[.. C/Fundamentals 2023. 7. 5.
C Basics 3/ (열혈 C프로그래밍) 😵 이번 세 번째 포스팅에서는 본격적인 코딩을 위한 다양한 분기문 / 반복문을 배우자! 그리고 함수까지 배우며 Part 01을 마무리하려 한다! 6장부터 10장까지 다룰 예정! 6. printf함수와 scanf함수 정리하기 ① 여러 특수문자의 출력 → 큰 따옴표 자체의 출력을 원하면 앞에 \를 붙여준다. → \n은 개행 → \\ 역슬래쉬 자체를 출력 → \'은 작은 따옴표를 출력 → \t는 수평 탭 효과 ② printf의 f는 formatted(서식이 지정된) 형태의 출력을 뜻한다. %d는 10진수 정수로 출력, %X는 16진수로 출력(알파벳은 대문자) %x는 16진수로 출력(알파벳은 소문자) 서식문자 출력 대상(자료형) 출력 형태 %d char, short, int 부호 있는 10진수 정수 %ld lo.. C/Fundamentals 2023. 6. 27.
C Basics 2/ (열혈 C프로그래밍) 🥸 저번 포스팅에서 1장부터 3장까지 다루었다. 이번 포스팅에서는 4장부터 5장까지 다루자! 4. 데이터 표현방식의 이해 ① 진법의 이해 → 2진수는 두 개의 기호(0과 1)를 이용해 데이터를 표현하는 방식. 컴퓨터는 2진수를 기반으로 데이터를 표현하고 연산 진행 → 이와 유사하게 10진수는 10개의 기호 / 16진수는 16개의 기호(1부터 10까지의 숫자 + A ~ F 대소문자 구분 x)를 사용 ex) 즉 10진수로 10은 16진수로 A로 표현하고 / 10진수로 17은 16진수로 11로 표현한다 Q. 16진수가 필요한 이유? → 2진수로만 표현하면 데이터의 길이가 길어지므로 한눈에 파악하기 어려움. 따라서 2진수 네 개는 16진수 1개로 간결히 표현 가능하므로 16진수를 많이 사용 ② 데이터의 표현 단.. C/Fundamentals 2023. 6. 26.

티스토리툴바