2-1 기본적인 프로그램

1) 함수 : 적절한 입력과 그에 따른 출력이 존재하는 것.

- 입력을 전달하는 것을 인자 전달이라 하며, 함수의 실행을 요구하는 것을 함수 호출이라 한다. 둘은 동시에 일어난다.

- 함수의 특성 : 함수의 이름, 입력 형태, 출력 형태


2) 연산을 수행하는 모든 문장들은 세미콜론으로 끝난다.

3) 표준 라이브러리 함수의 사용을 위해서 헤더 파일을 include 한다.

4) return은 함수 종료와 값의 반환이라는 두 가지 의미를 지닌다.


2-2 주석

// 내용 : 한줄 주석

/*
 내용
*/ : 여러줄 주석

-컴파일러는 주석을 무시함. 즉, 주석은 프로그램에 전혀 영향을 끼치지 않음.


2-3 printf함수

- printf함수는 첫번째 인자를 출력한다.
- 첫번째 인자에 출력 대상의 형태를 지정하는 서식문자가 올 수 있다. ex) %d, %f




'학부 전공 > C' 카테고리의 다른 글

6. printf함수와 scanf함수  (0) 2010.07.08
5. 상수와 기본 자료형  (0) 2010.07.08
4. 데이터의 표현방식  (0) 2010.07.07
3. 변수와 연산자  (0) 2010.07.06
1. C언어  (0) 2010.07.02

1-1 C언어 개론


1. C는 프로그래밍 언어이다.

-프로그래밍 언어란 사람과 컴파일러가 이해할 수 있는 약속된 언어.

-컴파일러의 역할은 프로그래밍언어로 작성된 프로그램을 컴퓨터가 이해할 수 있도록 기계어로 번역해주는 역할

// 기계어는 0과 1로 이루어진 비트열이다.


2. C언어의 특징

- Low-Level 언어 : 컴퓨터가 이해하기 쉬운 언어. ex) 어셈블리어
- High-Level 언어 : 사람이 이해하기 쉬운 언어. ex) C언어

- Low-Level 언어는 하드웨어 의존도가 높으며, 프로그래밍하기가 어려운 편이지만 그만큼 하드웨어에 최적화를 시킬 수 있어서 효율적이다.


3. C언어의 장점

1) 절차지향적이라 이해하기 쉽다.
2) 이식성이 좋다.
3) 효율성이 높다.

- C언어는 Low-Level 언어의 특성을 가지고 있다.


1-2 프로그램의 완성 과정

- 프로그램 작성 -> 컴파일 -> 링크 -> 실행파일 생성

1) 프로그램 작성 과정에서 프로그래머는 C언어로 소스코드를 작성한다.( = 코딩 )
2) 컴파일 과정에서 컴파일러는 소스코드를 기계어로 변환한다. 그 결과가 object file 이다.
3) 링크 과정에서는 컴파일된 코드를 라이브러리 파일과 연결시켜준다. 그 결과가 실행 파일(exe file)이 된다.

'학부 전공 > C' 카테고리의 다른 글

6. printf함수와 scanf함수  (0) 2010.07.08
5. 상수와 기본 자료형  (0) 2010.07.08
4. 데이터의 표현방식  (0) 2010.07.07
3. 변수와 연산자  (0) 2010.07.06
2. 프로그램의 기본 구성  (0) 2010.07.06


드디어.









드디어! 이클립스, 즉 옵티머스Q(이하 옵큐)를 영접하였습니다!(....)




사진을 오른발 새끼발톱으로 찍어서 요상하게 나와버렸지만(.........)


외관은 만족입니다.

뭐 사실 외관이 어쨌던간에 옵큐는.........





쿼티가 있으니까요!!

진리의 쿼티!!




사전을 실행해보았습니다.

수학공식 사전도 있군요. 덕분에 언제라도 심심하지는 않을 듯.ㅋㅋ






문자 보내는 화면.

쿼티를 써보니 그야말로 감동의 물결.

