IT's Time

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);: 남은..

문제 : https://www.acmicpc.net/problem/9009티어 : 실버 1 문제 유형 : 그리디 알고리즘 (탐욕법)문제 풀이 피보나치 수열이란? f(k) = f(k-1) + f(k-2)로 정의 될 수 있는 수열을 일컫는다. 즉, 예를 들어 정수 100을 생각해보면 여러 경우가 있을텐데 예시를 들면 아래와 같다1. f(4) + f(6) + f(11) = 3 + 8 + 89 = 1002. f(1) + f(3) + f(6) + f(11) = 1 + 2 + 8 + 89 = 100이 문제는 위와 같은 서로 다른 피보나치의 갯수를 구하는 것이다. 문제 접근 방법 = 문제 유형처럼 그리디 알고리즘 , 즉 탐욕법을 사용해서 앞에서 부터 가장 최선의 선택으로 채워 나가는 방식을 선택한다.1. 피보나치 수..

문제 링크 : https://www.acmicpc.net/problem/1931문제 티어 : 실버1 문제 유형: 그리디 알고리즘문제 풀이: 회의실을 최대한 많이 쓰기 위해선 시간이 겹치지 않아야 한다. 즉 이전 회의 종료 시간보다 다음 회의 시작 시간이 크면 된다. 이를 나타내면 아래와 같다. ex) 1 - 4 / 5 - 7 / 8 - 10 (O)       1 - 4 / 2 - 5 / 6 - 10 (X)  따라서 1 , 4 이 부분을 좌표로 만들어주면 어떨까 생각했다. 즉, (1,4) 라고 설정하고 (x1,y1) 이라 생각하기로 했다.위 경우를 일반화 시키면 아래와 같다. (x1,y1) = (1,4) // 첫 번째 입력 값if x2가 y1보다 크면   count++ ; // 회의할 수 있는 회의 갯수 ..

문제 링크 : https://www.acmicpc.net/problem/13305문제 유형 : 그리디 알고리즘문제 티어 : 실버3문제 풀이 : 주유소의 기름 가격과 도로의 길이가 나와 있다. 최소 비용을 구하려면 당연히 가격이 싼 주유소에서 제일 많이 넣어야 한다. 많이 넣어야 한다는 것은 다음 거리로 갈 때까지 최대한 많이 넣어야 한다는 점이다. 즉, 다음 도시 주유소 가격이 지금 주유소보다 싸면 다음 주유소 가격으로 설정해주고 그렇지 않다면 지금 최저가의 주유소 가격을 기본 값으로 계속 유지해줘야 한다. 그 후 거리를 곱해주면 최소 비용이 나올 것이다. 1) 첫 번째 주유소의 가격을 minValue로 설정해줌.2) 그 후 도시들을 순회하면서 기름 가격이 비싼 지 현재 minValue와 다음 도시들의 ..

문제 링크 : https://www.acmicpc.net/problem/1946문제 유형 : 그리디 알고리즘문제 티어 : 실버1 문제 풀이 : 적어도 하나는 다른 지원자보다 떨어지면 안된다는 조건이 있기 때문에 1차 서류 심사와 2차 면접 시험 중 하나를 오름차순으로 정렬 후 나머지 하나를 비교해줘야 한다.    예를 들어 1차 서류 심사 점수를 오름차순으로 정렬한다고 치자. 그러면 가장 첫 번째 즉, 맨 위에 있는 사람은 1차 서류 점수는 1등일 것이다. 이 때 최대 인원을 뽑으려면 그 아래부터는 무조건 앞 사람보다는 순위가 더 높아야 한다. 1차 서류가 1등인 사람은 무조건 뽑힐 것이고 그 아래부터 윗 사람보다 2차 면접 순위가 높으면 뽑힐 수 있기 때문에 최대한 이 구조를 만들어줘야 한다는 것이다...

문제 링크 :https://www.acmicpc.net/problem/1789문제 유형 : 그리디 알고리즘문제 풀이 : 서로 다른 N개의 자연수의 합으로 S를 만들어야 한다는 문제고 그리디 알고리즘의 특성을 살려서 풀었다.가장 핵심 아이디어는 1부터 쭉 더했을 때 어느 시점에 S를 넘어갈 것이다. 그 때를 체크해주면 된다. 1) 1부터 계속 더해준다. ex) 1+2+3+4....2) 그러다 S를 초과하는 경우가 발생할 때를 확인한다. ex) S = 15 , 1+2+3+4+5 (O) / 1+2+3+4+5+6 (X) 3) 한 번 씩 더 할 때마다 count를 세주고 만약 2)와 같이 초과하는 경우가 발생 했을 때 이미 count를 한 번 한 상황이니 1을 빼주고 그 count를 출력한다. ex) 6까지 갔을..

문제 링크 : https://www.acmicpc.net/problem/16953문제 유형 : 그리디 알고리즘문제 풀이 : 핵심 아이디어는 반대로 생각하는 것이다. 즉, A->B가 아닌 B->A로 간다고 생각하자.                1) 마지막에서 2로 나누었을 때 나누어 떨어지는 경우엔 나누기 2를 해줌               2) 일의 자릿수가 1인 경우는 1을 제거풀이 코드 const fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().split("\n");let [a,b] = input[0].split(" ").map(Number);let count = 0;while(a 2) GPTs 해설 GPT는 BFS의 방..