달력

112017  이전 다음

  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  •  
  •  

'개발하면서/Algorithm'에 해당되는 글 7건

  1. 2014.11.15 algospot] CLOCKSYNC
  2. 2014.06.27 Geohash
  3. 2013.02.02 N-Queen
  4. 2012.08.29 문제로 풀어보는 알고리즘 0.3 생각해보기 풀이
  5. 2010.12.02 [Algorithm] Binary tree
  6. 2010.12.02 [Algorithm] Tree 기초개념
  7. 2010.02.12 넥슨 면접 1번문제 (2)

CLOCKSYNC


1년전에 JM북에 나온대로 무식하게 풀기로 풀었는데 다른 풀이법을 보니 신기했었다

그걸 지금 정리해본다.  분명히 1년전에는 이해했었는데, 다시 이해하는데 꽤나 버벅거림...;;;


10개의 스위치중에 한개의 스위치로만 시침을 변경할수있는 시계가 존재한다

1번 스위치에 11번 시계가 그렇고, 4번 스위치에 8번 시계가 그렇다


1번이나 4번으로 각각의 시계를 12시로 맞춰놓는다

예를들어 4번 스위치로 8번시계를 12시로 맞춰놓았다고 하면 다음할건 4번 스위치를 제외한 9개의 스위치에서

한개의 스위치로만 변경되는 시계가 있는지 살핀다

2번의 10번 시계가 그렇다


icpc IRC에서 Being님이 설명해준걸 이해한 후에 충격과 공포!!





저작자 표시 비영리
신고
Posted by 오산돌구

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값은 전혀 다른값이 나온다는 한계가 있다.

대충 비슷한값이 나온다.


latitude 위도, longitude 경도

위도는 적도를 기준으로 북 90, 남, 90이라 하고, 경도는 본초자오선(처음들어봄..)을 기준으로
동경 180, 서경 180라 한다.

Equator 적도, meridian 자오선


우선 어떻게 진행되는건지 알아보자


ezs42 라는 Geohash 값이 있다고 하면 아래 표의 의해서 

01101 11111 11000 00100 00010 로 표현이 된다.



그럼 가장 왼쪽에 있는 0을 기준으로 짝수에 해당하는건 경도, 홀수는 위도이다.

왼쪽 카드가 위도, 오른쪽 카드가 경도 요런느낌? ㅎㅎㅎ


출처:http://theknaveofclovers.tumblr.com/post/41608490725/card-shuffle


그럼 경도는 0111110000000, 위도는 101111001001 가 된다.

10진수로 변환하고 싶지만 여기선 아니다.

binary search Tree처럼 왼쪽에서 오른쪼으로 하나하나씩 위치를 좁혀가는 과정을 진행한다.

위도를 예를 들어보자.


위도는 -90 ~ +90이다. 비트값이 0이면 -90 ~ 0, 1이면 0 ~ +90인것이다.



오른쪽 마지막까지 가면 소숫점 둘째나 셋째에서 반올림해준다.


인코딩은 거꾸로 하면 되겄지?


https://github.com/lyokato/libgeohash

https://github.com/the42/cartconvert

Go, C로 구현한게 있는데...어렵다. 공부하자


참고로 서울 GeoHash는 wydm99uq이다.

http://geohash.org/wydm99uq

저작자 표시 비영리
신고
Posted by 오산돌구

JM북과 함께 PS의 재미를 알게되고 삼주전? 부터인가 topcoder의 재미를 알게되었습니다.

지금까지는 그냥 단순한 알고리즘 이해 수준에 머물렀다면 앞으로는 PS를 많이 경험할 생각입니다.


topcoder를 재미를 알게된 3주전부터 C++를 하고 다른사람의 C++소스도 보고 있는데

C랑 비슷하면서도 많이 틀린...그런 오묘한 기분이네요.


C++공부하면서 STL도 써볼겸  NQUEEN 문제를 풀어봤습니다.

뭐 돌아가긴 가는데..........실행시간이........안습...ㅠ,ㅠ.


결국은 pan[MAX_N][MAX_N]으로해서 걸리나 안걸리나 check하면서 풀었다. ; ) 아 재미져
제출하고 다른 사람소스 보니....흠....미친듯이 공부해야겠구나


저작자 표시 비영리
신고
Posted by 오산돌구

요새 심심할때 문제로 풀어보는 알고리즘책을 보고있습니다.

저같은 초보자한테 참 좋네요 : ) 




4년전에 알고리즘 트레이닝북으로 개발에 발을 들여놨던 기억이 나네요. 

정말 계란으로바위치기하듯이.......디버깅만 수천번한것같아요 ㅋㅋㅋㅋㅋㅋㅋㅋ (생각없이 무작정 코딩코딩~!! ㅎㅎ)


무튼 이번에 인사이트북에서 이벤트로  아래 이벤트를 열었습니다.

책보면서 생각 했던게 있어서 코딩시작.....;;

