본문 바로가기

Greedy

[Greedy]Leetcode 1727, Largest Submatrix With Rearrangements 간만에 정말 재미있게 푼 문제다. 언제나 이야기 하듯이 Greedy 문제는 접근 방법을 생각하지 못하면 접근이 어렵다. 이 문제는 어떻게 접근해야 할까? 아래의 사실을 주의 깊게 생각해 한다. 1) Matrix의 크기가 $10^5$ 이하다. 계산량을 따져보았을 때 O(n), O(nlogn) 접근법을 떠올려야 한다. 2) Column 방향으로는 원소가 변화하지 않는다. column의 순서가 low 방향으로만 변화할 뿐이다. 3) Matrix에 접근할 때 접근 방법으로 현재 row 보다 큰 row 방향으로만 직사각형 넓이를 생각한다. 모든 row에 대한 탐색이 이루어 지기 때문에 위의 접근법은 유효하다. 접근 방법을 생각해 보자. 위의 사실을 유념해 두고 아래와 같이 column방향으로 1이 연속적으로 있을.. 더보기
[Greedy] 백준 25381, ABBC 이 문제의 해결 전략을 뭘까? 맨 처음 의심한 것은 A, B, C 3개중 한개로 입력이 좁혀져서 DP로 푸는 문제라고 생각했으나S의 길이가 30만에 육박한다. dp로 풀기에는 좀 크기가 큰 편이다. 그럼 어떻게? 이 문제는 Greedy 문제로, 핵심관찰이 중요한 문제다. Greedy는 규칙을 발견하면 정말 쉽게 풀 수 있지만, 규칙을 발견하지 못하면 손도 대지 못하는 양날의 검같은 문제가 많다. 그나저나 무엇이 핵심 관찰일까? 1) A, B를 지우거나 B, C를 지우거나 공통적으로 B를 포함하고 있다는 점이다. B의 갯수가 중요하다. 2) 문자열 S에서 A, B를 만들수 있는데 B, C 때문에 못만드는 경우는 어떤 경우일까? A, B에서 B를 B, C로 만드는데 사용하는 경우다. 그렇다면 A, B를 만들.. 더보기
[DP 응용] BJ_1398, 동전 문제 이 문제를 Greedy하게만 풀수 있을까? 즉 큰수로 나누어 지면 계속 빼면서 숫자를 구하면 해답일까? 직관적으로 알기 어렵다면 반례를 생각해 보면 된다. 예는 31이 되겠다. 31은 Greedy하게 풀면 25, 1, 1, 1, 1, 1, 1 로 구성되어 총 6개지만, 10, 10, 10, 1로 구성하면 4개로 구성할 수 있다. 따라서 Greedy하게만은 안된다. 그렇다면 DP로만 풀수 있을까? 값의 범위가 $10^{15}$ 로 매우 크기 때문에 배열을 이용해서 단순하게 확장하는 방법으로는 해법에 다가가기 어렵다. 그럼 어떻게 해야한다? 규칙성을 발견해야 한다. 규칙성을 바탕으로 문제를 단순하게 만들 수 있어야 한다. 아래의 글이 도움이 될것 같다. 생각보다 간단하게 작성할 수 있는데, 1부터 100까지.. 더보기
[Bit Mask]BJ_14939, 불 끄기 [문제의 접근] 전구 100개가 10x10 모양으로 주어지는 input, 무엇을 떠올려야 할까? 10이하로 주어지는 모양을 보아서는 뭔가 bit mask나 DFS적인 접근이 될거라는 생각이 먼저 떠올라야 한다. 또한 기초적으로 생각해야 할 것들을 적어보자. 1) XOR 연산을 떠올려야 한다. 스위치를 누르면 불이 켜져있을 때는 꺼지게 되고, 불이 꺼져 있을 때는 켜지게 된다. 이는 곧 XOR연산을 의미한다. 0을 꺼짐, 1을 켜짐으로 명명한다고 하면 0 ^ 1 = 1, 1 ^ 1 = 0 이 되니 말이다. 2) (특징) 행렬의 제일 위에서 부터 불을 끄게 된다고 한다면 현재보다 위의 행에 불이 켜져 있다면 반드시 현재 행의 스위치를 눌러야 한다. 예를 들면 위의 예제 입력에서 좌측 상단을 (0, 0)이라고.. 더보기

티스토리툴바