Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

G1sTagList

2014년 4월 27일 일요일

[Algospot] N-Queen

N-Queen

문제 ID : NQUEEN
시간제한 : 1000ms
메모리 제한 : 65536kb
제출횟수 : 973
정답횟수 (비율) : 522(53%)
출제자 : JongMan
출처 : 연습문제

N Queen 문제는 백트래킹 알고리즘에 자주 사용되는 문제라고 하네요.

백트래킹 알고리즘은 Queen을 하나하나 놓아보면서 제시 된 조건을 만족하는 해를 구해가는 것으로, 얼마나 빨리 탐색 가능여부를 판단하느냐가 속도를 줄이는데 관건일 듯 하다.

200894NQUEENGOnecpp630B정답71ms0

>>소스보기

2014년 4월 26일 토요일

[Algospot] 용감한 오리

용감한 오리

문제 ID : BRAVEDUCK
시간제한 : 1000ms
메모리 제한 : 65536kb
제출횟수 : 367
정답횟수 (비율) : 101(27%)
출제자 : Pekaz
출처 : 제 3회 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회

하나의 큐를 이용하면 간단히 해결이 가능하네요.
돌다리의 좌표를 점이라고 한다면.

우선 시작점을 큐에 넣고,

큐에서 선입선출에 따라 하나씩 점들을 빼며
이 점과 연결이 가능한(거리가 최대 점프력 J보다 작은) 점들을 큐에 넣으면 됩니다.

도착점이 큐에 들어간다면 YES.
큐에 더이상 넣을 수 있는 점이 없다면 NO.

여기서는 큐의 용량을 줄이기 위해 처음 점들의 좌표를 저장했던 배열을 이용하여 큐에 넣는 점들을 배열의 앞쪽 점들과 위치를 바꿔가며 진행하였습니다.

Algospot에서 제공하는 테스트 case 의 경우 시작점 보다는 끝점부터 연결해 가는게 좀 더 빠른 결과를 보는 듯 하네요.

200805BRAVEDUCKGOnecpp666B정답4ms1

>>소스보기

2014년 4월 19일 토요일

[Algospot] 최대 연속 부분합 찾기

최대 연속 부분합 찾기

문제 ID : MAXSUM
시간제한 : 5000ms
메모리 제한 : 65536kb
제출횟수 : 1837
정답횟수 (비율) : 458(24%)
출제자 : LIBe
출처 : 연습문제

먼저 입력받은 값부터 필요없는 부분을 소거해 주며, 합의 최대값을 구합니다.

입력값을 계속 더해가면서 0보다 작게 될 경우 해당 값은 이후 입력값에 도움이 되지 않으므로 소거,
초기화 하고 다시 값을 더해가며, 최대값을 비교해 나가면 간단히 답을 구할 수 있습니다.

199374MAXSUMGOnecpp272B정답155ms2

>>소스보기

[Algospot] 짝맞추기

짝맞추기

문제 ID : MEETING
시간제한 : 1000ms
메모리 제한 : 65536kb
제출횟수 : 2535
정답횟수 (비율) : 703(27%)
출제자 : LIBe
출처 : Algospot 1주년 모의고사

2년전에 풀었던 문제입니다.
남성회원과 여성회원을 내림 또는 오름차순으로 정렬 후 각 n 번째 남성회원과 여성회원의 차의 절대값을 모두 더하면 되는 간단한 문제네요.

199358MEETINGGOnecpp614B정답132ms0

>>소스보기

[Algospot] Weird Numbers


Weird Numbers

문제 ID :WEIRD
시간제한 : 3000ms
메모리 제한 : 65536kb
제출횟수 : 2264
정답횟수 (비율) : 446(19%)
출제자 : JongMan
출처 : Algospot 1주년 모의고사

2년 전에 풀었던 문제네요.
결과는 2년전의 2초 결과 보다 느리다고 나오지만.... 2년전 코드를 지금 돌리니
오히려 4초 대가 나오는.... 예상대로 해가 갈수록 테스트케이스가 증가하는 듯 하네요.

문제는 간단하게 입력값 n에 대해

1. 약수를 구한다.
2. 약수들의 조합의 합이 자신이 나오지 않음을 확인한다.

라고 할까요?

1번 약수를 구하는것은 간단하게 구할 수 있고,
2번을 얼마나 빠르게 구하느냐가 관건.
저는 약수의 총합에서 차가 n 보다 작거나 같을때까지
큰값순으로 선택하여 결과를 구했습니다.

199351WEIRDGOnecpp641B정답3ms4

>>소스보기

2014년 4월 13일 일요일

[Algospot] 0-1수열

0-1수열

문제 ID : ZEROONE
시간제한 : 2000ms
메모리 제한 : 65536kb
제출횟수 : 4590
정답횟수 (비율) : 945(20%)
출제자 : LIBe
출처 : 연습문제

문제자체는 간단한데 n의 값이 너무 커 시간제한이 걸리는 문제군요.
전처리 작업을 통해 시간복잡도를 O(n)으로 만들어야 시간안에 풀 수 있네요.

처음 입력받은 값을 탐색하며 0 또는 1이 몇번을 반복하고 있는지 기록한 후,
i,j 값의 큰값에서 작은 값을 뺀 값을 배열안의 값과 비교하여
작거나 같을 경우 Yes, 클 경우  No가 됩니다.

198526ZEROONEGOnecpp339B정답294ms7

시간을 많이 단축했다고 생각했는데도 더 빠른 결과를 내신분들이 많으시군요.
특히 가장 빠른 결과를 내신 err2083 님의 방법이 간단하고 좋은 것 같군요.(당연하겠지만)

>>소스보기

[Algospot] 남극기지

남극기지

문제 ID : ARCTIC
시간제한 : 1000ms
메모리 제한 : 65536kb
제출횟수 : 1702
정답횟수 (비율) : 404(23%)
출제자 : JongMan
출처 : 연습문제

최소비용신장 트리에 대한 문제이네요.
프림알고리즘을 응용하여 해결하였습니다.

총 10번만에 성공했네요.
머릿속으로 그린걸 바로 소스로 적용하다보니 어디가 틀렸는지 파악하기가 힘들군요.
결국 초기 설계부터 문제가 있어 다시 설계하였습니다.

프림알고리즘을 그대로 이용하였더라면 설계가 틀리지는 않았겠지만...
응용을 하여 좀 더 효율적으로 답을 구할 수 있는 방법을 찾다보니 설계에서 실수가 있었네요.
결국 결과는 최소비용신장트리는 아니게 되었군요.
하지만 이 문제의 답을 구하는데는 부합하고, 시간을 단축할 수 있었습니다.

198487ARCTICGOnecpp771B정답6ms10

결과는 만족스럽네요.
시간을 좀 더 단축할 수도 있을 것 같긴한데 소스만 길어지고 결과는 그대로 일 수도 있어 우선 이정도로 하겠습니다.

>>소스보기