그것은 마치 마약과도 같은 중독(뭣이)







그리고 누구나 다 하는 구성품 목록<-

다른건 제쳐두고 보호필름이랑 배터리를 추가로 제공해주는건 정말 고마웠습니다.





하잇. 스위치 온.






..........왠지 영화 "썸머워즈"의 한장면 같습니다?ㅋㅋㅋㅋㅋ







아....아무쪼록 부족한 몸이지만 앞으로 잘 부탁드립니다(__)





.........


이렇게 안드로이드 세계에 입성하게 되었습니다.

와아~ 짝짝짝~(....)



'안드로이드' 카테고리의 다른 글

LU2300 5월 중순 동향  (0) 2010.05.12
출시 임박! LU2300(이클립스)  (0) 2010.05.03

두번째 산행.

오늘은 아차산을 넘어 용마산까지 정ㅋ벅ㅋ하기로 했다<-




시작은 어제와 동일하게 아차산 정상으로 가는 계단.




구름이 잔뜩 꼈던 어제와 달리
오늘은 해가 떴다!


나무사이로 비치는 태양.
태양을 직접 찍고 싶은 욕망이 솟구쳐올랐지만
렌즈를 생각해서 자제했다(.....)



오오 서울시내가 보인다!!



그렇다면 오늘은 이 조망도처럼 보이는건가!

하고 봤더니...





-ㅅ-);;;;;;;;;;;;

그....그래도 어제보단 잘 보이네;;;;;;;;;





강에 비치는 태양이 참 예쁘다고 생각했다.




서울이다 서울~!




잘 조합하면 서울시내 대부분은 카메라에 담을 수 있을듯.





ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
이누야사 봐야되는데ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ



그리고 아차산 정상 도착!

지도에 나온 예상 소요시간은 2시간 40분

첫등산인 어제는 1시간 30분 걸렸고



그리고 오늘은



37분 걸렸다.?!!!!! -ㅅ-);;;;;;;;;;;;;;


핸드폰의 시계를 의심했을 정도였다.


1시간 30분이 어떻게 37분으로 단축되는거냐하면.......

어제는 첫등산이어서 여기저기 둘러보면서 천천히 걸었고
아차산 정상까지 얼마나 힘들지 몰라서 페이스를 무조건 낮게 잡았지만,

오늘은 뭐 두번째 가는 길이고,
정상까지 별로 안 힘들다는 걸 알고 있어서 평균 페이스를 좀 올렸다.


나중에 타임어택 같은거 해봐야지..ㅎㅎ




아무튼 그건 그거고 이제 아차산을 넘어 용마산 정상으로 향했다.





(주의)이 사진에 나와있는건 암벽이 아니라 등산로입니다.(..................)

사진으로보니까 경사가 잘 드러나지 않는 것 같다.
어떻게해야 경사가 드러나게 찍을수 있으려나...


아무튼 이걸 딱 맞닥뜨렸을때,



"등산로는 어디가고 왠 벽이 있는거지?"

라고 생각했다.=ㅅ=)a


아차산과 용마산은 등산레벨이 달라도 너무 달랐다.





용마산 정상으로 가는 도중 뒤를 돌아보며 찍은 사진.

보이는 산의 나무가 없는 부분이 아차산 정상이다.

근데 지금 내 위치랑 높이가 비슷한거 같다....ㄷㄷㄷ




헬기장도 있어!!

뭐 서울의 산들이 다 그렇겠지만

여기도 전쟁이 나면 전략적 요충지가 될 터이니...





용마산 정상까지 0.5KM!!!

근데 이때부터 다리가 후들거리기 시작했다.=ㅅ=);;;;;;;;;;;;;

아차산 정상을 밟을때만해도 멀쩡했었는데;;;;





약수터가 진리 *^^*


참고로 약수터는 아차산 입구에 있으며

차 다니고, 학생들 등교하는 길에서

10분정도만 아스팔트 위를 걸어오면 있습니다(..........)





