본문 바로가기

그리디14

[프로그래머스] 큰 수 만들기 문제 링크 >> https://programmers.co.kr/learn/courses/30/lessons/42883 📋 문제 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 👉 입출력 제한 조건 number는 2자리 이상, 1,000,000자리 이하인 숫자입니.. 2022. 4. 11.
[LeetCode] Assign Cookies 문제 링크 >> https://leetcode.com/problems/assign-cookies/ 📋 문제 Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, .. 2022. 4. 9.
[12주차] 분할정복법과 탐욕적기법 4월 9일 자 학습 내용 정리입니다. ✅ 분할정복법 분할정복법은 아래와 같다. 문제를 소문제로 분할한다. 각각의 소문제를 해결한다. 소문제의 해결 결과를 이용해 전체 문제를 해결한다. 분할정복법의 대표적인 예로는 합병정렬과 이분탐색이 있다. ✔️ 합병정렬 합병정렬(Merge Sort)은 흔히 하향식 2-way 방법으로 쓰이는데 이는 다음과 같이 작동한다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 아래 과정을 거친다. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로.. 2022. 4. 9.
[백준 1343번] 폴리오미노 문제 링크 >> https://www.acmicpc.net/problem/1343 📋 문제 민식이는 AAAA와 BB의 폴리오미노 2개를 무한개만큼 가지고 있다. 이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다. 폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오. 👉 입력 첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다. 👈출력 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. 📝 풀이 board = input() arr = board.split('.') def poly(arr): string = "" for item in arr:.. 2022. 4. 5.
[백준 11508번] 2+1 세일 문제 링크 >> https://www.acmicpc.net/problem/11508 📋 문제 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다. 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다. 예를 들어, 7개의 유제품이 있어서 각 제품의 가격이 10, 9, 4, 2, 6, 4, 3이고 재현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 13원을, 두 번째 꾸러미에서는 10원을, 세 번째 꾸러미에서는 9원을 지불해야 합니다. 재현이는 K.. 2022. 4. 5.
[프로그래머스] 무지의 먹방 라이브 문제 링크 >> https://programmers.co.kr/learn/courses/30/lessons/42891 📋 문제 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로.. 2022. 3. 12.
[이코테] 볼링공 고르기 이것이 취업을 위한 코딩테스트다 with 파이썬 책을 읽고 정리한 내용입니다. 📋 문제 A, B 두 사람이 볼링을 치고 있다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀있고 공의 번호는 1번부터 순서대로 부여한다. 같은 무게의 공이 여러 개 있을 수 있지만 이 경우 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지 자연수 형태로 존재한다. 예를 들어 N이 5이고 M이 3이며 각각의 무게가 차례대로 1, 3, 2, 3, 2 일 때 각 공의 번호가 차례대로 1번부터 5번까지 부여된다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같다. (1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번,.. 2022. 3. 11.
[이코테] 문자열 뒤집기 이것이 취업을 위한 코딩테스트다 with 파이썬 책을 읽고 정리한 내용입니다. 📋 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌.. 2022. 3. 10.
[백준 1026번] 보물 문제 링크 >> https://www.acmicpc.net/problem/1026 📋 문제 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. $$ S = A[0] × B[0] + ... + A[N-1] × B[N-1] $$ S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하는 프로그램을 작성하시오. 👉 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 .. 2022. 3. 10.

티스토리툴바