개발하면서/Algorithm,DS,PS
-
algospot] CLOCKSYNC개발하면서/Algorithm,DS,PS 2014. 11. 15. 19:34
CLOCKSYNC 1년전에 JM북에 나온대로 무식하게 풀기로 풀었는데 다른 풀이법을 보니 신기했었다 그걸 지금 정리해본다. 분명히 1년전에는 이해했었는데, 다시 이해하는데 꽤나 버벅거림...;;; 10개의 스위치중에 한개의 스위치로만 시침을 변경할수있는 시계가 존재한다 1번 스위치에 11번 시계가 그렇고, 4번 스위치에 8번 시계가 그렇다 1번이나 4번으로 각각의 시계를 12시로 맞춰놓는다 예를들어 4번 스위치로 8번시계를 12시로 맞춰놓았다고 하면 다음할건 4번 스위치를 제외한 9개의 스위치에서 한개의 스위치로만 변경되는 시계가 있는지 살핀다 2번의 10번 시계가 그렇다 icpc IRC에서 Being님이 설명해준걸 이해한 후에 충격과 공포!! int sync_switch[10][5] = { { 0, 1..
-
Geohash개발하면서/Algorithm,DS,PS 2014. 6. 27. 17:29
http://en.wikipedia.org/wiki/Geohash http://geohash.org/site/tips.html 어느 DB 프로젝트 issue를 보다가 GeoHash dataType 지원할 생각은 없냐는 글을 봤다. GeoHash? 처음 들어보는 hash다... 공부해보자. 공부라고 해봤자 wiki를 내 나름대로 정리하자는 거지 뭐... Geohash의 근간(?)이 되는 알고리즘은 1966년에 G.M. Morton 개발되었다고 한다. 간단히 살펴보면 지구를 커다란 네모로 보고 4등분을 한다. 그리고 나뉜 사각형 각각에 2개 비트를 할당한다. 00~11 총 4개 4개로 나뉜 사각형을 다시 한번 4등분 한다. 이때 첫 번째로 나누었을 때 비트는 두 번째, 첫 번째 비트에 값이 세팅되고 두 번째..
-
Java Collection Framework(JCF) intro개발하면서/Algorithm,DS,PS 2013. 8. 20. 14:54
기초가 많이 부족하다는 것을 느껴서 다시 공부려고 하다가 JCF라는걸 알게되었습니다. 자바는 자료구조가 다 구현되어서 마냥 좋다고 쓰기만 했지 이런게 있는지도 몰랐네요. 꾸준히 할지는...모르겠지만 한번 다 보도록 몸부림 쳐보려고요 : ) ================================================ java collection framework를 치면 기본적으로 다음과 같은 그림이 나온다. Map은 Collection과 연관이 없는데 그 이유에 대해서 이렇게 설명하고 있다.※ Map은 Collection과는 다른 구조이기 때문이다. Collection에는 add(Object o) 함수가 있는데 Map은 key-value 구조이므로 Collection 인터페이스를 사용할 수 없다..
-
N-Queen개발하면서/Algorithm,DS,PS 2013. 2. 2. 13:56
JM북과 함께 PS의 재미를 알게되고 삼주전? 부터인가 topcoder의 재미를 알게되었습니다. 지금까지는 그냥 단순한 알고리즘 이해 수준에 머물렀다면 앞으로는 PS를 많이 경험할 생각입니다. topcoder를 재미를 알게된 3주전부터 C++를 하고 다른사람의 C++소스도 보고 있는데 C랑 비슷하면서도 많이 틀린...그런 오묘한 기분이네요. C++공부하면서 STL도 써볼겸 NQUEEN 문제를 풀어봤습니다. #include #include #include #include using namespace std; #define MAX_N 12 struct Queen { int x, y; }; set ch; int solve(int row, int size, vector& queen); int main() { i..
-
문제로 풀어보는 알고리즘 0.3 생각해보기 풀이개발하면서/Algorithm,DS,PS 2012. 8. 29. 16:25
요새 심심할때 문제로 풀어보는 알고리즘책을 보고있습니다. 저같은 초보자한테 참 좋네요 : ) 4년전에 알고리즘 트레이닝북으로 개발에 발을 들여놨던 기억이 나네요. 정말 계란으로바위치기하듯이.......디버깅만 수천번한것같아요 ㅋㅋㅋㅋㅋㅋㅋㅋ (생각없이 무작정 코딩코딩~!! ㅎㅎ) 무튼 이번에 인사이트북에서 이벤트로 아래 이벤트를 열었습니다. 책보면서 생각 했던게 있어서 코딩시작.....;; http://www.insightbook.co.kr/post/3814 #include #include #include int data[] = {1, 2, 3, 4, 5, 6, 7, 8}; void right_rotate(int begin, int end, int k) { int length = end-begin+1; ..
-
[Algorithm]merge sort개발하면서/Algorithm,DS,PS 2011. 3. 13. 10:22
merge sort의 기본 개념은 아래 그림과 같습니다. 정렬되지 않은 데이타가 들어오면 쪼갤수 없을때까지 쪼갠다음에 합치면서 정렬을 해나가는 알고리즘입니다. 대부분 예제 소스에는 재귀함수로 merge sort를 구현했는데, 재귀함수로 안해도 되지않을까.....라는 생각이 시작이었습니다. 쪼갤수 없을때까지 쪼개는과정이 불필요하다는 생각이 들었고, 그래서 제가 구현한 소스에는 처음부터 끝까지 돌면서 처음에는 두개씩 정렬, 그 다음에는 네개, 그 다음에는 8개. 이런식으로 정렬을 수행합니다. 재귀함수를 안쓰다보니 추가 메모리가 필요하네요;;(안쓰고도 가능한게 있으면 알려주세요) 아래는 구현한 소스입니다. int merge_sort(void *data, int max, int data_size, cmp t_c..
-
[Algorithm] Heap sort개발하면서/Algorithm,DS,PS 2011. 2. 28. 21:32
Heap sort란 Heap 자료구조를 이용해서 sort하는 방법입니다. 우선 Heap에 대해 알아야겠죠? http://dol9.tistory.com/129 전에 포스팅한게 있네요 : ) root에는 max값 혹은, min값이 있습니다. 정렬이 안된 데이타를 heap 구조로 만들고, root의 값 하나꺼내고 heap구조 재정렬하고 root의 값 하나꺼내고 정렬하고, 이를 반복하면 정렬된 데이타가 생성됩니다. 단순한 방법이네요;;; 아래는 지금 두줄 설명한것을 코딩한것입니다. 생각한것을 막힘없이 구현할수 있도록 많이 짜보고 피드백 받고 수정하는 일련의 과정을 반복해야겠지요... // default max heap~!! int heap_sort(void *data, int max, int data_size,..
-
[Algorithm] Bubble sort, Insert sort, Select sort, Radix sort개발하면서/Algorithm,DS,PS 2011. 1. 5. 22:22
기존에 작성되어있는것을 지우고 다시 쓰려고 했지만, 내가 얼마나 초짜인지 각성하기위해 새롭게 포스팅을 합니다. 맨처음 작성한 소스 부끄러운 내소스 입니다. 기존에 DATA_TYPE을 한 이유가 대입과 swap때문에 했는데, 그럴필요없이, memxxx함수를 이용해 가능하다는것을 알고, (qsort에서 그렇게 하는것을 보고) 다시 짜보았습니다. 와.....너무좋다. 이렇게 간단한걸, 노가다로 짠 내자신이....흑흑 main.c #include "dol9_sort.h" int compare(const void *data1, const void *data2) { return *(char*)data1 - *(char*)data2; } int main(int argc, char *argv[]) { int input..