이분탐색을 이용해서 MN개의 조합에서 k번째 수를 찾는 놀라운 방법

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..

• format_list_bulleted 이분 탐색
• · 2023. 3. 21.
• textsms

나비 정리(butterfly theorem)

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학년 때 여러 가지 도형의 종류..

• format_list_bulleted 기하학
• · 2023. 3. 21.
• textsms

행렬을 이용한 피보나치 수열 문제의 해법

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..

• format_list_bulleted 선형대수학 알고리즘
• · 2023. 3. 19.
• textsms

피사노 주기를 이용한 피보나치 수열 해법

1. 피사노 주기 피보나치 수열을 자연수 n으로 나눈 나머지가 일정한 주기를 이룬다는 것을 1960년 IBM의 한 직원이 증명했다 예를 들어 0,1로 시작하는 피보나치 수열을 3으로 나눈 나머지는 위와 같이 0,1,1,2,0,2,2,1이 반복된다는 것을 알 수 있다 2. 연습문제 9471번: 피사노 주기 (acmicpc.net) 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. www.acmicpc.net 추가로 몇가지 성질이 있다고 제시해주는데 어쨌든 이 문제는 피보나치 수열을 자연수 m으로 나눈 나머지가 주기를 이룬다는 사실을 알고 코딩을 해서 반복되는 수열의 길이를 ..

• format_list_bulleted 정수론
• · 2023. 3. 19.
• textsms

우선순위 큐 재활하면서 응용력 키우기1 -카드 정렬하기, N번째 큰 수

1. 문제1 1715번: 카드 정렬하기 (acmicpc.net) 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 풀이 문제를 잘 보면 매 순간 최소인 얘들을 더해나가면 최적이 될 것 같다는 생각이 든다 우선순위 큐에 주어진 수를 모두 넣는다 큐가 빌때까지 정수를 2개 뽑아, 두 수를 더한 다음에, 다시 우선순위 큐에 넣어준다. 그러니까, 10, 20, 40이 있는데, 10,20을 뽑아 10+20을 한 다음에 40을 바로 뽑는게 아니고, 30을 우선순위 큐에 넣어서 30,40이 된 상태에서,..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 3. 18.
• textsms

위상정렬 재활치료하기 - 그래프에 사이클이 존재하여 정렬이 불가능한경우

1. 위상정렬 가볍게 복습 그래프의 노드를 정렬하는 위상정렬 정복하기 (tistory.com) 그래프의 노드를 정렬하는 위상정렬 정복하기 1. 개요 위상 정렬(topology sort)은 정렬 알고리즘의 일종 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 이론적으로, 위상 정렬은 방향 그래프의 deepdata.tistory.com 1) 그래프를 만들면서, 각 노드의 진입차수(indegree)를 세준다. 2) 진입차수가 0인 노드를 큐에 모두 넣는다. 3) 큐가 빌때까지 다음을 반복 3-1) 큐에서 노드를 하나 빼고, 결과 리스트에 넣어준다. 3-2) 3-1)에서 뺀 노드에서 출발하는 모든 간선을 제거 3-3) 3-2) 후에 노드의 진입차수가 0이 된 노드는..

• format_list_bulleted 위상정렬
• · 2023. 3. 17.
• textsms