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 위 블로그에..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net ◎ 문제풀이 가장 기본적인 플로이드-워셜 알고리즘 문제이다. [Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘이란? [Algorithm] 다익스트라 알고리즘(Dijkstra)이란? 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘은 특정지점에서 다른지점으로 가는 최단경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 그 lordofkangs.tistory.com 알고리..

12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net ◎ 문제 풀이 [PS] BOJ12015 가장 긴 증가하는 부분수열2 ( LIS ) with JAVA 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ◎ 문제풀이 DP는 lordofkangs.tistory.com (위 문제와 풀이는 똑같다. ..

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net ◎ 문제풀이 처음에는 대부분 DFS로 풀었다가 시간초과를 마주한다. 한 경로가 위처럼 이동했다고 해보자. 경로가 지나간 노드는 모두 방문된 노드가 된다. 보통의 DFS 풀이처럼 한번 방문한 노드를 다시 방문하지 못하도록 조건을 건다면 DFS의 시간복잡도는 O(N+E)가 된다. ( N은 노드의 개수, E은 간선의 개수 ) N은 최대 2,500개이고 간선은 노드 하나당 4개를 갖는다고 가정하면 10,000개이다. 시간복잡도가 O(N+E)면 충분히 시간제한 2초안에 풀 수..

17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net ◎ 문제풀이 앞뒤 방향으로 문자열이 같으면 회문, 한 문자만 다르면 유사회문이라고 한다. 회문이면 0, 유사회문이면 1, 그외 문자열은 2를 출력하는 문제이다. 투포인터를 떠올리기는 했으나 재귀호출을 발상하지 못해 문제풀이가 어려웠다. LEFT , RIGHT를 하나씩 비교하며 나갈 것이다. 그럼 이렇게 서로 다른 부분을 만날 수 있다. 경우는 2가지가 있다. 1) LEFT 포인터 문자를 제거하는 경우 2) RIGHT 포인터 문자를 제거하는 경우 1)인 경우와 2)인 경우를 재귀호출을 활용하여 ..

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

1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net ◎ 문제풀이 트리의 지름의 최대 길이를 구하는 문제이다. 이는 노드A에서 노드B까지 거리의 최댓값을 구하라는 의미이다. 한 노드에서 다른 노드까지 가는 경우의 수를 완전탐색하여 최댓값을 구하는 문제이므로 DFS를 이용하면 된다. 추가로, 문제를 더 빠르게 푸는 방법이 있다. 1) 1번 노드에서 DFS 완전탐색으로 가장 멀리 떨어져있는 노드A를 구한다. 2) 노드A까지 가는 경로는 가중치가 가장 높은 경로를 의미한다. 3) 노드A에서 거리가 가..

15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net ◎ 문제풀이 DP 점화식 구현이 까다로운 문제였다. 7일에 받을 수 있는 상담의 경우의 수는 다음과 같다. 1일에 시작된 상담이 6일 걸려 7일이 될 수 있고 3일에 시작된 상담이 4일 걸려 7일이 될 수 있다 그리고 만약 전날에 마무리 된 상담비용이 더 크면 그대로 7일의 상담비용이 된다. 이와 같이, 7일이 될 수 있는 모든 경우의 수에서 최댓값을 구하면 된다. ◎ 코드 import java.io.BufferedReader; im..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net ◎ 문제풀이 A지점에서 B지점으로 최소비용으로 이동하는 문제는 BFS로 풀어야 한다. 그러나 나는 최근에 DP 문제를 하나 풀어서 그런지, 이 문제를 보고 DP 발상을 했다. N에서 K까지 가는 경우를 모든 고려하는 문제이다. 이동하는 방법은 3가지이다. 1) x2 2) +1 3) -1 N이 5이고 K가 17이라고 가정해보자. 위 그림 같이, 경우의 수가 기하급수적으로 증가하니 DP로 풀기는 어려운 문제이다. 1) x2 2) ..

2608번: 로마 숫자 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다. www.acmicpc.net ◎ 문제풀이 문제가 복잡해 보이나 이해를 하면 어려운 문제는 아니다. 복잡한 개념이 들어가 있지는 않으나 구현력이 필요한 문제였다. 크게 두 가지 과정이 있다. 1) 로마 숫자를 십진법 숫자로 만들기 2) 십진법 숫자를 로마숫자로 만들기 - 로마 숫자를 십진법 숫자로 만들기 1) 로마문자와 십집법 숫자가 매핑된 Map 자료구조를 만든다. 2) 로마숫자를 좌측부터 한 문자씩 읽어온다. 3) 현재 문자는 이전 문자보다 작아야 한다. 4) 현재 문자가 이전 문자보다 크다면 XL, XC , CD ,CM ... 이런 문자..