달력

012019  이전 다음

  •  
  •  
  • 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 오산돌구
merge sort의 기본 개념은 아래 그림과 같습니다.
사용자 삽입 이미지


정렬되지 않은 데이타가 들어오면 쪼갤수 없을때까지 쪼갠다음에 합치면서 정렬을 해나가는 알고리즘입니다.
대부분 예제 소스에는 재귀함수로 merge sort를 구현했는데요.  재귀함수로 안해도 되지않을까.....
라는 생각이 시작이었습니다.

쪼갤수 없을때까지 쪼개는과정이 불필요하다는 생각이 들었고, 그래서 제가 구현한 소스에는
처음부터 끝까지 돌면서
처음에는 두개씩 정렬, 그 다음에는 네개, 그 다음에는 8개.
이런식으로 정렬을 수행합니다.  재귀함수를 안쓰다보니 추가 메모리가 필요하네요;;(안쓰고도 가능한게 있으면 알려주세요)
아래는 구현한 소스입니다.


Posted by 오산돌구


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

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

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


단순한 방법이네요;;;

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



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


Posted by 오산돌구
기존에 작성되어있는것을 지우고 다시 쓰려고 했지만, 내가 얼마나 초짜인지 각성하기위해 새롭게 포스팅을 합니다.
맨처음 작성한 소스 부끄러운 내소스 입니다.
기존에 DATA_TYPE을 한 이유가 대입과 swap때문에 했는데, 그럴필요없이, memxxx함수를 이용해 가능하다는것을 알고,
(qsort에서 그렇게 하는것을 보고) 다시 짜보았습니다. 와.....너무좋다. 이렇게 간단한걸, 노가다로 짠 내자신이....흑흑
main.c dol9_sort.h dol9_sort.c
Posted by 오산돌구
2-3-4 트리란
이진트리가 한쪽으로 쏠리는 경우가 발생할수있는데 이를 해결하기위해 고안한 자료구조이다.

2-3-4 트리의 특징으로는
이진트리의 경우 하나의 노드는 하나의 데이터와 두개의 자식노드를 가질수 있는데 반해
2-3-4 트리의 경우, 세개의 데이터와 네개의 자식노드를 가질수있다.

2-3-4 트리라는 명칭은 가질수 있는 자식노드의 수때문에 나온것같다.
그렇다면 왜 1개 자식노드를 가지는 노드는 없을까?
삽입, 삭제과정에서 발생하는 연산을 보면 이해가 된다.   split할때 자식이 두개인 노드생성, merge할땐 부모노드가 가진 자식노드 갯수가 3이상이므로(두개 이상의 데이타를가짐) 1개 자식노드를 가지는 노드는 있을수가 없다
(아....정말 설득력 없네요....)

마지막으로 데이타를 추가할때 이진트리는 아래로 트리가 커가지만 2-3-4 트리는 위로 커간다. (split)
데이타를 삭제할때 이진트리는 아래에서 줄어들지만 2-3-4트리는 위에서 줄어든다 (merge)



이젠 데이터 삽입, 삭제연산에 대해 알아보자.
들어가기에 앞서 알아야할 것이 있는데,  2 node 란 1개 데이터 2개 자식노드, 3 node란 2개 데이터 3개 자식노드,
4 node란? ????~~~~~~ 이다 ㅎㅎㅎ

우선 삽입 연산이다.

삽입연산에서는 이것만 기억하면 된다. 삽입 연산중 만나는 4 node에 대해서 split해주면 된다.

총 두개의 그림 삽입


1부터 10까지 차례대로 삽입






다음은 삭제 연산이다.

삭제 연산에서 가장 중요한것은 2-3-4 트리의 삭제연산은 leafnode에서만 이루어진다는 점이다.
한가지 의문점이 든다.  삭제하려는 데이터가 internal node 에 위치한다면?
그럴때는 leafnode의 데이타중에 삭제하려는 데이터와 가장 가까운 노드를 찾아 서로 교환하면 된다.

삭제하려는 데이타의 바로 앞 자식노드 이동후 그 자식노드와 연결된 leafnode중에서 가장 큰 데이타와 교환한후, leafnode에 위치한 데이타를 삭제해주면된다.



삭제 연산중 split 같이 균형을 맞추기위해 하는게 있다. 바로 merge와 redistribute이다.
삽입 연산과는 반대로 삭제 연산 중 만나는 2  node에 대해서 두 연산중 하나를 실행한다.
두개의 연산중 하나를 선택하는 기준은 형제노드의 갯수인데, 형제노드가 2 node면 merge,
3, 4 node면 redistribute를 수행한다. 
그림에서 형제노드 선택은 해당 노드 오른쪽으로 했다. 가장끝이라면 왼쪽 노드를 선택하면 되죠...허허

merge는 부모노드 한개, 형제노드 한개 데이타를 합쳐서 해당 노드를 데이타 3개를 만든다.




