프론트엔드 개발자의 기록 공간

백준 그리디 알고리즘 1202번_보석 도둑 난이도 : 골드IV 해결못한 문제 : 시간 초과 or 메모리 초과 문제 설명 입출력 예제 입력2 4 4 1 100 2 200 13 300 10 500 10 10 10 14 => 답 : 1100 문제 풀이 : 최대한 비싼 보석을 챙기는 것이 문제 핵심이다. 그러기 위해서는 제일 비싼 보석을 순차적으로 보석의 무게와 비슷한 가방을 찾아 넣어줘야한다. 만약 1kg짜리 보석을 10kg짜리 가방에 넣으면 비효율적이기 때문에 최대한 비슷한 가방을 찾아서 넣어야한다. 정리하면 다음과 같다. 1. 보석 가격을 기준으로 정렬을 해준다. 2. 가방은 오름차순 정렬을 시행해준다. 3. 가격이 높은 보석을 차례대로 보석 무게와 비슷한 가방을 찾아서 넣어준다(보석 가격 누적계산) *우..

백준 그리디 알고리즘 1715번_카드 정렬하기 난이도 : 골드IV 문제 설명 추가 입출력예시 예제 입력 2 => 5 20 20 20 10 10 예제 출력2 => 180 문제 풀이 : 1. 입력 받은 카드 묶음에서 제일 작은거 두개를 빼낸다. 2. 두개를 덧셈 후 결과값을 누적 카운트 해주고 다시 카트 묶음에 넣어준다. 3.모든 묶음을 위의 과정대로 반복한다. *최소힙 자료구조를 이용한 풀이(통과) //최소힙 자료구조 function MinHeap() { this.heap = [0]; this.insert = (v) => { this.heap.push(v); let p = this.heap.length - 1; while (p > 1 && this.heap[Math.floor(p / 2)] > this.h..

백준 그리디 알고리즘 2847번_게임을 만든 동준이 난이도 : 실버4 문제 설명 추가 입출력 예시 예제 입력2 => 5 9 5 6 2 5 예제 출력 2 => 20 예제 입력3 => 4 10 11 12 7 예제 출력3 => 18 문제 풀이 : 마지막 값이 제일 커야하므로 입력으로 받은 배열을 뒤집어 준다. 그 후 n번까지 앞에값을 기준으로 다음값을 계산해준다. 계산된 차이만큼 연산의 횟수가된다. //실버4 게임을 만든 동준이 const solution = (n, list) => { // 현재 list는 역순 상태 let cnt = 0; //연산 횟수 //1부터 시작 for (let i = 1; i < n; i++) { //이전값보다 현재값이 크거나 같다면 현재값을 감소 시켜야함 if (list[i - 1]..

백준 그리디 알고리즘 1339번_단어 수학 난이도 : 골드IV 문제 설명 입출력 문제 풀이 : 단어가 주어졌을때 해당 단어에 9부터 차례로 대입해서 최대값을 출력하면된다. ex )'GCFG' G:9, C:8 F:7(중복이면 큰값으로 설정) 개발로직 1. 단어의 길이에 따라 10의 거듭제곱으로 나타내준다. 'GCFG' G:1000, C:100, F:10 G:1 G는 중복되니깐 G: 1001, 나머지 그대로가 된다. 2. 이후 큰 값부터 정렬을한 뒤 9부터 대입해주면된다. 'GCFG' G(1001 * 9) + C(100 * 8) + F(10 * 7) = 9879 function solution(n, list) { let tmp = 0; //객체에서 value 의미 //여기서 각각의 단어는 key가되고 해당자..

백준 그리디 알고리즘 1449번_수리공 항승 난이도 : 실버III 문제 설명 입출력 또다른 입출력 예시: 3 3 4 5 9 답 : 2 7 4 1 2 3 4 10 15 20 답 : 4 문제 풀이 : 좌우 0.5 간격때문에 무지 헷갈렸다. 하지만 그냥 테이프의 길이(L) -1 이라고 생각하면 훨씬 편하다. 구멍난 위치를 기준으로 테이프를 붙이면 구멍난 위치 + 테이프의 길이 -1 만큼이 테이프가 붙여진 길이가 된다.(이를 fix범위라고 지칭) 즉, 테이프가 붙여진 길이안에 포함되어있는 구멍들은 자동으로 수리가 된 셈이다. 이 방식을 이용해서 풀면된다. 우선 구멍난 위치를 순차적으로 해결하기 위해 정렬을 해준다. 이 후, 반복문을 통해 fix범위보다 큰 경우(테이프의 범위를 벗어난 경우) 새 테이프를 추가하여..

백준 그리디 알고리즘 2437번_저울 난이도 : 실버V 문제 설명 입출력 문제 풀이 : 이 문제의 핵심은 병든 나이트의 이동방법이 항상 오른쪽 방향으로 움직인다는 것입니다. 여기서 최대 방문할 수 있는 최대 개수를 구해야합니다. 이동 횟수가 5가지 미만이면 1~4중에 마음대로 사용하면 됩니다. 이동 횟수가 5가지 이상이면 1~4를 모두 최소 1번씩은 사용해야합니다. (여기서 핵심을 적용시켜야한다.) 그럼 횟수가 5가지 이상에서는 1~4를 모두 써야하는데 나이트는 항상 오른쪽 방향으로 움직이니깐 오른쪽의 움직임을 최소화 하기 위해 2칸씩 움직이는 2,3번은 한번만 이동하고 나머지를 1,4번으로 반복해주면됩니다. 즉, 4가지 경우로 분류 1. 세로길이가 1일때 2. 세로길이가 2일때 3. 세로길이 3이상 가..