궁금한게 많은 개발자 노트

해당 문제는 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의 길이가 가장 긴 경우가 정답이 됩니다..

오름 차순으로 연결된 k개의 linked list를 하나의 오름 차순으로 연결된 linked list로 합쳐서 반환하는 문제입니다. min heap을 구현하여 node들을 heap에 모두 넣고, 하나씩 빼서 모두를 연결하여 반환하였습니다. queue library를 import하고, struct compare의 operator함수를 overriding하여 min heap을 선언하려 합니다. struct compare { bool operator()(const ListNode* a, const ListNode* b) { return a->val > b->val; } }; k개의 linked list를 모두 heap에 넣고, 하나씩 빼면서 prev node와 방금 뺀 node를 연결해주는 방식으로 구현하였습..