들어가며곧 시험기간을 앞두고 열심히 놀고있던 5월의 어느날, 갑자기 학교 행정실로부터 메일 한통을 받았다. 2026학년도 국가우수장학금(이공계) 2년지원유형에 추천을 해주겠다고 연락이 왔다.사실 이미 국가우수장학금의 존재에 대해 알고 있었다. 단과대마다 학점 순으로 컷해서 추천한다고 얼핏 듣긴 했다.하지만 학점이 높긴 한데 완전 높은 건 아니라서 별 기대를 안하고 있긴 했지만... 추천받아서 상당히 놀라긴 했다. 지원 과정사실 행정실로부터 추천을 받았단 이야기는 지원하면 거의 된다는 걸 어디서 본지라.. 생각보다 가벼운 마음으로 지원했다. 지원은 한국장학재단 홈페이지를 통해서 할 수 있고, 지원할 때 전인적 인재 성장 계획서 라는 것을 작성해야 한다.전인전 인재 성장 계획서는 쉽게 생각해서 자기소개서라..

문제번역문자열 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의 끝나는 시간보다 크면 어떤 구간이 끝난 것이므로 그룹을 재사용할 수 있다.그게 아니라면 새로운 그룹이 필요한 경우이다. 이를 해결하기 위해 시작 시간과 끝나는 시간을 각각 정렬한 뒤 투포인터를 통해서 문제를..