이건 뭐 100m마다 표지판이 하나씩 있네요(.......)

아차산 정상까지 몇 미터라는 표지판은 하나도 못봤는데(.........)


용마산이 아차산보다 올라가기 훨씬 힘들기 때문인걸까.





그리고 마지막 하이라이트..

저 위가 용마산 정상인데,

정말 다리가 후들후들거려서 올라가는데 힘들었음(.......)




용마산 정상에 꼽혀있는 태극기.


아차산 정상은 정비중이라고 들어가지도 못했는데=ㅅ=);;;;;;;;;;;

아무래도 아차산을 너무 차별하는것 같단말야;;;;;;;;;


어쨌든 용마산 정상에 도착!

등산을 시작한지 57분만에,

아차산 정상에서 출발한지 20분만에 도착하였다.


이렇게 적고보니까 꽤 짧은 시간인듯..

하긴 아차산과 용마산이 보통은 높은산으로 분류되지는 않으니까...




이것이 용마산 정상에서 보는 서울 시내!




..................망우산도 붙어있는거였어?!?!(.........)



내가 정ㅋ벅ㅋ한 부분,





망우산으로 넘어가는 부분. 뭔가 약수터도 많고, 전망대도 있다.

이 쪽으로도 가고 싶었지만..................


집으로 돌아오기가 힘들듯....=ㅅ=);;;;;;;;;

등산 열심히 하고 버스나 지하철을 타고 집에 온다니 뭔가 께름칙해!!!

라는 생각에, 아무래도 망우산쪽으로는 가지 않을듯 하다.





내려오는 길에 계속 서울 시내가 보였다.


.............유원지도 보였다.

그렇게 크던 관람차와 롤러코스터가 이렇게 조그맣게 보이다니...

꼭 롤러코스터타이쿤 하는것 같았음.ㅋㅋ




이......이거슨 용마산 명품 소나무!!<-




(주의)이 사진에 나와있는건 낭떠러지가 아니고 등산로입니다.(........)


용마산은 오르는 것도 대박이더니 내려가는 것도 대박이었다.

후들거리는 다리를 붙잡고 정말 조심조심 내려왔다(.......)




여기서 중랑구도 갈수 있어!(................)




우연히 본 산 아래의 모 초등학교 운동장.

초등학교 아침 조회인가??;;;

아침7시에??;;;;;;






등산로같지 않은 등산로도 계속 나왔다.






등산은 인생과도 같지.
내려갈 때가 있으면 올라갈 때도 있는 법<-




요즘 마을버스는 산에도 오네요ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ



센스는 재밌었지만, 등산로 안내문을 저렇게 만들어서야 쓰나.



근데 왠지 등산로가 아닌 길로 한번 가보고 싶었다.

화살표 방향은


이쪽이었는데 

표지판을 무시하고 그냥 앞으로 가봤다.


그랬더니





이런게 나왔다.=ㅅ=);;;;;;;;;;;;;;

차마 철조망을 넘어갈 용기는 안 나서 그대로 BACK.




다시 낭떠러지의 시작ㅇ>-<



(주의)이 사진에 나와있는건 동굴입구가 아니고 등산로입니다.




지못미ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ





그리고 갑자기 시작되는 "정비된 길"=ㅅ=);;;;;;

정말 뜬금없이 시작되어서 깜짝 놀랐다.






그나마 아직 공사중이었어ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ





이건 징검다리...............가 맞겠지?=ㅅ=);;;;;;;;



그리고 시작되는 주택가<-

이제 다시 도시 속으로.





내가 내려온 길이 빨간색 길 중에 윗쪽 길.

현위치라고 적혀진 곳이 이 곳이었는데 정말.





산길과 주택가골목길이 붙어있어!!0ㅅ0)!!!!!


산 근처의 주택가를 가본적이 없던 나에게는 살짝 쇼크.


그렇게 터덜터덜 내려오니 등교하는 중고등학생들이 보였다.

용곡초등/중학교와 대원외고, 대원여고 학생들이었다.

