본문 바로가기

알고리즘 문제해결 전략16

[종만북] PI - 원주율 외우기 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-PI 풀이 각 테스트케이스에 대해 dp[x] 를 x번째 숫자까지 표현하기 위한 최소 난이도라 정의하자. 저 정의대로 구할수만 있다면 답은 dp[문자열 길이] 가 될 것이다. 현재 문자열의 z번 문자를 보고 있다고 해보자. 이 때 dp[x]가 x번째 숫자를 표현하기 위한 최소난이도임이 확실하다면 dp[z]는, min( dp[z-3] + '이전 3개의 문자 난이도', dp[z-4] + '이전 4개의 문자 난이도', dp[z-5] + '이전 5갱의 문자 난이도') 라고 할 수 있다. 따라서 이대로 구현해주면 된다! 말한대로 이전 3개, 4개, 5개의 난이도를 계산하면서 최소값을 갱신해나가면 된다. 점수 계산은 score() 함수로 처리했다.. 2023. 4. 2.
[종만북] WILDCARD - Wildcard (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-WILDCARD 풀이 우선 '*'이 연속으로 있는 경우는 처리만 어렵게 만들고 하나만 있는 경우와 동일하다. 따라서 입력받은 W에서 '*'이 연속으로 있다면 하나로 변경해줬다. 즉, "ab********c" 라면 "ab*c"로 변경해준다. private String compressContinuousAsterisk(String w) { while (w.indexOf("**") != -1) { w = w.replace("**", "*"); } return w; } 그럼 이제 연속된 '*'이 하나로 합쳐진 W와 현재 보고 있는 문자열 cur에 대해 각각 포인터를 두고 움직인다고 해보자. 이 경우 두 개의 포인터가 가르키는 문자열이 동일하거.. 2023. 4. 2.
[종만북] CLOCKSYNC - Synchronizing Clocks (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-CLOCKSYNC 풀이 시계 자체에 초점을 맞추면 답이 안나온다. 스위치가 10개 밖에 없다는 부분에 초점을 맞춰보자. 결국 시계는 4번 돌면 제자리다. 따라서 각 10개의 스위치는 3번 이상 누를 일이 없고, 그럼 O(C x 4^10)으로 처리가 가능함을 알 수 있다. 즉, 시계가 몇칸인지는 상관 없고, 그냥 스위치가 10개이고 각각 최대 3번까지 누를 수 있으니 4x4x... 를 해주면 되는 것이다. 코드 : github import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTo.. 2023. 3. 20.
[종만북] BOARDCOVER - 게임판 덮기 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-BOARDCOVER 풀이 모든 칸에 블록을 놓아본다고 하자. 이 경우 흰 칸의 수는 50을 넘지 않는다고 했고, 블록 하나에 3칸씩이므로 최대 16개를 덮으면 된다. 블록의 모양은 4가지이므로, O(C x 4^16) 이 필요하다. 방법을 좀 다르게 생각해서 각 칸마다 놓거나 안놓거나 해봐도 O(C x 2^50)이므로 마찬가지로 불가능하다. 여기서 생각해볼 점은, 블록의 3칸 중 가장 상단 좌측의 위치를 기준으로 놓는다고 생각해보자. 그리고 주어진 게임판의 상단부터 하단으로, 좌측에서 우측으로 쭉 보면서 블록을 놓는다고 해보자. 이렇게 되면 만약 블록을 놓지 않고 그냥 지나쳤을 때, 해당 위치엔 다시는 블록을 놓을 수 없음이 증명된다... 2023. 3. 20.
[종만북] PICNIC - 소풍 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-PICNIC 풀이 n명을 일렬로 놓는 경우의 수는 n! 이다. 따라서 일렬로 놓고 2명씩 쌍을 짓는다고 생각해보면 O(C x n!)가 필요하므로 통과할 수 없다. 더 효율적으로 하려면 2명씩 짝지어볼 수 있다. 이 때, 주의할 점은 아래의 경우들은 모두 같은 경우라는 점이다. '일부만 다르더라도 다른 방법' 이라고 써져 있는 부분은 짝이 다를 경우이지, 이미 정해진 쌍에 대해서는 상관이 없다. (0, 1), (2, 3) (0, 1), (3, 2) (1, 0), (2, 3) (2, 3), (0, 1) (3, 2), (1, 0) ... 등 그리고 모든 학생이 쌍에 포함되어야 하므로, 그냥 쌍을 지어주는 방향을 고정시켜도 결과는 동일하다... 2023. 3. 20.
[종만북] BOGGLE - 보글 게임 (자바, C++) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-BOGGLE 풀이 전체적인 로직은 다음과 같다. A. 보글 게임판을 입력받는다. B. N개의 각 단어에 대해, 각 문자와 동일한 보글 게임판의 문자 위치를 찾는다. C. 이후 각 단어의 모든 문자를 찾을 수 있는 동안 보글 게임판의 현재 위치에서 8방향으로 탐색을 진행한다. D. 모든 문자를 찾았다면 YES, 아니면 NO 이다. 위와 같이 완전탐색으로 진행하면 O(C x N * 8^10) 정도의 시간이 필요하므로 풀 수 없다(10은 단어의 길이를 뜻한다). 그래서 좀 더 줄여봐야 한다. 우선 'A'를 입력받으면서 모든 대문자(26개)에 대해 존재유무를 체크해둔다. -> N개의 문자에 체크해둔 문자에 없는 문자가 등장한다면 탐색을 해보.. 2023. 3. 20.