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

문제번역정수 배열 nums와 정수 k가 주어질때, array에서 k번째로 가장 큰 원소를 반환해라.k번째 수는 정렬된 순서에서 k번째로 큰 수를 말하며, k번째의 구별되는 원소가 아니다. 정렬없이 구현해라.접근 방법과 소스코드대표적인 maxheap을 사용하는 문제이다.입력받은 수로 maxheap을 구성한다. 그러면 heap의 root는 첫번째로 가장 큰 수가 있을 것이다.이걸 k-1번 만큼 heap에서 pop을 하면 maxheap의 root는 k번째로 가장 큰 수가 담겨 있을 것이다.우린 이걸 pop 해서 반환해주면 된다. int heap[100001];int rsp = 0;void swap(int* a, int* b) { int t = *a; *a= *b; *b = t;}void pus..

문제번역게임에 참여하는 친구가 n명 있다. 이 친구들은 원형으로 앉아서 1번부터 n번까지 시계방향 순서로 번호를 부여받는다.좀 더 정확하게, i번째에서 시계 방향으로 이동하면 i+1 번째 친구에게 가게 되고, n번째 친구는 1번 친구에게 다시 가게 된다. 게임의 룰은 아래와 같다.1. 1번 친구부터 시작한다.2. 시작한 친구를 포함해서, 시계방향으로 다음 k명의 친구를 센다 원을 따라서 계속 세므로 한바퀴를 넘어가거나 두번 이상 셀 수 도 있다.3. 마지막으로 센 친구가 원에서 빠지고 게임에서 진다.4. 여전히 1명보다 많은 친구가 원에 있으면 2번부터 다시 수행한다.5. 그렇지 않으면 마지막으로 남은 친구가 게임에서 이긴다. n명의 친구가 주어지고, k 정수가 주어졌을 때 게임의 승자를 구해라.접근 방..