그런데 그 중에
체육복이라기엔 단정하고, 교복이라기엔 활동적인 
핑크색 or 노란색 상의를 입고있는 여학생들이 눈에 띄었다.
요즘엔 교복이 핑크색과 노란색도 있나?;;;;
그에 비해 남학생들은 그저 하얀색<-


그렇게 학생들도 지나쳐서

버스와 지하철이 있는 큰 길에 나오자

산행이 끝났구나 라는걸 실감했다.

너무 갑자기 주택가가 튀어나와서 미처 실감하지 못했었다.ㅋ


이렇게 두번째 산행도 무사히 완료.


'사진' 카테고리의 다른 글

100727 월드컵공원역  (0) 2010.08.12
100709 용마산 + 아차산  (0) 2010.07.14
100708 용마산 + 아차산  (0) 2010.07.14
100707 아차산 + 용마산  (0) 2010.07.14
100621 아차산  (0) 2010.06.21


갑자기 산행을 하고 싶어져서(..)

학교 근처 가까운 산이 어딨을까~ 하고 봤더니

아차산 & 용마산이 있었다.


그래서 먼저 아차산으로.





지도보고 대충 찾아갔더니

아파트 단지 사이에서

이런 계단이 갑툭튀!(.......)

아마 정식입구(..)는 관리사무소 쪽에 있는듯.






이것이 갑툭튀계단 옆에 있는 지도.

오늘의 목표는 아차산 정상.






조금 더 올라가니

이런 지도도 나왔다.






초반의 등산로.

적절하게 바위길과 계단이 조합되어 있었다.







엄청나게 큰 바위를 오르다보니 어느새 보이는 고구려정

고구려정을 지나가니 바로 첫 갈림길에 도착하였다.





목표는 정상!

1KM가 조금 넘는 산행이 되겠군..

지도상에서는 여기까지 오르는 '고구려정길 0.7km, 30분'이라고 되어있지만...




난 10분만에 주파!(...........)

젊은게 좋은거죠, 네..




슬슬 본격적으로 시작되는 산행!




표지판 옆으로 쭉쭉 올라가는 길.

마치 '포기하려면 지금 하렴ㅋㅋㅋㅋ'
라고 하는 듯 하다(.....)

하지만 가볍게 무시:)





무려 2000년도 광진구청장님으로부터의 전언(.....응?)



마치 동네 조그만 공원에 있을 법한 벤치들도 있었다.





조망도. 오오 한강이랑 서울시내가 이렇게 보인다고?!!


하며 고개를 들었더니


현실(..................)

경치는 다음을 기약해야했다.




지금이 2010년입니다?!<-



그래서 다 정비된건가?<-




중간중간 멋드러진 시들이 곳곳에 있었다.




등산로 치고는 무난한 길.






오오 명품 소나무 오오...




바로 옆에 2호(........)

나중에 5호까지 나와서 
"아차산 명품 소나무 5형제!!" 이런거 되는건가(.......)




여전히 아무것도 보이지 않는 산 아래.ㅡ.ㅜ




일로 내려가면 광진구!!!! 라니...

너무 광범위하잖....=ㅅ=);;;;;







왠지 아차산은 여기저기 정비하는데가 많았다.






그리고 드디어 정상에 올랐다!!!!

그런데 




이런 상황=ㅅ=)a

결국 정상이라는 느낌을 전혀 못 받은 상태에서
길은 옆산인 용마산으로 가도록 되어있었다.

체력은 조금 남았는데 왠지 아차산 정상이 여기라고 생각하니
힘빠져서 그냥 되돌아왔다.

아, 지도엔 여기까지를

"광개토대왕길(아차산정상길) 3.6km, 2시간 10분"

이라고 되어있는데

난 1시간 20분만에 주파......:P

그리고 하산할때는 50분만에 주파<-

아무래도 나는 산 지형에 가면 
기동력이 200%정도 상승하는 옵이 붙어있는듯(.........)