예외적으로 root의 경우 형제 노드가 존재하지 않으므로 두개(데이타가 한개일때 merge할지 redistribute할지 정하므로)의 자식노드의 데이터가 한개일 경우 merge를 실행한다. 


데이타 삽입의 경우 split을 통해 상위노드로 데이타로 추가되고, 반복되다가 결국 root 노드가 4node가 되면 split가 되고, 높이가 1 증가된다.
데이타 삭제의 경우 redistribute를 통해 상위 노드의 데이타가 줄어들고, redistribute, merge를 반복되다가 root 노드가 2 node가 되면 높이가 1 감소되는것이다.

높이를 유지하는 이유는 노드 추가시 밑에서 증가하는게 아니라 위에서 증가하고, [root에서 split이 발생할때]
노드 삭제시 밑에서 줄어드는게 아니라, 위에서 줄어든다. [root에서 merge가 발생할때]
 이것을 생각한 사람.....좀 짱인듯......

다른 self balancing 자료구조도 이와같이 방식으로 하지않았을까.....라는 생각을 해보며 red-black 트리를 공부하자.



개념 참조 : 
http://tultul.net/board/list.php?a=050000000000000000000003&w=




Posted by 오산돌구
sort 세개를 한꺼번에 포스팅하는 이유는?
세개 sort에 대해서는 자료가 너무 많아서 굳이 설명 하지 않아도 될 것같아서 였습니다.

그럼 지금 왜 포스팅을 하냐?
위 세개 알고리즘에 대한 소스를 공유하고자 입니다. 더 나은 방법이나 잘못된 부분이 있으면 알려주세요.
지금 개념 파악후 혼자 낑낑대면서 하고있는데.....정말 제가 부족하다는걸 뼈저리게 느끼고 있습니다.

int와 char을 지원하고 구조체 정렬까지 하려고 했는데 이 부분에 대해선 아직 머리가 안돌아가네요 허허허

dol9_sort.c, dol9_sort.h main.c 로 구성되어있습니다.

조금 수정한 내소스

dol9_sort.h
#include "dol9_sort.h"

int main(int argc, char *argv[])
{
	//int input[10] = {3, 2, 5, 6, 1, 4, 8, 9, 7, 0};
	char input[10] = {'d', 'c', 'e', 'b', 'w', 'z', 'q', 'x'};
	int data_size;

	data_size = 8;

	sort_init("char");
	//sort_init("Int");

	print_data(input, data_size);

	select_sort(input, data_size);

	print_data(input, data_size);
	
	return 0;
}
dol9_sort.h dol9_sort.c
#include "dol9_sort.h"
#include <string.h>

static short DATA_TYPE;

int compare(void *data1, void *data2);
void swapdata(void *data1, void *data2);


int sort_init(char *data_type){
	char t_data_type[10];
	int i;
	
	if (strlen(data_type) > 9) {
		printf("data_type error [char or int plz~~]\n");
		return 1;
	}

	i = 0;
	while(*data_type != '\0') {
		if (*data_type > 96 && *data_type < 123) {
			t_data_type[i] = (char)*data_type - 32;		
		}
		else if (*data_type > 64 && *data_type < 91) {
			t_data_type[i] = (char)*data_type;
		}
		else
			return 1;
		data_type++;
		i++;
	}		
	t_data_type[i] = '\0';

	if (strcmp(t_data_type, "INT")==0) {
		DATA_TYPE = 4;
	}
	else if (strcmp(t_data_type, "CHAR")==0) {
		DATA_TYPE = 1;
	}

	return 0;
}

int bubble_sort(void *data, int data_size)
{
	int i, j;

	for(i = 0; i < data_size-1; i++) {
		for(j = 0; j < data_size-1; j++) {
			if(compare((data+(j*DATA_TYPE)), (data+((j+1)*DATA_TYPE))) == 1) { 
				swapdata((data+(j*DATA_TYPE)), (data+((j+1)*DATA_TYPE)));
			}
		}
	}
	return 1;
}

int select_sort(void *data, int data_size)
{
	int i, j;
	int min, minidx;

	minidx = 0;
	if (DATA_TYPE == 4) {
		for(i = 0; i < data_size-1; i++) {
	min = 2147483647;
			for(j = i+1; j < data_size; j++) {
				if (compare(&min, ((int*)data+j+1)) == 1) {
					minidx = j;
					min = *((in*)data+j);
				}
			}
			swapdata((int*)data+i, (int*)data+minidx);	
		}
	}
	else if (DATA_TYPE == 1){
		for(i = 0; i < data_size; i++) {
	min = 127;
			for(j = i; j < data_size; j++) {
				if (compare(&min, ((char*)data+j)) == 1) {
					minidx = j;
					min = *((char*)data+j);
				}
			}
			swapdata((char*)data+i, (char*)data+minidx);	
		}
	}
	return 1;
}

