1. parametric search 이분 탐색을 응용하여, "최적화 문제"를 "결정 문제(decision problem)"로 바꿔서 문제를 푸는 알고리즘 최적화 문제는 예를 들면 다음과 같다. "f(x) = True가 되는 x의 최댓값을 구하세요" 이를 결정 문제로 바꾸면 다음과 같을 것이다. "어떤 x에서 f(x) = True인가?" 가능한 모든 x에 대해 f(x)가 True인지, False인지 검사한다면, 최적화 문제를 결정 문제의 집합으로 바꾸어 해결할 수 있을 것이다. 모든 결정 문제의 값 중에서 True인 최댓값을 구하면 되니까 하지만 모든 결정문제를 다 해결하는 것은 당연히 비효율적 그러나 어떤 조건을 만족한다면, 위 과정을 효율적으로 해결할 수 있다. x1 < x2이고, f(x2) = Tr..
1. 문제 2428번: 표절 (acmicpc.net) 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 2. 풀이 $F_{1}, F_{2}, ... , F_{n}$이 주어질때, $F_{i} = 0.9*F_{j}$인 $(F_{i}, F_{j})$의 개수를 구하는 문제 조건이 2개가 있는데.. 사실 $F_{i} = 0.9*F_{j}$을 만족하는 최대 인덱스 j를 찾는다 그러면 $F_{i}, F_{i+1}$, ..., $F_{i}, F_{j}$까지가..
1. 문제 1373번: 2진수 8진수 (acmicpc.net) 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 2. 2진수에서 바로 8진수로 바꾸는 알고리즘 [진법변환] 2진수,8진수,10진수,16진수 쉽게 변환하는 방법 알아보기! : 네이버 블로그 (naver.com) [진법변환] 2진수,8진수,10진수,16진수 쉽게 변환하는 방법 알아보기! 안녕하세요~~! 오늘도 여러분들께 유익한 정보를 드리러 온 나도비 입니다 !! 오늘의 주제는 2진수,8진수,1... blog.naver.com 8이 2의 세제곱이기 때문에, 원래 2진수에서 3자리씩 끊어서 각각을 10진수로 바꿔서 더해주면 그 수가 8진수가 된다. 1) 주..
1. 문제 1300번: K번째 수 (acmicpc.net) 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 2. 풀이 k 제한이 커서 그런지 이전에 배운 우선순위 큐 방법으로 풀면 시간초과로 통과를 못한다 import heapq from sys import stdin n = int(stdin.readline()) k = int(stdin.readline()) q = [] for i in range(1,n+1): heapq.heappush(q,(i*1,i,1)) for _ in r..
1. 나비정리 현 PQ의 중점 M을 지나는 두 현 AB와 CD가 있고, 현 AD, CB가 PQ와 만나는 점이 X,Y이면, M은 XY의 중점이기도 하다. 2. 증명 증명이 매우 많은데 하나만 따라가보자 [증명] 나비 정리 (The Butterfly Theorem) - 몇 가지 다른 방법 : 네이버 블로그 (naver.com) [증명] 나비 정리 (The Butterfly Theorem) - 몇 가지 다른 방법 수학교실 - Math7090 blog.naver.com 아래 그림에서 현 AB의 수직 이등분선이 원과 만나는 점을 각각 C,D라고 하자. 현의 수직이등분선은 원의 중심 O를 지난다는 성질이 있다 현의 수직이등분선 – 수학방 (mathbang.net) 현의 수직이등분선 1학년 때 여러 가지 도형의 종류..
1. 피보나치 수열의 행렬 표현 피보나치 수열의 점화식은 다음과 같다. $a_{n+1} = a_{n} + a_{n-1}$ $a_{n} = a_{n} + 0$ 따라서 행렬로 나타내면 다음과 같다 $$\begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}\begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix}$$ n = 1부터 반복적으로 곱해보면... $$\begin{pmatrix} a_{2} \\ a_{1} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}\begin{pmatrix} a_{1} \\ a_{0..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