내려오면서 본 아차산성.





끝이 보인데ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

아고 귀여워라. 

하지만...

저 화살표가 가르키고 있는 방향은...
아차산 정상 방향이었고(............)
화살표부터 아차산 정상까지는 2시간이 넘게 걸리는 거리임(..........)

어린아이들이 벌써부터 거짓표지판을.....ㅠㅠ





이것이 그 유명한(?!) 연리근.
양쪽 나무에 붙은 부분을 자세히 들여다 봤는데
정말 자기 뿌리처럼 나와있었다.

그런데 감탄하다가 특이한 점을 발견했다.


왼쪽의 나무는 잎도 무성하고 두꺼운데

오른쪽의 나무는 잎이 하나도(!) 없고 얇았다.


..............생각만큼 그리 아름다운 관계는 아닐지도 몰라..
라는 생각이 머리를 스치고 지나갔다.;;;;;;;;;






내려올때는 저 빨간색 길로 내려왔다.




산행이 끝나갈 때, 터벅터벅 걷는 느낌도 좋았다.




이 사진.


.................왼쪽 길에 대한 표지판이 없다!!!!!



도...도대체 어디로 가는 길인거지?ㅎㄷㄷ






내가 아까 찍고 왔던 아차산 정상이 1840m....





여기가 아차산의 정식 입구인가보다...


입구를 산행 마지막에 봐버렸다(..........)


총 등산시간은 2시간으로 첫 산행을 마쳤다.

'사진' 카테고리의 다른 글

100727 월드컵공원역  (0) 2010.08.12
100709 용마산 + 아차산  (0) 2010.07.14
100708 용마산 + 아차산  (0) 2010.07.14
100707 아차산 + 용마산  (0) 2010.07.14
100622 아차산 + 용마산  (0) 2010.06.22

 * Hash Table
- 최악의 경우를 따지지 않고, 평균적인 경우 즉 대부분의 경우에만 가능한 자료구조
- 조건에 맞으면 동작이 상수 시간 안에 끝나고, 간단하다.
- delete가 복잡하다. delete가 많은 상황에서는 쓰지 않는다.

- idea : 지정석. ex) 100만개의 가능한 키가 모두 등장.

- 정의 : 키 값 k,  k->h(k)
 h(k) : Hash Function. 범위는 0부터 배열의 크기-1 까지.
- k는 h(k)에 저장한다.

- Hash function. (입력값과 무관해 보이는 결과값을 원함)
 k % n
 (p*k) % n
 string folding

-Overflow handling (거의 발생하지 않는다. 따라서 성능에 특별한 영향을 안 줌)
 Open Addressing : linear probing(+1, +2 ...), quadratic probing(^2, ^3 ....) , rehashing(다른 hash함수 사용)
, random probing( pseude random number generator 사용)
 Chaining : 해당 인덱스를 링크드 리스트로 만들어서 저장
 Overflow bucket : 특정 공간을 만들어서 overflow된 값들을 저장. 디스크에서 주로 사용.
 Dynamic Hashing : 넘치면 두배로 늘림. 늘린후 hash값을 모두 재계산 하거나 lazy separation을 사용
 Bloom Filter : hash table보다 훨씬 큰 bitmap filter를 사용. table에 없는 값을 search할 경우 filter에서 걸러짐. 실제로 많이 사용됨.


 * RADIX
-내부 구조에 관심을 가져보자
-많은 경우에 O(nlog n). 범위가 좁고 개수가 적당할수록 성능이 보장됨
- Compression : Run-Length Encoding, Differential Encoding, Huffman Encoding

  Huffman Encoding
- idea : 자주 등장하는 character를 짧은 bit sequence로 표현.
- 각 character의 등장 확률이 미리 주어졌을 때, 최적의 prefix-tree code 생성
- radix의 한 예. tree의 좌, 우가 의미하는 바가 key의 내용에 관계가 있음.

