About Dev

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net Comments 알고리즘 : 구간 합 연속된 부분 합을 구하는 최적의 방법은 구간 합을 이용하는 것이다. index 0 1 2 3 4 5 array 1 2 3 1 2 SUM 0 1 3 6 7 9 위의 예제로 답을 구해본다면, 다음과 같은 연산이 필요하다. SUM[i] - SUM[0] (i=1~5) : array[1] 에서 시작하는 부분 합 SUM[i..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 알고리즘 : 그리디 or Dynamic Programming 풀이 날짜 : 2023.08.17. Greedy 와 Dynamic Programming 두 가지 풀이 모두 가능하다. N 을 3와 5이 배수들로 구성하는 것이니 수학적으로도 풀 수 있고 이전 값을 사용할 수 있어 값이 점진적으로 쌓이기도 하니 DP 로도 풀 수 있다. 1) Greedy 그리디 풀이 방식은 다양하다. 핵심 원리는, ..

https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 알고리즘 : 병합 정렬 풀이 날짜 : 2023.08.16. 버블 소트의 특징은 다음과 같다. 1) (N - 1) + (N - 2) + ... + 1 = O(N²) 의 시간 복잡도 2) 한 번의 iteration 후, 남은 값 중 제일 큰 값이 제일 뒤로 정렬 이 문제에서 N 의 최대 크기가 500,000 이므로, 버블 정렬의 흐름에 따라 swap 횟수를 직..

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 알고리즘 : 병합 정렬 (Merge Sort) or 구현 풀이 날짜 : 2023.08.16. 배열 크기 N이 백 만까지고 시간 제한이 2초 이므로 O(NlogN) = 1,000,000 * 20 까지 가능하다. Java 라이브러리 Arrays.sort( ) 를 쓰면, 음수를 처리를 못 한다. 가능한 방법으로 그냥 정렬과 병합 정렬이 있는데 그냥 정렬은, 배열 인덱스를 이..

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 : 이분탐색 or 투포인터, 재귀 풀이 날짜 : 2023.08.15. 물건의 개수는 N, 가능한 가방 무게는 C 로 입력이 주어질 때 처음에 물건들을 모두 같은 크기의 무게로 생각해서, 그 무게로 C 를 나누었을 때 개수를 R (C / 무게 = R) 이라고 했을 때 N 개 중 R ~ 0 개의 조합들 합으로 잘못 구했었다. 더보기 import java.io.Buffered..

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 알고리즘 : 투 포인터 or 이분 탐색 풀이 날짜 : 2023.08.10. 배열 A, B, C, D 의 모든 조합을 완전 탐색(브루트 포스) 을 하면 약 O(N⁴) 의 시간이 걸린다. N이 최대 4000 까지 나올 수 있고, 시간 제한이 12초 이므로 시간 초과가 난다. 그럼 최악으로 O(N² * logN) = 약 4000 * 4000 * 12 = 약 2억 번까..

https://www.acmicpc.net/problem/13325 13325번: 이진 트리 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거리는 www.acmicpc.net 알고리즘 : 트리에서 DP 풀이 날짜 : 2023.07.27. K 의 최댓값은 20 으로, 전체 노드 개수의 최댓값은 2 ^ (20 + 1) - 1 ≒ (10 ³) ² 으로 백 만개이다. 따라서 시간 복잡도 O(N) 안에 해결해야 한다. 처음에 같은 부모의 두 자식 edge 는 같은 weight 를 가져야 한다고 생각했다. 위로 같은 route 를 가기 때문이라고 생각했지만..

https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 알고리즘 : 트리에서 DP (DFS + DP) 풀이 날짜 : 2023.07.26. 다음 문제와 조건만 다를 뿐 풀이 로직과 방식은 동일하다. [백준/DP] - 백준 2533: 사회망 서비스(SNS) [골드 Ⅲ / Java] 2533 번 문제와 다른 점은, 노드 개수만이 아니라 마을 주민 수를 비교해 주어야 하고, 그 중 최솟값이 아니고 최댓값을 구하는 문제이다. 『 Ro..

https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 알고리즘 : DP 풀이 날짜 : 2023.08.08. 기본 풀이 원리는 다음 문제와 동일하다. [백준/DP] - 백준 12865: 평범한 배낭 [골드 Ⅴ / Java] 다만 12865번 문제에서는 시간 복잡도가 N (물건 수) * M (가능 배낭 무게) = 100 * 100,000 = 약 1,000만 이지만, 같은 코드에 대하여 해당 문제..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 알고리즘 : DP 풀이 날짜 : 2023.07.19. 어떤 물건을 사용하는 경우와 사용하지 않는 경우를 비교한다. 이때 DP 배열 정의를 다음과 같이 한다. DP[i][bag] = 0 ~ i 인덱스의 물건들의 조합으로 bag을 만들 수 있는 경우 중 최대 가치 그럼 무게가 w인 i 번째 인덱스의 물건을 탐색 중일 ..