Praying

2015년 3월 16일 월요일

HTML5 정리 (텍스트와 하이퍼링크)

텍스트와 하이퍼링크 관련 태그들

텍스트를 묶어서 처리하는 태그들

<p> - 단락 만들기
1. 태그로 표시하는 텍스트 앞뒤에서 줄바꿈이 일어난다.
2. 나중에 CSS를 이용해 텍스트 서식을 손쉽게 조절할 수 있다.

<blockquote> 태그 - 인용문 넣기
1. <blockquote [속성="속성 값]> 인용 내용 </blockquote>

<pre> 태그 - 입력하는 그대로 화면에 표시하기
1. 소스에 표시한 공백을 그대로 브라우저로 보여주는 태그
2. 주로 프로그램 소스를 표시할 때 사용한다.
3.<code> , <samp>, <kbd> 같은 태그들과 같이 사용한다.

다양한 텍스트 관련 태그들
//인라인 태그: 줄바꿈 없이 태그를 사용한 영역에만 적용되는 태그

<mark> 태그 - 형광펜 효과 내기
1. 선택한 부분에 형광펜을 그어놓는 듯한 효과를 준다.
2. <mark> 태그의 설정을 바꾸면 형광펜의 속성(색, 채도 등)을 바꿀수 있다.

<time> 태그 - 날짜 또는 시간 정보 표시하기
<time [datetime="YYYY-MM-DDThh:mm:ssZ"]> 내용 </time>

YYYY: 연도
MM: 월
DD: 일
T: 시간을 함께 표시해야 할 경우 앞의 날짜와 뒤의 시간 사이를 구분해주는 표시
hh: 24시간제로 표시한 시간
mm: 분
ss: 초
Z: 시간대

<strong>, <em> 태그 - 중요한 내용 강조하기
1. 전체 내용 중에서 강조하고 싶은 부분에 사용하는 태그.
2. <strong> 태그를 사용한 부분은 굵게 표시되고, <em> 태그를 사용하면 이탤릭체로
표시된다.

<b> 태그 - 굵게 표시하기

<i> 태그 - 이탤릭체로 표시하기

<q> 태그 - 인용한 내용 표시하기
1. <blockquote> 태그는 블록 레벨 태그이기 때문에 인용된 내용은 줄바꿈이 되고 다른 내용과 구별되도록 안으로 들여써진다.
2. BUT!!! <q> 태그는 인라인 레벨 태그이기 때문에 줄바꿈 없이 다른 내용과 한 줄에 표시

<span> 태그 - 줄바꿈 없이 영역 묶기
1. 태그 자체는 아무 의미 없음
2. 텍스트 단락 안에서 줄바꿈 없이 일부 텍스트만 묶어서 스타일을 적용하려고 할때 사용

<kbd>
1. 키보드 입력이나 음성 명령과 같이 사용자 입력 내용을 표시할 때 사용하는 태그
<code>
1. 파일 이름이나 컴퓨터 프로그램 등 컴퓨터가 인식할 수 있는 소스를 표시하는 태그
<samp>
1. 프로그램 처리 결과를 표시하는 태그
<sup>
1. 수학 식을 표현할 때 텍스트에 위 첨자를 표현하는 태그
<sub>
1. 수학 식을 표현할 때 텍스트에 아래 첨자를 표현하는 태그
<s>
1. 문서에서 특정 텍스트를 제거한다는 의미로 취소선을 그리는 태그

<ul>, <ol>, <li> 태그 - 목록 만들기
1. 순서가 필요하지 않을 경우: <ul> 태그
2. 순서가 필요할 경우 <ol> 태그
1. type 속성: 순서 목록 앞에 붙는 숫자의 종류를 조절
2. start 속성: 중간 번호부터 시작가능
3. reversed 속성: 번호를 역순으로 표시 가능
3. 각 항목을 표시: <li> 태그
4. 불릿을 바꾸고 싶을 때: CSS의 list-style-type
// 불릿: 각 항목 앞에 작은 원이나 사각형

<ul>
<li> 내용 </li>
<li> 내용 </li>
</ul>

<ol [속성="속성 값"]>
<li> 내용 </li>
<li> 내용 </li>
</ol>

<dl>, <dt>, <dd> 태그 - 정의 목록 만들기
// 사전 구성을 떠올리자 '제목'과 그에 대한 '설명'으로 이루어진 정의 목록을 만든다.
1.<dt> 태그 = '제목'
2. <dd> 태그 = '설명'

표 관련 태그들

<table> 태그 - 표만들기
1. 표의 시작과 끝을 나타냄
2. layout을 만들 때 쓰지 말 것!!!

<tr>, <td>, <th> 태그 - 표의 행과 열 만들기
//<tr> 태그가 행 하나를 만든 후 <tr> 과 </tr> 태그 사이에 셀을 만드는 <td> 태그가 필요한 갯수만큼 삽입된다. <table>, </table> 태그 사이에 <tr> 태그가 세 번 사용되면 행이 3개가 만들어지고, 각 <tr> 태그 안에 <td> 태그가 두 번씩 사용되면 각 행에 셀이 2개씩 만들어진다.
// <th> 태그 역시 셀을 만드는 태그로서 해당 셀에 들어가는 내용을 제목으로 처리하여 셀의 가운데 배치하고 굵게 표시합니다.

colspan, rowspan 속성 - 행 또는 열 합치기
<td colspan="합칠 열의 개수"> 내용 </td>
<th colspan="합칠 열의 개수"> 내용 </th>

<td rowspan="합칠 행의 개수"> 내용 </td>
<th rowspan="합칠 행의 개수"> 내용 </th>

<caption> 태그 - 표에 제목 붙이기
1. 붙여진 제목은 표의 위쪽 가운데에 표시됩니다.
2.<caption> 태그는 <table> 태그 바로 다음에 사용해야 하며,
<table> 태그 하나에는 <caption> 태그 하나만 사용할 수 있다.
3. <caption> 태그를 사용하지 않을 경우 <table> 태그의 summary 속성을 이용해서 표의 요약 내용을 추가해야 한다. 즉 <caption> 태그나 summary 속성 중 하나는 반드시 사용한다.

<col>, <colgroup> 태그 - 여러 열 묶기
1. 몇 개씩 열을 묶어 한꺼번에 스타일을 지정하고 싶을 때 사용
2. <col> 태그는 한 열에 있는 모든 셀을 묶는 것으로, 주로 한 열에 똑같은 스타일을 적용하려 할 때 사용
3. 닫은 태그는 없음
4.<colgroup> 태그는 여러 개의 <col> 태그를 묶어 그룹으로 스타일을 적용하기도 하고, <colgroup span="2">처럼 span 속성을 이용해 열을 묶기도 한다.
//행을 묶는 태그

<colgroup>
<col> <colgroup span="값"> ... </colgroup>
<col>
...
</colgroup>

//<col> 태그와 <colgroup> 태그를 사용하겠다면 <tr> 태그와 <td> 태그 전에 사용해야 하며, <caption> 태그가 있다면 <caption> 태그 다음에 써야 한다. 그리고 <col> 태그를 사용한 열의 개수와 <colgroup> 태그를 사용한 열의 개수를 합했을 때 전체 열의 개수와 정확히 일치해야 한다.

<thead>, <tbody>, <tfoot> 태그 - 표의 제목과 본문 등 구분해주기
제목 본문 바닥
1. <tbody> 태그 이전에 <thead>와 <tfoot> 태그가 와야 함.

원하는 곳으로 연결해주는 하이퍼링크

<a> 태그 - 원하는 문서나 사이트로 연결하기
1. <a href="경로"> 텍스트 또는 이미지 </a>

새 창 또는 새 탭에서 링크 열기
//<a> 태그 안에 target 속성을 추가해주면 된다.
1. <a href="경로" target="_blank"> 텍스트 또는 이미지 </a>

링크를 미리 알려주는 툴팁
// 링크 위에 마우스 포인터를 올려놓았을 때 나타나는 작은 설명 박스
1. <a href="경로" title="링크 내용에 대한 요약 설명"> 텍스트 또는 이미지 </a>

한 페이지 안에서 이동할 수 있는 앵커
//웹 문서가 길 경우 필요한 곳마다 문서 안에 이름을 붙여놓고 그 위치로 한번에 이동하는 링크를 만들 수 있는데, 이 기능을 앵커라고 한다.
사용법
1. 이동하고 싶은 위치마다 name 속성을 이용해 앵커를 만들고 각각 다른 이름을 지정한다.
<a name="앵커 이름"> 텍스트 또는 이미지 </a>
2. 이렇게 붙여놓은 앵커 이름들은 마치 링크를 만들 때처럼 이름을 링크한다.
<a href="#앵커 이름"> 텍스트 또는 이미지 </a>

2015년 3월 14일 토요일

HTML5 태그를 지원하지 않는 브라우저를 만났을때

파이어폭스 브라우저, iOS 사파리 브라우저 3.2 버젼, 오페라 미니 브라우저 5.0~6.0버전,
오페라 모바일 브라우저 10.0 버전, 안드로이드 브라우저 2.1 버전
// 시맨틱 태그들을 강제로 블록 레벨 태그(자신만의 영역을 만드는 태그)로 설정해야함

소스코드 Ex)
header, hgroup, section, nav, article, footer {
display:block;
}