- counting sort : 배열의 데이터가 곧 해당하는 인텍스 넘버의 개수.
- bucket sort : 배열에 버켓을 범위별로 나눠서 넣은 후 각각을 sort.
- radix sort : 배열에 버켓을 2개만 놓고 1개는 첫비트가 0인것, 나머지 1개는 1인것으로 넣음. 그리고 반복.

 * Binary Trie
- retrieve, 꺼내기 쉬운 자료구조
- 키 : integer ( 2진수로 표현 )
- 왼쪽 child는 해당 비트가 0 인 것, 오른쪽 child는 해당 비트가 1인 것.

- Compressed Binary Trie : 특정 노드 이하로 하나의 leaf만 존재할 경우, 그 leaf까지의 모든 비트를 한 레이블에 모아서 적어놓음. delete가 복잡해짐

- Radix trie, Patricia : compressed binary trie의 변형. interner node를 없앰.

- string trie : child로 가는 edge가 해당 칸의 문자열을 의미.

- Aho-corasick Trie : multiple keyword matching.

- Suffix tree : index structure. compressed trie 기반. 사전에 사용.



'학부 전공 > 자료구조' 카테고리의 다른 글

10. 탐색구조  (0) 2010.06.15
5. Tree  (0) 2010.06.08
4. Linked List  (0) 2010.06.07
3. Stack / Queue  (0) 2010.06.07
2. 배열  (0) 2010.06.07

- 최악의 경우에도 insert, search, delete가 O(log n)을 유지

10.2 AVL tree
- 정의 : Binary tree + label
- 각각의 node에 left, right label 표기
-left label : 왼쪽 subtree의 depth
-right label : 오른쪽 subtree의 depth
- left label과 right label이 2 이상 차이가 안 나게 유지.
(항상 같거나 1 차이.)

-Search : binary search tree와 동일. O(log n)
-Insert : binary search tree Insert + Tree 보정 ( label 조건을 만족시키기 위함)
-일단 insert를 시키고 난 후, search한 PATH를 따라 올라가다가 최초로 조건을 만족시키지 않는 node에서 Rotation.

 *Rotation
-LL, LR, RL, RR
-LL의 경우: 최초로 조건을 만족시키지 않는 node를 right child로 만들고, 그 자리에 left child를 올림.
 left child의 right child는 원래 root node의 left child로 바꿈.
 RR의 경우 좌우 대칭
-LR의 경우 : 최초로 조건을 만족시키지 않는 node를 right child로 만들고, 그 자리에 left child의 right child를 올림.
 root로 올린 node의 left child는 원래 자리의 parent에 붙이고, right child는 원래의 root node에 붙임.

 - Rotiation을 진행 하더라도 기본적인 크기 관계가 변하면 안 됨.


10.3   2-3 tree

- 정의 : 각 node에 키가 1개 혹은 2개, 따라서 각 node의 child가 2개 혹은 3개. 모든 leaf는 같은 level.
- search : O(log n)
- insert : search를 한 후에, leaf에 빈자리가 있으면 그냥 insert, 빈자리가 없으면 leaf를 split해서 중간값을 parent로 올려보내고 반복.


10.4   2-3-4 tree

- 각 node에 키가 1개 혹은 2개 혹은 3개.
- 나머지는 2-3 tree와 같으나 insert를 할 때, split을 하면서 내려오게 할 수 있다.-> tree를 한번 내려오면 insert가 끝남.


10.5 Red-Black tree
- 2-3-4 tree의 변형
- 2-3-4 tree를 binary tree형태로 표현.
- child node로 가는 link를 black으로, 같은 node에 있는 키로 가는 link를 red로 표시.

-특징 : root에서 leaf까지 black link의 수는 항상 동일, 어떤 path에서도 red link가 연속으로 등장하지 않는다.

-insert 과정은 AVL tree의 Rotation과 같다.


- AVL, 2-3, 2-3-4, Red-Black tree를 통틀어 Balanced tree라 부른다.


 * Skip list
