본문 바로가기

PS/AOJ6

[자바] 알고스팟 - CLOCKSYNC (Synchronizing Clocks) 문제 : aoj-CLOCKSYNC [ 종만북 책에 풀이가 있는데 제 풀이를 올리는 이유 ] 블로그에 풀이 글 쓰는게 오답노트 및 개인 복기용 이기도 하므로 책에 풀이가 있더라도 제 풀이 및 정답까지 접근한 방식을 올리는 겁니다. 즉, '책의 풀이를 보기 전에 문제를 푼다 -> 제 풀이를 올린다 -> 책의 풀이를 보고 더 좋은 방법이 있고 써야한다면 풀이 뒤에 추가한다.' 처럼 진행합니다. 단순 브루트포스인데 아이디어를 어떻게 잡냐에 따라 엄청 쉬워질수도, 엄청 어려워질수도 있는 문제였다. 처음엔 별 생각없이 스위치와 연결된 시계를 반대로 매핑시킨 후(어떠한 시계가 12가 아닐 때 어떤 스위치들을 눌러야 하는지 그래프의 edge 개념으로 생각해서) 모든 경우를 보려고 했다. 근데 이 경우 종료조건을 어떻게.. 2022. 4. 25.
[자바] 알고스팟 - BOARDCOVER (게임판 덮기) 문제 : aoj-BOARDCOVER [ 종만북 책에 풀이가 있는데 제 풀이를 올리는 이유 ] 블로그에 풀이 글 쓰는게 오답노트 및 개인 복기용 이기도 하므로 책에 풀이가 있더라도 제 풀이 및 정답까지 접근한 방식을 올리는 겁니다. 즉, '책의 풀이를 보기 전에 문제를 푼다 -> 제 풀이를 올린다 -> 책의 풀이를 보고 더 좋은 방법이 있고 써야한다면 풀이 뒤에 추가한다.' 처럼 진행합니다. 흰 칸의 수가 50을 넘지 않고, 3칸씩 채우므로 최대 16개만 덮으면 된다. 그럼 사실 모든 빈칸에서 놓을 수 있는 4자리 모양으로 놓자면 O(2^50 x 4^16) 어.. 말도안되는 수치다(2는 해당 빈칸에 놓거나 안놓거나라서 2개). 어떻게 칸을 쉽게 선택했다고 해도 O(4^16)이라 시간복잡도 상으론 시간초과긴.. 2022. 4. 22.
[자바] 알고스팟 - PICNIC (소풍) 문제 : aoj-PICNIC [ 종만북 책에 풀이가 있는데 제 풀이를 올리는 이유 ] 블로그에 풀이 글 쓰는게 오답노트 및 개인 복기용 이기도 하므로 책에 풀이가 있더라도 제 풀이 및 정답까지 접근한 방식을 올리는 겁니다. 즉, '책의 풀이를 보기 전에 문제를 푼다 -> 제 풀이를 올린다 -> 책의 풀이를 보고 더 좋은 방법이 있다면 풀이 뒤에 추가한다.' 처럼 진행합니다. brute force 1번문제부터 뭔가 이-지한 느낌이 안든다.. 역시 무서운 종만북.. 10!로 모든 쌍에 대해 해보는건 그래도 좀 너무 날로먹을 것 같아서, 존재하는 쌍을 기준으로 모든 경우를 확인하도록 해봤다. n이 항상 짝수이므로, n/2 쌍이 선택될 때 까지 선택되지 않는 쌍을 선택하는 식으로 진행했다. 이 때 중복으로 세는.. 2022. 4. 21.
알고스팟 - BOGGLE - 자바 (aoj java) 문제 : BOGGLE [ 종만북 책에 풀이가 있는데 제 풀이를 올리는 이유 ] 블로그에 풀이 글 쓰는게 오답노트 및 개인 복기용 이기도 하므로 책에 풀이가 있더라도 제 풀이 및 정답까지 접근한 방식을 올리는 겁니다. 즉, '책의 풀이를 보기 전에 문제를 푼다 -> 제 풀이를 올린다 -> 책의 풀이를 보고 더 좋은 방법이 있다면 풀이 뒤에 추가한다.' 처럼 진행합니다. 6장(무식하게 풀기)에 나온 첫 문제이다. '알고리즘 문제 해결 전략 6장을 읽고 이 문제를 푸시려는 분들은 주의하세요. 6장의 예제 코드는 이 문제를 풀기에는 너무 느립니다. 6장의 뒷부분과 8장을 참조하세요.' 라는 주의문구가 있긴 했는데, 대충 시간복잡도 때려보니 별 문제 없을 것 같아서 일단 도전해봤다. 물론 쌩 brute force.. 2022. 4. 17.
알고스팟 - QUADTREE - 자바 (AOJ JAVA) 문제 : QUADTREE 다음과 같이 상하가 뒤집히면 된다. 이 때, 현재 보고 있는 구역을 4사분면으로 나눴을 때 순서대로 1,2,3,4라고 해보자. 그럼 결국 1+2+3+4 순서이던게, 3+4+1+2 순서로 바뀌면 된다. 매번 4개씩 나뉘어 점점 디테일하게 진행되므로, 재귀적으로 다음과 같은 로직을 세워보자. A. 현재 보고 있는 문자가 'x'가 아니라면 해당 위치는 전체가 검정이거나 흰색일 것이므로, 그대로 리턴해도 된다. B. 현재 보고 있는 문자가 'x'일 경우 총 4번에 걸쳐 1->2->3->4 순서로 'A, B'를 다시 진행한다. 그리고 해당 결과를 3->4->1->2 순서로 리턴한다. 간단한 로직이지만 위 로직이면 끝난다. 분할정복 및 재귀에 대한 기초 이해력을 높이는데 도움이 많이 되는 .. 2022. 4. 5.
알고스팟 - FESTIVAL - 자바 (AOJ JAVA) 문제 : FESTIVAL N이 최대 1000 이므로 O(N^2)의 알고리즘이라도 충분히 통과할 수 있다. 따라서 단순히 차이가 L 이상인 모든 구간에 대해 O(N^2)으로 확인해주면 된다. (코드의 24~25 line 참고) 주의점은 10^(-7) 이하의 절대/상대 오차가 있어야 하므로, 그냥 바로 출력하면 안되고 소수점 8자리 이상을 출력하도록 해야 한다. 자바의 경우 String.format("%.8f", answer)과 같은 코드로(c언어와 비슷한 출력 방식) 소수점 8자리까지 출력할 수 있다. 그리고 모든 구간에 대해 직접 더해봐도 시간 제한에 충분히 맞출 수 있긴 하지만(O(N)), prefix sum을 미리 구해둘 경우 [a, b] 구간의 합은 arr[b]-arr[a-1] 과 같이 O(1)로 .. 2022. 4. 5.