문제정수 N을 정수 D로 나눴을 때의 몫을 Q, 나머지를 R이라고 하면 항등식 R = N - Q×D가 성립한다. n개의 정수로 된 수열이 있을 때, 모든 정수를 한 정수 D로 나눴을 때 나머지가 같아지는 경우가 있다. 그리고 수열에 따라서는 이러한 정수 D가 여러 개 존재할 수 있다. n개의 정수로 된 수열이 주어졌을 때, 가장 큰 D를 구하는 프로그램을 작성하시오.입력수열에 따라서는 이러한 정수 D가 여러 개 존재할 수 있다. n개의 정수로 된 수열이 주어졌을 때, 가장 큰 D를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 줄에는 절댓값이 1,000,000을 넘지 않는 n개의 정수들이 주어진다.출력첫째 줄에 가장 큰 D를 출력한다. 항상 가장 큰 D가 ..

문제동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍멍이보다 키가 작기 때문에 멍멍이를 쓰다듬어줄 수 없다. 원숭이가 멍멍이를 쓰다듬으려면 둘의 키가 같아야 하기 때문이다. 그래서 원숭이는 그 날부터 자신의 키를 조절하기로 마음먹었다. 원숭이는 초능력자이기 때문에 마음대로 키를 늘릴 수 있다. 하지만 안타깝게도 사람이 아니라 동물이기 때문에 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없다. 예를 들어 오늘 키를 5cm 만큼 늘렸다면, 내일은 키를 4cm, 5cm, 6cm 중 하나만큼 키를 늘릴 수 있다는 뜻이다. 늘릴 수 있는 키의 양은 음수가 될 수 없다. ..

이분 탐색 이란?이분 탐색 / 이진 탐색 알고리즘은 "오름차순으로 정렬된 리스트"에서 특정한 값의 위치를 찾는 알고리즘이다. 처음부터 끝까지 순서대로 탐색 하는 것보다 빠르게 탐색할 수 있다! 탐색 방법리스트를 정렬한다. start = 0, end = n으로 설정한다. mid = ( start + end ) // 2구하는 숫자와 mid 를 비교한다. 구하는 숫자보다 mid가 크다면 start = mid +1, mid보다 작다면 end = mid - 1start  아래의 그림은 0 ~ 100 사이에서 78을 탐색하는 과정이다.  이분 탐색 코드 (Python)def binary_search(array, target): start = 0 end = len(array) - 1 while st..

이모스 법(Imos Method)이란?이모스법은 누적 합 알고리즘을 다차원, 다차수로 확장한 것을 의미한다. https://imoz.jp/algorithms/imos_method.html いもす法いもす法の紹介記事ですimoz.jp1차원 이모스 법구간 [l, r)에 x를 더하는 쿼리를 처리할 때, 배열 d에 d[i] += x, d[r] -= x를 처리한다. 모든 쿼리를 처리한 후 배열 d에 대해 누적 합을 구하면 원래 배열의 각 위치에 대해 더해진 값을 구할 수 있다. O(N+Q)로 효율적이다.  예시) 손님 수 구하기문제식당을 방문한 각 고객의 입장 시간과 퇴장 시간이 주어진다. 같은 시간에 가게에 있던 손님의 수의 최대는 몇 명인가?손님이 아래와 같이 방문했다고 가정하자시간01234567891번OOO  ..

최대공약수 수론에서, 정수들의 공약수(common factor)는 동시에 그들 모두의 약수인 정수다. 적어도 하나가 0이 아닌 정수들의 최대공약수(greatest common factor, 약자 GCF)는 공약수 가운데 가장 큰 하나다. 1. Brute Force로 구하기두 수중 작은 수를 고르고 1부터 작은 수까지 모든 수를 순회하면서 두 수를 동시에 나누어 떨어지게 하는 가장 큰 수를 구해 최대공약수 값을 얻는다. import sysinput = sys.stdin.readlinea,b = map(int,input().split())min_num = min(a,b)for i in range(min_num, 0, -1): if (a%i == 0 and b%i == 0): answer = i ..

배낭문제란?배낭 문제는 주어진 제한된 용량의 배낭에 최대한의 가치를 가진 아이템을 넣는 방법을 찾는 문제를 의미한다. n개의 물건의 무게w와 가치 v에 주어질 때, 용량이 k인 배낭의 용량을 초과하지 않고 담을 수 있는 최대의 가치를 찾는 문제이다. 배낭문제의 해결 방법모든 경우 탐색 (brute-force)물건을 담는다/담지 않는다의 경우를 생각하여 2^n의 모든 조합을 탐색하는 방법은 시간 복잡도가 너무 커서 n값이 큰 경우에는 해결할 수 없다. 탐욕적 알고리즘 (Greedy)단위 무게당 높은 가치부터 담는 방법.분할 배낭 문제에서는 효율적으로 동작한다. 동적 프로그래밍 (Dynamic Programming)주어진 아이템과 배냥의 용량을 이용해 가능한 가치의 조합을 계산브랜치 앤 바운드 (Branch..

최소 신장 트리신장 트리는 그래프의 모든 정점을 포함하는 트리로, 사이클이 없는 부분 그래프이다. 최소 신장 트리는 신장 트리중에서 간선들의 가중치 합이 가장 작은 트리를 의미한다. 최소 신장 트리는그래프의 모든 정점을 연결사이클이 없는 트리 구조간선의 가중치 합이 최소의 특징을 가진다.  최소 신장 트리를 구하는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다. 이 포스트에서는 프림 알고리즘(Prim's Algorithm)에 대해 다룬다.프림 알고리즘 (Prim's Algorithm)프림 알고리즘은 최소 신장 트리를 구하기 위한 알고리즘이다. 단계적으로 정점을 확장해가면서 동작한다. 프림 알고리즘의 동작 과정[STEP 1] 시작 정점 선택 : 임의의 정점을 하나 선택[STEP 2] 최소 가중치 간선..

최소 신장 트리신장트리는 그래프의 모든 정점을 포함하는 트리로, 사이클이 없는 부분 그래프이다. 최소 신장 트리는 신장 트리중에서 간선들의 가중치 합이 가장 작은 트리를 의미한다. 최소 신장트리는그래프의 모든 정점을 연결사이클이 없는 트리 구조간선의 가중치 합이 최소가 됨의 특징을 가진다.  최소신장트리를 구현하기 위한 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있다. 이 포스트에서는 크루스칼 알고리즘(Kruskal's Algorithm)에 대해 다룬다.  크루스칼 알고리즘 (Kruskal's Algorithm)크루스칼 알고리즘은 그래프에서 최소 신장 트리를 찾기 위한 대표적인 알고리즘 중 하나이다. 그리디하게 작동하는 알고리즘이다. 크루스칼 알고리즘의 동작 과정[STEP 1] 간선 정렬 하기 :..