- head와 tail이 더미 노드인 링크드 리스트가 층으로 쌓여있는 자료구조
- 모든 동작이 O(log n)에 된다.


'학부 전공 > 자료구조' 카테고리의 다른 글

Hash Table, Radix, Binary Trie  (0) 2010.06.15
5. Tree  (0) 2010.06.08
4. Linked List  (0) 2010.06.07
3. Stack / Queue  (0) 2010.06.07
2. 배열  (0) 2010.06.07

-그래프의 특수한 경우

- Connected Graph with no cycle

 *정의
1. 하나 이상의 노드로 이루어진 자료구조
2. 노드들 중 하나는 root이다.
3. root를 제외한 나머지 노드들은 subtree들로 분할된다.
4. root와 subtree의 root 사이에는 edge가 있다.

 *용어
- node의 subtree root를 node의 child라고 부른다.
- degree(차수) : node의 child 수
- degree가 0인 node : leaf, terminal
- A가 B의 child => B는 A의 parent
- parent가 같은 node들 => 형제(sibling)
- root level : 1, node level : parent level + 1, 제일 큰 level : heght or depth
- parent, parent의 parent, ,,,,,, => 조상(ancestor)
- child, child의 child, ...... => 자손(descendant)
 

5.1.1 Tree의 표현(child를 표현하는 방법)
1) 배열 방법 
2) Left child - Right sibling
3) Binary Search Tree

5.2 Binary Tree
 - child가 최대 2개인 tree

5.2.3 Binary tree의 표현
 - 배열에 embeded.
 - 배열의 i에 있는 node의 children은 2i, 2i+1에 존재

5.3 Tree Traversal
-정의 : root에서 시작해서 node들을 "지정된 순서"에 따라서 "방문"하는 것
-종류 : preorder, inorder, postorder
-트리에 다항식을 넣으면 전위/중위/후위 연산자 표현이 가능하고, 변수를 넣으면 기계어를 만들 수 있다.

5.6 Heap
 - 우선 순위 큐를 만들 때 사용
 - Complete Binary Tree.
 - 어떤 노드의 키 값은 children의 키 값보다 작다.
 - Heap Insert : up-heap. leaf중에서 제일 오른쪽에 추가한 후, parent와 비교해서 조건에 안 맞으면 교환. 그리고 반복
 - Heap Delete : down-heap. root를 보내주고, leaf중에서 제일 오른쪽에 있는 것을 root로 올린 후, children과 비교해서 조건에 안 맞으면 교환. 그리고 반복.

 - tree는 재귀적으로 코딩하면 더 쉬워진다.

5.7 Binary Search Tree 
- Binary tree
- left, right의 children
- node a의 left subtree : a의 키보다 작은 키 값
- node a의 right subtree : a의 키보다 큰 키 값

- Insert : Search를 한 후, 실패했다면 그곳에 새 child로 insert
- Delete : leaf일 때는 그냥 삭제, one child 일때는 child를 parent에 붙여주고 삭제, two children 일때는 오른쪽으로 한번, 왼쪽으로 계속 내려가서 만나는 leaf랑 해당 노드를 바꾼 후, 바뀐 leaf를 삭제.


5.10 Union-Find
-집합의 연산 중 합집합과 대표 원소 찾기(집합 이름 찾기, 두 원소가 같은 집합에 있는지 확인)

-Minimum Spanning Tree 문제
-연결을 유지하면서 최소 비용 쓰기
방법1 : 한 노드르 찍고, 최소 비용 edge를 추가 해나감.
방법2 : 전체 edge를 sorting한 다음, 최소 비용 edge부터 추가 해나감

-항상 사이클을 만들지 않는다.
-사이클 검사 : 방법1 일때는 Tree에 이미 포함된 노드 둘을 연결할 때 사이클이 생기고, 방법2 일때는 같은 덩어리에 있는 노드 둘을 연결할 때 사이클이 생김.

-구현 : 배열상에서 구현. 포인터는 index, 무제한 tree, 포인터 방향은 child->parent. 즉 해당 node는 자신의 parent의 index의 값을 가지고 있음.

