문제번역문자열 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 등에 넣..

문제 번역서로 다른 값으로 이루어진 정수 배열 nums가 있다.이 배열은 원래 오름차순으로 정렬되어 있다.함수에 전달되기 전에, nums는 알 수 없는 인덱스 k(k는 1 이상 nums.length 미만)에서 왼쪽으로 회전되었을 수도 있다. 회전된 배열은 다음과 같은 형태가 된다.[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] 인덱스는 0부터 시작한다.예를 들어 [0,1,2,4,5,6,7] 배열이 왼쪽으로 3칸 회전하면 [4,5,6,7,0,1,2]가 된다. 회전되었을 수도 있는 배열 nums와 정수 target이 주어졌을 때, target이 nums안에 있으면 그 인덱스를 반환하고 없으면 -1를 반환해라.알고리즘의 시간복잡도는..

문제번역주어진 정수 배열 citations이 있다.citations의 i번째 원소는 한 연구자가 발표한 i번째 논문이 받은 인용 횟수를 의미한다.또한 citations 배열은 non-decreasing(감소하지 않는, 즉 오름차순) 순서로 정렬되어 있다.이때 연구자의 h-index를 반환해라. h-index란 연구자가 발표한 논문 중 적어도 h편의 논문이 각각 h회 이상 인용되었을때, h의 가장 큰 값이다.접근 방법과 소스코드이 문제를 풀려고 보니 정렬이 되어 있고, 로그 시간복잡도로 풀라고 되어있었다. 일단 citations 배열의 i번째 원소가 h-index 후보가 되려면 citations[i] >= citationsSize - i 여야 한다.이는 현재 논문부터 끝까지의 논문이 각각 최소 citati..

문제번역2차원 정수 배열 intervals가 주어진다. intervals의 각 원소는 \( [ left_i, right_i ] \) 로 구성된다.이 intervals를 하나 이상의 그룹으로 나눠서 각 그룹마다 교집합이 없게 만들어야 한다.이때 우리가 만들 수 있는 최소한의 그룹의 수를 반환해라[1, 5] , [5, 8] 과 같이 하나의 수라도 겹치면 겹친다고 판단한다.접근 방법과 소스코드특정 시점에 동시에 겹치는 구간의 최대 개수를 구하면 된다.어떤 interval의 시작시간이 다른 interval의 끝나는 시간보다 크면 어떤 구간이 끝난 것이므로 그룹을 재사용할 수 있다.그게 아니라면 새로운 그룹이 필요한 경우이다. 이를 해결하기 위해 시작 시간과 끝나는 시간을 각각 정렬한 뒤 투포인터를 통해서 문제를..

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