1. 좌표압축이란 정점 번호가 1에서 $10^{9}$사이의 값으로 이루어져 있는 그래프가 하나 주어질때, 1번 정점에서 시작하여, 방문 가능한 서로 다른 노드의 수를 구하는 프로그램을 작성하세요. 일반적인 DFS 탐색으로는 1번 정점에서 N번 정점까지 번호가 매겨져 있어서, 큰 문제 없이 크기가 N인 visited 배열과 간선 정보를 나타내는 인접 리스트를 만들어 해결할 수 있습니다. 하지만 위와 같이 정점 번호가 1번에서 $10^{9}$사이로 주어진다면, visited 배열을 만드는 순간 메모리 초과로 일반적인 방법으로는 해결하기 어렵다. 그런데 조금만 생각해보면... 주어진 정점 번호를 오름차순으로 나열할때, 1,4,6,7,30,2000,$10^{9}$밖에 없으며.. 이 정점들의 번호를 1번부터 순서..
1. 문제 1부터 차례대로 숫자를 적는데, 3이나 5의 배수는 숫자 대신 "Moo"라고 적습니다. 예를 들어 1부터 16까지의 숫자를 적는다면 아래와 같습니다. 1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16 이 때, N번째로 적히는 숫자는 무엇인지 구하는 프로그램을 작성해보세요. 2. 풀이 이게 쉽나?? 되게 어려운데 이분탐색에 얽매이다보니 적절한 생각이 안드네 답을 보니까 약간 소름돋았다 배열에서 K번째 수를 어떻게 찾을 수 있을까?를 생각해본다면.. 1부터 n까지 들어있는 배열 A에서, k번째 수를 나타내는 A[k]의 의미는? k이하의 수가 k개라는 뜻이다. 배열에 빈 부분이 없으니까 이게 무슨소리야? 하겠지만.. 그러면 이제 1부..
1. parametric search란 무엇인가1 - 합에 대한 탐색 1부터 n까지의 자연수의 합이 100이상인 경우 중 가능한 n의 최솟값을 구하는 프로그램을 작성해보세요. 단, 답은 1에서 30사이라고 가정합니다. 무작정 문제를 푼다면, 1,2,3,...,30 전까지 계속 더해보면서 최초로 합이 100을 넘는 경우, 그 숫자를 return하게 된다. 하지만 다음과 같이 시도해본다면? 1차시도: n = 15 15까지의 합은 120이므로 15는 답의 후보이며, n의 최솟값을 찾기 위해 이러한 합보다 더 작은 합은 1~14중 하나에서 찾을 수 있다. 2차시도: n = 7 7까지의 합은 28이므로, n은 확실히 7보다 커야하며, 8~14를 조사해본다. 3차시도: n = 11 11까지의 합은 66이므로, n은..
1. 문제 18113번: 그르다 김가놈 (acmicpc.net) 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 2. 풀이 문제를 보면 김밥의 길이가 k보다 큰 경우, 양쪽을 균일하게 k씩 자른다 하지만 2k보다 짧은 경우, 한쪽 k만 자른다. k보다 작거나 같은 경우 김밥은 그냥 폐기한다 김밥 길이를 받을 때, L > k인 경우, L 2k일때, L-2k를 리스트에 저장한다 L == 2k일때는 문제에서 아무런 언급이 없기..
1. 문제 14609번: 구분구적법 (Large) (acmicpc.net) 14609번: 구분구적법 (Large) 첫 번째 줄에는 다항함수의 차수를 나타내는 양의 정수 K(1 ≤ K ≤ 10) 가 주어진다. 두 번째 줄에는 최고차항부터 내림차순으로 각 항의 계수를 나타내는 정수 ci (0 ≤ ci ≤ 10, 1 ≤ c1 ≤ 10) 가 www.acmicpc.net 2. 풀이 실제 적분값과 근삿값이 일치하게 만드는 epslion을 찾는다 그러면 실제 적분값을 먼저 구해야겠지 최대 10차 다항함수까지로 제한되어있고 다항함수 적분 방법도 힌트로 나와있다 그러면 $c_{0}x^{k} + c_{1}x^{k-1} + ... + c_{k}$를 적분하면 된다 그러면 $$\frac{c_{0}x^{k+1}}{k+1} + \..
1. 기본문제1 n개의 숫자가 오름차순으로 정렬된 상태로 주어집니다. 이후 m개의 숫자가 추가적으로 주어졌을 때, 각각의 숫자가 처음 주어진 n개의 숫자 중 몇 번째로 나온 숫자인지를 구하는 프로그램을 작성해보세요. 2. 풀이 배운대로 기본에 충실하게 만들어보자 Main 클래스 내에서 public static int 함수로 binarysearch를 만들고, mid 포인트는 start + (end - start)/2로 하고 삼분탐색하지 말고, 이분탐색으로 arr[mid] >= target인 경우와, arr[mid] = ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
