달력

012018  이전 다음

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

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

  1. 2014.11.15 algospot] CLOCKSYNC
  2. 2014.06.27 Geohash
  3. 2013.08.20 Java Collection Framework(JCF) List
  4. 2013.08.20 Java Collection Framework(JCF) intro
  5. 2013.02.02 N-Queen
  6. 2012.08.29 문제로 풀어보는 알고리즘 0.3 생각해보기 풀이
  7. 2010.12.03 [Algorithm] Brute Force
  8. 2010.12.02 [Algorithm] Binary tree
  9. 2010.12.02 [Algorithm] Tree 기초개념
  10. 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 오산돌구

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과 연관이 없는데 그 이유에  대해서 이렇게 설명하고 있다.(http://howtodoinjava.com/2013/07/09/useful-java-collection-interview-questions/#why_map_not_extend_collection)

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

이므로 다르다. 그리고 Map은 keySet, valueSet, entrySet함수가 있는데 Collection에는 지원하지 않는다.


List, Queue가 어떻게 구현되었는지 알아본다.


마지막으로 http://howtodoinjava.com/2013/07/09/useful-java-collection-interview-questions/

소개한 질문들을 소스를 보면서 파악해본다.


Map은 삼실청년 블로그에 잘 설명되어있어서 패스하고 Set은 Map을 멤버 변수로 가지고 동작하는 자료구조라 패스!!


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

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

만약 찾고자 하는

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

 


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

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

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

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

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




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