7달 전에 한 10트 도전해서 안되서 포기하고, 오늘 다시 풀어봤다. 오늘도 의기양양하게 풀었으나 82%에서 TLE 발생해서 뭐지뭐지 한참을 고민했다. 결론은 어거지로 푼 거 같으니 며칠 내로 기억이 희미해질 쯤에 다시 풀어봐야겠다. 82% 시간 초과 해결을 위해서 거의 4시간을 붙잡고 있었던 거 같다. 82%에서 시간초과가 발생하는 이유는 간단한다. 탐색하는 모수가 너무 과하기 때문이다. 즉, 탐색 모수를 최소화 해야한다. 사이클이 형성되는 경우는 다음과 같이 2가지가 있다. 1. 1 → 2 → 3 → 4 → 1 2. 1 → 2 → 3 → 4 → 5 → 3 1번은 대부분의 사람들이 잘 처리하지만, 나 같이 TLE가 발생한 사람들은 2번에서 처리하는 방법에서 많이 헤맸던 거 같다..
https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net BFS 문제다. BFS 문제는 방문 처리를 어떻게 해야할지를 가장 먼저 고민하는 것이 국룰인 거 같다. 구해야하는 값은 "불이 켜져있는 방의 최대값"이다. 즉, 최소한 방문을 해야하는 것이 아니라, 가능한 모든 방을 다 방문해서 불을 켜야하는 것으로 이해를 할 수 있다. 이동 가능한 조건은 두 가지가 있다. 불이 켜져있는 방에만 들어갈 수 ..
https://www.acmicpc.net/problem/16920 BFS 문제다. BFS 문제에서 가장 핵심은 얼마나 방문을 최적화 할 것인지다. 방문을 최적화 하지 못하면 3가지 문제중 하나가 필수적으로 발생한다. 첫번째는 큐에 어마어마하게 많은 것들이 들어가게 되면서 메모리가 터진다. 두번째는 잘못된 방문 체크로 인해 방문한 곳에 계속 방문하며 무한루프에 빠지게 된다. 세번째는 과하게 방문해서 TLE가 발생한다. 이 부분을 고려해서 문제를 해결했다 1. 매 턴마다 플레이어 순서대로 성을 확장한다. (한 플레이어 확장 → 다음 플레이어 확장)→ 따라서 For문을 통한 순서대로의 처리가 필요한 것을 이해할 수 있다. 한번에 확장 가능한 영역은 10억이다. 그런데 N,M이 각각 1000이..
https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net N=1,000,000이다. 따라서 무조건 N / NlogN 수준으로 시간 복잡도를 줄여야 한다. 전체 배열부터 구간을 조금씩 줄이면서, 홀수 카운트를 측정한다. 이 때, 홀수 카운트
https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질5는 수빈이 뿐만 아니라 동생도 움직인다. 동생이 고정되어있을 때는 고정된 한점으로 이동하는 최단 경로를 찾기 때문에 쉽게 문제를 풀 수 있다. 그렇지만 이번에는 동생도 동적으로 움직인다. 그렇다면 여기서 고려해야할 부분은 예전에 방문했던 부분을 다시 방문하지 않아도 되냐는 것이다. 결론은 예전에 방문했던 부분을 다시 방문해야한다는 것이다. 이전에는..