본문 바로가기

분류 전체보기657

[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.
[SPRING] Controller redirect @GetMapping("main") public String main() { if(특정조건){ "redirect:fail"; // '/fail' path로 리다이렉트 } return "main"; } 특정조건인 경우 특정 path로 redirect 하게 해준다. @GetMapping("main") public String main() { if(특정조건) { return "fail"; // fail.jsp 반환 } return "main"; } 특정조건인 경우 특정 페이지를 내려준다. (이 경우는 리다이렉트가 아님) 2019. 5. 30.
힙 정렬(Heap sort) 힙 정렬(Heap sort)는 최대 힙과 최소 힙을 이용해서 정렬하는 방법입니다. N개의 자료들을 이용해서 먼저 힙을 만들고 루트를 삭제하면서 정렬합니다. 삭제된 루트 노드의 자료를 차례대로 배열에 넣어 정렬하므로 루트 노드에 어떤 수가 들어가냐에 따라 내림차순 정렬과 오름차순 정렬이 정해집니다. 최대 힙은 루트 노드에 가장 큰 수가 들어가고, 최소 힙은 루트 노드에 가장 작은 수가 들어가기 때문에 최대 힙을 이용하면 내림차순 정렬을 최소 힙을 이용하면 오름차순 정렬을 할 수 있습니다. (물론 루트노드 데이터를 배열에 거꾸로 넣으면 어떤 힙을 이용하든 내림차순 정렬, 오름차순 정렬 둘 다 가능합니다.) 4 5 3 6 7 2 1 데이터를 이용하여 최대힙을 만들고 이를 내림차순 정렬 해보겠습니다. 최대 히프.. 2019. 5. 30.
[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.

티스토리툴바