IT's Time

1. 문제 링크 : https://www.acmicpc.net/problem/66032. 문제 티어: 실버23. 문제 유형 : 백트래킹 , 재귀4. 문제 풀이 :  백트래킹 종류로, 단계적으로 문제를 푼다.1) S, K를 입력 받는다. 문제에서 따로 이야기 없이 한 줄에서 입력 받게 했으므로 input에서 첫 번째 요소는 K 나머지는 배열로 입력 받는다.2) 배열과 선택된 숫자(=K)개의 조합을 짜주는 재귀함수를 선언한다. 재귀함수인 이유는 조합은 중복이 허락되지 않기 때문에 기존에 만든 부분은 고정시켜야 하고 나머지 부분만으로 조합을 만들어야 중복이 허용되지 않는다.예를 들어, [1, 2, 3, 4]에서 2개의 원소를 선택하는 경우:가능한 조합: [1, 2], [1, 3], [1, 4], [2, 3],..

1. 문제 링크 : https://www.acmicpc.net/problem/109712. 문제 유형 : 백트래킹3. 문제 티어 : 실버24. 문제 풀이  : 전형적인 모든 경우의 수를 완전 탐색하는 백트래킹 문제 : 모든 도시를 방문 후 다시 돌아와서 그 최소 경로를 구해야  함 : 이 과정에서 방문 처리 유무를 남겨놓아서 다시 방문하지 않도록 하여 연산 속도 빠르게 처리 : 도시 i부터 j까지 가서 그 비용을 현재 측정된 비용에 더한 후 기존에 있던 최솟값과 지속적으로 비교해서 최솟값을 갱신하는 재귀함수 호출하면서 최적의 값 찾음 5. 문제 코드 // 1. 값 입력 받기const fs = require("fs");let input = fs.readFileSync("/dev/stdin").toStrin..

1. 문제 링크 : https://www.acmicpc.net/problem/156522. 문제 티어 : 실버33. 문제 유형 : 백트래킹4. 문제 풀이1) 내림차순을 유지해야 하기 때문에 start 지점을 찾아서 인덱스를 유지 시켜줘야 한다.2) 그 외는 N과 M(3)과 비슷하다.3) 중복 조합을 찾아서 넣어주는 문제다. 5. 문제 코드let result = []; // 결과를 저장할 배열function recursive(current, start, n, m) { if (current.length === m) { result.push(current.join(" ")); // 길이가 M인 수열을 결과에 추가 return; } for (let i = start; i

1. 문제 : https://www.acmicpc.net/problem/109742. 문제 유형 : 백트래킹3. 문제 티어 : 실버34. 문제 풀이 1) 백트래킹으로 푸는 전형적인 문제2) N만큼 반복문 돌리면서 백트래킹 재귀 함수 호출 후 3) 이전 단계로 돌아가기 위해 visited와 current.pop() 해준다. 5. 문제 코드const fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().split("\n");let N = Number(input[0]);let visited = new Array(N+1).fill(false);let arr = [];// 재귀함수function recursive(current, visit..

1. 문제 : https://www.acmicpc.net/problem/156492. 문제 유형 : 백트래킹 알고리즘3. 문제 티어 : 실버3 4. 개념 학습1) 백트래킹이란?백트래킹(backtracking)은 모든 경우의 수를 탐색하면서, 조건에 맞지 않는 경우에는 중간에 탐색을 포기하고 돌아가는 방법. 즉, 안되는 길은 가지 않고, 될 가능성이 있는 길만 계속 탐색하는 알고리즘이다. 보통 재귀 호출을 사용하며, 탐색의 효율성을 높이기 위해 조건에 맞지 않는 경우를 빠르게 배제하는 것이 핵심이다. 2) 백트래킹의 동작 원리 1. 결정 트리 탐색 :    - 가능한 선택지를 하나씩 시도하며 트리 형태로 탐색한다. 2. 조건 만족 여부 확인:     - 특정 조건에 부합하지 않으면, 더 깊이 탐색하지 않고..

