![]()
이진탐색, 투 포인터로 다시 풀어보기 이진탐색 NlogN 투 포인터 N 누적합 N^2 https://www.acmicpc.net/problem/2118 2118번: 두 개의 탑 첫째 줄에 지점의 개수 N(2 ≤ N ≤ 50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 양의 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다. www.acmicpc.net 환형구조에서 반대쪽으로의 거리를 구할려면 전체 거리 - 순방향 거리를 하면 된다. 투포인터 문제이지만 나는 N2 복잡도인 누적합으로 해결하였다. 환형구조의 경우 선형자료형에 저장하기 위해 모듈러(%)를 사용하여 인덱스를 관리해 주어야 한다. 상황에 따라 그냥 배열을 두배로 늘리고 모듈러를 사용하지 않는..
https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 해쉬맵을 쓰거나 문자열을 인덱스로 변환해주는 메소드를 만들어서 사용하면 된다. left와 right사이의 거리가 일정한 문제이다. import java.util.*; import java.io.*; public class Main { public static HashMap std = new HashMap(); public static int s; public static i..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int search(int[] numbers, int m){ int right = 0; int min_diff = 2_000_000_000; for(int left=0; left
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int search(int[] acc, int s){ int right = 0; int sum_length=acc.length+1; for(int left=1; left
![]()
투 포인터 (주로) 선형 데이터 구조에서 두 개의 인덱스를 관리하여 특정 조건을 만족하는 부분집합이나 특정 값을 찾는 알고리즘 1. 두 포인터(인덱스)를 시작점(left=0, right=0 또는 left=0, right=마지막인덱스 또는 서로다른 배열 등)으로 초기화한다. 2. 규칙에 따라 포인터를 이동시킨다. - 같은 배열에서 동일한 방향으로 이동하는 투 포인터 - 같은 배열에서 마주보는 방향으로 좁혀가는 투 포인터 - 서로 다른 배열에서 이동하는 투 포인터 - 여러 형태에서 효율적인 시간 복잡도를 가진다. 3. 두 포인터 중 하나 혹은 둘 모두가 끝에 도달할 때까지 반복한다. * 인덱스가 아니더라도 오른쪽(시계방향), 왼쪽(반시계) 거리를 right, left로 둘 수 도 있다. https://yun..
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 이문제는 Map과 이분탐색 두가지 방법으로 풀 수 있다. 나는 Map이 더 간단해보여 Map을 이용했다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ Bu..
https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net check()함수 만드는 것이 꽤 생각을 요하는 문제 질투값이 널널하다면 그냥 true을 뱉으면 된다. 왜냐면 다음 탐색에서 정답을 찾기 때문에 최대한 빡세게 검사하고 보석을 다시 분배에서 사람수만큼의 집합으로 만든다고 생각하면됨 다시 문제를 보니 보석을 주지 않아도 되기 때문에 간단한 문제였다.. import java.util.*; import java.io.*; public class Main ..
https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net check함수의 반복문 처음에 각 영상이 디스크크기를 초과할 경우가 있다는 것을 확인해주지 않아서 풀이시간이 꽤 걸렸다. import java.util.*; import java.io.*; public class Main { public static int n; public static int m; public static int[] input; public static boolean check(int ..
