IT's Time

1. 문제 링크 : https://www.acmicpc.net/problem/156512. 문제 티어 : 실버33. 문제 유형: 백트래킹4. 문제 풀이1) N과 M(1) , N과 M(2)에 이은 백트래킹으로 길이가 M인 수열을 구하는 문제 시리즈이다.2) 같은 수를 여러 번 골라도 된다는 조건이 있기에 start 혹은 i+1 등으로 인덱스를 부여할 필요가 없으며3) 하나의 계산을 끝내고 그 다음 계산을 할 때 이전 선택과 관계 없이 n까지 모두 돌려도 된다는 뜻이다. 4) 3) 과 같이 할 시 console.log로 출력값을 찍는 부분에서 시간 초과가 이루어질 수 있으니 미리 새로운 배열에 문자열을 생성해서 한 번에 출력하여 백준의 시간 초과 문제를 해결하는 방법이다.5) 기존 (1)과 (2) 에서는 c..

1. 문제 : https://www.acmicpc.net/problem/74902. 문제 티어 : 골드 53. 문제 유형 : 백트래킹 , 구현4. 문제 풀이 1) 백트래킹을 이용한 모든 경우 탐색 - 숫자 1부터 N까지의 사이에 가능한 연산자(+ , - , " ") 를 삽입하여 모든 경우의 수를 만든다. - 연산자를 삽입할 때마다 다음 숫자를 추가해가며 재귀적으로 탐색한다. - 이 때 수식은 사전순으로 해야하기 때문에 "-"보다 "+" 먼저 작성해줘야한다. 2) 수식 계산 - 만들어진 수식의 공백은 숫자를 이어붙이는 역할을 한다. - 수식을 계산하여 값이 0인지 확인하는 과정 3) 결과 출력 - 문제 요구사항에 따라 사전순으로 출력해야함 5. 문제 코드const fs = require("fs");let ..

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) 만약 배정된 예산의 총합이 ..

문제 링크 : https://www.acmicpc.net/problem/19939문제 티어: 실버 4문제 유형: 그리디 알고리즘문제 풀이 : N개의 공을 K개의 바구니에 나눠 담아야 하지만 담기는 공의 갯수는 모두 다르게 해야하고 또한 차이는 최소여야 한다는 것이다. : 그리디 알고리즘으로 1개씩 공을 다 넣고  Max(공의 갯수) - Min(공의 갯수) 가 최소여야 한다는 것: 일단 1개씩 공을 다 줌 => 공 남으면 다시 첫 번째로 가서 주고 계속 반복 => 만약 공 다 줬는데 같은 수 있으면 넘어가고 없으면 Max - Min을 해준다.: 최소 필요한 공 갯수 => 1 + 2 + .... + k = k * (k+1) / 2 :  만약 공 부족해서 못 나눠주는 경우 console.log(-1);: 남은..