문제 링크 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 소스 코드 import sys import heapq input = sys.stdin.readline n = int(input().rstrip()) q = [] for i in range(n): num = int(input().rstrip()) if num == 0: if q: print(heapq.heappop(q)[1]) else: print(0) else: #..
분류 전체보기
문제 링크 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 소스 코드 import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().rstrip().split()) # 무방향 그래프 입력받기 graph = [[] for _ in range(n+1)] for i in range(m): a,b = map..
문제 링크 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 소스 코드 import sys input = sys.stdin.readline n = int(input().rstrip()) graph = [] # 그래프 입력받기 for i in range(n): graph.append(list(map(int,input().rstrip()))) def dfs(x,y,n): if n == 1: # 최소 사각형인 경우 바로 추가 answer...
1. Changing basis Coordinate System(좌표계) 벡터는 기저 벡터의 합으로 표현된다. 이 벡터를 다른 기저 벡터의 합으로 표현할 수 있다. 단, 이 기저 벡터들은 서로 직교해야 한다(orthogonal to each other) 직교하는 vector에 대해 내적(dot product) 취해보기 기저벡터 e1, e2로 벡터 r을 표현 또다른 기저벡터 b1,b2 scalar projection을 구하고 여기에 b1, b2의 방향벡터를 곱해서 vector projection을 구한다. 벡터 r이 기저벡터 b1, b2로 표현되는 것을 확인했다. 요약 vector는 우리가 지금 표현하는 axes에 묶여있는 것이 아니다. basis vector는 data의 공간을 표현한다. 위처럼 어떤 벡..
1. Modulus & inner product 벡터를 단위벡터로 표현하기 벡터는 length(길이)와 direction(방향)을 가진다. 단위벡터 i,j 로 벡터 r을 표현할 수 있다. i 와 j 의 상수배를 제곱하고 루트를 씌우면 r의 크기(길이)가 된다. 이는 피타고라스 정리에 의한 것이다. Inner(dot) product 정의하기(내적) 내적은 inner product, dot product, scalar product, projection product 등 다양하게 불린다. 두 벡터 r, s 가 있을 때 innder product는 다음과 같이 정의된다. 결과값은 벡터가 아닌 스칼라다. 벡터의 성질 세 가지 1) commutative (교환법칙 성립) 2) distribute over add..
1. Operation with vectors 집을 사는 상황을 가정 120평, 침실 2개, 화장실 1개, 집값 30만 이와 같은 현실 문제를 해결하는데 도움이 되는 개념이다 ex) Machine Learning, Data Science 덧셈(addition) 방향을 나타내는 화살표의 끝을 이어서 덧셈을 수행 두 벡터 s,r 을 어떤 순서로 더하더라도 그 결과는 동일(s + r = r + s) associative law(결합 법칙) 적용됨. (r+s)+t = r+(s+t) 곱셈(multiplication) 벡터의 길이를 늘이거나 줄이는 것 음수를 곱하면 방향이 반대가 됨 muliplication by scalr - 그냥 벡터 각 원소에 scalr를 곱하면 됨 뺄셈(subtraction) 마찬가지로 방향..
