목록분류 전체보기 (316)

https://www.acmicpc.net/problem/17175 문제는 피보나치 수열을 응용하여, input이 들어왔을 때 피보나치 수열이 몇 번 호출되는지를 묻는다. 먼저 문제에서 제시된 함수를 살펴봐야 하는데, fibonacci(n)이 호출되고 fibonacci(n-1)과 fibonacci(n-2)이 호출됨을 확인할 수 있다. (이때 n이 2 이하인 경우는 추가 호출이 없음을 인지해야 한다.) 즉 예를 들면 다음과 같다. // input === 2 fi(2) fi(1) fi(0) // => 총 3번 호출 // input === 3 fi(3) fi(2) fi(1) fi(1) fi(0) // 이때 fi(1)와 fi(0)은 fi(2)에서 일어나는 호출 // => 총 5번 // input === 4 fi..

https://www.acmicpc.net/problem/13909 해당 문제에는 아래와 같이 접근했다. 최대 입력값이 21억이기 때문에, 반복문으로는 해결할 수는 없으므로 나름의 규칙성이 있을 것이라 판단했다. 따라서 먼저 문제가 요구하는대로 시뮬레이션을 할 수 있는 코드를 먼저 작성해서 적용해보았다. // 시뮬레이션 코드 function solution(data) { const arr = Array.from({length : +data+1}, (_,i)=> [false,i]) for(let i = 1 ; i < +data+1 ; i ++) { for(let j = 1 ; j < +data+1 ; j ++) { if(j % i === 0) { arr[j][0] = !arr[j][0] } } } cons..

https://school.programmers.co.kr/learn/courses/30/lessons/77885 생각한 풀이과정은 다음과 같다. numbers 의 요소가 짝수인 경우, 2진수로 변환했을 때 마지막 비트는 무조건 0이다. '4'를 예로 들면, 4의 이진수가 '1000' 일 때, 마지막 비트 0을 1로 수정하면 1001(5)가 되므로 비트가 1~2개 다른 수 중 가장 작은 수가 5임을 확인할 수 있다. 따라서 짝수일 경우는 n이 주어질 때 n+1. 하지만 numbers의 요소가 홀수인 경우는 직접 구해야 한다. 만약 '7'이 주어질 경우의 7의 이진수는 111인데, 조건이 이보다는 커야 하므로 비트 자릿수는 최소 4자릿수이어야 한다. 때문에, 홀수 n이 주어진 경우는 7을 이진법으로 바꾼 ..

https://www.acmicpc.net/problem/5671 문제는 범위가 주어질 때, '중복되어 사용되지 않는 수'가 몇 개인지 구하는 문제다. 테스트 케이스가 여럿이고 범위는 1 ~ 5000으로 작지 않은 값이기 때문에, 해쉬 테이블을 구현하여 테스트 케이스가 테이블을 활용하는 방식으로 연산 자체를 줄였다. 이때 테이블에서의 table[n]은 'n 이하의 중복되지 않는 수의 갯수'를 갖게 했는데 이 과정은 다이나믹 프로그래밍으로 메모리라이징된 이전 값을 참조하여 테이블에 값을 추가하도록 했다. 소스 코드 const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")..

https://www.acmicpc.net/problem/19947 문제는 초기 금액과 투자 기간과 1 / 3 / 5년의 기한마다 얻을 수 있는 이윤이 주어질 때, 주어진 투자 기간동안 최대로 얻을 수 있는 이윤을 구하는 문제다. 각 년차마다 얻을 수 있는 최대 이익을 기록하고, 이를 활용하여 다음 연산에 활용할 수 있도록 다이나믹 프로그래밍(DP) 알고리즘 기법을 활용하여 문제를 해결하였다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim() function solution(data) { const [h, y] = data.sp..

https://school.programmers.co.kr/learn/courses/30/lessons/42839 이 문제도 어제 포스팅한 문제와 같은 백트래킹 로직으로 풀이했다. 2023.10.04 - [개발/algorithm] - 프로그래머스 - Lv.2 모음사전(백트래킹) JS 어제 문제풀이와 다른 점이 있다면, 이 문제 풀이는 중복되는 연산을 피하기 위해 노력했다는 정도. (이전 '모음 사전' 문제는 중복을 고려할 필요가 없었음) 문제 풀이 로직은 다음과 같다. 먼저 주어진 수를 쪼개어 배열로 만든 뒤, 해당 배열을 백트래킹 로직을 사용하여 만들 수 있는 모든 경우를 만들도록 했다. 이때 연산을 효율적으로 하기 위해 visited 배열 / table 객체를 선언했는데, visited 배열은 주어진..

https://school.programmers.co.kr/learn/courses/30/lessons/84512 해당 문제는 모음 A,E,I,O,U 를 조합하여 1~5 길이의 단어를 만들어 각각에 순서를 붙이고, 특정 문자열을 제시할 때 해당 문자열이 몇 번째 위치하는가에 대한 문제다. 먼저 A,E,I,O,U 를 조합하여 만들 수 있는 1~5가지의 문자열의 갯수는 3905(5^5 + 5^4 + 5^3 + 5^2 + 5^1)이기 때문에, 완전 탐색을 수행해도 높은 시간 복잡도가 우려되지는 않았다. 허나 이미 답에 맞는 문자열을 찾았음에도, 구태여 모든 탐색을 진행하는 것은 불필요하기에 내가 만든 문자열과 문제에서 제시된 문자열이 같다면 중지되도록 구현했다. 소스 코드 function solution(wo..

https://www.acmicpc.net/problem/1009 해당 문제는 백준에서 제시하는 난이도에 비해, 정답률이 낮은 문제라 포스팅하기로 했다. 문제는 컴퓨터 10대가 순차적으로 데이터를 처리한다고 하고 a^b 의 데이터가 주어졌다고 한다면, 마지막 데이터를 처리할 컴퓨터가 무엇인지 묻는다. 즉, a^b의 1의 자리 수를 묻는 문제로, 6^2 라는 데이터가 주어졌다면, 6 (36의 1의 자리 수)를 출력하면 된다. 하지만, 지수인 b의 최댓값이 100만이기 때문에 전체 수를 구한 뒤 1의 자리를 파악하는 것은 시간초과가 우려되고, 단순히 a의 1의 자리가 제곱될 때 어떤 규칙성을 가지고 있는지 파악하면 메모리와 시간을 아끼면서 풀이가 가능하다. 예를 들어, a가 각각 2 | 12 가 주어졌다고 ..