1. 문제 : https://www.acmicpc.net/problem/183532. 문제 유형 : Dynamic Programming3. 문제 티어 : 실버 24. 문제 풀이  - 병사의 최대 수를 물어보기 때문에 LIS 알고리즘을 고려해야 한다. ( 최대 수 , 최장 길이 , 가장 많은 .. 등이 들어갈 때 LIS 알고리즘을 고려해보자) - LIS 알고리즘을 고려하기 위해 DP와 이진탐색 두 가지 방법이 있다. 여기서 나는 이진탐색 방법을 선택했다.(복잡한 대신 더 속도가 빠르고 효율적이기 때문이다.)* LIS 알고리즘이란?최장 증가 부분 수열(LIS)라고 하며 주어진 수열에서 일부 숫자들을 선택하여 만든 증가하는 부분 수열 중 가장 길이가 긴 수열을 찾는 방법이다.ex) 수열 : [10, 20, 1..

1. 문제 : https://www.acmicpc.net/problem/108162. 문제 유형 : 이진 탐색, 해시맵3. 문제 티어: 실버44. 문제 풀이처음 생각한 문제 풀이 방법은 배열을 처음부터 끝까지 순회하면서 같은 값이 있을 시 카운트를 추가하고 그 추가한 것을 새로운 결괏값 배열에 담는 과정을 반복하는 것이었다. 따라서 처음 코드는 아래와 같았다.const fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().split("\n");let N = Number(input[0]);let first_arr = input[1].split(" ").map(Number);let M = Number(input[2]);let seco..

1. 문제 : 랜선 자르기2. 문제 티어: 실버23. 문제 유형 : 이진 탐색4. 문제 풀이 방법=> 나무 자르기와 동일한 방식으로 이진 탐색으로 최적의 갯수를 찾는 것이 핵심이다.1) 필요한 변수 값 입력 받음2) 랜선 잘랐을 때 값을 얻을 수 있는 지 판단하는 함수 작성3) 이진 탐색으로 최적의 갯수를 카운트하는 함수 작성4) 결과 출력 5. 코드 1) 필요한 변수 값 입력 받음// 1. 필요한 값 입력 받음const fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().split("\n");let [N,M] = input[0].split(" ").map(Number);let lengths = [];for(let i=1;i 2..

1. 문제 : https://www.acmicpc.net/problem/28052. 문제 유형 : 이진 탐색3. 문제 티어 : 실버24. 문제 해결 방법=> 이진 탐색 문제이다. 특정 높이까지 오기 전까지 계속 반복해야 하는 문제이기 때문에 로직을 아래와 같이 잡았다.1) 필요한 변수들 입력 받음 (N, M , arr) * N = 나무 수 ,  M = 나무 길이 , arr = 나무 높이가 들어가 있는 배열 2) 총 나무 길이를 구할 수 있는 함수 작성3) 이진 탐색으로 최적의 절단기 높이를 찾는 함수 작성 4) console.log로 출력 5. 코드1) 필요한 변수들 입력 받음// 입력값 받는 부분const fs = require("fs");let input = fs.readFileSync("/dev/s..

문제 링크 : https://www.acmicpc.net/problem/2512문제 티어 : 실버2문제 유형 : 이진 탐색문제 풀이 한정된 값을 최대한의 예산으로 나누어 주어야 한다.1) 적절한 상한금액을 찾는 것이 목표2) 배정을 다하고도 남는 예산이 0이상이어야함3) 남은 예산이 0에 가까워야 함 이진 탐색 방법으로 생각하면 양 쪽 끝을 기준으로 최댓값과 최솟값을 잡고 그 사이를 점점 간격을 좁혀 나가면서 예산의 최댓값을 찾아주는 것이 핵심이다. 예를 들면 아래와 같다. 1) 최솟값 = 0 , 최댓값 = Math.max()  , mid = (최솟값 + 최댓값 ) / 22) 만약 배정된 예산의 총합이 mid 보다 크면 상한액을 줄여야 하므로 mid를 -1 해서 점점 줄임3) 만약 배정된 예산의 총합이 ..