어흥

문제 링크: https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. 주의할 점 - 이분탐색으로 접근한다(양 끝에서 시작하는 투 포인터) - 정렬 이후, 이분탐색을 수행한다 2. 구현 - 모든 수를 입력받은 후, 오름차순으로 정렬한다 - Left 포인터를 0, Right 포인터를 Num-1로 설정하고 Al, Ar(출력시킬 정답), Result를 초기화하고 시작한다 - Left 포인터가 Right포인터를 넘지 않을때..

문제 링크: https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 문제 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 www.acmicpc.net 1. 주의할 점 - 두 포인터를 사용하여 풀어야 한다 - 검사를 할 때 마다 Check[][]배열을 False로 초기화 해야 한다 2. 구현 - 배열을 입력받고, 배열의 최소값과 최대값을 구한다 - L,R을 배열의 최소값으로 설정하고 While문을 시작한다(L~R 사이여야 이동 가능) - 만약 시작지점이 L보다 작거나 R보다 크다면 R++를 한다 - 시작지점 L..

문제 링크: https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 �� www.acmicpc.net 1. 주의할 점 - 간선에 대한 정보를 배열이 아닌 List 형태인 V[] 벡터에 저장한다 - 다익스트라를 2번 구현한다 2. 구현 - 모든 간선에 대한 정보를 V[] 벡터에 저장한다 - Dijsktra 알고리즘을 통해 Root Node에서 가장 길이가 먼 Node를 구한다 - 위에 구한 Node에서 시작하여 Dijsktra를 다시 수행하며 가장 긴 트리의 지름을 ..

문제 링크: https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 1. 주의할 점 - BFS로 접근하되, 시작지점을 아기상어의 위치로 잡는다 2. 구현 - 모든 Check[][]값을 MAX로 초기화한다 - 아기상어가 위치한 곳을 큐에 넣고, Check[][]값을 0으로 설정한다 - 8방향 탐색을 통해 이동하려는 곳의 Check[][]값이 현재 이동한 거리(CV)+1보다 크다면 이동하고 Result를 CV+1와 비교하여 큰..

문제 링크: 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 1. 주의할 점 - Arr[] 배열을 Long Long 타입으로 받는다 - DP[] 배열에 가장 긴 증가하는 부분 수열이 저장되어 있는 것이 아니다 2. 구현 - 모든 수를 Arr[]배열에 입력받고, Dp[0]=Arr[0], Idx=0, Ans[0].idx=0, Ans[0].val=Arr[0]으로 초기화 하고 시작한다 - For문을 1~Num-1까지 돌리..

문제 링크: https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1. 주의할 점 - 이분탐색을 사용하는 LIS에 대해 알고 있어야 한다. - 가장 긴 증가하는 부분 수열 2와 풀이 방법은 같다. 다른점은 모든 변수를 Int가 아닌 Long Long으로 받아들인다. 풀이 방법: https://imnotabear.tistory.com/183 [백준 12015] 가장 긴 증가하는 부분 수열 2 (C++) 문제 링크: htt..

문제 링크: https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 1. 주의할 점 - 직전의 게시물과 같이 N^2의 시간복잡도를 지니는 방법으로는 TLE가 난다 - 이분탐색을 사용하여 NlgN의 시간복잡도를 지니게 한다 2. 구현 - 모든 배열에 대한 정보를 Arr[] 배열에 저장하고 Dp[0]= Arr[0], idx=0으로 초기화한다 - i: 1~Num-1까지 For문을 수행하며, Dp[idx]< Arr[i]인 경우, 무조건 추가한다 - 이외의 경..

문제 링크: 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 1. 주의할 점 - DP처럼 진행한다 - 가장 긴 증가하는 부분 수열을 어떤 방식으로 담을 건지 생각한다 2. 구현 - 배열을 입력받으면서, Result[]배열도 초기화 작업을 한다 - i: 1~Num-1, j: 0~i-1까지 반복하면서 Arr[i]>Arr[j]를 만족한다면 Result 배열의 인자를 비..