본문 바로가기

알고리즘 문제408

[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.
[programmers] 베스트앨범 문제 : https://programmers.co.kr/learn/courses/30/lessons/42579# 수록 기준 1. 속한 노래가 많이 재생된 장르를 먼저 수록. 2. 장르 내에서 많이 재생된 노래를 먼저 수록. 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록 map를 이용했다. 사용한 map은 총 3가지. 1. key: 장르 / value : 재생수, 고유번호를 원소로 가지는 배열 => songMap 2. key: 장르 / value : 해당장르의 총 재생수 => cntMap 3. key: 해당장르의 총 재생수 / value: 장르 [cntMap의 key, value를 바꾼 map] => rcntMap 1번 songMap은 수록 기준 2, 3을 만족하기 .. 2019. 5. 7.

티스토리툴바