http://www.insightbook.co.kr/post/3814






요새 ruby를 시작해서 ruby로 하면 어떻게 될까.....해서 봤더니....엄머....rotate라는 함수가 있네요. 
아래와 같이 짜봤습니다.


 


c는 범위에 반을 나눠서(divide_into) 옮기려고 하는크기에 따라서 다르게했습니다. 
사용하는 메모리를 조금이나마 아껴보고자;;; 
ruby는 slice로 범위만큼 도려내고, rotate한다음에 다시 insert. 간단합니다. 
이런 재미있는 이벤트를 기획하신 인사이트북. 감사합니다~!!




저작자 표시 비영리
신고
Posted by 오산돌구

이진트리란 ? 모든 노드의 차수가 2 이상을 넘지 않는 트리를 말한다.
왼쪽자식노드는 부모노드의 값보다 작이야하며 오른쪽 자식노드는 부모노드의 값보다 커야한다.

이진트리 의 종류


<포화 이진트리> 각 레벨이 꽉차있는경우를 말한다. 레벨이 n이라고 할경우 포화이진트리의 경우 총 노드수는 2의 n승 -1 이다.






<완전 이진트리> 높이가 h인 트리의 경우 h-1까지는 모두 채워져있고 마지막 레벨 h은 다 채워져있지는 않지만
왼쪽에서 오른쪽으로 순서대로 채워져있는 트리




이진트리를 순회하는 방법은 preorder, inorder, postorder가 있다.
루트 방문순서를 기준으로 이름이 붙여진것으로 이해하면 좋다  pre : 처음, in : 중간,  post : 나중


쓰레드 이진트리란 ? 이진트리를 구성하다보면 null 포인터가 생기는데 이 널포인터를 순회할때
사용하는 구조를 쓰레드 이진트리라고 한다.
왼쪽의 널포인터는 현재노드 순회하기전에 노드를 가리키고, 오른쪽의 노드는 현재노드를 순회하고 난 다음의 노드를 가리킨다.

그리고 가장 처음 방문하는 노드의 왼쪽 널포인터, 가장 마지막에 방문하는 오른쪽 널포인트는 어느것도 가리키지 않으므로 헤드노드를 만들어서 그것을 가리키게 한다.

장점으로는 순회를 한후 다음 노드로 가기위해 왔던 노드들을 다시 지나가는 것을 불필요한 작업을 제거할 수 있다.

Animated Binary Tree : http://www.cs.jhu.edu/~goodrich/dsa/trees/btree.html
이진트리 코드 : http://www.cprogramming.com/tutorial/lesson18.html

저작자 표시 비영리
신고
Posted by 오산돌구


>다양한 트리를 배우기전에 트리에 나오는 명칭에 대해 알아보는 시간을 가져보자.
node
A, B, C, D, E, F, G, H, I, J, K, L처럼 데이터를 가지는 분기점을 말하고,
node와 node사이의 연결선을 edge라 한다.

Bparent nodeA 이며, parent node가 없는 node를
root
라하며 여기서는 A이다.
B
childE, F 이다.

degree(차수)란 child node의 수를 말한다.  A의 Degree는 3, C의 Degree는 1이다.
leaf node란 child node를 가지지 않는 node로서, 여기선 K, L, F, G, M, I, J 를 말한다.




Bsubtree는 위 그림과 같이 E, K, LF 이다.




level이란 root node를 1은 가진다고 가정하고 child node갈때마다 1을 더한값이다.

즉, root node로 부터의 거리 + 1 이다.


저작자 표시 비영리
신고
Posted by 오산돌구
현재 소장님이 작성하신 메모리 저장구조를 분석하고있습니다.일하다가 찾은 사이트에서 재미난 문제가 있어서 풀어봤습니다.(정말 일하다가? ㅋㅋㅋㅋㅋ)
Nexon 면접문제    (좀 오래됐음;;;)

뭐 genrator구하는것은 쉽게 되는데 1부터 5000까지의 숫자중 generator인지 아닌지를 체크해주는것이
메모리 저장구조에 있는것을 써먹으면 좋을것 같아 적용을 시작했습니다....

8bit * 625 = 5000~!! 딱떨어지네요 문제도 이걸원한게 아닐까 생각합니다.

generator에 해당하는 비트에 체크를 해주고 나중에 이 비트를 검사해서 selfnum여부를 판별하는 구조입니다.



원문에 해결한 답하고 45가 차이납니다......
아놔.......뭐가 잘못됐지? 라며 프린트도하고 비교도 했는데 모르겠습니다
지금보니 제가 generator에 대한 이해가 부족했네요. 한자리 자연수는 그 자체가 generator수로 처리를 했다는....

그냥 이거하면서 많은 생각을 할수 있었다는것에 대만족 ㅋㅋㅋ

보시면서 잘못된 부분이나 수정했으면 하는부분을 알려주시면 정말 감사하겠습니다~ : )
저작자 표시 비영리
신고
Posted by 오산돌구