달력

072018  이전 다음

  • 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
  • 31
  •  
  •  
  •  
  •  

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값들은 비슷한 값들이 나와 비교가 쉽다는 장점이 있다.


가까운 두 점이라도 Geohash값은 전혀 다른값이 나올수 있다. 위에서는 비슷하다고 해놓고 전혀 다른 값이 나온다고??

그 이유는 본초 자오선과 적도를 경게로 인접한 지역들은 위도 혹은 경도 값이 크게 달라서 Geohash도 다른 값이 나온다.


예로 적도가 지나가는 인도네시아를 보면 위치는 비슷하지만 Geohash는 전혀 다른 값이 나온다.

※ https://www.movable-type.co.uk/scripts/geohash.html



latitude 위도, longitude 경도

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

Equator 적도, meridian 자오선


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

※ 예제는 Wiki에 있는 것이다. https://en.wikipedia.org/wiki/Geohash

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

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

그럼 가장 왼쪽에 있는 0부터 시작해서 두칸씩 오른쪽 이동하면서 concat하면 011...이 나오고 이 값은 경도,

가장 왼쪽에 있는 0에서 한칸 옆에 있는 1부터 시작해서 두칸씩 오른쪽 이동하면서 concat해서 나온 값은 위도이다.




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


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


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

10진수로 변환하고 싶지만 아직 아니다.

왼쪽에서 오른쪽으로 읽어가면서 범위를 좁혀가는 과정을 진행한다.

위도를 예를 들어보자.


1이면 오른쪽, 0이면 왼쪽을 선택해서 범위를 좁혀가는 것이다.

위도는 처음 시작할땐 -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 오산돌구

ArrayList, CopyOnWriteArrayList, LinkedList, Vector, CheckedList,


ArrayList

멤버 변수에는 저장된 데이타의 갯수 size와 데이타를 담는(C에서 포인터처럼 가리키는) Object elementData[]가

정의되어 있다.


넉넉하게 elementData를 잡아놨다가 저장 공간이 부족하면 grow를 호출한다.

또한 elementData 중간에 데이타를 추가하거나, 제거할때는 그 뒷부분의 배열을 앞쪽으로 당기거나 뒤쪽으로 미는
동작을 수행한다.        마지막에 위치한  데이타를 삭제하고 추가시 elementData의 이동은 없다.


여기까지가 기본적인 데이타 추가/수정/삭제 얘기고 ArrayList 보면서 재미진 부분에 대해(지극히 주관적입니다;;) 얘기한다.


* removeAll, retailAll method  사실 이런게 있는지 처음 알았다... A.removeAll(B)는 A에 A-B의 데이타가 남고

A.retailAll(B)는 A와 B의 교집합 데이타가 A에 남는다.


* 데이타를 추가/삭제시 modCount++를 수행하는데 그 이유는 writeObject 에 있다.

writeObject 를 보면 Object를 쓰기전에 modCount를 저장해놨다가 쓰기 작업이 완료된 후, 쓰기 작업 중간에
추가/삭제 작업이 진행됐는지 체크한다.

* sublist가 있는데 사용법은 아래 url에 잘 나와있다.

http://stackoverflow.com/questions/6189704/how-to-take-a-valid-sublist-in-java  
전체가 아닌 부분에 대해서만 작업을 하고 싶을때 사용하면 좋다고 한다.



Vector에서 ArrayList와 가장 큰 차이점이 public method들이 synchronized를 사용한다는 점이다. (생성자와 enumeration 제외) 그래서 writeObject에서는 사용하지 않는다.


Stack은 Vector를 상속하고 5개의 method가 추가되었다. LIFO 동작을 위해 필요한 method들이다.
javadoc에서 더 확실한 LIFO를 사용하고싶다면 Deque를 사용하라고 한다.


LinkedList는 배열이 아닌 포인터(이렇게 말해도 되려나..)를 이용해 양방향 링크드 리스트를 구현하였다.

synchronized가 아니고, 다른 자료구조와는 다르게 modCount를 사용하지 않는다. 그래서 writeObject시 쓰는 중간에

추가/수정/삭제가 실행되도 에러가 발생되지 않는다. 


CopyOnWriteArrayList는 ArrayList를 thread-safe하게 만든 자료구조다.
멤버 변수로 ReentrantLock lock을 갖고있고, 추가/수정/삭제시 lock을 건다. 그리고 clone 시에는 얕은복사를 하고,
추가/수정/삭제시에 데이타를 갖고있는 array 복사를 한다.
추가/수정/삭제시 매번 복사가 발생하므로 데이타 변경이 빈번한곳에서는 쓰면 안될것같다.

Posted by 오산돌구
TAG Java

기초가 많이 부족하다는 것을 느껴서 다시 공부려고 하다가 JCF라는걸 알게되었습니다.

자바는 자료구조가 다 구현되어서 마냥 좋다고 쓰기만 했지 이런게 있는지도 몰랐네요.  

꾸준히 할지는...모르겠지만 한번 다 보도록 몸부림 쳐보려고요 : )   


