게으른 엔지니어

아래 포스팅에 자세히 나와있다.

http://norus.tistory.com/22

공식 홈페이지는 여기

설치.

다음 명령어를 통해 빌드옵션을 확인할 수 있다.

아래와 같이 빌드

spin.js는 추가적인 이미지나 CSS를 호출하지 않고 순수 자바스크립트만으로 만들어지는 로딩 알리미이다.

http://fgnass.github.io/spin.js/

책 소개

• Sublime Text 따라잡기

유용한 정보

• 서브라임 텍스트 2(오픈 튜토리얼)
• Sublime Text 유용한 기능과 단축키
• ToolCon 2014에서 발표한 "Sublime Text Tips & Tricks"

공식 홈페이지는 여기

libxml2 Git web에서 체크아웃 하자.

FAQ의 Compilation 항목을 보면, 4번 항목에 SVN 버전을 사용하며 configure 스크립트가 없는 경우에 대해 나와있다.

아래와 같이 입력하자.

이어서 아래와 같이 입력하면 설치 끝

다음 명령어를 통해 빌드옵션을 확신할 수 있다.

아래와 같이 빌드

TIP

1. 간단한 사용법

2. libxml 사용하여 xml 파싱하기

C언어에서 json-c 라이브러리를 사용하여 json 파싱

GitHub repo로 가보자

README.md를 잘 읽어보면..

사전에 필요한 것들:

• gcc, clang과 같은 C 컴파일러
• libtool

tarball을 사용하지 않는다면, 이것들도 필요:

• autoconf(autoreconf)
• automake

$ sudo apt-get install libtool
$ sudo apt-get install autoconf
$ sudo apt-get install automake

clone하여 json-c 설치

$ git clone https://github.com/json-c/json-c.git
$ cd json-c
json-c$ sh autogen.sh
json-c$ ./configure --prefix=/usr/local
json-c$ make
json-c$ make install

테스트 프로그램을 실행

$ make check

all: static

static:
    gcc -static json-example.c -L/usr/local/lib -ljson-c -I/usr/local/include/json-c -o json-example-static
    ./json-example-static

shared:
    gcc json-example.c -L/usr/local/lib -ljson-c -I/usr/local/include/json-c -o json-example-shared
    ./json-example-shared

.PHONY: all static shared

$ make static
또는
$ make shared

ArrayList

• 사이즈가 고정되어 있음
• 삽입 시 사이즈를 늘려주는 연산이 필요
• 삭제 시에는 순차적인 인덱스 구조로 인해서 삭제된 빈 인덱스를 채워야 하기때문에 채워주는 연산이 필요
• 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 이런 부가적인 연산이 시스템의 성능 저하로 이어져 치명적임
  

LinkedList

• 뒤로 밀거나 채우는 작업 없이 단지 주소만 서로 연결시켜 주면 되기 때문에 추가/삭제가 ArrayList보다 빠르고 용이
• 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현 하는것이 바람직
  

LinkedList의 단점

• ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access) 만 가능
• LinkedList는 단방향성을 갖고 있기 때문에 인덱스를 이용하여 자료를 검색하는 애플리케이션에는 적합하지 않음
  
• 사실 순차 접근도 참조의 지역성(locality of reference) 때문에 LinkedList 보다는 ArrayList가 훨씬 빠름
  
• n개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장하는 반면, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장
• LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 ArrayList보다는 긴 지연 시간이 소모됨
• 참조자를 위해 추가적인 메모리를 할당해야 하므로 자료들의 크기가 작은 리스트의 경우 참조자를 위한 추가 적인 메모리할당은 비실용적일 수 있음
  

Double LinkedList

• 기존의 링크드리스트는 단방향으로만 탐색할 수 있으나 더블링크드리스트는 앞의 노드의 주소도 가지고 있으므로
  양방향 탐색이 가능
  

참조의 지역성:  전산 이론중의 하나로 한번 참조한 데이터는 다시 참조될 가능성이 높고 참조된 데이터 주변의 데이터 역시 같이 참조될 가능성이 높다는 이론

Reference

• 자료구조: Linked List 대 ArrayList
• Double LinkedList
  

선형/비선형 자료구조

• 선형 자료구조
• 리스트, 스택, 큐와 같이 데이터 집합을 한 줄로 늘어 세운 구조
• 비선형 자료구조
• 트리(Tree)는 데이터 집합을 여러 갈래로 나누어 세운 비선형 구조
• 삽입, 삭제, 검색에 대해서 선형 구조보다 나은 시간적 효율을 보임
  

트리

• 일반트리

• 이진트리
• 최대 두 개까지의 자식노드를 가질 수 있는 트리

일반트리의 이진트리 변환

• 일반트리에서는 자식노드의 수가 몇 개가 있는지 예측 불가하여 컴퓨터로 표현하기 어려움
  
• 모든 일반 트리는 이진 트리로 바꾸어 표현 가능
• 왼쪽자식노드-오른쪽형제노드 방법

이진트리의 종류

• 포화 이진트리
• 리프노드를 제외한 모든 노드의 자식은 2개
• 완전 이진트리
• 모든 노드의 자식은 0개 또는 2개
• skew 이진트리
  
• 한 쪽으로 치우친 트리
  

이진트리의 저장

• 배열
• 완전 이진트리의 경우

• skewed 이진트리의 경우

• 배열의 단점
• 배열의 이용하지 않는 저장 공간이 많다.
• 트리의 최대 깊이를 대비하여 기억장소를 확보하기 때문에 메모리 사용량이 많고, 확보한 기억장소보다 트리를 확장할 수 없다.

• 링크드리스트
  

이진트리의 순회(Traversal)

• 전위순회(Preoder Traversal)
• 방문 순서:  G, C, A, E, L
  

void PreOrder (Nptr T) {
	if (T != NULL) {
		Visit(T->Name);
 		PreOrder(T->LChild);
		PreOrder(T->RChild);
	}
}

• 중위순회(Inoder Traversal)
• 방문 순서:  A, C, E, G, L
  

void InOrder (Nptr T) {
	if (T != NULL) {
		InOrder(T->LChild); 
		Visit(T->Name);
		InOrder(T->RChild); 
	} 
} 

• 후위순회(Postorder Traversal)
• 방문 순서:  A, E, C, L, G
  

void PostOrder (Nptr T) {
	if (T != NULL) {
		PostOrder(T->LChild); 
		PostOrder(T->RChild); 
		Visit(T->Name);
	} 
} 

Reference

• http://dblab.duksung.ac.kr/ds/pdf/Chap08.pdf
  
• http://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CC8QFjAA&url=http%3A%2F%2Flink.koreatech.ac.kr%2Fcourses%2F2007_1%2FDS%2FLecture10-1.ppt&ei=AmZwU-WdOcKk8AXsu4CgAg&usg=AFQjCNGbcyfAtUWzlX0I0R6iZncOuo_F0A&sig2=25sWoGvRYgdcnYhme8PMfw&bvm=bv.66330100,d.dGI&cad=rjt
  

NP-Hard와 NP-Complete의 차이가 무엇인지 잘 이해가 가지 않았으나 포함관계를 보니까 알겠다.

P, NP-Hard, NP-Complete