어흥

문제 링크: www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 1. 주의할 점 - LIS 알고리즘에 대해 알고 있어야 한다 - 이분탐색을 통한 LIS를 수행한다 2. 구현 - 모든 수를 Arr[] 배열에 담는다 - DP[idx] 배열에 가장 긴 증가하는 부분수열 중에서 idx번째에 위치한 수를 저장한다 - DP[0] = Arr[0]을 담은 후, 1번째 index부터 탐색을 시작한다 - 만약 DP[Idx]보다 Arr[i]가 크다면, 가장 긴 ..

문제 링크: www.hackerrank.com/challenges/max-array-sum/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dynamic-programming Max Array Sum | HackerRank Find the maximum sum of elements in an array. www.hackerrank.com 1. 주의할 점 - DP로 풀지 않고 일반 DFS로 풀 경우, TLE발생 - DFS + DP 즉, 메모이제이션으로 풀 수 있다 2. 구현 - DP[][]배열을 통해 [현재 Index][현재 Arr[]값 사용 여부] 형태로 최대값을 저장한다. 단, Arr[] 벡..

문제 링크: www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1.주의할 점 - 메모리의 제한이 극단적이니 배열의 크기를 최소로 한다 2. 구현 - 각 줄을 Arr[]배열에 입력받는다 - 만약 첫 번째 줄이라면, Maxi[1][], Mini[1][] 배열에 그대로 값을 대입한다. Maxi[0][] 배열은 t번째 숫자를 입력받기전인 t-1번까지의 최대 점수를 저장하는 배열이다. Maxi[1][] 배열은 t번째 숫자를 받은 후, t번째까지의 최대 점수를 저장하는 배열이다. Mi..

문제 링크: www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. 주의할 점 - 매 TC마다 구하지 않고, 각 열의 1~N까지의 합을 Arr[][N]에 저장한다 2. 구현 - Arr[M][N] = Arr[M][N-1] + [M][N]에 입력받는 수를 저장한다 - 각 쿼리마다 Arr[][Y2]-Arr[][Y1-1] 까지의 합을 X1~X2행까지 수행하여 출력한다 #include using namespace std; lo..

문제 링크: www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 1. 주의할 점 - 메모아이징 기법을 이용한다 - 값을 저장해서 사용하는 형태로 한다 2. 구현 - 모든 수를 입력 받고, Check[][] 배열에는 현재 지점에서 시작하여 살 수 있는 최대 일수를 저장한다 - 만약 Check[][] 값이 0이라면 DFS()를 수행한다 - DFS(y,x) 함수에는 이미 해당 Check[y][x] 값이 양수라면 해당 값을 반환한다. 0이라면, 현재 위치를 기..

문제 링크: www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 �� www.acmicpc.net 1. 주의할 점 - DP를 이용하여 푼다 2. 구현 - 현재 상자를 기준으로 왼쪽에 위치한 상자들만 생각한다 - 현재 상자보다 크기 작으면서, DP[] 값이(들어갈 수 있는 상자의 수) 가장 큰 수를 Maxi에 저장한다 - Maxi+1을 현재 상자번호에 해당하는 DP[] 배열에 할당한다. 할당 이후, Result의 값과 비교하여 최대값을 Result에 저장하도록 한다 #include #include u..

문제 링크: www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 1. 주의할 점 - i번째 곡은 p-v[i] or p+v[i]여야 한다(범위가 아니다) - 최악의 경우 2^100 -> TLE 발생 2. 구현 - DFS나 그리디로 구현하면 TLE가 발생할 수도 있다 -> DP로 해결 - N과 M의 범위가 작다 -> 2차 배열을 이용해도 풀 수 있다 - DP[i번째 곡을][이 값으로 연주할 수 있다]: True or False ..

문제 링크: www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 1. 주의할 점 - DP를 사용해서 문제를 해결한다(점화식) 2. 구현 - 1개의 타일: 1개(1) - 2개의 타일: 2개(00, 11) - N개의 타일을 사용할 때 : (N-1개의 타일 + N-2개의 타일)%MOD (여기서 MOD는 15746) 따라서 점화식은 N>=3일때, Arr[N] = (Arr[N-1] + Arr[N-2])%MOD로 이루어진다 #define MOD 15746 #include u..