Month: March 2017

자료구조

알고리즘 복잡도

속도 –  시간 복잡도Time Complexity
메모리 – 공간 복잡도Space Complexity

복잡도의 기준은 비교연산의 횟수 or 반복문 횟수

worst case 기준으로 복잡도 측정

빅-오 표기법( Big-Oh notation)

좋은 알고리즘

O(1) 상수형 빅-오

y=1

O(log n) 로그형 빅-오

O(n) 선형 빅-오

O(nlong n)

보통

O(n^2)

거의사용불가

O(n^3)

O(2^n)

 

재귀 알고리즘 예제

  1. 입력값 n을 넣으면 n~0까지 출력
  2. Fibonacci – 입력값 n을 넣으면 n번째 값 출력 0 1 1 2 3 5 8 …
  3. Factorial – 입력값 n을 넣으면 n! 값 출력 5! = 5*4*3*2*1
  4. BinarySearch
  5. 하노이 타워

 

종류

선형구조Linear

List
Stack
Queue

비선형구조

Tree
Graph

파일구조

순차파일
색인파일
직접파일

단순구조

정수
실수
문자
문자열

 

Stack – LIFO(Last In, First Out)

 

Queue – FIFO(First In, First Out)

뱀그림 대가리 입력 꼬리 출력

Deque

아무리봐도 디큔데 덱이라고 읽음
양방향 입출력 큐

Tree

계층적 관계, Hierarchical Relationship을 표현하는 자료구조

Decision Tree, 조직도

 

Full Binary Tree 왕세모
Complete Binary Tree 작은세모집합

Traversal

1

2       3

전위 순회Preorder Traversal (2 1 3)
중위 순회Inorder Traversal (2 3 1)
후위 순회Postorder traversal (1 2 3)

 

예제) 계산기

전위 표기법prefix notation
중위 표기법infix notation
후위 표기법postfix notation

 

BubbleSort

Selection Sort

Insertion Sort

Heap Sort

Merge Sort

Quick Sort

 

Tomcat 사용시 주의점 – Java 웹개발시 초기설정

Tomcat 압축을 풀어보면

webapps 디렉토리에 기본 디렉토리가 존재한다.

docs
examples
host-manager
manager
ROOT

이 상태로 톰색을 실행시키면 이 디렉토리 경로로 접속이 되는데….

이것때문에 충돌이 발생하는 상황이 있다.

딱 봐도 개발하다보면 종종 사용될만한 주소 패턴이다.

문제는, ide에서 / 경로에 웹을 띄웠을 때

/docs
/manager
/examples

로 접속하면 톰캣 기본디렉토리가 우선 접속된다.

 

webapps 디렉토리는 꼭 비워주고 쓰자.

저번에 당했었는데.. 오랜만에 또 당해서..

 

 

MongoDB 특성 분석 01, 사용전 기능조사~ 에서 ~ 적용사례까지

개요

몽고디비는 처음 알게됐을 때 부터 써보고싶기는 했는데.. SI만 하다보니 쓸 기회가 없었다.
개인적으로 테스트용이나 회사에서 간단한 모듈을 만들 때 사용하긴 했지만, 제대로 분석을 해 보고 적용해본게 아니라서 깊이있는 지식은 없는 상태

사용목적

기술적으로 몽고디비가 꼭 필요한 상황은 아니라고 판단되지만… 나쁜 선택은 아닐 것 같아서 일단 적용 해 볼 생각이다.
저장할 데이터 : Crawling, Scrapping 데이터, 게시판 글, 댓글, GIS정보, GridFS를 이용한 이미지 저장

 

GIS 정보 관리
PostgreSQL의 PostGIS를 써도 되지만…. 내부정보가 아닌 사용자 데이터를 저장해야 한다. 서비스가 급성장하면서 데이터가 엄청나게 쌓일거라서 MongoDB를 쓸 수 밖에 없잖아

Crawling, Scrapping 데이터
텍스트 파일 저장

GridFS를 이용한 이미지 저장
이 부분은 써야할까? 모르겠다. 성능문제도… 별 생각없이봐도 문제가 잇겠지?
http://symplog.tistory.com/entry/MongoDB-MongoDB-GridFS-%EB%B6%80%ED%95%98%ED%85%8C%EC%8A%A4%ED%8A%B8
있다고하네…
그리고 cdn에 올리면 필요없는 부분 아닌가