문제번역배열의 XOR Total 이라는 것은 배열의 모든 원소에 대해 XOR을 한 것을 말합니다. 만약 배열이 비어있다면 XOR Total은 0이 됩니다. nums라는 정수 배열이 주어졌을 때, nums의 모든 부분 배열의 XOR Total의 합을 반환해라.- 동일한 원소를 가진 부분배열은 동시에 카운트될 수 있습니다. 접근 방법 및 소스 코드입력의 길이를 \(n\)이라고 하자.그러면 subset은 총 \(2^n\) 개가 생긴다. 즉, 각 원소마다 선택지가 2개가 생긴다.해당 원소를 집어넣으면 기존 값과 xor을 하고, 해당 원소를 집어넣지 않으면 기존 값을 그대로 가져간다.이를 그냥 재귀로 돌려주고 더해주면 끝이다.물론 종료조건은 배열의 끝까지 가면 xor을 반환해주면 된다. int recursive(..

문제번역nums 라는 정수 배열과 정수 k가 주어졌을때, 부분배열의 모든 원소의 곱이 k보다 작은 부분배열의 개수를 반환해라.접근 방법 및 소스 코드투 포인터를 사용하면 된다.i를 0부터 numsSize-1까지 반복하면서 i에 해당하는 인덱스를 곱셈의 시작점으로 쓴다.포인터 j를 한칸씩 뒤로 가면서 곱해본다. 이때, 곱한 값이 k보다 작은지 매번 검사하면서 곱한다.그래서 가능한 가장 큰 j를 구한 뒤, counter에 해당 부분배열 길이 만큼 다시 더해준다.그 다음 i를 한칸 밀고, 기존에 곱했던 값에서 배열의 i번째의 값만큼 다시 나눠준다.그리고 j를 또 한칸씩 뒤로 가면서 곱해본다... 이를 끝까지 반복한다. int numSubarrayProductLessThanK(int* nums, int nums..

문제(원문)문제(번역)정수 n이 주어질때, 정수 n보다 작은 소수의 개수를 구해라.접근 방법소수 구하는 문제는 거의 에라토스테네스의 체를 활용하면 된다.에라토스테네스의 체란 2부터 시작해서 각 소수의 배수를 차례대로 지워가면서 소수만 남기는 방식이다.어떤 수 i가 소수이면 i의 배수는 전부 합성수가 되기 때문이다. 보통 \(i^2\) 부터 지우면 이미 처리된 수를 건너 뛰게 되어 더 효율적이다. 해당 문제에서도 에라토스테네스의 체를 활용했다. 메모리 사용량을 더 줄이기 위해 동적할당을 사용해 체에 필요한 리스트를 할당했다. 소스 코드int countPrimes(int n) { if(n

문제(원문) 문제(번역)양수가 담긴 배열 nums와 양의 정수 target이 주어진다.이때 subarray의 합이 target보다 크거나 같은 subarray의 최소 길이를 반환해라.적절한 subarray가 존재하지 않는다면 대신 0을 반환해라. 접근 방법처음에는 감이 잡히지 않아 해당 문제의 주제를 보니 슬라이딩 윈도우가 있다.슬라이딩 윈도우란 배열이나 문자열에서 연속된 구간을 잡아두고, 그 구간을 한칸씩 밀면서 원하는 조건을 찾는 기법이라고 한다. 현재 구간의 합이 target보다 작으면 오른쪽으로 한칸을 늘린다.만약 현재 구간의 합이 target 보다 크거나 같다면 최소 길이인지 확인 후 갱신한다. 그리고 target보다 작아질때까지 구간을 왼쪽에서 한칸 당겨서 줄여본다. 그리고 다시 조건을 만족하..

문제(원문)문제(번역)주어진 Linked List head가 있을때, 뒤에서 부터 n번째 노드를 삭제해라.단 Linked List 는 단방향이다. 이 문제를 1번에 풀 수 있는가?접근 방법Two pointer 기법을 사용하면 된다.현재 노드를 가리키는 포인터와 n만큼 앞서가는 포인터를 두고 사용하면 된다.앞서가는 포인터가 마지막 노드라면, 현재 노드가 자연스레 삭제될 노드가 되기 때문이다.이와 함께 현재의 이전 노드를 저장할 포인터도 필요하다. 앞서가는 포인터가 마지막 노드에 도착했을때 현재 삭제할 노드가 중간에 있는 노드인지, head 원소인지 확인해야 한다.우리는 원본 리스트를 그대로 반환할 것이기 때문에, head 노드가 삭제 대상이라면 head 노드를 head->next로 바꾸어주어야 한다.삭제할..

문제(원문) 문제(번역)비어있지 않으면서 음수가 아닌 두 linked list가 주어진다. 이 수들은 역순으로 정렬되어 있고, 각 노드는 하나의 숫자만 갖고 있다.이둘을 더한 linked list를 반환해라.단, 이 linked list에는 0인 경우를 제외하고 앞에 0이 들어있지 않다. 접근 방법그냥 Linked List를 순회하면서 수를 더하되, 10을 넘어가면 그 수를 다음에 보내서 더해주는 로직만 잘 작성하면 된다.하지만 Linked List를 할당하는 것과 Null 처리하는 부분을 조심하지 않으면 쉽게 에러가 난다. 소스 코드int safeGet(struct ListNode* l) { if(l == NULL) return 0; return l->val;}struct ListNode* ..

문제(원문)문제(번역)정렬되지 않은 정수 배열 nums가 주어진다. 이때 nums에 없는 가장 작은 양의 정수를 반환해라.반드시 반드시 반드시 O(n)의 시간복잡도를 가지면서 O(1)의 공간복잡도를 갖는 알고리즘을 구현해라.접근 방법처음에 보자마자 떠오른 생각은 단순하게 배열을 만들어서 flag 형식으로 수가 나왔는지 확인하려 했다. 그러나 수의 범위가 매우 크고 무엇보다 위에 O(1) // 추가적인 선형 배열 없이 구현하라고 나와있었다. 비상이다.감이 잡히지 않아 AI에게 힌트를 달라고 했다.AI 왈 입력 배열 자체를 값의 존재 여부를 표현하는 구조로 쓰라고 한다. 즉 입력받은 배열을 순회하면서 계속해서 해당 원소를 해당 원소의 인덱스로 보내버리면 된다.배열 순회가 끝나면 다시 배열을 순회하면서 i자..