오늘은 유명한 유형 중 하나인 LIS 유형에 대해 정리해보고자 한다. 해당 유형을 안 지 얼마 되지 않았지만, 유형이 어느정도 정형화 되어있는 느낌이다. 해당 유형을 풀이하는 방법은 DP, 이분탐색 2가지가 있다. DP로 풀이할 경우 O(N^2)의 시간복잡도를, 이분탐색으로 풀이할 경우 O(NlogN)의 시간복잡도를 가진다. 따라서 문제에 나와있는 조건을 잘 보고 시간복잡도를 따져서 알고리즘을 선택하는 것이 중요하다. 해당 유형은 가장 긴 증가하는 부분 수열의 길이까지만 구하거나, 더 나아가 부분 수열 자체를 출력해야하는 문제들이 있다. 해당 유형은 1,2편으로 나누어 작성하고자 하며, 해당 글(1편)에서는 가장 긴 증가하는 부분 수열의 길이까지만 구하는 문제를 다뤄보고자 한다. 우선 백준 12015번 ..
이번 글은 삼성 코테 기출 문제인 19238번 문제를 복기하면서 쓰는 글이다.https://www.acmicpc.net/problem/19238 해당 문제는 문제설명에서도 나와있듯이, 택시가 승객이 위치한 곳으로 이동해야하며 이때 택시의 위치에서 가장 가까운 위치에 있는, 즉 최단경로에 있는 승객을 태우러 가기 때문에 BFS 알고리즘을 떠올려야 했다. + 조건을 잘 따져가면서 풀어야 하는게 중요했다. 해당 문제는 눈높이 개발에서 진행하는 코딩테스트 챌린지를 진행하면서 푼 문제인데, 여기서 힌트를 주신게 메모리 초과가 나지않게 점검해보라고 하셨던 거였다! 그래서 처음에 딱 생각이 났던게, 택시와 승객의 최단 경로 길이를 구해야하는데 이걸 승객마다 BFS를 돌리기에는 시간초과가 뜰 것 같다는 생각이 들었다..
백준(BEAKJOON) | 알고리즘 분류 이진탐색 #2110번 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 문제 | 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 ..
백준(BEAKJOON) | 알고리즘 분류 DFS #2606번 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 | 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과..
백준(BEAKJOON) | 단계별로 풀어보기 5-1단계 #10818번 www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 문제 | ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 지우를 도와 줄 프로그램을 작성하고자 한다. 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 ..
백준(BEAKJOON) | 단계별로 풀어보기 5-3단계 #2577번 www.acmicpc.net/problem/2577 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 같거나 크고, 1,000보다 작은 자연수이다. www.acmicpc.net 문제 | 세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오. 예를 들어 A = 150, B = 266, C = 427 이라면 A × B × C = 150 × 266 × 427 = 17037300 이 되고, 계산한 결과 17037300 에는 0이 3번, 1이 1번, 3이 2번, 7이 2번 쓰였다. ..
백준(BEAKJOON) | 단계별로 풀어보기 5-2단계 #2562번 www.acmicpc.net/problem/2562 2562번: 최댓값 9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오. 예를 들어, 서로 다른 9개의 자연수 3, 29, 38, 12, 57, 74, 40, 85, 61 이 주어 www.acmicpc.net 문제 | 9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오. 예를 들어, 서로 다른 9개의 자연수 3, 29, 38, 12, 57, 74, 40, 85, 61 이 주어지면, 이들 중 최댓값은 85이고, 이 값은 8번째 수이다. 입력 | 첫째 ..
백준(BEAKJOON) | 단계별로 풀어보기 5-1단계 #10818번 www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 | N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성하시오. 입력 | 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 ..
