알고리즘/Greedy 썸네일형 리스트형 [Greedy]Leetcode 1727, Largest Submatrix With Rearrangements 간만에 정말 재미있게 푼 문제다. 언제나 이야기 하듯이 Greedy 문제는 접근 방법을 생각하지 못하면 접근이 어렵다. 이 문제는 어떻게 접근해야 할까? 아래의 사실을 주의 깊게 생각해 한다. 1) Matrix의 크기가 105 이하다. 계산량을 따져보았을 때 O(n), O(nlogn) 접근법을 떠올려야 한다. 2) Column 방향으로는 원소가 변화하지 않는다. column의 순서가 low 방향으로만 변화할 뿐이다. 3) Matrix에 접근할 때 접근 방법으로 현재 row 보다 큰 row 방향으로만 직사각형 넓이를 생각한다. 모든 row에 대한 탐색이 이루어 지기 때문에 위의 접근법은 유효하다. 접근 방법을 생각해 보자. 위의 사실을 유념해 두고 아래와 같이 column방향으로 1이 연속적으로 있을.. 더보기 [Greedy] BJ_21762, 공통부분수열확장, 정올 이 문제는 처음 접했을 때, 어떤 알고리즘으로 문제에 접근해야 하는지 생각하기 난해한 문제다. 제목에서 알 수 있듯이 Greedy 문제로, Greedy 문제는 접근법을 떠올리지 못하면 풀이에 쉽게 다가가지 못한다. 이해를 쉽게 하기 위해 아래 예시를 들어 보자. X, Y를 독립적으로 생각하고, 아래와 같이 주어졌다고 한다면 공통 부분 수열인 w를 중심으로 w의 원소인 w[i]의 사이사이에 어떠한 인자들이 들어갈 수 있는지 계산해 보는 것이 필요하다. 즉 w = da인 아래의 케이스 에는 d의 앞에, d와 a의 사이, a의 뒤에 어떤 알파벳이 들어올 수 있는지를 계산하고 X, Y에 각각 동일한 원소가 있다면 확장 가능한 공통부분 수열이라는 것을 확인할 수 있다. w는 이미 공통 부분 수열이기 때문에 위와 .. 더보기 [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를 만들.. 더보기 이전 1 다음
