IT's Time

문제 링크 : 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의 방..

문제 링크 : https://www.acmicpc.net/problem/2839문제 유형 : 그리디 알고리즘문제 티어 : 실버4문제 풀이 : 5키로랑 3키로짜리 봉지가 있고 이 두 개를 통해 최대한 적은 갯수의 봉지를 가져가야 한다.  => 5키로로 담을 수 있는 만큼 담고 그 다음 3키로로 채우면 될 것 같은 문제다. 시간 복잡도 : O(N)const fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().split("\n");let n = Number(input[0]);let count = 0;while(true) { if(n%5===0){ count -= n/5; break; } n-=..

문제 링크 : https://www.acmicpc.net/problem/1541문제 유형 : 그리디 알고리즘문제 티어: 실버2 문제 풀이1) 최솟값을 찾아야 하기 때문에 일단 "-" 기준으로 수식을 나눈다. 2) ( ) - ( ) 기준으로 나왔을 때 무조건 뒷 괄호를 크게 만들어놓고 앞 괄호에서 뒷 괄호를 빼는게 제일 최솟값일 것이다. 3) 만약 - 기준으로 나눴을 때 +로 묶인 부분이 있으면 더해주어야 한다.4) 첫 번째 괄호는 그냥 더해주고 두 번째 괄호부터는 다 빼주는게 제일 최솟값일 것이다(이미 -로 구분 지었고 첫 번째는 숫자로 시작 즉, + 이기 때문에 더해줘야 함)const fs = require("fs");let input = fs.readFileSync("/dev/stdin").toStr..

문제 : https://www.acmicpc.net/problem/11004문제 등급 : 실버 5 문제 풀이 :  두  수를 받아서 이를 정렬 한 다음 주어진 K를  index로 하는 수(K-1)를 console.log로 찍어주면 된다.const fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().split("\n");let [N,K] = input[0].split(" ").map(Number);let arr = input[1].split(" ").map(Number);for(let i=1;ia-b);console.log(arr[k-1]); 배운 것띄어쓰기 기준으로 한 줄에 여러 개 받는 것 : input[0].split(" "..