본문 바로가기
728x90
반응형

코딩/백준

알고리즘 - Python / 백준 - 2110번 : 공유기 설치 2110번: 공유기 설치 (acmicpc.net) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 수직선 상에 존재하는 집들의 좌표가 주어지고 , 집에 공유기를 k개 설치할 때 , 인접한 공유기끼리의 거리들 중 최솟값이 최대가 되도록 배치하는 문제다. 어떠한 범위를 k개로 잘라 , 자른 부분의 최솟값이 가장 커지려면 최대한 고르게 분배해야 한다는 아이디어를 통해 문제를 이해하였다. 예를 들어 9cm의 나뭇가지를 3개로 나눌 때 , 가장 작은 길이가 가장.. 더보기
알고리즘 - Python / 백준 - 1737번 : Pibonacci 1737번: Pibonacci (acmicpc.net) 1737번: Pibonacci 첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 점화식이 다음과 같은 Pibonacci 수를 구하는 문제다. 피보나치 수열과 비슷하게 DP로 접근해 풀어 보았다. DP[N][K] 배열에서 N은 P[K-N*파이] 로 정의하였다. 즉 만약 P[10]을 구하고 싶다면 DP[0][10] = DP[10-0*파이] 를 구하면 되는 것이다. 이때 Pibonacci 점화식에 따른 DP 점화식은 DP[N][K] = DP[N+1][K] + DP[N][K-1] 이다. 해석하자면 , 만약 DP[0][10] 의 경우 , P.. 더보기
알고리즘 - Python / 백준 - 9024번 : 두 수의 합 9024번: 두 수의 합 (acmicpc.net) 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 풀이 음수와 양수가 섞여있는 배열이 있을 때 , 두 수를 더해서 어떤 수에 가장 가깝게 나오는 경우가 몇 가지 인지 출력하는 문제다. 만약 4를 만들어야 하는데 5가 가장 가까운 수라면 , 더해서 5가 되는 조합의 개수를 출력해야 한다. 모든 구간을 확인해야 하는데 기준점이 있으므로 투 포인터로 해결하였다. 먼저 배열을 오름차순으로 정렬한 후 , 구하고자 하는 값과 비교해 크면 뒤쪽을 한칸 당기고 , 작으면 앞쪽을.. 더보기
알고리즘 - Python / 백준 - 4386번 : 별자리 만들기 4386번: 별자리 만들기 (acmicpc.net) 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 2차원 평면 위에 별들의 좌표가 주어지고 해당 별들을 가지고 그래프를 만들 때 거리 합의 최솟값을 구하는 문제다. 노드와 노드 사이 간선의 가중치가 주어지고 , 최소 거리합을 구하는 문제 이므로 최소 신장 트리 문제라고 생각했다. 최소 신장 트리를 푸는 방법에는 크루스칼 알고리즘 ( Kruskal Algorithm ) 과 프림 알고리즘 ( Prim Algorithm )이 존재한다. 프림 알고리즘이 더 익숙해.. 더보기
알고리즘 - Python / 백준 - 2293번 : 동전 1 2293번: 동전 1 (acmicpc.net) 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 대표적인 DP 문제인 동전 문제다. 동전이 주어지고 , 그 동전들을 가지고 해당 금액을 만들 수 있는 경우의 수를 구하는 문제다. DP 점화식은 DP[I] = DP[I-K] + DP[I] 로 I 금액을 K 금액의 동전으로 만드는 경우를 이야기한다. 만약 1원 2원을 가지고 17원을 만드는 경우는 16원을 만드는 경우에 1원 동전을 사용하는 경우 , 15원을 만드는 경우에 2원 동전을 사용하는 경우 2가지 일 것이.. 더보기
알고리즘 - Python / 백준 - 11441번 : 합 구하기 11441번: 합 구하기 (acmicpc.net) 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 풀이 숫자를 입력받고 , 구간합을 구하는 문제다. 누적 합을 구현하는 기초적인 문제다. STACK 이라는 리스트를 통해 누적합을 저장하고 , 저장한 누적합을 통해 구간합을 출력하였다. import sys n = int(sys.stdin.readline()) c = list(map(int, sys.stdin.readline().split(" ").. 더보기
알고리즘 - Python / 백준 - 2960번 : 에라토스테네스의 체 2960번: 에라토스테네스의 체 (acmicpc.net) 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 풀이 에라토스네테스의 체를 구현하고 몇 번째에 어떤 수가 지워지는지 출력하는 문제다. 단순하게 에라토스테네스의 체를 구현하고 해당 순서의 수를 출력하였다. n,u=map(int , input().split(" ")) prime = [0 for i in range(n+1)] ans = [] for i in range(2,n+1): for k in range(i,n+1,i): if prime[k] == 0: prime[k] = 1 ans.append(k) if len(ans) >= u: break.. 더보기
알고리즘 - Python / 백준 - 2467번 : 용액 2467번: 용액 (acmicpc.net) 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 오름차순으로 나열된 수들을 더해서 0이 되는 2개의 수를 구하는 문제다. 입력 자체가 오름차순으로 나열되어 있다는 점에서 힌트를 얻었다. 투 포인터를 사용해 좌측 , 우측에서 부터 수를 더해가면서 MIN 값과 비교한다. 만약 더한 값의 절댓값이 MIN보다 작으면 업데이트한다. 더한 값이 양수라면 0에 가까워지기 위해 양수 부분을 줄여야 하므로 뒤쪽 포인터를 앞으로 하나 민다. 더한값이 음수라면 0에 가까워지기.. 더보기
반응형

티스토리툴바