인터넷 익스플로러 8.0 이하 버전
//시맨틱 태그들을 아예 새로 정의해야 함

소스코드 Ex)
<script>
document.createElement('article');
document.createElement('section');
document.createElement('aside');
document.createElement('hgroup');
document.createElement('nav');
document.createElement('header');
document.createElement('footer');
</script>

// 이 소스를 <heed> 와 </heed> 태그 사이에 넣을 것

// 위에 소스 코드는 HTML5의 시맨틱 태그를 정의하려고 만들어진 소스로서
// 다른 태그들을 더 추가하거나 있던 태그를 빼야할 경우도 있을 수 있음

HTML5 정리 (기초)

HTML 문서 작성 방법

1. 태그는 소문자로 씁니다.
// 대문자랑 혼용 사용 금지
2. 여는 태그와 닫는 태그를 정확히 입력합니다.
// 닫는 태그가 없는 경우도 있다.
// ex) <img> <br>
3. 적당하게 들여쓰기 합니다.

4. 태그는 속성과 함께 사용됩니다.
// <태그 속성 = "속성 값" 속성 = "속성 값" ...>
// ex) <img> 태그에는 이미지 파일의 경로를 알려주는 src 속성
이미지의 크기를 알려주는 width, height 속성
이미지에 보조 설명을 붙여주는 alt 속성
... 등이 같이 붙는다.
5. 인코딩 방식은 utf-8로 합니다.
// <meta charset = "utf-8">
// why? utf-8이 모든 언어를 표시할 수 있는 문자세트이기 때문에

