전체 글
-
접미사배열알고리즘/자료구조 2015. 2. 24. 21:23
문자열로 나오는 문제들은 접미사 배열을 이용해 어려운 문제들도 간단히 해결이 가능하다.접미사 배열은 말 그대로 어떤 문자들의 접미사들을 모아놓은 묶음이다.예를 들면 Algorithm이면 접미사들로는m, hm, thm, ithm, rithm, orithm, gorithm, lgorithm, Algorithm,이 있을 건데이것들을 사전 순데로 정리해서 Algorithmgorithmhmithmmorithmrithm으로 나타낸 것이다. 어떤 점에서 유용하냐 그냥 정렬만 해두었으면서 라 할수도 있다 하지만 이게 사전순으로 정리되어 있다는 점을 주목할 필요가 있다.우리가 어떤 문자열을 찾는다면처음부터 모두 뒤져보는 원시적인 방법을 써야하지만 O(N*N) 위 처럼 정리해두면 O(N*logN)이 걸린다. 단순하면서도 ..
-
KMP 알고리즘알고리즘/자료구조 2015. 2. 24. 18:38
예전에 KMP는 왜 KMP인가라는 문제를 보고 KMP이거 뭐지 장난하는건가 싶었는데;문자열에 관한 알고리즘인걸 책을 보고 깨달았다.. 이렇게 심오하고 환상적인 알고리즘이 있었다니 ㄷㄷ KMP알고리즘은 어떤 문자에서 특정 문자열이 존재하는지 확인하는 방법이다.예를 들어 길이가 N인 문자열에서 M이라는 문자열이 있는지 없는지 확인하고 싶으면N의 모든 위치에서 M의 시작문자와 비교해보는 방법이 있다. 이 방법은 O(MN)이 든다. 하지만 KMP알고리즘은 모두 비교하지 않고 접두사 접미사의 개념을 활용해서 푼다. 예를들어 abcabce -> 문자열 Mabcabcabcd -> 문자열 N 위의 M과 N을 비교했더니 abcabcabc까지는 같고 뒤에부터 달랐다.그런데 다음 비교를 N의 두번째 문자열 부터 시작 하지 ..
-
2109알고리즘/acmicpc 2015. 2. 22. 16:09
처음에 문제 이해못해가지고 왜 이런걸 틀리지 싶었는데 내가 틀렸다 ㅡㅡQnA에서 문제를 제대로 이해하고 다시 풀어서 맞았다. 이 문제의 핵심은 d 기간 내에는 어떤 날짜에 강연을 해도 상관 없다는거다 그래서 3 1 1 10 2 10 2 라는 인풋이 들어오면정답으로 20을 출력해야한다. 어떤 강연을 할 지 말지 결정하는 과정은 다음과 같다. 기간내에 강연 할 수 있는 빈 시간이 있다면강연을 하고 이미 강연이 다 차있다면 차있는 강연들 중에서 가장 돈을 조금 주는 강연과 비교 한 다음하려고 하는 강연이 더 돈을 많이 주면 가장 돈을 조금 주는 강연과 바꾸면 된다. 생각 과정은 그리 어렵지 않은데 자료 구조를 어떤걸 쓸 것인지가 고민이었다.최대 10000개의 강연이 있기 때문에 생각하기 쉬운 자료구조(n*n)..
-
9463알고리즘/acmicpc 2015. 2. 21. 23:39
자력으로 해결하지 못했다. 다른사람이 푼 해설지 보고 어찌어찌 풀었는데음... 시간 문제는 BIT를 이용해서 해결하는 거로 하고 여기서 명심해야할 거는간선의 개수를 구하는 방법인데... 놀라웠다. 지금까지 나는 기를 쓰고 어케 풀어볼려고 생각했는데간단히 현재까지의 간선의 개수 - 연결된 간선의 위치 까지의 간선수로 한번에 해결 음 그니까 read(N) - read(v[i].second)라는 코드로 한번에 해결했다. 왜 나는 이런게 떠오르지 않을까 지금 생각해보면 정말 간단한 원리인데 원래 N*N에 얽매여서 자력으로 해결하지 못하고ㅠ 또 신기한거는 시간차인데 출력형식이 시간에 영향을 많이 준다.그런데 int보다는 long long이 출력할 때 빠르다. printf("%d") 로 출력하면 시간초과가 뜨는데p..
-
BIT(Binary Indexed Tree)알고리즘/자료구조 2015. 2. 21. 21:56
어려운거 많이 가르치기로 소문난 양교수님께서 왜 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개념 설명이 내가 너무너무 부족하니 여기 있는 글을 통해서 이해하길... 나는 이것을 어떻게 응용할 것인지를 생각해보면..
-
2776알고리즘/acmicpc 2015. 2. 21. 21:45
암기왕 문제..예상외로 쉽게 풀릴수 있는 문제인데 괜히 어렵게 풀었다.속도도 내 알고리즘이 더 빠를 줄 알았는데 오히려 더 느렸고 메모리도 더 많이 잡아먹고..모두 한꺼번에 모아서 sort함수 때리고 앞의꺼랑 뒤에꺼가 같으면 ok라 놓고 풀었는데계속 오답이 나왔다.. 오답의 원인을 찾으니까 내 알고리즘은 검사를 두 번 실시하면 안에있는 거로 간주하는 문제가 있었다.. 아 진짜 이런 찐따가 따로없다.. binary_search라는 stl이 있어서 빠르게 해결 할 수 있었다... 이런거는 빨리 알아야 하는데아 그리고 왠만하면 cin, cout을 쓰지 말고 #include에서 printf, scanf를 사용하는 습관을 들여야 겠다. cin, cout이 5배나 더 느리다니... 이것도 cin, cout 썼으면 ..
-
ASYMTLING알고리즘/algospot 2015. 2. 21. 12:31
내가 스스로 풀때는 n개를 채울 때 대칭인 경우와 비대칭인 경우로 나누어서접근하려고 했는데 그렇게 풀 필요가 전혀 없었다.책에서 양 끝에서부터 채워가는 방식을 읽고 정말 놀랬다 ㄷㄷㄷㄷ이렇게 생각하면 정말 쉽게 풀리는 구나... 재귀함수의 매력에 놀랬고 저자의 천재성에 감탄하고 나의 부족함을 다시한번 깨달았다 ㅠㅠ양끝이 대칭이면 내부는 비대칭이어야 하고양끝이 비대칭이면 내부는 대칭이어야 한다. 이 경우로 모든 경우의 수를 만들 수 있었다...dp로 문제를 해결하는 두 가지 조건- 모든 경우의 수를 포함해야 하며- 중복되는 경우가 있어선 안된다를 다시 한번 실감하는 순간이었다