그리디
-
Problem : https://leetcode.com/problems/largest-number Difficulty : Medium Status : Solved Time : 00:15:23 문제 설명 더보기음의 정수가 아닌 nums를 입력으로 받아, 이들을 하나로 이었을 때 가장 큰 수가 되도록 정렬하여 반환하라. 결과값이 매우 클 수 있으므로, 정수 대신 문자열 형태로 반환하도록 한다. 풀이 분명히 어디서 많이 봤었는데...? 하는 문제. 정렬을 그리디하게 수행하면 되는데, 임의의 수 a, b에 대해서 (a, b를 이은 결과) >= (b, a를 이은 결과)가 항상 유지되도록 정렬하면 된다. 그리디 + 정렬 문제. 풀이 코드class Solution: @staticmethod def com..
179. Largest NumberProblem : https://leetcode.com/problems/largest-number Difficulty : Medium Status : Solved Time : 00:15:23 문제 설명 더보기음의 정수가 아닌 nums를 입력으로 받아, 이들을 하나로 이었을 때 가장 큰 수가 되도록 정렬하여 반환하라. 결과값이 매우 클 수 있으므로, 정수 대신 문자열 형태로 반환하도록 한다. 풀이 분명히 어디서 많이 봤었는데...? 하는 문제. 정렬을 그리디하게 수행하면 되는데, 임의의 수 a, b에 대해서 (a, b를 이은 결과) >= (b, a를 이은 결과)가 항상 유지되도록 정렬하면 된다. 그리디 + 정렬 문제. 풀이 코드class Solution: @staticmethod def com..
2024.09.18 -
Problem : https://leetcode.com/problems/score-after-flipping-matrix/ Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 비트마스킹은 너무 느렸다...! 좀 더 간결히, 그리고 문제의 본질을 꿰뚫어야 풀 수 있는 문제였다. 언뜻 보면 모든 경우의 수를 다 테스트해보아야 할 것 같지만, 함정이 있다. score는 이진법으로 계산되므로, 제일 높은 차수(0번째 column)가 모두 1인 경우가 그리디하게 가장 큰 값을 지니게 된다. 즉 column 0을 1로 세팅하도록 하자. 이제 column 1부터 순회를 시작하면 된다. 이 때, column 0이 원래 1인 경우는 row가 뒤집어진 경우이므로..
861. Score After Flipping MatrixProblem : https://leetcode.com/problems/score-after-flipping-matrix/ Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 비트마스킹은 너무 느렸다...! 좀 더 간결히, 그리고 문제의 본질을 꿰뚫어야 풀 수 있는 문제였다. 언뜻 보면 모든 경우의 수를 다 테스트해보아야 할 것 같지만, 함정이 있다. score는 이진법으로 계산되므로, 제일 높은 차수(0번째 column)가 모두 1인 경우가 그리디하게 가장 큰 값을 지니게 된다. 즉 column 0을 1로 세팅하도록 하자. 이제 column 1부터 순회를 시작하면 된다. 이 때, column 0이 원래 1인 경우는 row가 뒤집어진 경우이므로..
2024.05.14 -
Problem : https://leetcode.com/problems/maximize-happiness-of-selected-children Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 릿코드에서 맞닥뜨린 한국적인(?) 문제. 지금껏 릿코드 문제를 풀어서 느꼈던 점은. 왠지 백준 골드문제를 달아줘도 손색없을 난이도였다. 그리디로 접근해보자. 어떻게 사람을 뽑던 간에, 최종적으로 k명의 사람을 뽑으므로 감소치는 최대 k*(k-1)/2명이 될 것이다. happiness value는 음수가 될 수 없다. 즉 매 순간 행복도가 최대치인 아이들을 뽑고, 어느 시점에서 행복도 최대치가 0이라면 감소는 더 이상 적용되지 않는다. 즉 내림차순으로 정..
3075. Maximize Happiness of Selected ChildrenProblem : https://leetcode.com/problems/maximize-happiness-of-selected-children Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 릿코드에서 맞닥뜨린 한국적인(?) 문제. 지금껏 릿코드 문제를 풀어서 느꼈던 점은. 왠지 백준 골드문제를 달아줘도 손색없을 난이도였다. 그리디로 접근해보자. 어떻게 사람을 뽑던 간에, 최종적으로 k명의 사람을 뽑으므로 감소치는 최대 k*(k-1)/2명이 될 것이다. happiness value는 음수가 될 수 없다. 즉 매 순간 행복도가 최대치인 아이들을 뽑고, 어느 시점에서 행복도 최대치가 0이라면 감소는 더 이상 적용되지 않는다. 즉 내림차순으로 정..
2024.05.09 -
Problem : https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 00:39:59 문제 설명 더보기 N2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. 은 N이 3일 때의 예이다. 이들 N2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 ..
[백준/1285] 동전 뒤집기 (Python)Problem : https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 00:39:59 문제 설명 더보기 N2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. 은 N이 3일 때의 예이다. 이들 N2개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 ..
2024.03.22 -
Problem : https://www.acmicpc.net/problem/30014 30014번: 준영이의 사랑 선린의 대표 스윗남인 준영이는 여자친구 아스나를 위한 선물을 준비 중이다. 그는 $N$개의 진주로 이루어진 원형의 진주 목걸이를 선물해 줄 생각이다. $i$ $(1 \leq i \leq N)$번째 진주알은 가치 $P_{ www.acmicpc.net Difficulty : Gold 2 Status : Solved Time : ??:??:?? 문제 설명 더보기 선린의 대표 스윗남인 준영이는 여자친구 아스나를 위한 선물을 준비 중이다. 그는 N개의 진주로 이루어진 원형의 진주 목걸이를 선물해 줄 생각이다. i(1
[백준/30014] 준영이의 사랑 (Python)Problem : https://www.acmicpc.net/problem/30014 30014번: 준영이의 사랑 선린의 대표 스윗남인 준영이는 여자친구 아스나를 위한 선물을 준비 중이다. 그는 $N$개의 진주로 이루어진 원형의 진주 목걸이를 선물해 줄 생각이다. $i$ $(1 \leq i \leq N)$번째 진주알은 가치 $P_{ www.acmicpc.net Difficulty : Gold 2 Status : Solved Time : ??:??:?? 문제 설명 더보기 선린의 대표 스윗남인 준영이는 여자친구 아스나를 위한 선물을 준비 중이다. 그는 N개의 진주로 이루어진 원형의 진주 목걸이를 선물해 줄 생각이다. i(1
2024.03.20 -
Problem : https://www.acmicpc.net/problem/31411 31411번: 대회 개최 용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 $N$가지 종류의 알고리즘 문제들을 각각 $K$개씩, 총 $N\times K$개의 문제를 만들었다. 그중 $i$번째 알고리즘의 $j$번째 문제의 난이도는 $d_{ij} www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 00:18:41 문제 설명 더보기 용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 N가지 종류의 알고리즘 문제들을 각각 K개씩, 총 NxK개의 문제를 만들었다. 그중 i번째 알고리즘의 j번째 문제의 난이도는 d_ij이다. 그러나 만든 문제를 모두 내기에는 대회 시간이 부족..
[백준/31411] 대회 개최 (Python)Problem : https://www.acmicpc.net/problem/31411 31411번: 대회 개최 용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 $N$가지 종류의 알고리즘 문제들을 각각 $K$개씩, 총 $N\times K$개의 문제를 만들었다. 그중 $i$번째 알고리즘의 $j$번째 문제의 난이도는 $d_{ij} www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 00:18:41 문제 설명 더보기 용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 N가지 종류의 알고리즘 문제들을 각각 K개씩, 총 NxK개의 문제를 만들었다. 그중 i번째 알고리즘의 j번째 문제의 난이도는 d_ij이다. 그러나 만든 문제를 모두 내기에는 대회 시간이 부족..
2024.03.02