6. 웹 문서에서 특수 문자 및 특수 기호 사용하기
1. 한글모음 + 한자키
2. 만약 HTML에서 공백이나 괄호 같은 문자들을 소스 기호로 인식하지 않고 그대로 화면에 표시하려고 할 때에도 특수 기호를 이용하면 된다.
// & &
// (공백 한 칸)  
// < <
// > >
// " "
// | }
// ( (
// ) )
// . ,
// - -
// ' ´

HTML 문서의 구조

<!doctype html>
// 문제 유형을 지정하는 태그
// "HTML 문서이고 어떤 유형을 사용했다"라는 것을 알려주는 태그이다.

<html>
// 웹문서의 시작
<html lang = "ko">
// 문서에서 사용할 언어를 지정
<head>
// 웹 브라우저 화면에는 보이지 않지만, 웹 브라우저가 알아두어야 할 정보들은 모두 <head>부분에 입력한다.
<meta charset="utf-8">
// 문자 인코딩을 지정
<title> 문서 제목 </title>
// 웹 브라우저의 제목 표시
</head>
<body>
// 실제 브라우저에 표시될 내용을 입력
// 대부분의 태그가 쓰일 곳
</body>
</html>
// 웹문서의 마지막

자주 쓰는 기본 태그 익히기
<hn> 태그 - 제목 표시하기
1. 제목 텍스트는 일반 텍스트보다 크기가 크고 진하게 표시된다.
2. <h1> 이 가장 크고 <h6>이 가장 작게 표시된다.

<p> 태그 - 텍스트 단락 만들기
1. 웹 문서에서 가장 많이 사용하는 태그들 중 하나
2. 반드시 닫는 태그를 사용하기

<br> 태그 - 줄 바꾸기
1. 웹 문서에서 가장 많이 사용하는 태그들 중 하나
2. 닫는 태그 없음

<b> 태그 - 텍스트를 진하게 표시하기

<i> 태그 - 텍스트를 이탤릭체로 표시하기

<img> 태그 - 이미지 추가하기
1. <img> 태그 안에 반드시 src 속성을 이용해서 삽입경로를 표시해야함
2. 닫는 태그 없음

<a> 태그 - 웹 문서나 외부 사이트 연결하기(하이퍼링크)
1. href 속성을 이용해 연결한 웹 문서 이름이나 웹 사이트 주소를 지정해야 함.

주석 - 설명글 추가하기
1. HTML 태그 주석: 
2. CSS 주석 : /* 주석 내용 */

시맨틱 태그
// 이번 프로젝트의 Layout에서 가장 중요한 부분인 것 같다.
why?
1. 소스만으로도 문서내용을 알 수 있다.
2. 그래서 검색할 때 필요한 내용을 정확하게 찾을 수 있어 편리하다.
// 예를 들어 웹사이트의 실제 내용을 검사하고 싶을 때에는 <section> 과 <article> 부분만 // 찾아서 검사하면 된다.

<!DOCTYPE html>
<html lang="ko">
<head>
<meta charset="utf-8">
<title>내가 처음 만드는 HTML 문서</title>
</head>
<body>
<header>
<h1>입양하기</h1>
<nav>

</nav>
</header>
<section>
<article>
<h2>강아지 용품 준비하기</h2>

</article>
</section>
<footer>
<p>Copyright 2012 funnycom</p>
</footer>
</body>
</html>

레이아웃을 위한 HTML5 시맨틱 태그들
//<body> 태그와 </body> 태그 사이에 들어갑니다.

<header> 태그 - 머리말(제목) 지정하기
1. 특정 부분의 머리말
2. 여러 태그에 동시에 사용 가능
// <form> 태그를 이용해 검색창을 넣거나 <nav> 태그를 사용해 사이트 메뉴를 넣는다.

<nav> 태그 - 문서를 연결하는 내비게이션 링크
1. <header> 나 <footer> 태그등에 포함시킬 수도 있고 독립해서 사용할 수도 있다.
//포함시키면 포함된 태그의 영향을 받음

<hn> 태그 - 제목 표시하기
1. 제목 텍스트는 일반 텍스트보다 크기가 크고 진하게 표시된다.
2. <h1> 이 가장 크고 <h6>이 가장 작게 표시된다.

<hgroup> 태그 - 제목과 부제목 묶어주기
1. 제목과 관련된 부제목들이 있다면 제목과 부제목이 서로 관련이 있음을 나타낼 수 있다.
2. 화면에 그 결과가 표시되지는 않지만, 문서의 구조를 편리하게 만든다.

<section> 태그 - 콘텐츠 영역 나타내기
1. <header> 태그, <footer> 태그와 비교해서 콘텐츠 영역을 구분 짓는 용도로 사용
2. 실제 내용은 <article> 태그를 사용
3. <section> 태그 안에 또 다른 <section> 태그를 넣을 수도 있다.
// 이 것으로 <section> 영역을 여럿으로 나눈다.

<article> 태그 - 실제 콘텐츠 내용 넣기

<aside> 태그 - 본문 이외의 내용 표시하기

<footer> 태그 - 제작 정보와 저작권 정보 표시하기

<address> 태그 - 사이트 제작자 정보, 연락처 정보 나타내기
1. <footer> 태그 안에 들어가는 태그
2. 실제 주소는 <p> 태그, 웹주소는 <address> 태그 사용

<div> 태그
1. 콘텐츠에 CSS를 적용할 때 <div> 태그를 사용한다.

