Greedy Algorithm
1.[백준] 10162번 - 전자레인지
최종 코드
2.[백준] 1931번 - 회의실 배정
1차 시도 T개의 회의를 입력받을 때 순서대로 회의가 시작된다고 생각했다. T개의 회의는 입력 순서대로 시작되는 것이 아니므로 입력받은 회의들을 먼저 오름차순으로 sorting할 필요가 있음 -> 또한, 만약 (1,10), (2,2), (3,5) 이런 회의들이 있을 때 끝나는 시간 기준으로 sorting을 하지 않을 경우, (1,10)이 먼저 회의를 점령...
3.[백준] 11399번 - ATM
최종 코드 입력받은 시간들을 오름차순 정렬한 뒤, 최솟값을 구한다.
4.[백준] 11047번 - 동전 0
최종 코드 동전 N개를 입력받고 내림차순으로 정렬한다. 큰 값부터 K값에 할당한다.
5.[백준] 1541번 - 잃어버린 괄호
1차 시도 55+50+40-30 처럼 +가 두번 나오는 경우를 생각하지 못했다. 2차 시도 런타임 에러 발생 최종 코드 너무 복잡하게 생각했다. '+'와 '-'를 기준으로 split해주면 간단하게 해결되는 문제였다.
6.[백준] 5585번 - 거스름돈
아이디어 1) 타로는 1000엔을 지불할 예정이고 입력받는 값은 지불할 돈이므로 우선, 타로가 거스름돈을 받아야 하는 값을 계산한다. -> money = 1000엔 - 지불할 돈 2) 잔돈(500엔, 100엔, 50엔, 10엔, 5엔, 1엔)이 충분히 있다고 가정하였으므로 기본적인 거스름돈 문제 (그리디 알고리즘) 방법으로 문제를 해결하면 된다. -> 잔돈...
7.[백준] 1946번 - 신입 사원
1차 아이디어 1차, 2차 시험 모두 동석차는 없이 1위부터 N위까지 결정된다고 가정하였다. 1) 각 테스트 케이스에 대하여 1차 시험을 기준으로 오름차순 정렬한다. 2) 이때 1차 시험 1등은 무조건 합격이므로(적어도 하나가 다른 지원자보다 떨어지지 않으면 합격), 1차 시험 2등부터 2차 시험 성적을 확인한다. 3) 1차 시험 2등은 1차 시험 1등의 ...
8.[백준] 1789번 - 수들의 합
아이디어 서로 다른 N개의 자연수의 합이 S일 때 N의 최댓값을 구하는 문제이다. 1부터 1씩 증가시키면서 200에 가까운 수를 만든다고 생각해보자. 예를 들어 S가 200이라면 1+2+...+19 = 190이라는 값을 가지게 된다. 19 다음은 20인데 20을 더하면 200을 초과하게 된다. 따라서 마지막 값을 19가 아닌 29로 더해줘야 정확히 200이...
9.[백준] 1339번 - 단어 수학
1차 아이디어 1) 주어진 단어 길이순으로 내림차순 정렬 2) 제일 긴 단어의 큰 자릿수부터 0~9중 max값을 알파벳마다 지정해준다. 알파벳과 숫자의 매칭은 dict를 사용하면 될 것 같다. 코드 2차 아이디어 1차 아이디어에서 살짝 변형하여 (알파벳,자릿수)로 묶어 정렬한다. 코드 >반례 2 AB BB 정답 = 188 출력결과 = 186 ...
10.[백준] 13305번 - 주유소
1차 아이디어 1) 주유소중 가격 최솟값을 찾는다. 2) 그 값을 기준으로 도착지점까지 가격을 계산한다. 3) 위의 과정을 반복하며 시작지점까지 도달하게 한다. 코드 시간초과 발생 -> 반복문을 때려넣었으니..당연한 결과임...매우 비효율적인 코드... 최종 아이디어 굳이 거꾸로 생각할 필요가 없었음...순차적으로 진행하면 됨!!! minPrice에 ...