문제번역문자열 s가 주어졌을때, 가장 긴 팰린드롬 부분배열의 길이를 반환해라.여기서 부분배열이란, 원래 문자열에서 일부 문자를 지우거나 지우지 않아서 만들 수 있는 수열이다.일부 문자를 지워도 남아있는 문자들의 순서는 바뀌면 안 된다. 접근 방법 및 소스코드문자열 전체를 보지 않고 작은 구간부터 찾아가면 된다.dp[i][j] 는 문자열 i번째부터 j번째까지의 구간에서 만들 수 있는 가장 긴 팰린드롬 부분배열의 길이라고 하자. 양 끝 문자가 같다면 이 둘은 팰린드롬의 양 끝으로 같이 쓸 수 있다.그러면 안쪽 구간에서 만든 가장 긴 팰린드롬에다가 양쪽 문자 2개를 더하면 된다. 양 끝 문자가 다른 경우 둘 다 쓸 수 없다.그래서 왼쪽 문자 i를 버리거나 오른쪽 문자 j를 버려야 한다.이 둘 중 하나를 버렸을..

문제번역정수 배열 nums가 주어졌을 때, 배열을 2개의 부분 배열로 나누었을 때 두 배열의 합이 같으면 true를 반환해라.그렇지 않으면 false를 반환해라.접근 방법 및 소스 코드일단, 배열의 합이 홀수이면 그 어떤 경우의 수로 나누어도 두 부분배열의 합이 같아질 수 없다. 이 문제를 풀기 위해서는 부분배열의 합 = 전체 배열의 합 / 2 인지를 확인해야 한다.즉 nums에서 몇 개의 수를 골라서 전체 합 / 2를 만들 수 있는지 확인하면 된다. bool dp[10001];bool canPartition(int* nums, int numsSize) { memset(dp, 0, sizeof(dp)); int s=0; for(int i=0;i= t; j--) { d..

문제번역정수 n이 주어졌을때, n을 만들 수 있는 가장 적은 perfect squares 수의 개수를 구해라.perfect squares 란 어떤 정수의 제곱이 되는 정수를 말한다.예를 들어 1,4,9,16은 perfect squares 이지만, 3과 11은 아니다.접근 방법 및 소스 코드일단 어떤 숫자 i에 대해서, 이 수를 만들 수 있는 가장 적은 perfect squares 수의 최악의 경우는 1로만 이루어진 경우이다.즉, 숫자 i를 만들기 위해 1을 i번 쓰는 것이 가장 최악이다. 그 다음, i라는 숫자를 만들기 위해 어떤 제곱수 하나를 더 더한다고 생각해보자.k라는 제곱수가 있다고 해보자.k그 중 가장 작은 값을 저장하면 된다. int dp[10005];int min(int a, int b) {..

문제번역m by n 정수 배열 matrix가 주어진다.이때 matrix에서 가장 긴 증가하는 길의 길이를 반환해라.각 셀에서, 우리는 상하좌우로만 움직일 수 있다. 대각선으로 움직이거나 경계 밖으로 나갈 수는 없다.접근 방법 및 소스코드Hard 단계라서 처음에 조금 두려웠는데, 생각보다 쉽게 풀렸다.DP를 사용한 풀이로 접근하면 된다. 각 칸을 그래프의 노드로 보고 상하좌우 중 현재 값보다 큰 값을 갖는 노드로 이동한다.DFS를 통해 해당 칸에서 시작하는 최대 증가 경로 길이를 위해 자신을 기준으로 해 상하좌우 노드를 탐색한다.같은 칸의 결과를 재계산하지 않도록 DP를 통해 저장하고 재사용한다(메모이제이션 기법) 이를 코드로 구현하면 다음과 같이 작성할 수 있다. int m,n;int dr[4] = {-..

문제번역총 numCourses 개의 과목이 있고, 0번부터 numCourses-1번까지 번호로 라벨링이 되어 있다.prerequisites 배열의 i번째 원소는 a, b로 되어 있는데, 이는 a과목을 듣기 위해서는 b과목을 먼저 들어야 한다는 것을 의미한다.(선수과목)만약 모든 과목을 들을 수 있다면 true를, 그게 불가능 하다면 false를 반환해라. 접근 방법 및 소스코드선수과목의 관계를 방향 그래프로 생각해보자. 자료구조개론과 알고리즘개론 수업이 있다고 해보자.알고리즘개론 수업을 듣기 위해서는 자료구조개론 수업을 먼저 들어야 한다.이 경우에는 자료구조개론 -> 알고리즘개론 으로 간선이 그려질 것이다.이와 함께 자료구조개론 수업을 듣기 위해서는 알고리즘개론 수업을 먼저 들어야 한다.이 경우에는 알고..

문제 번역 0번부터 n-1번까지의 번호가 붙은 n개의 방이 있고, 0번 방을 제외한 모든 방은 잠겨있다.우리의 목표는 모든 방을 방문하는 것이다. 하지만, 너는 열쇠 없이는 방에 들어갈 수 없다. 우리가 방에 방문한다면 구별되는 키들의 집합을 찾을 수 있을 것이다(여기에는 공집합이 있을 수 있다, 다시 말해 비어있다.) 각 키의 번호가 각 방을 열 수 있는 열쇠이다. rooms 배열의 i번째 원소는 i번째 방을 방문했을 때 얻을 수 있는 키들이다. 만약 모든 방을 방문할 수 있다면 true를, 불가능하다면 false를 반환해라. 접근 방법 및 소스코드0번 노드부터 시작하는 DFS/BFS 탐색으로 접근하면 된다.0번 노드에서 얻은 키는 0번 노드와 연결된 방들이고, 이 키들을 stack/queue 등에 넣..

문제번역events 배열이 주어지고 events 배열의 각 원소는 [startDay_i, endDay_i]로 이루어져 있다.각 이벤트 i 는 startDay_i 날에 시작해서 endDay_i 날에 끝난다.우리는 이벤트가 열리는 날 중 하루만 참석할 수 있다. 이벤트는 하루에 한번만 참여할 수 있다.우리가 참석 가능한 이벤트의 최대 개수를 반환해라. 접근 방법과 소스코드그리디와 MinHeap을 써서 오늘 참석 가능한 이벤트 중 가장 빨리 끝나는 이벤트에 참석하면 된다.늦게 끝나는 이벤트는 나중에 참석할 수 있기에 빨리 끝나는 이벤트를 우선해서 고른다. 오늘 시작하는 이벤트를 MinHeap에 전부 넣는다. 그리고 오늘 이전에 끝난, 즉 내가 더이상 참석하지 못하는 이벤트는 전부 날린다.그 중 가장 빨리 끝나..

문제번역정수 배열 nums와 정수 k가 주어질때, array에서 k번째로 가장 큰 원소를 반환해라.k번째 수는 정렬된 순서에서 k번째로 큰 수를 말하며, k번째의 구별되는 원소가 아니다. 정렬없이 구현해라.접근 방법과 소스코드대표적인 maxheap을 사용하는 문제이다.입력받은 수로 maxheap을 구성한다. 그러면 heap의 root는 첫번째로 가장 큰 수가 있을 것이다.이걸 k-1번 만큼 heap에서 pop을 하면 maxheap의 root는 k번째로 가장 큰 수가 담겨 있을 것이다.우린 이걸 pop 해서 반환해주면 된다. int heap[100001];int rsp = 0;void swap(int* a, int* b) { int t = *a; *a= *b; *b = t;}void pus..

문제번역게임에 참여하는 친구가 n명 있다. 이 친구들은 원형으로 앉아서 1번부터 n번까지 시계방향 순서로 번호를 부여받는다.좀 더 정확하게, i번째에서 시계 방향으로 이동하면 i+1 번째 친구에게 가게 되고, n번째 친구는 1번 친구에게 다시 가게 된다. 게임의 룰은 아래와 같다.1. 1번 친구부터 시작한다.2. 시작한 친구를 포함해서, 시계방향으로 다음 k명의 친구를 센다 원을 따라서 계속 세므로 한바퀴를 넘어가거나 두번 이상 셀 수 도 있다.3. 마지막으로 센 친구가 원에서 빠지고 게임에서 진다.4. 여전히 1명보다 많은 친구가 원에 있으면 2번부터 다시 수행한다.5. 그렇지 않으면 마지막으로 남은 친구가 게임에서 이긴다. n명의 친구가 주어지고, k 정수가 주어졌을 때 게임의 승자를 구해라.접근 방..

문제번역배열의 XOR Total 이라는 것은 배열의 모든 원소에 대해 XOR을 한 것을 말합니다. 만약 배열이 비어있다면 XOR Total은 0이 됩니다. nums라는 정수 배열이 주어졌을 때, nums의 모든 부분 배열의 XOR Total의 합을 반환해라.- 동일한 원소를 가진 부분배열은 동시에 카운트될 수 있습니다. 접근 방법 및 소스 코드입력의 길이를 \(n\)이라고 하자.그러면 subset은 총 \(2^n\) 개가 생긴다. 즉, 각 원소마다 선택지가 2개가 생긴다.해당 원소를 집어넣으면 기존 값과 xor을 하고, 해당 원소를 집어넣지 않으면 기존 값을 그대로 가져간다.이를 그냥 재귀로 돌려주고 더해주면 끝이다.물론 종료조건은 배열의 끝까지 가면 xor을 반환해주면 된다. int recursive(..