반응형

그리디 23

백준 2138 : 전구와 스위치 - javascript(그리디)

문제 출처 https://www.acmicpc.net/problem/2138 정답 풀이 브루트포스와 그리디를 함께 이용한다. 첫번째 스위치를 클릭하는 경우와 클릭하지 않는 경우를 각각 확인한다.  풀이 접근 1. 첫번째 스위치 클릭 기준 :첫번째 전구의 상태를 바꾸면 나머지 전구의 상태도 다르게 변화하기 때문에 이를 기준으로 삼는다.  2. 그리디 :첫번째 스위치 선택 이후에는 두번째부터 차례대로 조작을 결정하여 목표 상태와 맞추어 나간다.  정답 코드 const fs = require('fs');const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');const n = Number(input[0]);const initial = ..

백준 13904 : 과제 - javascript(그리디)

문제 출처 https://www.acmicpc.net/problem/13904 정답 풀이 마지막 날짜에서 ~ 1일 차까지 계속 최대 점수를 채워준다. - max 값을 채워준다. - 이미 넣은 값은 해당 x - 남은 날을 비교했을 때, 현재 날짜보다 커야한다.  정답 코드 let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const n = Number(input.shift()); input = input.map(el => el.split(' ').map(v => +v))input.sort((a,b) => b[0] - a[0])const visited = new Array(n).fill(false)let an..

백준 10775 : 공항 - javascript(그리디 쌈박한 문제, Union-Find)

문제 출처 https://www.acmicpc.net/problem/10775 정답 풀이  사람들 천재야? 어떻게 이런 생각을 했는지 싶다 그리디 참 쌈박한 문제다. 인정 ! - 그리디 알고리즘 - 유니온 파인드 자료구조 를 활용해서 풀 수 있다.  각 게이트는 비행기를 수용할 수 있고, 가장 큰 번호의 게이트에 비행기를 도킹시켜야 최대한 많은 비행기를 도킹시킬 수 있다.  1. Union-Find 자료구조- find(x): x가 속한 집합의 대표자를 찾는다. 경로 압축을 사용하여 효율적으로 찾는다. - union(x,y): x와 y를 같은 집합으로 합친다.   2. 그리디 - find(gate) : 각 비행기에 대해, 해당 비행기가 도킹할 수 있는 가장 큰 번호의 게이트를 찾는다 - union(avai..

백준 2437: 저울 - javascript(그리디)

문제 출처 https://www.acmicpc.net/problem/2437 정답 풀이 이건 문제 푸는 아이디어를 생각하기 정말 어려웠을 것 같다. 나도 여러 블로그를 통해 이해가 됐고, 만약 이런 방식으로 설명이 되어 있었다면 ,이해가 좀 더 수월할 수 있었을 것 같은 방식으로 이야기 해보려고 한다.  [1,1,2,3,6,7,30] 배열이 주어졌다고 가정하자. 이해하기 쉽게 중간부터 흐름을 따라가보자.  1,1,2,3 으로 표현할 수 있는 최솟값은 1이다. 최댓값은 7이다.  (1 + 1 + 2 + 3)   그 다음 숫자 6을 넣으려고 할 때, 6이 내포하는 의미가 무엇이겠는가? 적어도 6을 표현할 수 있고, 이전 숫자들로 표현할 수 있었던 값 7과 더한다면 최대로 13을 표현할 수 있다는 뜻이 된다...

백준 11000 : 강의실 배정 - javascript()

문제 출처 https://www.acmicpc.net/problem/11000 문제 풀이 생각의 전환이 필요한 문제였다.  - 일단 시간들을 오름차순으로 정렬하자 - 정렬한 시간들을 탐색한다.   - 그때 start의 시간이라면 방이 하나 필요하다 "+1" 는 뜻   - 그때 end의 시간이라면 방을 하나 반납한다 "-1" 는 뜻  - 매순간 방을 최대로 쓴 값이 답이 된다.     - 왜냐하면 이미 우리는 강의실을 최적으로 정렬을 해놨기 때문에       그때 필수적으로 써야 했던 방의 개수가 최소의 강의실을 사용하는 것이 된다. 정답 코드 let fs = require('fs');let [N, ...input] = fs.readFileSync('/dev/stdin').toString().trim()...

백준 1744: 수 묶기 - javascript(그리디)

문제 출처 https://www.acmicpc.net/problem/1744 문제 풀이머리 뽀갈 날뻔 했다.그래도 1시간 30분 걸려서 풀어냈다..    역시 test case를 추가하면서 어떤 부분을 놓쳤는지 알아내는 것이 참 중요하다 처음에 작성한 코드는 웬만하면 틀린 부분이 있기 때문에,  console.log() 를 잘 이용해서 자신의 실수를 잘 발견하는 것이 코테의 핵심이라는 생각이 든다.  거두절미하고, 이 문제의 핵심은 뭐다?"어떻게 묶어야 최대의 값이 될까?" 내가 세운 기준은 이렇다.  - 1. 절대값이 큰 숫자대로 곱한다. - 2. 양수끼리 계산하고, 음수끼리 계산한다. - 3.양수끼리 계산할 때 1은 묶지 말고 더해준다. - 4. 음수끼리 계산할 때 0이 있다면 묶어준다.  이제 이 ..

백준 1339: 단어 수학 - javascript(그리디)

문제 출처 https://www.acmicpc.net/problem/1339 문제 풀이 이건 정말 아이디어가 필요했다. 난 정~ 말 복잡하게 풀었었는데, 해법을 보고 머리를 탁 ~ 쳤다 ! 앞으로 비슷한 문제가 있다면 이런 접근을 활용해야 겠다   이 문제는 사실 두개를 고려해야 하는데 우선순위가 높을 수록 높은 숫자를 받는 것이라고 할 때, - 높은 자리에 있을 수록 (십의 자리 > 일의 자리) 우선순위가 올라간다. - 빈번하게 나타날 수록 (만약 십의 자리에 있는 문자가 'A', 'B'가 있을 때, 만약 A가 일의 자리에 B보다 더 많이 나타났다면)우선순위가 올라간다. 이 복잡한 셈처럼 보이는 것이 아주 ~ 간단한 아이디어로 쉽게 풀린다.  "각 문자를 돌면서 해당 문자가 있는 자리수를 계속 더해주는..

백준 1049: 기타줄 - javascript(그리디)

문제 출처 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 문제 Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다. 끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱..

백준 19941: 햄버거 분배 - javascript (그리디)

문제 출처 https://www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 (추가 시간 없음) 256 MB 10871 5279 4294 50.093% 문제 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 �$K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사람 햄버거 햄버거 사람 사람 햄버거 사람 1 2 3 4 5..

백준 1449: 수리공 항승 - javascript(그리디)

문제 출처 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 문제 항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다. 파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다. 항승이는 길이가 L인 테이프를 무한개 가지고 있다. 항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 ..

반응형