매일 조금씩

문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 문제가 바로 이해하기가 힘든데, 교차로는 노드이고 도로는 간선으로 생각하면 된다. 문제의 핵심은 시작지점에서 목적지까지 최단 거리로 가는데 g-h 간선을 통과했다는 점이다. 따라서, s -> 목적지 까지의 최단 거리 == s -> g까지의 최단 거리 + g-h 도로의 가중치 + g -> 목적지의 최단거리 s -> 목적지 까지의 최단 거리 == s -> h까지의 최단 거리 + h-g..

문제 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이 위상 정렬 알고리즘으로 풀 수 있다. 예시 1. 작년 순위 정보를 저장한다. 작년 순위 5 -> 4 -> 3 -> 2 -> 1 인접 노드에 대한 정보를 담을 자료 구조를 생성한다. 나는 ArrayList[] adjs = new ArrayList[] 을 이용하였다. 이 때, 중요한 것은 해당 팀보다 순위가 낮은 모든 팀의 정보를 넣어야 한다. adjs[5] 에는 4, 3, 2, 1..

문제 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 nCk 조합을 구한는 문제로 조합의 성질을 이용하여 재귀함수를 구현하여 풀 수 있다. (메모제이션 기법도 적용) nCn =1, nC0 = 1 nCk = n-1Ck-1 + n-1Ck 소스코드 package math; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ11051 { public static ..

문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 서쪽의 N개의 다리가 있고 동쪽에 M개의 다리가 있다. 다리를 겹치지 않게 배치할 수 있는 경우의 수는, 강 동쪽에서 M개의 다리 중 N개의 다리를 순서 없이 선택하는 경우의 수와 동일하다. 메모제이션 기법과 조합의 성질로 해당 문제를 풀 수 있다. 알아야 할 조합의 성질 nCn = 1, nC0 = 1 nCm = n-1Cm-1 + n-1Cm https://ko.wikipedia.org/..

문제 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 복습 차원에서 풀어 보았다. 이전에 작성한 코드와 비교해보니 구현 방법에서 약간 차이가 보인다. 해당 문제는 이분 탐색으로 가장 긴 증가하는 부분 수열의 길이를 구한 후, 인덱스를 이용한 역추적으로 수열의 값을 도출하여 문제를 풀 수 있다. 2021.11.04 - [Algorithm] - [Algorith..

문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색을 이용해 풀 수 있다. 예시 3 5 5 5 4 오영식이 이미 가지고 있는 랜선의 개수가 3개 5 5 4 내가 필요한 랜선의 개수는 5개이다. 이 조건이 충족될 때까지 이분 탐색을 진행한다. 초기 값 left = 1 right = 5 첫 번째 탐색 left = 1 right = 5 mid = 3 5, 5, 4 를 3으로 나눈 몫을 모두 더하면 랜선의..

문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 풀이 이게 왜 정답률이 높은지 모르겠다. 막상 풀면 쉬운데 접근법을 생각하기가 쉽지 않다. 구글링을 통해 힌트를 얻어서 풀었다. 예제 설명 예제는 다음과 같다. N = 3, k = 7 3 7 3*3 배열에 각각 행과 열을 곱한 값이 입력되어 있다. 1 2 3 2 4 6 3 6 9 위 값들을 일렬로 쭉 나열 하면 아래와 같다. 1, 2, 3, 2, 4, 6, 3,..

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 절단기의 설정할 수 있는 높이로 이분 탐색을 하여 풀었다. 예제를 그려보면 다음과 같다 적어도 7미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제이다. 최초 시작과 끝을 아래와 같이 설정한 후, 이분 탐색을 진행하여 답을 구할 수 있다. 절단기에 설정할 수 있는 최소 H: 0 절단기에 설정할 수 있는 최대 H..

문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 이분 탐색을 이용하여 풀 수 있다. 처음에 문제를 이해하는데 시간이 걸려서, 최대한 자세히 풀이를 써보려고 한다. 예제는 다음과 같다. 집의 개수 : 5개, 공유기 개수: 3개 5 3 1 2 8 4 9 여기서 구해야 할 것은?? 가장 인접한 두 공유기 사이의 최대 거리를 출력하는 것이다. 아래와 같이 집이 위치해있다고 가정했을 때, 가..

문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 2021.11.08 - [Problem Solving/BOJ] - [BOJ 9251] LCS 최장 공통 부분 수열 문제 (Java) [BOJ 9251] LCS 최장 공통 부분 수열 문제 (Java) LCS 문제란? 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을..