완전탐색7 [BOJ][20529] 가장 가까운 세 사람의 심리적 거리 문제 : www.acmicpc.net/problem/20529 완전탐색을 하면 O(N^3)의 시간복잡도를 가지는데 제한 사항을 보면 N이 10만이기 때문에 TLE가 발생할것이다. 시간을 줄일만한게 어디없나 보면 MBTI는 총 16가지이다. 이걸 사용할 수 있을 것 같다. 사람들은 16개 중 하나를 가지는데 최대한 겹치지 않게 MBTI를 가지고 있다고 가정하자. 그럼 16명의 사람까지는 동일한 MBTI를 가지지 않고 모두 고유한 값을 가질 수 있다. 16 ~ 16*2 명의 사람까지는 동일한 MBTI를 가지는 사람이 최대 두 명까지 나올 수 있다. 그러면 16 * 2 + 1 이상의 사람은 어떻게 되는가. 16*2 명의 사람들은 동일한 MBTI를 가지는 사람이 2명이 있다. (각 MBTI 모두 2명의 사람) .. 2021. 1. 1. [algospot][PI] 원주율 외우기 문제 : https://algospot.com/judge/problem/read/PI DP 문제로 풀었다. dp[ind] = 문자열[ind~끝]으로 구할 수 있는 최소 난이도. = 최소값(문자열[ind~ind+len)의 난이도 + dp[ind+len]) (3 2019. 6. 8. [algospot][JLIS] 합친 LIS 문제 : https://www.algospot.com/judge/problem/read/JLIS 배열 A, B의 인덱스(indA, indB)를 파라미터로 받는 재귀함수를 만든다. A[indA], B[indB] 는 증가 부분 수열에 반드시 포함된다고 가정한다. 따라서 A[indA], B[indB]의 최대 값보다 큰 배열 요소만이 증가 부분 수열에 추가 될 수 있다. int solve(indA, indB){ int maxNum = max(A[indA], B[indB]); for(nextInd = [indA + 1, N)){ if(maxNum < A[nextInd]) ans = max(ans, solve(nextInd, indB) + 1); } } 위 코드는 배열 A에 정답 배열에 들어갈 수 있는 다음 배열 .. 2019. 6. 7. [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. 이전 1 2 다음
