기맹기 개발 블로그

BOJ 10986 나머지 합 난이도 : 골드 3 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 전략 수열의 길이 N은 최대 10^6이므로 모든 부분 구간을 탐색하는 O(N^2)으로는 풀 수 없다. 누적 합을 이용하면 두 지점 사이의 부분 배열의 합을 구할 수 있다. 나는 누적합 % M이 반복되었을 때 해당 구간의 합 % M은 0이 되는 것을 주목했다. 문제의 예제를 예로 들어보자. N = 5, ..

BOJ 2143 두 배열의 합 난이도 : 골드 3 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 전략 처음에는 prefix sum을 구해놓고 포인터를 움직여가는 방식은 어떨까 생각해봤는데 배열이 두개라서 상당히 복잡할 것 같았다. 따라서 부배열 합들을 모두 저장해놓고 탐색하는 것이 좋겠다고 생각했다. 길이가 N인 배열에서 모든 부배열의 합을 구하는 것은 O(N^2..

BOJ 1799 비숍 난이도 : 골드 1 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 전략 N-Queen를 백트래킹으로 풀 때와 유사하지만 다음 조건들이 다르다. 1. 놓을 수 없는 위치가 존재한다는 점 2. 놓을 수 있는 비숍의 최대 개수를 구해야한다는 점 3. 비숍은 자신이 속한 흑/백 칸이 아닌 곳으로는 이동할 수 없다는 점 흑색/백색 칸을 따로 dfs로 진행하면서 더 이상 비숍을 놓을 수 없는 경우에는 백트래킹하고, 놓을 수 있는 경우에는 비..

BOJ 1644 소수의 연속합 난이도 : 골드 3 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 전략 매번 소수 판별을 하는 것보다 전처리를 하여 N 이하의 소수 목록을 만들어놓는 것이 유리하다. 따라서 에라토스테네스의 체를 이용하여 ArrayList에 소수들을 저장한 뒤에 투 포인터를 사용한 부분합 탐색을 진행했다. 시행착오 N의 최소 범위인 1이 입력되었을 때 빈 ArrayList에 index로 접근하면서 IndexOutOfBoundsException이 발생했다. 따라서 이를 확인하는 코드를 추가하였다. 코드 import java.util.ArrayList;..

BOJ 1806 부분합 난이도 : 골드 4 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 전략 수열의 길이 N이 최대 100,000이므로 당연히 O(N^2)으로 모두 탐색하는 것은 불가능하다. 투 포인터를 이용하여 O(N)에 배열의 연속된 부분합을 탐색할 수 있다. 시행착오 처음에는 하나의 loop 안에서 start와 end를 함께 옮기려고 했는데 조건문이 좀 복잡해진다. 따라서 둘 중 하나(코드에서는 start)를 루프의 기준..

BOJ 14003 가장 긴 증가하는 부분 수열 5 난이도 : 플래 5 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 전략 수열의 크기 N이 최대 1,000,000이므로 O(N^2) 알고리즘으로는 해결할 수 없다. 이를 O(NlogN)만에 해결할 수 있는 LIS 알고리즘은 이분 탐색과 메모이제이션을 함께 사용한다. 1. dp[len]은 길이가 len인 증가하는 부분 수열 중에서 가장 작은 마지막 원소가 저장된다. ..

BOJ 1647 도시 분할 계획 난이도 : 골드 4 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 전략 간단한 MST 문제이다. 크루스칼 알고리즘은 사이클을 만들지 않는 가중치가 낮은 간선부터 차례대로 연결하는데, 두 마을로 분할하려면 간선 하나를 덜 연결하면 된다 따라서 기존 V - 1만큼의 간선을 연결하던 것을 V - 2로 수정해주면 끝이다 시행착오 다행히 없었음! 코드 import java.io.Bu..

BOJ 2239 스도쿠 난이도 : 골드 4 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 전략 간단한 백트래킹 문제로 예전에 c++로 한번 풀었던 적이 있다. (BOJ 2580) 재귀에 너무 익숙해져있는 것 같아서 이번에는 스택으로 구현해보고자 풀어보았다. 시행착오 재귀로는 정적 배열을 수정하면서 간단하게 백트래킹을 구현할 수 있었다. 스택으로 하려니까 실패했을 때 이전 상태로 돌리는 것을 어떻게 처리할지 고민을 많이 했다. 따라서 cl..