2015년 2월 22일 일요일

데이터 구조와 알고리즘 6장 1

트리란 무엇인가?
트리는 연결 리스트와 유사한 데이터 구조이다. 하지만 각 노드가 선형적으로 다른 노드를 가리키는 게 아니라 각 노드가 여러 개의 노드를 가리킨다. 트리는 비선형적 데이터 구조의 한 예이다. 트리 구조는 구조의 계층적 속성을 그래프의 형태로 나타내는 방법이다.
// 항목의 순서는 중요하지 않다.

- 용어 설명
1. 트리의 뿌리는 부모가 없는 노드이다. 트리에는 최대 한 개의 뿌리 노드가 있을 수 있다.(A)
2. 간선(edge)은 부모로부터 자식에게 이어지는 연결 선을 뜻한다.(모든 선)
3. 자식이 없는 노드를 잎(leaf) 노드라고 한다(E, I, J, K, I)
4. 같은 부모를 가진 자식들을 형제(sibling)라고 한다.(B, C, D는 A를 부모로 하는 형제 노드들이고 E, F는 B를 부모로 하는 형제 노드들이다.)
5. 뿌리 노드로부터 노드 q에 이르는 경로에 노드 p가 있으면 노드 p를 노드 조상 노드(ancestor)노드라고 한다. 노드 q는 노드 p의 자손(descendant)노드이다.
// A, B, F는 J의 조상 노드들이다.
6. 주어진 깊이의 모든 노드의 집합을 그 트리의 레벨이라고 한다.

7. 노드의 깊이는 뿌리로부터 그 노드까지의 경로의 길이이다.
// F의 깊이는 2, A-C-G
8. 노드의 높이는 그 노드로부터 가장 깊은 노드까지의 경로의 길이이다. 트리의 높이는 뿌리로부터 가장 깊은 까지의 경로의 길이이다.
// B의 높이는 2이다.(B-F-G)
9. 트리의 높이는 트리의 모든 노드의 높이 중 최대 값이고 트리의 깊이는 트리의 모든 노드의 깊이의 최대 값이다. 주어진 트리에 대해 높이와 깊이는 같은 값을 가진다. 하지만 각각의 노드에서의 값은 다를 수 있다.
10. 노드의 크기는 자기 자신을 포함하여 그 노드가 가진 자손의 수이다.
// B의 크기는 4이다.
11. 트리의 모든 노드가 오직 한 개의 자식만을 가질 때(잎 노드를 제외하고) 이 트리를 경사(skew) 트리라고 한다. 모든 노드가 왼쪽 자식만을 가지면 왼쪽 경사 트리라고 한다.
반대의 경우에는 오른쪽 경사 트리라고 한다.

- 이진 트리

각 노드가 자식이 없거나, 한 개 혹은 두 개의 자식을 가질 때 이진 트리라고 한다. 빈 트리 역시 유효한 이진 트리이다. 이진 트리는 뿌리와 왼쪽 부속 트리, 오른쪽 부속 트리라고 불리는 두 개의 분리된 이진 트리로 구성되어 있다고 볼 수 있다.

- 이진 트리의 종류

엄격한 이진 트리: 모든 노드가 두 개의 자식을 가지거나 자식이 없을 때 엄격한 이진 트리

포화 이진 트리: 모든 노드가 두 개의 자식을 가지고 잎 노드가 같은 레벨에 있을 때 포화 이진 트리
완전 이진 트리: 완전 이진 트리를 정의하기 전에, 이진 트리의 높이가 h라고 할 때, 완전
이진 트리에서는 뿌리부터 시작해서 각 노드에 번호를 매기면, 1부터 시작 해서 트리 안의 노드 수까지의 완전한 순열을 얻는다. 탐색할 때 NULL 포인터에게도 숫자를 매겨야 한다. 모든 잎 노드가 높이 h나 h - 1에 있고 순열에서 빠진 숫자가 없을 때 완전 이진 트리라고 부른다.

