본문 바로가기

정보올림피아드

[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를 만들.. 더보기
[Implementation] 백준 28217, 두 정삼각형 이 문제를 풀기 위해서는 삼각형 행렬의 120도 회전과 대칭 operation을 구현해야 한다. 대칭 operation의 경우는 단순히 중간점을 기준으로 좌우를 swap해주면 되기 때문에 생각보다 간단하게 구현할 수 있다. 그런데 120도 회전을 구현하는 부분은 고민이 필요해서 생각보다 시간이 많이 걸릴 수 있다. 삼각형을 3번 회전 시키면 원래 자리로 돌아오기 때문에 우리가 필요한 구현은 삼각형의 120도 3번 회전 했을 때의 배열과 각각 회전한 상태에서 대칭 시키는 구현을 포함해서 총 6개의 행렬만 있으면 비교가 가능하다. A를 모두 회전 시키면 B는 특별히 회전 시킬 필요가 없다. 이 구현만 한다면 나머지는 두 행렬을 비교하는 부분만 남는다. 회전을 구현하는 부분은 다양하게 구현할 수 있는데, 아래.. 더보기

티스토리툴바