IT's Time

1. Object 생성자 함수: new 연산자와 함께 Object 생성자 함수를 호출하면 빈 객체를 생성하여 반환됨.const person = new Object();// 프로퍼티 추가person.name = "Lee"; : 생성자 함수란 new 연산자와 함께 호출하여 객체(인스턴스)를 생성하는 함수를 말함.: 생성자 함수에 의해 생성된 객체를 인스턴스라 한다.: :객체 생성 방법은 객체 리터럴을 사용하는 것이 더 간편한다. 2. 생성자 함수1) 객체 리터럴에 의한 객체 생성 방식의 문제점: 직관적이고 간편하나 동일한 프로퍼티를 갖는 객체를 여러 개 생성해야 하는 경우 매번 같은 프로퍼티를 기술해야 하기 때문에 비효율적임const circle1 = { radius: 5, getDiameter() ..

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/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..