1914

알고리즘/acmicpc 2015. 2. 22. 14:03 Posted by 아는 개발자

옛날에 못풀었던걸 풀면 기분이 상쾌한데 이번꺼는 뭔가 찜찜하다... 왜 예전에는 못풀었지?


내 예전 코드들은 스택을 통해서 위치를 찾아가는 방법이었다.

재귀함수를 쓴 현재 코드 보다는 훨씬 속도가 빠를 것 같은데

시간초과가 난 원인은 역시 printf와 cout의 차이인듯 하다..


또 2^100을 해결하는 문제가 있었는데

이거는 long long 두개를 써서 해결할수 있었다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2568  (0) 2015.02.25
2109  (0) 2015.02.22
1914  (0) 2015.02.22
9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17

9463

알고리즘/acmicpc 2015. 2. 21. 23:39 Posted by 아는 개발자

자력으로 해결하지 못했다. 다른사람이 푼 해설지 보고 어찌어찌 풀었는데

음... 시간 문제는 BIT를 이용해서 해결하는 거로 하고 여기서 명심해야할 거는

간선의 개수를 구하는 방법인데... 놀라웠다.


지금까지 나는 기를 쓰고 어케 풀어볼려고 생각했는데

간단히 현재까지의 간선의 개수 - 연결된 간선의 위치 까지의 간선수로 한번에 해결


음 그니까


read(N) - read(v[i].second)라는 코드로 한번에 해결했다.


왜 나는 이런게 떠오르지 않을까


지금 생각해보면 정말 간단한 원리인데 원래 N*N에 얽매여서 자력으로 해결하지 못하고ㅠ


또 신기한거는 시간차인데


출력형식이 시간에 영향을 많이 준다.

그런데 int보다는 long long이 출력할 때 빠르다.


printf("%d") 로 출력하면 시간초과가 뜨는데

printf("%lld")로 출력하면 시간 내에 들어온다.

출력 형식이 중요하긴 하나 보다. 다른 사람들도 모두 이렇게 출력하고 있다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2109  (0) 2015.02.22
1914  (0) 2015.02.22
9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17

BIT(Binary Indexed Tree)

알고리즘/자료구조 2015. 2. 21. 21:56 Posted by 아는 개발자

어려운거 많이 가르치기로 소문난 양교수님께서 왜 BIT를 설명 안해주셨을까

이렇게 감탄스러운 자료구조가 있는 줄 몰랐다.

RB Tree, AVL, 24 Tree이런거는 구현이 어려운데

이거는 구현도 어렵지 않고 편리하다


간단히 소개를 하면

기본적으로 어떤 data를 추가 할 때 O(1) 

그리고 그 data의 총 합을 구할 때는 O(n)이 걸린다.


하지만 BIT는 추가 할때도 O(logn) 총 합을 구할 떄도 O(logn) 시간이 걸리는

신기한 자료구조이다.


http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree

개념 설명이 내가 너무너무 부족하니 여기 있는 글을 통해서 이해하길...


나는 이것을 어떻게 응용할 것인지를 생각해보면...

위 사이트에서도 이미 응용 했지만


부분 합을 구하는 자료 구조 뿐만 아니라

부분 최소 값을 구하는 자료 구조로도 이용 할 수 있지 않을까 한다.


1차원을 사용하면 원래 값들을 모두 잃어버리겠지만

만약 내가 최소값을 찾길 원한다면 모두 다 돌아다니지 않아도 O(logn)시간에 찾을 수 있으니

효율적이다. 


LIS에서도 이 방법을 적용 할 수 있다고 하니

응용할 수 있는 방법이 무궁무진한 자료구조이다.




#include<iostream>

using namespace std;


int tree[20];

#define MaxVal 16

int read(int idx)

{

int sum = 0;

while(idx > 0){

sum += tree[idx];

idx -= (idx & -idx);

}


return sum;

}


void update(int idx, int val)

{

while(idx <= MaxVal)

{

tree[idx] += val;

idx += (idx & -idx);

}

}


int main()

{

for(int i = 1; i <= 16; i++)

update(i, i);


for(int i = 1; i <= 16; i++)

cout<<tree[i]<<endl;

return 0;

}


728x90

'알고리즘 > 자료구조' 카테고리의 다른 글

오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25
접미사배열  (0) 2015.02.24
KMP 알고리즘  (0) 2015.02.24
BIT(Binary Indexed Tree)  (0) 2015.02.21

2776

알고리즘/acmicpc 2015. 2. 21. 21:45 Posted by 아는 개발자

암기왕 문제..

예상외로 쉽게 풀릴수 있는 문제인데 괜히 어렵게 풀었다.

속도도 내 알고리즘이 더 빠를 줄 알았는데 오히려 더 느렸고 메모리도 더 많이 잡아먹고..

모두 한꺼번에 모아서 sort함수 때리고 앞의꺼랑 뒤에꺼가 같으면 ok라 놓고 풀었는데

계속 오답이 나왔다..


오답의 원인을 찾으니까 내 알고리즘은 검사를 두 번 실시하면 안에있는 거로 간주하는 문제가 있었다.. 아 진짜 이런 찐따가 따로없다..


binary_search라는 stl이 있어서 빠르게 해결 할 수 있었다... 이런거는 빨리 알아야 하는데

아 그리고 왠만하면 cin, cout을 쓰지 말고 #include<cstdio>에서 printf, scanf를 사용하는 습관을 들여야 겠다. cin, cout이 5배나 더 느리다니... 이것도 cin, cout 썼으면 분명 시간초과 떴을꺼다 ㄷㄷ


이 글 거의 읽는 사람은 내가 무슨 말 하는지 모를거다. 나도 다시 읽으면 모르겠다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1914  (0) 2015.02.22
9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17

ASYMTLING

알고리즘/algospot 2015. 2. 21. 12:31 Posted by 아는 개발자

내가 스스로 풀때는 n개를 채울 때 대칭인 경우와 비대칭인 경우로 나누어서

접근하려고 했는데 그렇게 풀 필요가 전혀 없었다.

책에서 양 끝에서부터 채워가는 방식을 읽고 정말 놀랬다 ㄷㄷㄷㄷ

이렇게 생각하면 정말 쉽게 풀리는 구나... 

재귀함수의 매력에 놀랬고 저자의 천재성에 감탄하고 나의 부족함을 다시한번 깨달았다 ㅠㅠ

양끝이 대칭이면 내부는 비대칭이어야 하고

양끝이 비대칭이면 내부는 대칭이어야 한다. 이 경우로 모든 경우의 수를 만들 수 있었다...

dp로 문제를 해결하는 두 가지 조건

- 모든 경우의 수를 포함해야 하며

- 중복되는 경우가 있어선 안된다

를 다시 한번 실감하는 순간이었다


728x90

'알고리즘 > algospot' 카테고리의 다른 글

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21