개발하면서/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는 Gustavo Niemeyer가 geohash.org 웹서비스를 개발하면서 위도/경도를 표현하기 위해 개발한 geocode라고 한다. 좌표 2개를 하나로 표현할수있고, 주변의 Geohash값들은 비슷한 값들이 나와 비교가 쉽다는 장점이 있다. 가까운 두 점이라도 Geohash값은 전혀 다른값이 나올수 있다. 위에서는 비슷하다고 해놓고 전혀 다..
-
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..
-
2-3-4 tree개발하면서/Algorithm,DS,PS 2010. 12. 26. 11:04
2-3-4 트리란 이진트리가 한쪽으로 쏠리는 경우가 발생할수있는데 이를 해결하기위해 고안한 자료구조이다. 2-3-4 트리의 특징으로는 이진트리의 경우 하나의 노드는 하나의 데이터와 두개의 자식노드를 가질수 있는데 반해 2-3-4 트리의 경우, 세개의 데이터와 네개의 자식노드를 가질수있다. 2-3-4 트리라는 명칭은 가질수 있는 자식노드의 수때문에 나온것같다. 그렇다면 왜 1개 자식노드를 가지는 노드는 없을까? 삽입, 삭제과정에서 발생하는 연산을 보면 이해가 된다. split할때 자식이 두개인 노드생성, merge할땐 부모노드가 가진 자식노드 갯수가 3이상이므로(두개 이상의 데이타를가짐) 1개 자식노드를 가지는 노드는 있을수가 없다. (아....정말 설득력 없네요....) 마지막으로 데이타를 추가할때 이진..