================================================


java collection framework를 치면 기본적으로 다음과 같은 그림이 나온다.

 

Map은 Collection과 연관이 없는데 그 이유에  대해서 이렇게 설명하고 있다.

※ Map은 Collection과는 다른 구조이기 때문이다. Collection에는 add(Object o) 함수가 있는데

  Map은 key-value 구조이므로 Collection 인터페이스를 사용할 수 없다.

  그리고 Map은 keySet, valueSet, entrySet함수가 있는데 Collection에는 key-value쌍이 아니기 때문에 사용할 수 없다.

(http://howtodoinjava.com/2013/07/09/useful-java-collection-interview-questions/#why_map_not_extend_collection)



앞으로 Set, List, Queue, Map이 어떻게 구현됐는지 알아본다.


그리고 http://howtodoinjava.com/2013/07/09/useful-java-collection-interview-questions/ 의 질문과 답변들을

소스를 참고하여 알아가면 좋을것 같다.


ref : http://howtodoinjava.com/2013/07/09/useful-java-collection-interview-questions/#what_is_collection_in_java

http://www.cse.ohio-state.edu/software/2231/web-sw2/extras/slides/31.Java-Collections-Framework.pdf

Posted by 오산돌구
TAG Java

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 오산돌구


Heap sort란 Heap 자료구조를 이용해서 sort하는 방법입니다.

우선 Heap에 대해 알아야겠죠?
http://dol9.tistory.com/129  전에 포스팅한게 있네요 : )
root에는 max값 혹은, min값이 있습니다.

정렬이 안된 데이타를 heap 구조로 만들고, root의 값 하나꺼내고 heap구조 재정렬하고
root의 값 하나꺼내고 정렬하고, 이를 반복하면 정렬된 데이타가 생성됩니다.


단순한 방법이네요;;;

아래는 지금 두줄 설명한것을 코딩한것입니다. 
생각한것을 막힘없이 구현할수 있도록 많이 짜보고 피드백 받고 수정하는 일련의 과정을 반복해야겠지요...



실용주의 개발자를 향해 부단히 노력해야겠습니다.


Posted by 오산돌구

가장 간단한 알고리즘입니다.

만약 찾고자 하는

패턴은 ABTBA, 원본 텍스트는 AAABTABTBAB일 경우 아래 그림과 같이 비교를 합니다.

 


아래와 같은 방법으로 문자열을 찾습니다.

패턴첫글자와 원본을 비교하면서 일치가되는것을 찾습니다.

일치가 되었으면, 다음글자가 일치되는지 확인하고,

중간에 일치하지 않는다면 바로 다음칸으로 이동해서 다시 패턴 첫 글자부터 일치여부를 판단합니다.

구현이 간단하지만 비효율적인 문자열 검색 알고리즘 이네요.




Posted by 오산돌구

Heap이란 ? complete binary tree이고, 부모노드는 항상 자식노드보다 크거나 같음을 만족하는 자료구조이다.

 

출처: http://code.cloudkaksha.org/binary-tree/types-binary-tree

위 사진은 binary tree의 3가지 타입을 보여준다.

full binary tree는 잎 노드를 제외한 노드들의 자식 노드가 0개 혹은 2개인 트리를 말한다.
complete binary tree는 마지막 level을 제외한 모든 level에 노드가 채워져있고 마지막 level은 최소한 왼쪽으로 노드가 채워진 트리를 말한다. 
perfet binary tree는 잎노드를 제외한 모든 노드들의 자식노드가 2개인 트리를 말한다. 노드의 갯수는 2^n-1개 있다.(n은 마지막 level)

앞에서 본것처럼 Heap에는 max heap과 min heap이 있다.
이름에서도 알수 있듯이, max heap은 현재 저장하고 있는 값중 가장 큰 값을 root에 위치시키고,
min heap
은 가장 작은 값을 root에 위치시키는것을 말한다.

max heap
의 삽입, 삭제 과정을 보자.

<<<<<<<<<<<<<<<<<<<<
삽입>>>>>>>>>>>>>>>>>>>>>>>>
삽입 시 제일 마지막 노드에 추가후,
부모노드보다 추가된 노드의 키값이 크면, 바꾼다.(min heap은부모노드보다 작으면 바꿈)




<<<<<<<<<<<<<<<<<<<<
삭제>>>>>>>>>>>>>>>>>>>>>>>>

삭제된 노드를 채우기 위해서 마지막 level의 가장 오른쪽 노드를 삭제할 노드로 이동시킨 후,
자식노드와 비교하면서 Heap을 재구성 한다.

 검색에 Heap을 쓴다고해서 공부해 봄 . . .


Posted by 오산돌구

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

이진트리 의 종류


<Full Binary Tree> 모든 레벨의 노드가 꽉 차있는 트리를 말한다. Full Binary Tree의 총 노드수는 2 ^ n -1 이다.(n은 마지막 레벨)





<완전 이진트리> 높이가 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 오산돌구