[백준] 2748: 피보나치 수 2 - JS (재귀, DP)

목 차 문제 접근 방식 풀이 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 접근 방식 이 문제는 대표적인 DP 문제이다. 그냥 재귀함수를 통해서 문제를 푼다면 시간이 초과되어 실패할 것이다. >> DP란? 백준에서 입력은 첫째 줄에 n이 주어진다. n은 90보다 작거..

Algorithm 2023.07.30

[Algorithm] 다이나믹 프로그래밍(DP) 개념 및 적용

목 차 개요 DP를 사용하는 이유 DP 적용하기 DP 체감하기 개요 Dynamic Programmin(DP) 또는 동적 프로그래밍이라고도 하는데, DP는 복잡한 문제를 간단한 여러개의 문제로 나눠서 푸는 방식이다. DP는 작은 문제가 반복하여 발생하고 이에 대한 해답을 저장해두고 재사용 하는 특징이 있다. 이렇게 함으로써 계산 속도를 크게 향상시킬 수 있다. DP를 사용하는 이유 DP는 주로 다음 두 가지 속성을 가진 문제에 적용된다. 1. 중복되는 문제 해결: 대표적으로 피보나치 수열의 예시가 있는데, 이 피보나치 수열을 재귀함수로 풀어본다면 코드는 아래 코드와 비슷할 것이다. Fn 을 계산하기 위해서 F(n-1) 과 F(n-2)을 계산해야 하지만, 이들 역시 F(n-3)과 F(n-4)를 필요로 한다...

Algorithm 2023.07.29

[백준] 별찍기 1-8 문제풀이 - JS

목 차 별찍기 1 별찍기 2 별찍기 3 별찍기 4 별찍기 5 별찍기 6 별찍기 7 별찍기 8 별찍기 1 Goal N번 째 줄에는 N개의 별이 찍혀야 한다. * ** *** **** ***** Design 그저 반복문을 통해 별이 추가되는 식으로 설계를 하고 구현을 해보았다. const input = 5; let result = ''; for(let i = 0; i < input ; i++) { result += '*'; console.log(result); }; 별찍기 2 Goal 별찍기 1과 같이 N 번째 줄에는 N개의 별을 찍는다. 하지만 이번엔 오른쪽 정렬을 한다. * ** *** **** ***** Design 바깥 for문은 줄을 바꾸는 반복문, 안쪽 for문에서는 별을 찍는 역할을 하는데, '..

Algorithm 2023.07.13

[알고리즘] 버블정렬 (Bubble Sort)

목 차 버블정렬이란? 버블정렬 예시 버블정렬 설계 버블정렬 후기 버블정렬이란? 버블정렬 알고리즘은 인접한 두 개의 요소를 비교하고, 필요하다면 두 요소의 위치를 바꾸는 과정을 반복하여 전체 배열을 정렬하는 방식이다. 버블정렬 예시 숫자 5, 3, 8, 4, 2 가 요소로 들어있는 배열이 존재한다고 할 때. 이 배열을 버블정렬 알고리즘으로 정렬을 해보려고 한다. 1. 첫 번째 요소와 두 번째 요소를 비교한다. 만약 왼쪽의 요소가 더 크다면 두 요소의 자리를 바꾼다. 2. 두 번째 소요와 세 번째 요소를 비교한다. 만약 왼쪽의 요소가 더 크다면 두 요소의 자리를 바꾼다. 3. 세 번째 요소와 네 번째 요소를 비교한다. 4. 네 번째 요소와 다섯 번째 요소를 비교한다. 이렇게 여러번 반복을 하면 정렬이 된다...

Algorithm 2023.07.12