[백준] 9095: 1, 2, 3 더하기 - JS (DP)

목 차 문제 접근 방식 풀이 문제 접근 방식 규칙을 먼저 찾아보자. 1의 경우: 1 2의 경우: 2 3의 경우: 4 4의 경우: 7 5의 경우: 13 6의 경우: 24 4의 경우를 살펴보면 앞에 3개를 더한 값이다. 5의 경우도 직전 3개를 더한 값이다. 만약 저 숫자들이 dp 배열에 있다고 한다면, dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이 된다는 의미이다. 반복문의 조건식은 i

Algorithm 2023.10.19

[백준] 1717: 집합의 표현 - JS (Union-Find)

목 차 문제 접근 방식 answer 배열이 필요하다! 풀이 문제 접근 방식 이 문제는 Union-Find / Disjoint-Set문제이다. 이 문제에서는 parent 배열과 rank 배열(최적화), 그리고 *answer 배열(JS만 필요한 듯)이 필요하다. answer 배열이 필요한 이유는 접근 방식 챕터의 가장 마지막에 작성하도록 하겠다. 랭크 시스템을 적용하지 않은 Union-Find 알고리즘은 구현하기 쉬운데 Find와 Union 함수를 구현하면 된다. Find: 숫자를 받아오고 계속 타고 올라간다. 올라가면서 num과 parent[num]이 같지 않다면 가장 조상의 인덱스 번호로 바꿔준다. function find(num){ if(num !== parent[num]){ parent[num] = ..

Algorithm 2023.10.17

[자료구조] Union Find / Disjoint-Set 알고리즘 개념 및 최적화

목 차 Union-Find Algorithm 기본 개념 최적화 Union-Find Algorithm 기본적으로 Union-Find는 자료구조이다. 하지만 이 자료구조를 지원하는 Union과 Find는 알고리즘이다. 여러 노드가 서로 중복되지 않는 집합 여러 개로 나뉘어 있을 때, 각 집합을 대표하는 노드를 찾거나 두 집합을 합치는 연산을 하는 자료구조이다. 기본 개념 1. Union: 두 개의 원소가 포함된 집합을 하나로 합친다. 2. Find: 주어진 원소가 속한 집합의 대표 노드를 반환한다. 최적화 대표적인 최적화는 '경로압축' 인데, 바로 Find 연산을 수행할 때, 방문한 노드를 모두 그 집합의 대표 노드로 바꾸는 것이다. 여기에 'Rank' 시스템을 도입하면 시간 복잡도가 눈에 띄게 줄어드는데,..

Algorithm 2023.10.16

[백준] 1697: 숨바꼭질 - JS (그래프 탐색(DFS&BFS))

목 차 문제 접근 방식 풀이 문제 접근 방식 이번에는 BFS로 풀려고 한다. 구현 전에 설정한 조건은 다음과 같다. 방식: BFS (queue) 이동: -1, +1, *2 방문 체크: push 후 해당 요소를 1로 바꿈 범위: 100000 while문 조건: queue.length queue 에는 [item(이동), time]이 한 노드임 item과 K가 같다면 출력 후 반복문 종료 push 조건 - 1: item - 1 >= 0 && arr[item - 1] == 0 + 1: item + 1

Algorithm 2023.10.12

[Algorithm] 그래프 탐색 알고리즘(DFS, BFS)

목 차 DFS와 BFS 구현 방법 대표 문제 유형 DFS와 BFS DFS: 깊이 우선 탐색, 재귀 함수를 사용하여 구현하는 것이 일반적이다. 재귀를 타고타고 탈출 조건에 도달하고, 그 다음에 파라미터를 하나씩 바꿔 가면서 정답을 찾는 방식. BFS: 너비 우선 탐색, Queue나 LinkedList를 사용하는 것이 일반적이다. DFS와 BFS의 장단점 DFS 장점 현재 경로상의 노드만 기억하므로 적은 메모리를 사용한다. 재귀함수를 사용하여 구현이 BFS 보다 간편하며, 코드 검증이 쉽다. 단점 비효율적인 경로를 탐색하는 경우가 있다. 가장 먼저 찾은 경로가 최단 경로라는 보장이 없다. BFS 장점 시작노드에서 가장 가까운 노드부터 탐색하기 때문에 최단 경로를 보장한다. 단점 모든 노드를 큐에 저장하므로 ..

Algorithm 2023.10.12

[백준] 1463: 1로 만들기 - JS (DP)

목 차 문제 접근 방식 풀이 문제 접근 방식 알고리즘 문제를 풀 때, 1초에 CPU가 계산하는 양은대략적으로 10^6~ 10^8 정도이다. 이 문제에서 입력은 최대 10^6 이므로 시간 복잡도가 O(N)인 알고리즘으로 풀 수 있다는 얘기이다. 나는 이 꼼수?를 이용하여 풀어봤다. dp = [0, 0] 초기 설정을 해주고 for문으로 2부터 10^6 까지 다 dp 배열에 넣어버리는 것이다. for(let i = 2; i

Algorithm 2023.10.05

[백준] 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

[백준] 4673: 셀프 넘버 - JS (브루트포스)

목 차 문제 접근 방식 풀이 문제 n = 100) { const devided = devide(i); selfNums[(i + devided[0] + devided[1] + devided[2]) - 1] = true; } else if (i >= 10) { const devided = devide(i); selfNums[(i + devided[0] + devided[1]) - 1] = true; } else if (i

Algorithm 2023.08.05

[백준] 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