그리디
[프로그래머스] 단속카메라
https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 어려워보이지만 조금만 쉽게 생각해보면 간단히 풀리는 문제였다. 문제를 요약하자면 N대의 자동차가 어느 도로 위를 주행한다. 각 차마다 그 도로에 진입하는 지점과 도로에서 나가는 지점이 주어진다. 이 도로에 진입하여 주행하는 차들은 적어도 한 번은 단속카메라를 거쳐야 하는데 단속카메라를 최소한의 개수로 설치하여 모든 차가 단속카메라를 거치게 하고 싶다. 이때 필요한 카메라의 개수를 구하는 문제이다. 상식적으로 생각했을때 도로 위에 자동차가 가장 많는 지점에 카메라를 ..
[프로그래머스] 큰 수 만들기
https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 문제를 접하고보니 백준에서 똑같은 문제를 풀었던 기억이 났다. 그때는 고민을 하다가 힌트를 보고 풀었었는데, 지금 다시 풀려고 하니 기억이 잘 나지 않았다. 이 문제를 풀면서 복습의 중요성을 깨닫게 됐다. 자리 수가 최대 100만인 어떤 수가 주어지고, 그 수에서 k개 만큼의 숫자를 빼서 얻을 수 있는 가장 큰 수를 구하는 문제이다. 단순하게 생각했을때 주어진 수 number에서 k개 만큼 뺐을때 얻는 수의 자리 수는 len(number)-k이다. 가장 왼쪽 자리의 수(값이 큰 자리 수)부터 만든다고 가정할때 number안에 존재하는 가장..
백준 2812번 : 크게 만들기
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어 접근은 쉬우나 구현이 까다로웠던 그리디 문제다. 입력으로 주어지는 N자리 숫자에서 K개 만큼의 수를 제거하여 만들 수 있는 가장 큰 (N-K)자리 수를 구하는 문제다. 처음 생각한 해결 아이디어는 이렇다. N자리 수를 구성하는 숫자들 중 가장 큰 숫자가 만들어야 하는 수의 첫째 자리로 오는 것이 수를 가장 크게 만들 수 있다. 예를들어 주어진 예시 3번에서 10자리 숫자 중 가장 큰 수는 8이지만, 8을 첫째 자리로 만들기 위해선 8 앞의 7개의 숫자를 모두 지워야..
백준 1715번 : 카드 정렬하기
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net N개 만큼의 카드묶음이 있으며 이들 중 2개를 골라 1개의 카드묶음으로 만드는 작업을 수행할 수 있고 최종적으로 N개의 카드묶음을 1개의 카드묶음으로 만드려고 한다. 2개의 카드묶음을 합칠 때에는 각 카드묶음에 있는 카드 수를 합한 만큼 비교를 수행하는데, 비교 횟수를 최소화하려고 한다. 이때 최소화된 비교 횟수를 구하는 문제이다. 전형적인 그리디 알고리즘 유형이다. N개의 카드묶음..