문제(원문)문제(번역)정수 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로 바꾸어주어야 한다.삭제할..