궁금한게 많은 개발자 노트

해당 문제는 숫자로 이루어진 배열에서, 서로 다른 인덱스 i, j, k가 i < j < k관계를 이루고, index에 존재하는 값도 nums[i] < nums[j] < nums[k]를 이루는 i, j, k가 존재하는지 여부를 판단하는 문제입니다. 연속성을 가질 필요는 없지만 해당 조건을 만족하기 위해서는 두 변수가 필요하고, 한 변수에는 가장 작은 값을 업데이트하고, 두 번째 변수에는 첫 변수보다 높은 값이 나타나면 업데이트, 그리고 세번째 아이템을 만났을 때 두번 째 변수보다 크다면 해당 조건을 만족하는 i, j, k가 존재한다는 의미입니다. 첫번째 변수가 채워졌는데 배열에서 다음 값이 더 작다면 다시 첫변수를 업데이트해주고, 더 크다면 두번째를 채우고, 두번째보다 더 큰 값이 나오면 조건을 만족한다고..

해당 문제는 숫자 배열과 diff가 주어졌을 때, arr의 subsequence 중에서 diff간격으로 이어지는 가장 긴 subsequence 길이를 반환하는 문제입니다. subsequence는 연속되지 않아도 됩니다. 특정 숫자로 시작하는 subsequence길이를 저장하는 것이 주요하여 map자료 구조를 사용하여 특정 숫자로 끝나는 subsequence의 최대 길이를 저장해두었습니다. subsequence는 diff를 더해가며 나오는 배열의 길이를 찾는 것이므로, i번째 숫자 - diff가 이미 map에 존재한다면 그 길이에 +1을 해서 i번째 숫자를 map에 저장해두고 반복해나가면 됩니다. 즉, arr[i] - diff가 map에 이미 존재한다면 arr[i] - diff까지의 길이 + 1을 arr[..

해당 문제는 n길이의 배열에서 서로 인접한 두 인덱스를 고르지 못하는 제약 조건 내에서 선택한 인덱스에 존재하는 숫자들의 가장 큰 합을 구하는 문제입니다. Dynamic Programing의 기본적인 문제일 수 있고, 연습에 좋은 문제라고 생각되었습니다. i번째 index까지의 선택한 숫자들의 합중 가장 큰 값은 i-2까지의 가장 큰 값과 i번째 숫자를 더한 것과 i번째 숫자를 선택하지 않고 i-1까지의 합 중 가장 큰 값을 비교하여 큰 값으로 설정합니다. dp[i-2] = max(dp[i-1], dp[i-2] + nums[i])로 표현될 수 있습니다. #define max(a,b)((a) > (b) ? (a) : (b)) class Solution { public: int rob(vector& nums..

이 문제는 주어진 numCourses만큼의 과목들을 모두 수강할 수 있는 지를 판단하는 문제입니다. numCourses가 주어진다면 과목은 0부터 numCourses-1까지 존재하며, prerequisites가 주어지는데 크기가 2인 배열의 집합으로 구성되어 있으며 [1,0]으로 표현되는 prerequisite은 1과목을 수강하기 위해서는 0과목을 먼저 수강해야 한다는 의미입니다. 문제를 분석해보면, [1,0], [0,1]처럼 cycle이 생기는 경우를 판단하는 문제이고 cycle이 생기지 않는다면 true를 반환합니다. cycle이 생기는 것을 판단하기 위해서는 우선, 각 과목과 선수 과목이 있으면 해당 과목들을 표기하는 adjacent vector가 필요하고, 미리 들어야 하는 과목에 해당하는 것의 ..

해당 문제는 숫자로 이루어진 배열에서 target 숫자보다 같거나 큰 가장 짧은 sub array길이를 구하는 문제입니다. two point로 i, j가 움직인다면 i는 배열을 순회하며 새로운 숫자를 sum에 더하고, j도 0부터 시작하며 sum이 target보다 같거나 크다면 앞에서부터 하나씩 제거하면서 target을 넘는 가장 작은 길이를 업데이트합니다. #define min(a,b)((a) > (b) ? (b) : (a)) class Solution { public: int minSubArrayLen(int target, vector& nums) { int answer = INT_MAX; int sum = 0; int j = 0; for (int i = 0; i < nums.size(); i++) ..