본문 바로가기

종만북11

[algospot][WILDCARD] Wildcard 문제 : https://algospot.com/judge/problem/read/WILDCARD DP로 풀었다. dp[i][j] = pattern[i~끝] 부분문자열과 s[j~끝] 부분문자열이 같은가(같으면 1, 다르면 0, 아직 탐색 전이면 -1) 패턴문자열(pattern)과 패턴에 맞는지 확인하고자 하는 문자열(s)가 있다고 할 때 DP에 사용할 배열은 위와 같이 나타낼 수 있다. 패턴 문자열에 올 수 있는 문자는 '*', '?', 알파벳이다. 만약 알파벳이라면 pattern[i]와 s[j]가 같은지 체크하고 다르면 false를 반환, 같다면 i+1, j+1 부터 다시 탐색해간다. '?' 인 경우 s[j] 가 어떤 문자가 오던지 정답이 가능하므로 i+1, j+1 부터 다시 탐색해나간다. '*' 인 경.. 2019. 6. 3.
[algospot][CLOCKSYNC] Synchronizing Clocks 문제 : https://algospot.com/judge/problem/read/CLOCKSYNC 완전탐색으로 돌린다. 만약 하나의 스위치를 4번 돌리면 원래 상태와 같아진다. 따라서 하나의 스위치를 0~3번 돌리면서 탐색해나간다. void solve(시계상태, 스위치 번호, 스위치 누른 횟수){ for (현재 스위치 누른 횟수 = [0,4)) { solve(시계상태, 스위치 번호 + 1, 스위치 누른 횟수 + 현재 스위치 누른 횟수); 스위치 한 번 눌렀을 때 시계상태 갱신. } } 의사 코드로 짜면 위와 같다. 여기에 몇 가지 종료 조건과 정답 갱신하는 코드 추가해준다.. 시간복잡도는 O(4^10). 10은 스위치 개수이다. 소스코드 : https://gist.github.com/fpdjsns/78c.. 2019. 5. 31.
[algospot][BOARDCOVER] 게임판 덮기 문제 : https://algospot.com/judge/problem/read/BOARDCOVER x 위치를 탐색할 때 x를 채울 수 있는 L 블럭 모양은 위와 같다. 블럭은 (0,0) 인덱스부터 탐색하며 열우선탐색으로 탐색해나간다. 따라서 x 위치를 탐색할 때는 이전 행들과 이전 열은 모두 블럭이 채워져있음을 보장해야 한다. 즉, 열우선탐색을 하면서 아직 채워져 있지 않은 곳을 찾은 다음 위 4가지 중에 한 가지 이상 방법으로 채울 수 있으면 그 방법으로 채우고 다시 처음부터 열우선 탐색으로 빈 곳을 찾고를 반복한다. 만약 4가지 중 어느 방법으로도 L 블록을 채울 수 없다면 현재 빈 곳을 채울 수 없다는 뜻이므로 탐색을 중단한다. 만약 모든 블록이 채워져있다면 정답 +1을 한다. 소스코드 : htt.. 2019. 5. 31.
[algospot][PICNIC] 소풍 문제 : https://algospot.com/judge/problem/read/PICNIC N이 10으로 아주 작아서 완전탐색을 돌렸다. 인덱스를 0부터 N까지 탐색하면서 현재 탐색중인 인덱스 사람이 친구가 될 수 있는 쌍을 구한 뒤 인덱스를 탐색한다. N = 4 쌍이 가능한 조합 : (0,1) (1,2) (2,3) (3,0) (0,2) (1,3) 라고 한다면 0부터 탐색하면서 0과 쌍이 가능한 조합을 탐색 후, 쌍이 맺어진 사람은 다음번에는 짝을 못이루므로 따로 체크해둔다. 0 : (0,1) -> 1 : 이미 짝이 있음 -> 2 : (2,3) -> 3 : 이미 짝이 있음 -> 4 : 정답 가능 0 : (0,2) -> 1 : (1,3) -> 2 : 이미 짝이 있음 -> 3 : 이미 짝이 있음 -> 4 .. 2019. 5. 28.
[algospot][QUADTREE] 쿼드 트리 뒤집기 문제 : https://www.algospot.com/judge/problem/read/QUADTREE 분할정복 문제. 만약 입력으로 받은 문자열의 길이가 1이라면 이는 압축이 되는 경우가 없을 때이다. (x가 입력에 없음) 이 때는 해당 문자열을 그대로 반환한다. 문자열 길이가 1이 아닌 경우는 첫 번째 문자가 반드시 x가 된다. 입력으로 받은 문자열을 앞에서부터 탐색하면서 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 부분을 배열에 각각 저장한다. 탐색 하면서 나올 수 있는 경우는 총 3가지이다. 탐색 중인 문자(now)가 1. 'w'인 경우 : 배열에 "w" 저장 2. 'b'인 경우 : 배열에 "b" 저장 3. 'x'인 경우 : 탐색 중인 인덱스부터 시작하는 문자열로 다시 왼쪽 위, 오른쪽 위, .. 2019. 5. 24.