코딩 테스트 (BOJ)(38)
-
[백준 / BOJ] 1929번 소수 구하기 (Javascript / Node js)
https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 해석 이번 문제는 입력받은 M과 N 사이의 모든 소수들을 출력해주면 되는 아주 단순한 문제이다. 소수를 구하면 되니 에라토스테네스의 체를 이용하면 매우 효율적으로 구할 수 있다. 에라토스테네스의 체에 관해서는 이전 [소수 찾기] 문제에서 다룬적이 있다. 그런데 바로 지난 문제인 [다음 소수]를 풀며 깨달은 점은 내가 소수 찾기 문제에서 사용했던 에라토스테네스의 체는 반쪽짜리도 안되는 알고리즘이었다는 것이다. 그 이유는 에라..
2023.10.14 -
[백준 / BOJ] 4134번 다음 소수 (Javascript / Node js)
https://www.acmicpc.net/problem/4134 4134번: 다음 소수 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. www.acmicpc.net 문제 해석 문제 자체는 간단하고 명확하다, 테스트 케이스마다 입력받은 n보다 큰 소수 중 가장 작은 소수를 출력하면 정답이다. 즉, n 바로 다음에 나올 소수가 정답이 되겠다. 이번에도 마찬가지로 정수 n의 범위가 1억을 가볍게 넘기는걸 보니 단순한 for문으로는 반드시 시간 초과가 걸릴 것이다. 1. 일단 단순하게 시간 초과를 고려하지 않고 n 바로 다음에 나올 소수를 찾기 위해선 for문과 n++ 을 통해 n에서 1씩 증가시키고 증가된 값을 i라고 가정했을 때 i가 본인과 1..
2023.10.13 -
[백준 / BOJ] 2485번 가로수 (Javascript / Node js)
https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 문제 해석 첫 번째 입력으로 예시를 들어보자 나무는 현재 1 3 7 13 의 위치에 존재한다. 현재 존재하는 나무들 사이에 나무들을 추가하여 모든 나무들의 간격이 일정하게 만들어 주는게 문제다. 위 예시에서 모든 나무들의 간격이 일정해지기 위해서는 위와 같이 5, 9, 11에 나무들을 추가적으로 심어주면 모든 나무들의 간격이 [2]로 동일해진다. 여기서 문제는 어떻게 [2]라는 숫자를 도출..
2023.10.12 -
[백준/BOJ] 1735번 분수 합 (Node js / Javascript)
https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 문제 해석 각각 A / B로 이루어진 두 개의 분수가 "A B" 와 같은 형식으로 두 줄에 나뉘어서 입력 받는다. 그리고 입력받은 두 분수의 합을 기약 분수로 나타내는 것이 문제이다. 즉, 두 분수의 합을 A3 / B3 이라 할 때, A3와 B3의 공약수가 없을때까지 같은 수로 나눠주면 된다. 1. 두 분수를 합하려면 분모를 같은 수로 통일시켜줘야 한다. 단순히 두 분모를 서로 곱해줘도 되지만 나는 지난 문제에서 배운 최대공배수를 복습하는 겸 사용하..
2023.10.10 -
[백준/BOJ] 1934번 최소공배수 (Javascript / Node js)
https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 문제 해석 문제 자체는 명확하고 간단하다. 테스트 케이스 각각의 두 수(A, B)의 최소 공배수를 출력해주면 된다. 부끄럽지만 나는 이 문제를 풀기전까지 유클리드 호제법에 대해 아는 것이 없었다. 최대공약수로 최소공배수를 구할 수 있다는 사실조차 어렴풋이 중고등학교 시절에 배운 기억이 있지만 기억이 났던건 문제를 다 풀고 난 후였다. 그래서 내가 생각해낸 풀이 방식은,, 입력 ..
2023.10.10 -
[백준/BOJ] 11478번 서로 다른 부분 문자열의 개수 (Javascript / Node js)
https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 문제 해석 입력 받은 문자열에서 모든 경우의 부분집합들을 추출해낸 후, 중복된 값들만 제거해주면 되는 간단한 문제이다. Javascript에서는 Set객체를 사용해서 중복을 제거할 수 있기 때문에 입력 받은 문자열에서 모든 경우의 부분집합들을 추출해 내는 알고리즘만 구현해 내면 된다. 나는 2중 for문을 사용해서 첫번째 for문의 i 값으로 잘라낼 문자열의 길이를 정의했고, 두번째 for문의 j 값으로 잘라낼 문자열의 시작부분을 정의했다. 그러니 자연스럽게 잘라낼..
2023.10.10