몽고디비에 대해 잘 정리된 페이지
http://kkyunstory.tistory.com/65
이런 평가를 많이 보긴 했는데…

아몰랑 그냥 쓰다가 안되는거 한개씩 옮겨야겠다.

특성 ~~ 확인중

문서형 데이터베이스

데이터를 문서형태로 저장 – BSON을 이용하여 저장
BSON : JSON을 Binary 형태로 저장

장점

다양한 인덱스 제공
Sharding

 

인덱싱 방법

종류

Unique고유 인덱스
Sparse희소 인덱스 : Null인 경우 인덱스 생성하지 않음
다중 키 인덱스, 복합인덱스

주의점

롤백은 불가능
트랜잭션 안된다고 치고
인덱싱 걸면 디비 먹통

Crawling, Scrapping… 갑자기 뭔 신기술처럼 대접받는

요즘 갑자기 신기술처럼 포장되는 것 중 하나
그냥 Html파싱, 퍼오기라고 생각해서 이력서에도 굳이 안 쓰는데
시시콜콜하게 다 써놔야하나 하는 생각이 든다.
별것 아니고 계속 사용되어 왔지만 갑자기 주목받는 기술 중 하나

Crawling, Scrapping을 구분해보면

구분 할 필요가 있긴한지 잘 모르겠지만… 굳이 구분해서 쓰는 사람이 있을지 모르니 알아두자
혼용되서 사용되기도 하고.. 굳이 구분하기도 하는데 이게 맞는지 정확하지는 않다.

Crawling

웹사이트를 걍 다 퍼오는 개념으로
링크를 타고 다음링크를 다시 타고들어가는 기능(Spider)이 중요하다.
한 주소를 가지고 거기있는 링크를 타고타고 또 들어가야 하는데 이것을 꼼꼼히 구현하는게 생각보다 힘들다. depth가 많아질수록…  이 부분은 Nutch, Scrapy 같은 라이브러리에서 지원을 해 주니 굳이 따로 구현을 할 필요는 없다.

Scrapping

스크래핑은 .. 사실 그냥 파싱 아닌가
특정 웹페이지에서 원하는 데이터를 뽑아내는 기술이다.

웹페이지를 만들 때 구조적으로 만드는게 구현도 더 쉽기 때문에 html의 id, class에는 보통 패턴이 숨어있다. 이걸 찾아서 데이터를 찾아오게 코딩을 해 주면 된다.
가끔 막코딩된 페이지는 별 수 없다. 막파싱 해야한다 .dom 계층을 무식하게 따라가면
노가다는 승리한다.

이런식으로 특정 사이트를 정해놓고 원하는 데이터를 뽑아내는 것은 쉽다.

카톡, 블로그, 페북도 요즘 이런걸 지원한다. 글쓰기 창에 링크를 박으면 해당 주소의 대표이미지와 요약정보를 보여주는데 보통 Meta데이터에 포함된 정보를 보여준다.
여기서, Meta데이터가 없을 경우에 알아서 정보를 표현 해 주는 기능을 만들려면 머리가 좀 아플거다.
(아직까지 알아서 잘 되는건 못 봤다)

여기서도 BeautifulSoup, Jsoup, Gson 등 각 언어별로 Html, Xml 라이브러리가 있으니 갖다 쓰자.

JS를 이용해 데이터가 다이내믹하게 변하는 웹사이트는 좀 다른 노력이 필요하다.
Ajax,Websocket, AngularJS등을 이용하는 페이지는 그냥 HTML을 다운받아 파싱하면 뻘 데이터가 나온다. 이럴 때는 WebDriver를 써야한다.
파싱은 python의 Selenium라이브러리를 이용해서 phantomJS 드라이버를 사용하면 편하다. 이렇게 하면 브라우저로 보는것과 HTML을 얻을 수 있다.
참고로.. 암표 봇이나 수강신청 봇도 이런기술을 이용해서 만들면 된다.(IP차단당할수도있다)

사용법은 공식사이트에서

http://phantomjs.org/
http://www.seleniumhq.org/
https://www.crummy.com/software/BeautifulSoup/
https://scrapy.org/
http://nutch.apache.org/

구석구석 잘 알고 쓰면 좋지만… 간단한 기능을 만드는데 모든 기능을 이해할 필요는 없다.
그래도 기술의 구조와 개념정도는 이해하고 쓰는게 좋은 것 같다.