[백준] 1644: 소수의 연속합 - JS(투포인터)

목 차 문제 접근 방식 풀이 문제 단, 20은 0인데, 20은 소수가 아니기 때문에 0이 나와야 한다. 접근 방식 2~N까지의 소수를 모두 구해야 하기 때문에 이전에 '소수 구하기'에서 구현했던 코드를 가져와 M부터 N 이였던 것을 처음부터 N 까지로 변경했다. 그리고 이 문제를 읽으면서 두 포인터 기법을 사용해야 겠다고 생각했다. 먼저 소수를 배열에 넣는다. 그리고 start와 end가 있는데 먼저 가장 첫 번째 요소를 가리키게 해 준다. 만약 N과 같거나 작다면 end를 하나 올려준다. start와 end가 1 이상 차이 나게 되면 그 요소들을 더해준다. 그리고 똑같이 N과 같거나 작다면 end를 하나 올려주고, N 보다 크다면 start를 하나 올려주어 결과적으로 맨 앞에 있는 요소를 빼는 역할을 ..

Algorithm 2023.09.30

[백준] 1929: 소수 구하기 - JS (에라토스테네스의 체)

목 차 문제 접근 방식 풀이 문제 접근 방식 에라토스테네스의 체 알고리즘은 큰 범위 내에 있는 모든 소수를 빠르게 찾을 때 효율적이다. 기본 원리는 다음과 같다. - 2부터 원하는 숫자 N 까지의 모든 숫자를 나열한다. - 2는 소수이므로, 2의 배수를 모두 제거한다. - 다음 남아있는 숫자인 3의 배수를 모두 제거한다. - 다음 남아있는 숫자인 5의 배수를 모두 제거한다. - 다음 남아있는 숫자인 7의 배수를 모두 제거한다. - 다음 남아있는 숫자인 ... ... 이런 방식으로 N 까지 한다. 남아 있는 숫자들이 2 부터 N 까지의 소수이다. 그리고 다른 방식은 숫자 N을 2 부터 루트N 까지 나누어 보는 것이다. 이 두 방식의 차이점은 메모리 제한, 시간 복잡도 이다. 에라토스테네스의 체 알고리즘은 ..

Algorithm 2023.09.30

[백준] 1654: 랜선 자르기 - JS (이분 탐색)

목 차 문제 접근 방식 풀이 문제 예시로 const 랜선: number[] = [802, 743, 457, 539] 이렇게 랜선 4개가 있다면 여기서 랜선 11개를 가져가야 할 때 최대로 자를 수 있는 길이를 구하라는 것이다. 접근 방식 일단 나무 자르기와 비슷한 방식으로 접근하기로 했다. 아래는 코드 설계 전 내가 설계할 코드의 큰 틀을 설계한 것들이다. 최댓값 = max 최솟값 = min 반 값 = half for문: 전체적인 계산 처리를 하는 코드 result = for문에서 계산된 결과가 N과 같다면 result 변수에 저장한다. 단, result 변수의 초기값은 0으로 시작하고, 최대의 값을 구해야 하므로 result의 값 보다 큰 경우 갱신하도록 한다. 풀이 tamp >= N 일 때 resul..

Algorithm 2023.09.05

[백준] 2805: 나무 자르기 - JS (이분 탐색)

목 차 문제 접근 방식 풀이 문제 나무의 수 N과 필요한 나무의 길이 M이 주어진다. 두 번째 줄에는 나무의 높이가 주어진다. ex) [20, 15, 10, 17] 접근 방식 아직 퀵 정렬을 배우지 않은 초보개발자로, 미비한 점이 많을 것이다. 나중에 되돌아보며 더 나은 코드로 수정할 예정이다. 먼저 나는 재귀 함수를 사용하기 보다는 그냥 변수에 할당해서 사용하기로 했다. (메모리 문제) 전체적인 풀이 방법은 단순하다. 값을 할당할 변수를 선언하고, 최대한 반복을 하지않기 위해 가장 큰 값을 highest 변수에 할당하고 계속 업데이트 해주려고 한다. 그리고 H 값은 커터의 높이이므로 퀵 서치 방식으로 한다. 디버깅을 하다가 보니 저 종료 조건에서 for문이 제대로 작동하지 않는 현상을 발견했다. 그래서..

Algorithm 2023.09.03

[백준] 1920: 수 찾기 - JS (이분 탐색)

목 차 문제 접근 방식 풀이 문제 N개의 정수 내에서 제공된 M개의 정수들이 존재하는지 확인하세요. 접근 방식 학습을 목적으로 하여 재귀 함수 방식을 선택하였다. 그리고 해당 문제는 정렬도 함께 사용하기 때문에 정렬을 배우지 않았다면 먼저 정렬이 되어있는 배열을 생성하여 시도해 본다. 먼저는 퀵 정렬을 사용하여 정렬을 하고, 탐색을 하는 것이다. 나는 아직 퀵정렬을 배우기 전 이기에 미리 정렬된 배열로 해보았다. 이 문제는 퀵서치 느낌으로 해결하려고 한다. 풀이 quickSearch 함수는 arr와 target을 인자로 받고 boolean 형태의 데이터를 반환한다. 먼저 탈출조건은 arr.length가 0일 때는 데이터를 찾지 못한것이기에 false를 반환한다. pivot을 설정해주는데 Math.flo..

Algorithm 2023.09.02