궁금한게 많은 개발자 노트

해당 문제는 숫자 배열과 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++) ..

0과 1로만 이루어진 배열에서 한 가지 원소를 제거하였을 때, 1로만 이루어진 가장 긴 subarry의 길이를 반환하는 문제. array를 순회하면서 나올 수 있는 경우의 수를 생각해보면 다음과 같습니다. [0] 1을 만난다면 현재 len을 증가시켜 줍니다. len++, zero_count = 0; [1] 0을 만나기 전 1이 없었다면 정답과 관련된 길이를 구할 수 없습니다. zero_coun++; [2] 0을 만나기 전 1이 있었고, 0을 만난게 처음이라면 정답과 관련된 길이를 해당 길이는 과거형이 됩니다. prev_len = len, len = 0; [3] 0을 두 번 만났다면 prev_len과 len모두 0이됩니다. 이렇게 해서 결국 prev_len + len의 길이가 가장 긴 경우가 정답이 됩니다..