L.O.K

2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net ◎ 문제풀이 아직 투포인터 알고리즘에 대학 숙련도가 낮아 처음에 투포인터를 어디에 위치시켜야 할지를 몰랐다. [BOJ] 백준 2230번 : 수 고르기 (JAVA) 문제 N(1≤N≤100,000)개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하 steady-coding.tistory.com 위 블로그에..

2118번: 두 개의 탑 첫째 줄에 지점의 개수 N(2 ≤ N ≤ 50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 양의 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다. www.acmicpc.net ◎ 문제풀이 차례로 각 지점이 원으로 연결되어 있을 때, 두 지점 사이의 거리의 최댓값을 구하는 문제이다. 지점의 개수가 최대 5만개이니 두 지점의 모든 경우를 완전탐색하면 시간초과가 난다. 그러니 Two Pointer 알고리즘을 사용해보자. Two Pointer 알고리즘은 두 지점의 경우 중에 비교할 가치가 있는 경우만 가지치기하여 탐색하는 알고리즘이다. PointerA와 PointerB 사이의 거리는 두 가지가 있다. PointerA지점의 오른쪽 ..

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net ◎ 문제풀이 여러 용액 중 2가지를 골라 합칠 때, 그 값이 0에 가장 가까운 조합을 고르는 문제이다. 가장 간단한 풀이는 2가지 조합을 구하는 문제이니 2중 for문을 만들어서 완전탐색하는 것이다. 그러나 용액이 최대 100,000개이니 2중 for문으로 탐색하면 시간제한에 걸릴 수 있다. 여기서는 TwoPointer 알고리즘을 활용하는 것이 좋다. Two Pointer 알고리즘은 정렬과 두개의 포인터를 이용하여 시간복잡도를 ..