- 성능 : Find와 Union 둘 다 tree depth에 비례.
- Path Compression 사용




'학부 전공 > 자료구조' 카테고리의 다른 글

Hash Table, Radix, Binary Trie  (0) 2010.06.15
10. 탐색구조  (0) 2010.06.15
4. Linked List  (0) 2010.06.07
3. Stack / Queue  (0) 2010.06.07
2. 배열  (0) 2010.06.07

-Linked List의 특징 : 순서를 유지한다. 삽입과 삭제를 주로 한다. Binary Search가 불가능 하다.

-Node와 Link로 구성되어 있다.
-Node는 데이터를 저장하는 Linked List의 구성단위이고, Link는 Node와 Node를 연결하는 포인터이다.

-Multi thread에서는 포인터 하나로 delete를 수행할 수 없다. 

-메모리 사용이 유연한 장점이 있다.


*다항식
-다항식 표현에 다양하게 사용된다.

*동치관계(등호의 예)
1) Reflexive : 모든 a에 대해서 a = a이다.
2) Symmetric : 모든 a,b에 대해서 a = b이면 b = a이다.
3) Transitive : 모든 a,b,c에 대해서 a = b, b = c이면 a = c이다.

-동치관계의 일부가 주어졌을 때, 주어진 것으로 유추할 수 있는 자연스러운 partition을 계산하는데 쓰인다.

-DFS(depth first search : 깊이 우선 탐색)




'학부 전공 > 자료구조' 카테고리의 다른 글

Hash Table, Radix, Binary Trie  (0) 2010.06.15
10. 탐색구조  (0) 2010.06.15
5. Tree  (0) 2010.06.08
3. Stack / Queue  (0) 2010.06.07
2. 배열  (0) 2010.06.07

- Search를 고려하지 않음
- Insert와 Delete 대신에 Push와 Pop을 씀.
- 값에 의존하지 않고 순서에만 의존.

*Stack : Last-in First-out 방식(LIFO)
*Queue : First-in First-out 방식(FIFO)

-Queue에서는 full 과 Empty 일 때 top,bottom포인터의 상대위치가 같기 때문에 구별해주어야 한다.


*미로찾기
-길을 찾다가 막혀있으면 왔던 길을 되돌아 간다. 왔던 길의 좌표를 Stack에 저장해 놓을 수 있다.

*수식의 계산
-infix(중위표기법) : 연산자를 연산하려는 두 숫자 사이에 두는 방법. 예) 3 + 5
-postfix(후위표기법) : 연산자를 연산하려는 두 숫자 뒤에 두는 방법. 예) 35+
-prefix(전위표기법) : 연산자를 연산하려는 두 숫자 앞에 두는 방법. 예) +35

이 중에서 인간이 이해하기 쉬운 표현은 infix, 프로그램 입장에서 이해하기 쉬운 표현은 postfix.

 *infix를 postfix로 변환하는 알고리즘
1. 피연산자인 경우 출력
2. 연산자인 경우 Stack top의 연산자와 우선순위를 비교하여 입력된 연산자의 우선순위가 더 높을 경우 Push하고, Stack top의 연산자의 우선순위가 더 높을 경우 Pop한 후 반복 비교.

 *postfix로 된 수식을 계산하는 알고리즘
1. 피연산자이면 Stack에 Push
2. 연산자이면 Stack에서 피연산자 2개를 Pop해서 계산 한 후, 결과는 Push


-최하위 우선순위를 가지는 연산자를 하나 지정해서 Stack에 미리 넣어두면, 코드가 단순해진다.


'학부 전공 > 자료구조' 카테고리의 다른 글

Hash Table, Radix, Binary Trie  (0) 2010.06.15
10. 탐색구조  (0) 2010.06.15
5. Tree  (0) 2010.06.08
4. Linked List  (0) 2010.06.07
2. 배열  (0) 2010.06.07

+ Recent posts