int insert_sort(void *data, int data_size)
{
	int value, movesize;
	int i, j;
	
	if (DATA_TYPE == 4) {
		for (i = 1; i < data_size; i++) {
			value = *(((int*)data)+i);
			for(movesize=0, j = i; j > 0 && *(((int*)data)+j-1)>value; j--) {
				movesize++;
			}
			if ( movesize ) {
				memmove(data+j+1, data+j, movesize);
				*((int*)data+j) = value;
			}
			*((int*)data+j) = value;
		}
	}
	else if (DATA_TYPE == 1) {
		for (i = 1; i < data_size; i++) {
			value = *(((char*)data)+i);
			for(movesize=0, j = i; j > 0 && *(((char*)data)+j-1)>value; j--) {
				movesize++;
			}
			if ( movesize ) {
				memmove(data+j+1, data+j, movesize);
				*((char*)data+j) = value;
			}
		}
	}
	return 1;
}

int compare(void *data1, void *data2)
{
	int rvalue = 0;
	if (DATA_TYPE == 4)
    	rvalue = *(int*)data1 > *(int*)data2 ? 1 : \
                          *(int*)data1 == *(int*)data2 ? 0 : -1;
	else if (DATA_TYPE == 1)
		rvalue = *(char*)data1 > *(char*)data2 ? 1 : \
                                     *(char*)data1 == *(char*)data2 ? 0 : -1;
	
	return rvalue;
}

void swapdata(void *data1, void *data2)
{
	int itemp;
	char ctemp;

	if (DATA_TYPE == 4) {
		itemp = *(int*)data1;
		*(int*)data1 = *(int*)data2;
		*(int*)data2 = itemp;
	}
	else if (DATA_TYPE == 1) {
		ctemp = *(char*)data1;
		*(char*)data1 = *(char*)data2;
		*(char*)data2 = ctemp;
	}
}


void print_data(void *data, int data_size)
{
    int i;
	if (DATA_TYPE == 4) {
		for (i = 0; i < data_size; i++) {
			printf("input[%d] : %d\t", i, *(int*)(data+i));
			if (i%3==0) {
				printf("\n");
			}
		} 
	}
	else if (DATA_TYPE == 1) {
		for (i = 0; i < data_size; i++) {
			printf("input[%d] : %c\t", i, *(char*)(data+i));
			if (i%3==0) {
				printf("\n");
			}
		} 
	}
	printf("\n");
}
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 오산돌구
문자열 S, P가있고, S에서 P를 검색한다고 할때, 가장 기초적인건 아래와 같이 검색을 합니다.




비효율적인부분이 있습니다.  그래서 Knuth, Morris, Pratt 세 사람이 만든 KMP 알고리즘을 지금 설명하려고 합니다.

제가 이해한것을 풀어쓰는거라 잘못 이해한 것이 있을 수도 있습니다.
그럴때는 말씀해주시면 감사하겠습니다.

KMP는 패턴을 만들어서 검사에 실패했을때 다음 검사에서 불필요한 부분을 생략하는데 있습니다.
위 그림은 검사에 실패했을때 P를 오른쪽으로 한칸 이동하지만 KMP는 안해도 되는부분은 과감히 건너뜁니다.

KMP는 크게 나눠보면 찾고자하는 문자열에 패턴을 구하고 그 패턴을 이용해서 검사를 하는 것입니다.

문자열 페턴 구하는것을 설명하기에 앞서 suffix, prefix에 대해 알아봅시다.

문자열 abcdabc에 대한 suffix, prefix는

   prefix suffix
 1  a  c
 2  ab  bc
 3  abc  abc
 4  abcd  dabc
 5  abcda  cdabc
 6  abcdab  bcdabc
 7  abcdabc  abcdabc




3번 열을 보면 'abc', 'abc'같죠?  [ 마지막 전체 비교는 필요없는거죠....허허]
패턴을 찾는건 suffix와 prefix가 같은 부분을 찾는다고 할수 있습니다.

[a는 할필요가 없겠죠?]
ab, abc, abcd, abcda, abcdab, abcdabc에 대한 suffix, prefix가 같으면서 가장 긴~부분을 찾는 것이죠.


index 5, 문자 'b'를 예로 들면,
abcda까지 문자열 매칭이 됐는데, b에서 틀릴경우 1번째 문자로 이동하라는 얘기입니다.

1
 a
 a
2
 ab
 da
3
 abc
 cda
4
 abcd
 bcda
5
 abcda  abcda

첫번째문자 'a'와 마지막 문자 'a'가 같으니 이동해도 문제없겠죠?


6번째 문자 C의 경우, 매칭된 문자열은 abcab이고   최대 prefix, suffix는   ab이므로  2가 들어간것이죠~ : )
c,6이 실패했을때 진행방향이 틀렸네요;; d,3이 아니라 c,2로 이동하는게 맞습니다. 2010/12/01
틀렸는데도 아무 댓글이 없다는게 쓸쓸하네요......ㅠ,.ㅠ ㅋㅋ


소스는 아래와 같습니다.

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

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

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

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



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

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

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