- 이진 트리 속성
1. 포화 이진 트리의 노드 개수 n은 2^(h+1) - 1이다. 모두 h 레벨이 있기 때문에 각 레벨의 노드를 다 더해야 한다.(2^0 + 2^1 + 2^2 + 2^3 + 2^4 +... + 2^h = 2^(h+1) - 1
2. 완전 이진 트리의 노드 개수 n은 2^h(최소 값)과 2^(h+1) - 1(최대 값) 사이에 있다.
3. 포화 이진 트리의 잎의 개수는 2h이다.
4. n개의 노드를 가진 완전 이진 트리의 NULL 연결(낭비된 포인터)의 개수는 n + 1이다.

- 이진 트리의 구조
이제 이진 트리의 구조를 정의해보자. 예를 들어 노드의 데이터가 정수라고 하자. 다음 그림은 왼쪽과 오른쪽 자식을 가리키는 두 연결을 가진 데이터 필드로, (데이터를 포함한) 노드를 표현한 것이다.

class BinaryTreeNode {

int data;

class BinaryTreeNode *left;

class BinaryTreeNode *right;

};

- 이진 트리의 연산

기본 연산

트리에 항목 삽입하기

트리로부터 항목 삭제하기

항목 검색하기

트리 탐색하기

부가적 연산

트리의 크기 구하기
트리의 높이 구하기
최대의 합을 가진 레벨 찾기
주어진 노드 쌍에 대해 최소 공통 조상 찾기
... ...

- 이진 트리 탐색
트리를 처리하기 위해서는 트리를 탐색하는 방법이 필요하다. 트리의 모든 노드를 방문하는 과정을 트리 탐색이라 한다. 각 노드는 오직 한 번씩 처리되지만 한 번 이상 방문될 수도 있다. 선형 데이터 구조(연결 리스트, 스택 , 큐)에서는 항목들이 순차적으로 방문된다.
그러나 트리 구조에서는 여러 가지 방법이 있다.
트리 탐색은 트리를 검색과 기본적인 동작이 같지만, 탐색의 목적은 특정한 순서로 트리 안을 움직이는 것이다. 또한 탐색에서는 모든 노드가 처리되지만 검색에서는 찾는 노드가 발견되면 멈L춘다.

- 탐색 가능성
이진 트리의 뿌리부터 시작해서 모든 노드를 탐색하는 데는 세 가지 단계가 있는데, 이 단계들의 수행 순서에 따라 탐색 유형이 달라진다. 이 단계들은 현재 노드에 대해 어떤 작업 수행하기(노드를 '방문'한다고 하고 'D'라고 표기한다), 왼쪽 자식 노드 탐색하기('L'이라고 표기한다), 그리고 오른쪽 자식 노드 탐색하기('R'이라고 표기한다)이다. 이 과정은 재귀적 방법으로 쉽게 표현할 수 있는데, 다음과 같은 여섯 가지 가능성이 있다.
1. LDR: 왼쪽 부속 트리를 처리하고, 현재 노드의 데이터를 처리하고, 오른쪽 부속 트리를 처리한다.
2. LRD: 왼쪽 부속 트리를 처리하고, 오른쪽 부속 트리를 처리하고, 현재 노드의 데이터를 처리한다.
3. DLR
4. DRL
5. RDL
6. RDL

- 탐색 분류하기
이 요소들이 처리되는 순서가 특정한 탐색 기법을 정의하게 된다. 현재 노드가 처리되는 순서에 따라 분류가 된다. 즉 현재 노드(D)에 의해 분류하는데, D가 가운데에 온다면 D의 왼쪽에 L이 오거나 상관없다. 비슷하게, D의 오른쪽에 L이 오거나 R이 오거나 상관없다. 이런 특성 때문에 모두 여섯 가지 가능성이 다음의 세 가지로 줄어든다.
1. 전위 탐색(DLR)
2. 중위 탐색(LDR)
3. 후위 탐색(LRD)

앞의 순서와 상관없는 또 다른 탐색 기법이 하나 더 있다.

레벨 순서 탐색: 이 기법은 너비 우선 탐색의 영향을 받은 것이다.

다음 그림을 기반으로 설명한다.

전위 탐색
전위 탐색에서 각 노드의 탐색은 부속 트리를 탐색하기 전에 처리된다. 각 노드가 부속 트리 전에 처리되더하도 몇몇 정보는 탐색이 트리의 다음 순서로 이동하는 동한 유지되어야 한다. 1이 먼저 처리되고 나서 왼쪽 부속 트리, 오른쪽 부속 트리 순서로 처리된다. 왼쪽 부속 트리 처리 후 오른쪽 부속 트리로 이동하려면 뿌리의 정보가 유지되어야 한다. 이런 정보를 위한 ADT는 당연히 스택인데, 스택의 LIFO 구조 때문에 오른쪽 부속 트리에 대한 정보를 역순으로 얻는 것이 가능하다.
전위 탐색은 다음과 같이 정의된다.
1. 뿌리를 방문한다.
2. 전위 탐색으로 왼쪽 부속 트리를 탐색한다.
3. 전위 탐색으로 오른쪽 부속 트리를 탐색한다.

앞의 트리의 노드는 1 2 4 5 3 6 7의 순서로 방문된다.

void PreOrder(BinaryTreeNode root) {
if(root != null) {
System.out.println(root.getDate());
PreOrder(root.getLeft());
PreOrder(root.getRight());
}
}

시간 복잡도: O(n)
공간 복잡도: O(n)

중위 탐색
중위 탐색에서는 뿌리 노드가 탐색에서는 뿌리 노드가 부속 트리 사이에 방문된다. 중위 탐색은 다음과 같이 정의된다.

1. 왼쪽 부속 트리를 중위 탐색으로 탐색한다.
2. 뿌리 노드를 방문한다.
3. 오른쪽 부속 트리를 중위 탐색으로 탐색한다.

앞의 트리 노드는 4 2 5 1 6 3 7의 순서로 방문된다.

void InOrder(BinaryTreeNode root) {
if(root != null) {
InOrder(root.getLeft());
System.out.println(root.getData());
InOrder(root.getRight);
}
}

시간 복잡도: O(n)
공간 복잡도: O(n)

후위 탐색
후위 탐색에서 뿌리 노드는 양쪽 부속 트리 뒤에 방문된다. 후위 탐색은 다음과 같이 정의된다.

1. 왼쪽 부속 트리를 후위 탐색으로 탐색한다.
2. 오른쪽 부속 트리를 후위 탐색으로 탐색한다.
3. 뿌리 노드를 방문한다.

앞의 트리 노드들은 4 5 2 6 7 3 1의 순서로 방문된다.

void PostOrder(BinaryTreeNode root) {
if(root) {
PostOrder(root.getLeft());
PostOrder(root.getRight());
System.out.println(root.getData());
}
}

시간 복잡도: O(n)
공간 복잡도: O(n)

레벨 순서 탐색
레벨 순서 탐색은 다음과 같이 정의된다.

1. 뿌리 노드를 방문한다.
2. 레벨 l을 방문하는 동안 레벨 ㅣ + 1의 모든 항목을 큐에 저장한다.
3. 다음 레벨로 가서 그 레벨의 모든 노드를 방문한다.
4. 이 과정을 모든 레벨이 끝날 때까지 방문된다.

앞의 트리의 노드들은 1 2 3 4 5 6 7의 순서로 방문된다.

void LevelOrder(BinaryTreeNode root) {
BinaryTreeNode temp;
LLQueue Q = new LLQueue();
if(!root)
return;
Q.enQueue(root);
while(!Q.isEmpty()) {
temp = Q.deQueue();
// 현재 노드를 처리한다.
System.out.println(temp.getData());
if(temp.getLeft())
Q.enQueue(temp.getLeft());
if(temp.getRight())
Q.enQueue(temp.getRight());
}
Q.deleteQueue();
}

시간 복잡도: O(n)
공간 복잡도: O(n)

2015년 2월 20일 금요일

데이터 구조와 알고리즘 5장

큐란 무엇인가?
큐(Queue)는 (연결 리스트와 스택과 유사하게) 데이터를 저장하는 데이터 구조이다. 큐에서는 데이터가 도착하는 순서가 중요하다. 일반적으로 큐는 사람들이나 물건들이 한 줄로 서서 차례를 기다리는 것과 비슷하다.

정의: 큐는 데이터의 삽입이 한쪽 끝(뒤, rear)에서 이루어지고 삭제는 다른 쪽 끝(앞, front)에서 이루어지는 정렬된 리스트이다. 가장 처음 삽입된 항목이 맨 먼저 삭제된다(FIFO)

스택에서처럼 큐는 두 가지 동작의 종류가 있다. 항목이 큐에 삽입될 때, 인큐(EnQueue)라고 하고, 항목이 큐로부터 제거될 때, 디큐(DeQueue)라고 한다. 빈 큐로부터 디큐하려고 하는 것을 언더플로우(underflow)라고 부르고, 꽉 찬 큐에 항목을 인큐하려고 하는 것을 오버플로우(overflow)라고 하는데, 일반적으로 예외로 처리된다.

- 큐는 어떻게 사용되는가?

큐는 데이터의 순서를 유지해야 할 필요가 있는 경우에 매우 유용하다.

- 큐 ADT

큐의 주된 연산들

EnQueue(int data): 큐의 가장 끝에 항목을 삽입한다.

int DeQueue(): 큐의 가장 앞의 항목을 제거하고 리턴한다.

큐의 보조 연산들

int Front(): 큐의 가장 앞에 있는 항목을 제거하지 않고 리턴한다.

int QueueSize(): 저장된 항목의 개수를 리턴한다.

int IsEmptyQueue(): 저장된 항목이 없는지를 나타낸다.

- 예외들

다른 ADT들과 유사하게 빈 큐에 대하여 디큐하려고 시도하면 '빈 큐 예외(Empty Queue Exception)'가 발생하고, 꽉 찬 큐에 인큐하려고 하면 '꽉찬 큐 예외(Full Queue Exception)' 가 발생한다.

- 큐의 구현

간단한 원형 배열에 기초한 구현

동적 원형 배열에 기초한 구현

연결 리스트 구현

왜 원형 배열인가?

먼저, 스택에서 사용했던 것처럼 단순한 배열을 사용할 수 있는지 살펴보자. 큐의 삽입은 한쪽 끝에서, 삭제는 다른 쪽 끝에서 이루어진다는 것을 알고 있다. 그런데 몇 번의 삽입과 삭제 연산 뒤에 다음 그림과 같은 상황에 처하는 경우가 많다.

(배열의 앞쪽 공간이 낭비되는 현상)

이 문제는 원형 배열로 해결할 수 있는데, 원형 배열은 마지막 항목과 첫 번째 항목이 연결되는 형태이다. 이를 이용하여 앞쪽에 빈 공간이 있으면 뒤(rear)포인터가 다음 빈 공간으로 쉽게 이동할 수 있다.

간단한 원형 배열 구현

public class ArrayQueue {

private int front;

private int rear;

private int capacity;

private [] array;

private ArrayQueue(int size) {

capacity = size;

front = -1;

rear = -1;

array = new int [size];

}

public static ArrayQueue createQueue(int size) {

return new ArrayQueue(size);

}

public boolean isEmpty() {

return (front == -1);

}

public boolean isFull() {

return ((rear + 1) % capacity == front);

}

public int getQueueSize() {

return ((capacity - front + rear + 1)%capacity);

}

public void enQueue(int data) {

if(isFull()) {

throw new QueueOverflowException("Queue Overflow");

}else{

rear = (rear + 1) % capacity;

array[rear] = data;

if(front == -1) {

front = rear;

}

public int deQueue() {

int data = null;

if(isEmpty()) {

throw new EmptyQueueException("Queue Empty");

}else{

data = array[front];

if(front == rear) {

front =rear - 1;

}else{

front = (front+1)%capacity;

}

return data;

}

- 성능과 한계

동적 원형 배열 구현

public class DynArrayQueue extends Queue {

private int front;

private int rear;

private int capacity;

private int[] array;

private DynarrayQueue() {

capacity = 1;

front = -1;

rear = -1;

array =new int[1];

}

public static DynArrayQueue createDynArrayQueue() {

return new DynArrayQueue();

}

public boolean isEmpty() {

return (front == -1);

}

private boolean isFull() {

return ((rear + 1) % capacity == front);

}

public int getQueueSize() {

if(front == -1) return 0;

int size = (capacity - front + rear + 1) % capacity;

if(size == 0) {

return capacity;

}else return size;

}

private void resizeQueue() {

int initCapacity = capacity;

capacity *= 2;

int[] oldArray = array;

array = new int[this.capacity];

for(int i=0; i<oldArray.length;i++) {

array[i] = oldArray[i];

}

if(rear < front) {

for(int i=0; i<front; i++) {

array[i+initCapacity] = this.array[i];

array[i] = null;

}

rear = rear + initCapacity;

}

}
public void enQueue(int data) {

if(isFull()) resizeQueue();

rear = (rear + 1) % capacity;

array[rear] = data;

if(front == -1) front = rear;

}

public int deQueue() {

int data = null;

if(isEmpty()) throw new EmptyQueueException("Queue Empty");

else { data = array[front];

if(front == rear) front = rear = -1;

else front = (front + 1) % capacity;

}

return data;

}

성능

연결 리스트 구현

public class LLQueue extends Queue {

private LLNode frontNode;

private LLNode rearNode;

private LLQueue() {

this.frontNode = null;

this.rearNode = null;

}

public static LLQueue createQueue(){

return new LLQueue();

}

public boolean isEmpty() {

return (frontNode == null);

}

public void enQueue(int data) {

LLNode newNode = new LLNode(data);

if(rearNode != null) {

rearNode.setNext(newNode);

}

rearNode = newNode;

if(frontNode == null) {

frontNode = rearNode;

}

public int deQueue() {

int data = null;

if(isEmpty()) {

throw new EmptyQueueException("Queue Empty");

}else{

data = frontNode.getData();

frontNode = frontNode.getNext();

}

return data;

}

성능

2015년 2월 17일 화요일

데이터 구조와 알고리즘 4장

스택은 데이터를 저장하기 위해 사용되는 (연결 리스트와 유사한) 간단한 데이터 구조이다.
스택에서는 데이터가 도착하는 순서가 중요하다.

정의: 스택은 삽입과 삭제가 한쪽 끝에서 이루어지는, 순서가 매겨진 리스트이다. 이 끝을 탑이라고 부른다. 제일 마지막에 추가된 항목이 제일 먼저 삭제된다(LIFO, FILO).

스택이 가질 수 있는 두 가지 변화에 대한 특별한 이름이 있다. 스택에 항목이 삽입될 때, 이 것을 푸시(push)라고 부르고, 항목이 스택으로부터 삭제되는 것을 팝(pop)이라고 부른다. 빈 스택으로부터 항목을 팝하려는 것을 언더플로우(underflow)라고 하고, 가득 찬 스택에 푸시하려는 것을 오버플로우(overflow)라고 하는데, 일반적으로 이런 경우는 예외처리한다.

- 스택 ADT

스택의 주요 연산들

push(int data): 데이터를 스택에 넣는다.

int Pop(): 스택에 제일 마지막에 추가된 항목을 스택으로부터 삭제하고 리턴한다.

스택의 보조적 연산들

int Top(): 스택에 마지막에 추가된 항목을 삭제하지 않고 리턴한다.

int Size(): 스택에 저장된 항목의 개수를 리턴한다.

int IsEmptyStack(): 스택에 항목이 저장되어 있는지 아닌지를 확인한다.

int IsFullStack(): 스택이 가득 찼는지 아닌지를 확인한다.

- 스택의 구현

여러 가지 방법들

간단한 배열에 기반한 구현

동적 배열에 기반한 구현

연결 리스트 구현

간단한 배열 구현

이렇게 ADT를 구현할 때는 하나의 배열이 사용된다. 배열에 항목을 왼쪽에서 오른쪽으로 추가하면서 변수 하나를 사용하여 탑 항목의 인덱스를 추적한다.

스택 항목을 저장하는 배열은 가득 찰 수도 있다. 이 경우, 푸시 연산은 '꽉찬 스택 예외'를 발생시킨다. 유사하게 빈 스택으로부터 항목을 삭제하려고 하면 '빈 스택 예외'를 발생시킨다.

public class ArrayStack{

private int top;

private int capacity;

private int[] array;

public ArrayStack() {

capacity = 1;

array = new int[capacity];

top = -1;

}

public boolean isEmpty(){

/* 이 조건이 참이면 1이 리턴하고 아니면 0이 리턴된다. */

return (top == -1);

}

public int isStackFull(){

// 이 조건이 참이면 1이 리턴되고 아니면 0이 리턴된다.

return (top == capacity - 1); //혹은 return (top == array.length);

}

public void push(int data) {

if(isStackFull()) System.out.println("Stack Overflow");

else // 'top'을 증가시키고 데이터를 'top'위치에 저장한다.

array[++top] = data;

}

public int pop(){

if(isEmpty()) { // top == -1은 스택이 비었음을 뜻한다

System.out.println("Stack is Empty");

return 0;

}

else return (array[top--]);

}

public void deleteStack(){

top = -1;

}

성능과 한계

성능

스택 안의 항목의 개수를 n이라고 하자. 이 구현의 스택 연산 복잡도는 다음과 같다.

- 동적 배열 구현

top이라는 인덱스 변수를 써서 스택에 가장 최근에 추가된 항목의 인덱스를 가리키게 했다.

항목을 추가하려면 top인덱스를 증가시키고 새 항목을 그 인덱스 자리에 넣는다. 유사하게 항목을 삭제하려면, top 인덱스의 항목을 취하고 top 인덱스를 감소시킨다. 우리는 top의 값을 -1로 두어 빈 스택을 나타낸다. 여전히 해결해야 할 문제는 고정된 크기의 배열 스택의 모든 항목이 다 찼을 때 처리하는 방법이다.

첫번째 시도

스택이 가득 찰 때마다 배열의 크기를 1씩 증가시키자.

문제점)

이 방식으로 배열 크기를 증가시키는 것은 비용이 너무 크다. 예를 들어 n = 1일 때 새 항목을 푸시하려면 크기가 2인 배열을 만들고 이전 배열의 모든 항목을 새 배열로 복사한 후 맨뒤에 새 항목을 추가해야한다. 또다른 경우로서 n = n-1일 때 새 항목을 푸시하려면, 크기가 n인 새 배열을 만들어 이전 배열의 모든 항목을 새 배열로 복사한 후 맨 뒤에 새 항목을 추가해야 한다. n번의 푸시 이후에 전체 시간 T(n0 (복사 연산의 횟수)은 1 + 2 + ... + n ≒ O(n^2)에 비례한다.

다른 접근 방법: 반복적인 두 배 확장

배열이 가득 차면, 크기가 2배인 새 배열을 만들어 항목들을 복사한다. 이 방법에서는 n개의 항목을 푸시할 때 n(n^2이 아닌)에 비례하는 시간이 걸린다. 처음에 n = 1에서 시작해서, n = 32일 때까지 계속한다고 하자. 즉 1,2,4,8,16일 때 두 배로 만든다는 것이다. 이를 분석하는 다른 방법은, n = 1일 때 새 항목을 추가하려면 현재 배열의 크기를 두 배로 만들고 모든 항목을 이전 배열에서 새 배열로 복사하는 것이다.

n = 1일때 한 번의 복사를 하고, n = 2일 때 두 번의 복사를 하고, n = 4일 때 네 번의 복사를 하는 식이다. n = 32가 될 때면 복사 연산의 총합은 1 + 2 + 4 + 8 + 16 = 31이고, 이것은 대략 2n(32)와 비슷하다. 자세히 관찰하면, 두 배로 만드는 연산을 logn번 하는 것을 알 수 있다. 이제 n번의 푸시 연산에 배열 크기를 두 배로 만드는 것을 logn번 수행하면, logn 항을 갖는다. n번의 푸시 연산의 전체 시간 T(n)은 연산의 횟수에 비례한다.

1 + 2 + 4 + 8 ... + n/4 + n/2 +n = 2n = O(n)

T(n)은 O(n)이고 푸시 연산의 상각 시간은 O(1)이다.

public class DynArrayStack {

private int top;

private int capacity;

private int[] array;

public DynArrayStack() {

capacity =1;

array = new int[capacity];

top = -1;

}

public boolean isEmpty(){

return (top == -1);

}

public int isStackFull(){

return (top == capacity - 1);

}

public void push(int data) {

if(isStackFull())

doubleStack();

array[++top] = data;

}

private void doubleStack(){

int newArray[] = new int[capacity*2];

System.arraycopy(array, 0 ,newArray, 0, capacity);

capacity = capacity*2;

array = newArray;

}

public int pop() {

if(isEmpty()) System.out.println("Stack Overflow");

else return (array[top--]);

}

public void deleteStack() {

top = -1;

}

- 성능

연결 리스트 구현

스택을 구현하는 또 다른 방법은 연결 리스트를 사용하는 것이다. 푸시 연산은 리스트의 맨 앞에 항목을 삽입하는 것으로 구현된다. 팝 연산은 리스트 가장 처음 노드를 삭제하는 것으로 구현된다.

public class LLStack extends Stack {

private LLNode headNode;

public LLStack() {

this.headNode = new LLNode(null);

}

public void Push(int data){

if(headNode == null) {

headNode = new LLNode(data);

}else if(headNode.getData() == null){

headNode.setData(data);

}else{

LLNode llNode = new LLNode(data);

llNode.setNext(headNode);

headNode = llNode;

}

public int top() {

if(headNode == null) return null;

else return headNode.getData();

}

public int pop(){

if(headNode == null) {

throw new EmptyStackException("Stack empty");

}else{

int data = headNode.getData();

headNode = headNode.getNext();

return data;

}

public boolean isEmpty() {

if(headNode == null) return true;

else return false;

}

public void deleteStack(){

headNode = null;

}

- 성능

- 각 구현 방법의 비교

점진적 증가 기법과 두 배 확장 기법의 비교

점진적 증가 기법

푸시 연산의 상각 시간은 O(n)이다.

두 배 확장 기법

푸시 연산의 상각 시간이 O(1)이다.

- 배열 구현과 연결 리스트 구현의 비교

배열 구현

연산의 수행에는 일정한 시간이 걸린다.

가끔 비용이 큰 두 배 확장 연산을 수행한다.

(빈 스택으로부터 시작하는) n번의 연산에 상각하는 n에 비례하는 시간이 걸린다.

연결 리스트 구현

부드럽게 커지고 작아진다.

모든 연산에 일정한 시간 O(1)이 걸린다.

모든 연산에 레퍼런스를 다루기 위한 부가적인 공간과 시간이 필요하다.