Best Square Root Method - Algorithm - Function (Precision VS Speed)
sqrt를 구하는 14개의 알고리즘을 비교한 글
sqrt(n)을 O($\sqrt{n}$)보다 빠르게 구할 수 없나를 알아보다 찾은 글
답은 못 얻었다.
결론은 std::sqrt 쓰는 게 빠르다.
2016년 5월 30일 월요일
2016년 5월 27일 금요일
11058 - 크리보드
https://www.acmicpc.net/problem/11058
출력 결과에 영향을 미치는 연산이 A를 그냥 누르는 거랑(+1), Ctrl-V (+복사했던 크기) 인데 클립보드에 복사해놓은 크기때문에 재귀로 짜는데 애를 먹었다.
복사한 크기만큼 늘어나기 때문에, Ctrl-V 를 하기 위해서는 이전에 Ctrl-A, Ctrl-C 가 꼭 필요하다.
문제에 적힌 연산을 순서대로 A, S, C, V 라고 한다면 $N=6$인 경우는 아래와 같이 가능하다.
$$ f(0) = 0, f(n) =
\begin{cases}
f(n-1) + 1, \\
f(k) * (n-k-1), & \text{if $k$ < n - 4 }
\end{cases}
$$
출력 결과에 영향을 미치는 연산이 A를 그냥 누르는 거랑(+1), Ctrl-V (+복사했던 크기) 인데 클립보드에 복사해놓은 크기때문에 재귀로 짜는데 애를 먹었다.
복사한 크기만큼 늘어나기 때문에, Ctrl-V 를 하기 위해서는 이전에 Ctrl-A, Ctrl-C 가 꼭 필요하다.
문제에 적힌 연산을 순서대로 A, S, C, V 라고 한다면 $N=6$인 경우는 아래와 같이 가능하다.
AAAAAA AAASCV AASCVV ASCVVV이 정도가 의미있는 타이핑인거같다. 타이핑을 n번한 것을 $f(n)$이라 하자. 그럼 위 4줄은 각각 $f(5)+1$, $f(3)*2$, $f(2)*3$, $f(1)*4$ 이다.
$$ f(0) = 0, f(n) =
\begin{cases}
f(n-1) + 1, \\
f(k) * (n-k-1), & \text{if $k$ < n - 4 }
\end{cases}
$$
알고스팟 - ROUTING
https://algospot.com/judge/problem/read/ROUTING
노이즈의 증폭이 최소가 되는 경로를 찾는 문제이다. 책에는 "노이즈 $c$ 는 언제나 1 이상 3 이하의 실수입니다" 라고 나와있다고 한다.
음.. 이게 딱히 문제는 없을 거 같지만, $c$의 범위를 몰라서 정답의 범위를 모르기때문에, 무한대값(INF)를 설정을 못한다. INF=987654321 로 설정하면 오답이 나온다.
987654321 보다 큰 경로만 남아있을 때, 방문하지 않은 정점들은 987654321 일테니 탐색하지 않아버린다.
근데 모든 노이즈가 3이면 어떻게 될까. 3^10000 ...!!
방문한 노드와 방문하지 않은 노드를 따로 구분해야한다. 다익스트라에서는 음수인 가중치가 없을테니 방문하지 않은 노드를 -1 로 해도 될거같다.
노이즈의 증폭이 최소가 되는 경로를 찾는 문제이다. 책에는 "노이즈 $c$ 는 언제나 1 이상 3 이하의 실수입니다" 라고 나와있다고 한다.
음.. 이게 딱히 문제는 없을 거 같지만, $c$의 범위를 몰라서 정답의 범위를 모르기때문에, 무한대값(INF)를 설정을 못한다. INF=987654321 로 설정하면 오답이 나온다.
987654321 보다 큰 경로만 남아있을 때, 방문하지 않은 정점들은 987654321 일테니 탐색하지 않아버린다.
방문한 노드와 방문하지 않은 노드를 따로 구분해야한다. 다익스트라에서는 음수인 가중치가 없을테니 방문하지 않은 노드를 -1 로 해도 될거같다.
2016년 5월 26일 목요일
SyntaxHighlighter 변경
블로거에 설정한 Syntax Highlighter가 갑자기 적용이 안됬다.
무슨일이지 싶어서 콘솔을 봤더니 불러오기 실패라고 한다. (SOF 글 - Failed to load resources when trying to perform syntax highlighting in a blog) 을 보니까, 전에 연결한 프로젝트가 없어졌다고 한다(예...??!)
Syntax Highlighter를 배포하는 제작자의 링크를 직접 연결하면 되지만.. 문제는 하이라이트를 적용하는 구문이 다르다 (!)
<pre name="code" class="언어"> 로 사용하고 있었는데, 이제 원래 구문인 <pre class="brush: 언어"> 로 써야한다. 이제까지 적었던 글들을 모두 바꿔야 하는가.... 허어......
우선 원저작자걸로 다시 연결하려했으나 link랑 script 태그에 적은 http 가 https 로 강제 변환됐다. 이유는 모르겠으나 http://itsonlycode.blogspot.com/2015/06/blogger-setup-syntaxhighlighter-for.html 를 참고하여 새로 설정했다.
지금 포스트 이후로는 class="brush:언어;" 형태로 쓰겠지만, 이전의 포스트들의 HTML 태그를 수정하지 않고 그대로 사용하고 싶다.
그래서 아래와 같은 코드를 추가했다.
무슨일이지 싶어서 콘솔을 봤더니 불러오기 실패라고 한다. (SOF 글 - Failed to load resources when trying to perform syntax highlighting in a blog) 을 보니까, 전에 연결한 프로젝트가 없어졌다고 한다
Syntax Highlighter를 배포하는 제작자의 링크를 직접 연결하면 되지만.. 문제는 하이라이트를 적용하는 구문이 다르다 (!)
<pre name="code" class="언어"> 로 사용하고 있었는데, 이제 원래 구문인 <pre class="brush: 언어"> 로 써야한다. 이제까지 적었던 글들을 모두 바꿔야 하는가.... 허어......
우선 원저작자걸로 다시 연결하려했으나 link랑 script 태그에 적은 http 가 https 로 강제 변환됐다. 이유는 모르겠으나 http://itsonlycode.blogspot.com/2015/06/blogger-setup-syntaxhighlighter-for.html 를 참고하여 새로 설정했다.
지금 포스트 이후로는 class="brush:언어;" 형태로 쓰겠지만, 이전의 포스트들의 HTML 태그를 수정하지 않고 그대로 사용하고 싶다.
그래서 아래와 같은 코드를 추가했다.
<script type='text/javascript'>
function addBrushToClass(){
var codes = document.getElementsByName("code");
for(var i in codes){
var originClass = codes[i].className;
codes[i].className = "brush: " + originClass +";";
//codes[i].setAttributes('name', 'converted');
}
}
window.setTimeout(function() {
addBrushToClass();
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.all();
}, 50);
</script>
2016년 5월 25일 수요일
1766 - 문제집
https://www.acmicpc.net/problem/1766
처음에는 문제의 접근 방향을 후위순회처럼 생각했다. 어떤 x번째를 하기 위해서 그 이전것을 무조건 해결해야하는 방식.
틀리고 나서 문제를 다시 이해했는데, 깨달은 테스트 케이스부터 말하자면 아래와 같다.
1번보다 4번을 먼저 풀어야하고, 3번보다 2, 5번을 먼저 풀어야한다. 1번을 풀기 위해서 4번을 풀어야하는데, 같은 우선순위에서 4번보다는 2번이 쉽다. (둘 다 1개의 문제 앞에 있음)
2번을 풀고 4번을 풀면, 1번이 풀리고 남은 5번을 풀면 3번이 풀린다.
처음에 생각한 대로라면 4 1 2 5 3 이 나와야하는데, 이게 틀려서 위 생각으로 다시 풀었더니 맞았다.
위상정렬 도중에 indegree가 없는 정점을 선택할때마다 번호가 작은(문제 난이도가 낮은) 정점을 선택하게 하면 된다.
처음에는 문제의 접근 방향을 후위순회처럼 생각했다. 어떤 x번째를 하기 위해서 그 이전것을 무조건 해결해야하는 방식.
틀리고 나서 문제를 다시 이해했는데, 깨달은 테스트 케이스부터 말하자면 아래와 같다.
5 3 4 1 2 3 5 3내가 생각한 이 입력의 정답은
2 4 1 5 3이다.
1번보다 4번을 먼저 풀어야하고, 3번보다 2, 5번을 먼저 풀어야한다. 1번을 풀기 위해서 4번을 풀어야하는데, 같은 우선순위에서 4번보다는 2번이 쉽다. (둘 다 1개의 문제 앞에 있음)
2번을 풀고 4번을 풀면, 1번이 풀리고 남은 5번을 풀면 3번이 풀린다.
처음에 생각한 대로라면 4 1 2 5 3 이 나와야하는데, 이게 틀려서 위 생각으로 다시 풀었더니 맞았다.
위상정렬 도중에 indegree가 없는 정점을 선택할때마다 번호가 작은(문제 난이도가 낮은) 정점을 선택하게 하면 된다.
2016년 5월 22일 일요일
2016 JNUPC을 마무리하며
제 11회 전북대학교 프로그래밍 경진대회를 마치며..
올해에도 문제 출제를 맡았다. 물량으로 공세하다보니 10문제 중 4문제나 만들었다. 난이도 때문에 못낸 아쉬운 문제들이 많다.특히 이번 대회는 강민이와 승균의 도움으로 대회 규모를 학교 전체로 넓히고, 8문제에서 10문제로 문제 수를 늘릴 수 있었다. BOJ에도 문제를 등록했다!
알고리즘이 별로 필요없는 5문제와, 알고리즘이 섞인 5문제로 출제했다. 알고리즘이 섞인 문제들 중 2~3문제는 꽤 정석적인 문제(BFS, LIS 등)를 냈다고 생각했는데, 문제 난이도에 비해 전체적인 solved 수는 낮았다. 내년 대회는 난이도를 어떻게 조정해야할지....
대회 당시에는 학부생들의 실력을 고려해서 일부 문제들은 Naive한 솔루션도 정답으로 처리하게 문제 조건과 데이터를 약간 느슨하게 했다. 하지만 I번 문제는 데이터 부실때문에 의도하지 않은 솔루션으로 풀려버렸다. 대회 순위 결과에는 영향이 없었지만 만약.... 윽. 내년에는 데이터를 더욱 꼼꼼하게!
ICPC 스타일의 스코어보드를 만들었지만 스크립트로 30초 단위 새로고침을 시켰고, 프리징도 없어서 이 기능들을 모두 완성하지 못함에 개인적으로 아쉬웠다.
더욱이 아쉬웠던 것은, 대회 내내 스코어보드가 재밌었다! 대회 종료 10초전에 ACCEPT를 받은 팀부터, 1, 2등의 순위싸움과 3~5등의 순위싸움. 3위 팀의 굳히기와 6위 팀의 역전 등..
내년에는 프리징과 애니메이션을 꼭 추가해야겠다.
대회 홈페이지 호스팅도 엉망이고, 온라인 저지 역시 혼돈의 카오스다. 개선해야할 문제점들이 너무 많다..
전대 프로그래밍 대회 타이틀때문에 계속 포스터를 바꾸고 (.....) 고생했지만, 이번 행사도 잘 마무리했다.
이번 대회로 고생한 강민이와 승균이의 노고에 심심한 감사를 표한다.
2016년 5월 18일 수요일
Codeforces Round #353 (Div. 2)
http://codeforces.com/contest/675
A. Infinite Sequence
$a$에서 $c$의 차이만큼 계속 더해서 $b$를 만들 수 있는가를 묻는 문제이다.
직접 돌리는건 안된다. 예를 들어, $c=0$ 이기만해도 반복문으로는 안된다.
$ a+k*c == b $ 가 되는 $k$가 존재하는 가? 다시말해, $(b-a) \mod c == 0$ 인가? 이다.
B. Restoring Painting
2x2크기로 묶었을때 나오는 사각형 안의 수들의 합이 모두 같아지게 하는 빈칸의 경우의 수를 묻는 문제였다. 문제의 핵심은 정가운데 $?$는 전체 합에 영향을 미치지 않는다는 것이다.
그럼 나머지 모서리에 있는 4개의 $?$ 중에 하나를 설정해보면 나머지 물음표가 모두 해결되서, 이게 가능한 수인지 판별이 가능하다.
한 모서리 칸을 1~$N$까지 하나씩 설정하면서 가능한 경우를 세면 된다.
근데 코딩이 말려서 계속 틀렸다. 흠.. 분발해야겠다.
A. Infinite Sequence
$a$에서 $c$의 차이만큼 계속 더해서 $b$를 만들 수 있는가를 묻는 문제이다.
직접 돌리는건 안된다. 예를 들어, $c=0$ 이기만해도 반복문으로는 안된다.
$ a+k*c == b $ 가 되는 $k$가 존재하는 가? 다시말해, $(b-a) \mod c == 0$ 인가? 이다.
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b, c;
while(~scanf("%d %d %d", &a, &b, &c)){
if(c == 0) puts( a == b ? "YES" : "NO" );
else if(c > 0 && b < a) puts("NO");
else if(c < 0 && b > a) puts("NO");
else puts( (b-a)%c == 0 ? "YES":"NO" );
}
return 0;
}
B. Restoring Painting
2x2크기로 묶었을때 나오는 사각형 안의 수들의 합이 모두 같아지게 하는 빈칸의 경우의 수를 묻는 문제였다. 문제의 핵심은 정가운데 $?$는 전체 합에 영향을 미치지 않는다는 것이다.
그럼 나머지 모서리에 있는 4개의 $?$ 중에 하나를 설정해보면 나머지 물음표가 모두 해결되서, 이게 가능한 수인지 판별이 가능하다.
한 모서리 칸을 1~$N$까지 하나씩 설정하면서 가능한 경우를 세면 된다.
근데 코딩이 말려서 계속 틀렸다. 흠.. 분발해야겠다.
2016년 5월 11일 수요일
2082 - 시계
https://www.acmicpc.net/problem/2082
각 자리에서 가능한 후보들을 추린다.
어떤 숫자가 나타나려면 다음과 같은 조건을 만족해야한다.
각 자리에서 가능한 후보들을 추린다.
어떤 숫자가 나타나려면 다음과 같은 조건을 만족해야한다.
- 시계에 불이 들어와있다면, 수 $X$도 그 자리가 켜져있어야한다.
- 수 $X$에 불이 꺼져있는 자리는, 시계에도 불이 꺼져있어야한다.
- 시계에 불이 꺼져있어도, 수 $X$에 불이 들어온것과는 상관이 없다.
1089 - 엘리베이터
https://www.acmicpc.net/problem/1089
2082번: 시계같은 구현문제일 줄 알고 가벼운 마음으로 시작했다.
풀다보니 모든 수의 합을 구하는 과정에서 DP로 작성하고 있었다.(하지만 DP로는 풀지 못했다.)
우선 각 자리에서 나올 수 있는 숫자들을 추려냈고, (이 과정은 2082번 풀이를 참고)
만들어진 수에 이전에 나온 경우의 수만큼 곱한다. 그만큼 중복으로 등장하기 때문이다.
각 자리에서 나올 수 있는 수를 괄호로 묶었을 때, $(0, 8)$, $(8, 9)$ (예제)와 같은 경우는 1의 자리에서 $8, 9$가 두번씩 나온다. 자리수가 길수록, 다른 자리에 가능한 수가 다양할수록 등장 횟수는 많아질 것이다. 그래서 DP를 생각했다.
가능한 숫자들의 합을 구하는 DP 코드는 아래와 같다.
뭔가 찝찝한 느낌이 있었는데 채점 40% 정도에서 틀렸다. 오버플로우가 아닐까 싶었다.
아래 입력은 각 자리마다 $(2, 8), (0, 2, 8), (3, 8, 9)$ 의 조합으로 수가 만들어질 수 있다.
가능한 수를 모두 적어보면 아래와 같다.
1의 자리에서 (3+8+9)가 6번 나온다. 10의 자리에서 (0+20+80)이 2번*3번 나온다.
이런식으로 수를 쪼개보면 $10^x$의 자리에서 나올 수 있는 수들의 합은 (자리에서 가능한 숫자들의 합) $\ast$ (전체 경우의 수 / 가능한 숫자의 개수) 이다.
지금 이걸 하려는 이유가 합을 모두 누적한다면 오버플로우가 나기 때문이라고 생각해서이다.
평균값은 (전체의 합)$/$개수이므로 어떤 수 하나의 비율은 (수 하나)$/$개수 이다. 각 숫자들의 비율을 모두 더해도 평균은 똑같이 구할 수 있다!
비율로 계산한다면 (자리에서 가능한 숫자들의 합) $\ast$ (전체 경우의 수 / 가능한 숫자의 개수) / (전체 경우의 수) 를 누적하면 되는 데 약분하면, (자리에서 가능한 숫자들의 합) / (가능한 숫자의 개수) 이다.
2082번: 시계같은 구현문제일 줄 알고 가벼운 마음으로 시작했다.
풀다보니 모든 수의 합을 구하는 과정에서 DP로 작성하고 있었다.
우선 각 자리에서 나올 수 있는 숫자들을 추려냈고, (이 과정은 2082번 풀이를 참고)
만들어진 수에 이전에 나온 경우의 수만큼 곱한다. 그만큼 중복으로 등장하기 때문이다.
각 자리에서 나올 수 있는 수를 괄호로 묶었을 때, $(0, 8)$, $(8, 9)$ (예제)와 같은 경우는 1의 자리에서 $8, 9$가 두번씩 나온다. 자리수가 길수록, 다른 자리에 가능한 수가 다양할수록 등장 횟수는 많아질 것이다. 그래서 DP를 생각했다.
가능한 숫자들의 합을 구하는 DP 코드는 아래와 같다.
typedef long long lld;
int n;
vector<int> cand[10]; // i번째 자리에 가능한 숫자들
int nCase[11];
lld DEC[11]={1,1,10,100,1e4,1e5,1e6,1e7,1e8,1e9};
lld dp[11];
lld sum(int pos){
if(pos >= n) return 0;
lld& r = dp[pos];
if(r != -1) return r;
r = 0;
for(int i=0; i<cand[pos].size(); ++i){
r += nCase[pos+1] * cand[pos][i] * DEC[n-pos] + sum(pos+1);
}
return r;
}
뭔가 찝찝한 느낌이 있었는데 채점 40% 정도에서 틀렸다. 오버플로우가 아닐까 싶었다.
아래 입력은 각 자리마다 $(2, 8), (0, 2, 8), (3, 8, 9)$ 의 조합으로 수가 만들어질 수 있다.
3 ###.###.### ..#...#...# .#......##. #...#.....# ###.###....위 입력의 정답은 $540.0$ 이다.
가능한 수를 모두 적어보면 아래와 같다.
203 208 209 223 228 229 283 288 289 803 808 809 823 828 829 883 888 889
1의 자리에서 (3+8+9)가 6번 나온다. 10의 자리에서 (0+20+80)이 2번*3번 나온다.
이런식으로 수를 쪼개보면 $10^x$의 자리에서 나올 수 있는 수들의 합은 (자리에서 가능한 숫자들의 합) $\ast$ (전체 경우의 수 / 가능한 숫자의 개수) 이다.
지금 이걸 하려는 이유가 합을 모두 누적한다면 오버플로우가 나기 때문이라고 생각해서이다.
평균값은 (전체의 합)$/$개수이므로 어떤 수 하나의 비율은 (수 하나)$/$개수 이다. 각 숫자들의 비율을 모두 더해도 평균은 똑같이 구할 수 있다!
비율로 계산한다면 (자리에서 가능한 숫자들의 합) $\ast$ (전체 경우의 수 / 가능한 숫자의 개수) / (전체 경우의 수) 를 누적하면 되는 데 약분하면, (자리에서 가능한 숫자들의 합) / (가능한 숫자의 개수) 이다.
풀고 난 후
long long으로 해도 오버플로우는 안 난다.lld DEC[11]={1,1,10,100,1e3,1e4,1e5,1e6,1e7,1e8,1e9};
배열에서 1e3를 빼먹어서 틀린거였다..2016년 5월 10일 화요일
1477 - 휴게소 세우기
https://www.acmicpc.net/problem/1477
정답을 미리 가정하고 정답의 범위를 점차 줄여나가보자.
만약 정답(휴게소가 없는 최대 구간)이 $x$라면 몇 개의 휴게소를 지어야할까?
길이가 $L$인 도로에는 $\{a_0, a_1, \dots, a_{n-1}\}$ 과 같이 휴게소가 있다고 하자.
최대 구간의 길이가 $x$라면 $a_0$과 $a_1$ 사이에는 $\frac{a_1-a_0-1}{x}$개 만큼의 휴게소가 필요하다.
$x$의 범위를 점차 줄여나간다면 휴게소의 개수($C_x$)가 원하는 $M$개 이상인 순간이 문제의 정답이다.
휴게소의 개수 $C_x$가 너무 많다면, 휴게소가 너무 많이 지어졌다는 의미이다. 너무 많이 지은 이유는 구간의 길이 $x$가 너무 좁았기 때문이다. $x$ 범위의 하한을 높이면 된다.
너무 적은 경우에는 반대로 $x$ 범위의 상한을 낮춘다.
도로의 처음과 끝 사이에도 휴게소를 세울 수 있으니 위치가 $0$인 곳과 위치가 $L$인 곳에도 가상의 휴게소가 있다고 생각하자.
정답을 미리 가정하고 정답의 범위를 점차 줄여나가보자.
만약 정답(휴게소가 없는 최대 구간)이 $x$라면 몇 개의 휴게소를 지어야할까?
길이가 $L$인 도로에는 $\{a_0, a_1, \dots, a_{n-1}\}$ 과 같이 휴게소가 있다고 하자.
최대 구간의 길이가 $x$라면 $a_0$과 $a_1$ 사이에는 $\frac{a_1-a_0-1}{x}$개 만큼의 휴게소가 필요하다.
$x$의 범위를 점차 줄여나간다면 휴게소의 개수($C_x$)가 원하는 $M$개 이상인 순간이 문제의 정답이다.
휴게소의 개수 $C_x$가 너무 많다면, 휴게소가 너무 많이 지어졌다는 의미이다. 너무 많이 지은 이유는 구간의 길이 $x$가 너무 좁았기 때문이다. $x$ 범위의 하한을 높이면 된다.
너무 적은 경우에는 반대로 $x$ 범위의 상한을 낮춘다.
도로의 처음과 끝 사이에도 휴게소를 세울 수 있으니 위치가 $0$인 곳과 위치가 $L$인 곳에도 가상의 휴게소가 있다고 생각하자.
2865 - 나는 위대한 슈퍼스타K
https://www.acmicpc.net/problem/2865
본선에 $K$명만 나갈수 있다. 한 사람이 여러 장르를 부를 수는 없지만, 여러 사람이 같은 장르를 부를 수는 있다.
굵은 글씨가 문제의 핵심인 것 같다. 각 참가자의 제일 높은 점수를 더하면 된다.
$K$명만 선발해야하므로, 최고점수가 높은 순으로 $K$명을 고른다.
본선에 $K$명만 나갈수 있다. 한 사람이 여러 장르를 부를 수는 없지만, 여러 사람이 같은 장르를 부를 수는 있다.
굵은 글씨가 문제의 핵심인 것 같다. 각 참가자의 제일 높은 점수를 더하면 된다.
$K$명만 선발해야하므로, 최고점수가 높은 순으로 $K$명을 고른다.
7808 - Email from The Professor
https://www.acmicpc.net/problem/7808
문자열을 n개만큼 한 줄씩 잘라서 각 칸마다 대응되는 key를 새로운 줄로 삼는 문제이다.
vector로 각 문자를 대응되는 줄(key)에 차곡차곡 붙였다.
마지막엔 각 줄을 일렬로 다시 출력했다.
문자열을 n개만큼 한 줄씩 잘라서 각 칸마다 대응되는 key를 새로운 줄로 삼는 문제이다.
vector로 각 문자를 대응되는 줄(key)에 차곡차곡 붙였다.
마지막엔 각 줄을 일렬로 다시 출력했다.
10465 - Rolling Encryption
https://www.acmicpc.net/problem/10465
이전 $k$의 길이만큼에서 가장 많이 출현한 알파벳만큼 shift한다. 오른쪽으로 이동하면서 이전 길이 $k$만큼의 빈도를 계속 갱신했다. $k \le 10,000$와 $c \le 100,000$가 생각보다 커서 라인 스위핑하듯이 했다. 이걸 스위핑이라고 해도 될지 모르겠다.
이전 $k$의 길이만큼에서 가장 많이 출현한 알파벳만큼 shift한다. 오른쪽으로 이동하면서 이전 길이 $k$만큼의 빈도를 계속 갱신했다. $k \le 10,000$와 $c \le 100,000$가 생각보다 커서 라인 스위핑하듯이 했다. 이걸 스위핑이라고 해도 될지 모르겠다.
1700 - 멀티탭 스케줄링
https://www.acmicpc.net/problem/1700
멀티탭에 k개 이상 꽂아야하는 순간 하나를 뽑는다. 뽑아야할 녀석은 가장 나중에 사용되는 플러그부터 뽑는다. 그런게 없다면 아무거나 뽑는다.
멀티탭에 k개 이상 꽂아야하는 순간 하나를 뽑는다. 뽑아야할 녀석은 가장 나중에 사용되는 플러그부터 뽑는다. 그런게 없다면 아무거나 뽑는다.
2016년 5월 8일 일요일
3770 - 대한민국
https://www.acmicpc.net/problem/3770
http://www.spoj.com/problems/MSE06H/
세그먼트 트리로 풀었다.
위 그림을 참고해서 풀었음. 다듬어서 다시 업로드 예정
http://www.spoj.com/problems/MSE06H/
세그먼트 트리로 풀었다.
위 그림을 참고해서 풀었음. 다듬어서 다시 업로드 예정
2016년 5월 7일 토요일
12014 - 주식
https://www.acmicpc.net/problem/12014
주어진 배열의 LIS의 길이가 $K$ 이상이면 1, 아니면 0을 출력하면 된다.
$N$의 범위로 보아 시간복잡도가 적당한 LIS를 사용한다. 길이만 알면 되서 $O(NlogN)$으로 작성했다.
국정원 소프트웨어 SW 공채 역량평가 샘플 예제
(여기 참조)
(여기 참조)
주어진 배열의 LIS의 길이가 $K$ 이상이면 1, 아니면 0을 출력하면 된다.
$N$의 범위로 보아 시간복잡도가 적당한 LIS를 사용한다. 길이만 알면 되서 $O(NlogN)$으로 작성했다.
2016년 5월 6일 금요일
알고스팟 - QUANTIZE
https://algospot.com/judge/problem/read/QUANTIZE
사용할 숫자의 개수를 "그룹의 개수"라 생각했다. 한 그룹에서 오차의 합이 최소가 되려면 그룹의 평균을 기준(양자화하는 숫자)으로 잡아야한다.
모듈화를 제대로 못해서 코딩이 계속 꼬였다. 다음부터는 함수로 적절히 쪼개서 문제를 푸는 데 방해되지 않도록 해야겠다.
사용할 숫자의 개수를 "그룹의 개수"라 생각했다. 한 그룹에서 오차의 합이 최소가 되려면 그룹의 평균을 기준(양자화하는 숫자)으로 잡아야한다.
모듈화를 제대로 못해서 코딩이 계속 꼬였다. 다음부터는 함수로 적절히 쪼개서 문제를 푸는 데 방해되지 않도록 해야겠다.
2016년 5월 3일 화요일
알고스팟 - WILDCARD
https://algospot.com/judge/problem/read/WILDCARD
패턴 문자열 $p$와 비교 대상 $s$을 한자리씩 비교한다. 이 때, 비교하는 위치는 서로 다를 수 있다.
비교하고자하는 $p$의 위치를 $i$, $s$의 위치를 $j$ 라 하면, 각 자리의 비교 함수 $f(i, j)$의 진행은 아래와 같이 조건 분기가 가능하다.
- $p_i$와 $s_j$가 같거나 $p_i$가 ?인 경우, $f(i+1, j+1)$ 을 확인한다.
- $p_i$가 *인 경우, *가 $[s_j, s_k]$ ($k$는 문자열 $s$의 끝 위치) 까지의 범위를 대응시킬 수 있다. 하나씩 확인해본다.
- $p_i$와 $s_j$가 다른 경우, 패턴을 찾을 수 없다.
- 종료조건 : 패턴에 있는 모든 문자에 대해 검색이 끝났을 때, 비교 문자열 역시 검색을 마친(끝 위치에 있는) 경우라면 패턴에 부합한다는 뜻이다.
패턴 문자열 $p$와 비교 대상 $s$을 한자리씩 비교한다. 이 때, 비교하는 위치는 서로 다를 수 있다.
비교하고자하는 $p$의 위치를 $i$, $s$의 위치를 $j$ 라 하면, 각 자리의 비교 함수 $f(i, j)$의 진행은 아래와 같이 조건 분기가 가능하다.
- $p_i$와 $s_j$가 같거나 $p_i$가 ?인 경우, $f(i+1, j+1)$ 을 확인한다.
- $p_i$가 *인 경우, *가 $[s_j, s_k]$ ($k$는 문자열 $s$의 끝 위치) 까지의 범위를 대응시킬 수 있다. 하나씩 확인해본다.
- $p_i$와 $s_j$가 다른 경우, 패턴을 찾을 수 없다.
- 종료조건 : 패턴에 있는 모든 문자에 대해 검색이 끝났을 때, 비교 문자열 역시 검색을 마친(끝 위치에 있는) 경우라면 패턴에 부합한다는 뜻이다.
피드 구독하기:
글 (Atom)