IT 개발 돼지의 일상

출저 : https://www.acmicpc.net/problem/1339 "수학적 접근 혹은 백트래킹" 나는 수학적으로 접근하지 못하고, 백트래킹을 이용했다. 그래서 실행 시간이 오지게 길었다. 그래도 돌긴 도는구나.. Set을 쓰면 더 좋을 것 같은데 iterator 구현이 익숙치 않아서 리스트에서 contains 체크를 했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;im..

출저 : https://www.acmicpc.net/problem/2580 "백트래킹" 아... 분명 시간 초과가 날 것이 없다고 생각했는데, 또 소스를 봐도 날것이 없다고 생각했는데... 전체적인 로직은 잘 짰으나 아래와 같은 실수를 했다. DFS 탐색에 BFS 처럼 가능한 list를 다 순회하다니. 1234567891011121314for (int i = idx; i

출저 : https://www.acmicpc.net/problem/1799 "독립사건을 분할처리해서 시간복잡도를 줄인다." N-queen 과 유사하게 해당 문제를 풀려고 시도했고, 생각보다 금방 풀리네? 라는 생각을 했다. 하지만 시간 초과... 시간복잡도를 줄여야 한다. 중복 탐색하는 부분은 없었고 어딘가 시간 복잡도를 줄일 방법을 찾아야 했다. 원래 시간복자도는 O(2^(N*N)) 로 제한 시간내에 문제를 풀 수가 없다. 비숍의 움직임 특성을 보면 4방향 대각선으로만 영향을 끼친다. 즉 아래 체스판을 봤을 때, 같은 색깔의 칸에만 영향을 미친다. 검은칸에 비숍들과 흰 칸의 비숍들은 독립적인 사건인 것이다. 따라서 전체 탐색 범위를 줄여 시간복잡도를 줄이는 방법을 쓴다. O(2^N) 이 될 것 같다. ..