태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

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          

Notice

'(탈퇴) 테슬라's Post'에 해당되는 글 31

  1. 2009.04.01 음?... 후기랄까요?(2)
  2. 2009.03.30 Tesla's post 연기 공지
  3. 2009.03.25 그래프 - Prim식 최소신장트리??(2)
  4. 2009.03.24 Tesla's Post 연기 공지
  5. 2009.03.20 그래프 - Kruskal식 최소신장트리??(1)
  6. 2009.03.16 Tesla's Post 연기 공지(4)
  7. 2009.03.11 그래프 - 최소신장트리(Minimum spanning tree)??
  8. 2009.03.09 Tesla's Post 공지(1)
  9. 2009.03.02 그래프 - 신장트리(Spanning tree)??
  10. 2009.02.23 Tesla's Post 연기 공지(4)
  11. 2009.02.18 그래프(Graph) - 깊이우선검색(DFS)??(5)
  12. 2009.02.17 Tesla's Post 공지
  13. 2009.02.13 그래프(Graph) - 너비우선검색(BFS)??(9)
  14. 2009.02.05 그래프(Graph) - 표현법??
  15. 2009.01.25 Tesla's Post 연기 됩니다.
  16. 2009.01.20 그래프(Graph) - 그래프??(2)
  17. 2009.01.19 Tesla's post 연기 공지
  18. 2009.01.06 이진 트리(Binary Tree) - 이진 트리의 운행 2(5)
  19. 2008.12.30 이진 트리(Binary Tree) - 이진 트리의 운행 1(6)
  20. 2008.12.23 이진 트리(Binary Tree) - 이진 트리?(1)
  21. 2008.12.23 테슬라 포스트 연장 (정말 죄송합니다)
  22. 2008.12.15 [공지] 12/15일 포스트 연기 공지(1)
  23. 2008.12.08 이진 트리(Binary Tree) - 트리란?(7)
  24. 2008.11.17 테슬라's Post 연기 공지(5)
  25. 2008.11.10 동적인 단일 연결 리스트 (Singly Linked List) - 큐(4)
  26. 2008.11.04 동적인 단일 연결 리스트 (Singly Linked List) - 스택
  27. 2008.11.03 테슬라 포스트 살짝 연장 안내...
  28. 2008.10.27 동적인 단일 연결 리스트 (Singly Linked List) - 2(3)
  29. 2008.10.12 포스팅 연기에 관하여...(1)
  30. 2008.09.29 동적인 단일 연결 리스트 (Singly Linked List) - 1(5)
2009.04.01 23:56 (탈퇴) 테슬라's Post
안녕하세요~ 테슬라 입니다.

만우절이에요~ 모두 낚이셨죠?

위에건 무시하시고요~

요번에 이진트리와 그래프를 했습니다.

네. 제가 많이 미숙하여 부족한 부분이 있었던 기억이 새록새록하군요...

일단 그래프는 이걸로 끝을 본 것 같습니다.

제가 알고 있는 부분이 여기까지 인지라...

사실 제가 공부했던 경우에는 그래프 뒤에 최단거리를 구하는 알고리즘이 소개되었었는데요.

제가 그 부분은 아쉽게도 모르는 부분이라 설명해드리기가 힘들 것 같습니다.

제가 나중에 학습하여 포스트의 기회를 가지도록 하겠습니다.

다음 포스트 주제를 사실 정렬을 하고자 했지만, 아쉽게도 리턴군이 해서...

해서 다음 포스트 주제를 못정했어요...!!!! 떡밥이 다 떨어진 것이죠...!!!

아직 배움이 얕은지라 무엇을 해야할지 구체적으로 떠오르는 것이 없습니다.

해서 얼마 동안의 기간동안 떡밥을 찾아 떠나는 여행을 하려고요...

그 후에 포스팅을 하고자 합니다.

단 쌓여버린 문제들은 시간 나는 틈틈이 풀어서 올릴거에요. (더이상 쌓이면 감당 불가능할거 같아서...)

빠른 시간 안에 떡밥을 찾아내서 돌아오겠습니다.

네~ 그렇습니다~

그럼, 여러분 다음 시간까지 평안하시길~

'(탈퇴) 테슬라's Post' 카테고리의 다른 글

음?... 후기랄까요?  (2) 2009.04.01
Tesla's post 연기 공지  (0) 2009.03.30
그래프 - Prim식 최소신장트리??  (2) 2009.03.25
Tesla's Post 연기 공지  (0) 2009.03.24
그래프 - Kruskal식 최소신장트리??  (1) 2009.03.20
Tesla's Post 연기 공지  (4) 2009.03.16
posted by 비회원

댓글을 달아 주세요

  1. .... 완전히 잠수타실라고? =_=;;

  2. 테슬라 2009.04.02 22:25  Addr Edit/Del Reply

    음 포스트는 좀 천천히 할게... 떡밥이 없어서...;;
    그래도 문제는 계속 풀 예정이야...

2009.03.30 23:23 (탈퇴) 테슬라's Post
우아 이거... 이번주는 단체로 바쁘군요.

제가 사실 요즘 들어서 제 시간에 포스팅을 못하고 있습니다.(으, 죄송합니다.)

다음주까지는 아마 살짝 이런 현상이 지속될 거 같습니다.

아 그리고 오늘자 포스트는 수요일에 올라갈 것 같습니다.

넓으신 아량으로 용서해주세요.

'(탈퇴) 테슬라's Post' 카테고리의 다른 글

음?... 후기랄까요?  (2) 2009.04.01
Tesla's post 연기 공지  (0) 2009.03.30
그래프 - Prim식 최소신장트리??  (2) 2009.03.25
Tesla's Post 연기 공지  (0) 2009.03.24
그래프 - Kruskal식 최소신장트리??  (1) 2009.03.20
Tesla's Post 연기 공지  (4) 2009.03.16
posted by 비회원

댓글을 달아 주세요

2009.03.25 19:06 (탈퇴) 테슬라's Post

안녕하세요~ 테슬라 입니다.

저번에 이어서 이번 포스트는 최소신장트리 구현방식중에 하나인
Prim식 최소신장트리에 대해서 알아보도록 합시다.


저번 포스팅때 했던 Kruskal식을 생각해보죠...

그냥 가중치가 작은 순서대로 간선들을 이어서 하나의 최소신장트리를 만들었죠?

하지만 그 방법은 생각해보면 여러개의 트리를 잇고 이어서 하나의 큰 트리를 만드는 것이라고 생각할 수 있습니다. 예를 들어볼까요?

이런 그래프가 있다고 하죠. Kruskal식의 경우
사용자 삽입 이미지
라면,
사용자 삽입 이미지
이런 방법이지요?

이때 보시는 것처럼 여러개의 트리가 생긴 뒤 마지막에 모두 이어지는 모습을 보실 수 있으실거에요.

그런데 Prim식은 그런식으로 나눠져있다가 연결되는 방식을 거부한다는 것이지요.

말인즉슨, 하나의 트리에 계속 하나하나 간선들을 추가해서 이어나가는 겁니다.

단! 이때에도 역시 가중치가 작은 순서대로 잇는것입니다. 그래야 최소신장트리가 되는것이지요.

아까의 그림으로 연결해볼까요?
사용자 삽입 이미지
이런식인 것이죠. 자 첫번째는 시작이지요. 아까 Kruskal식의 두번째와는 다르게도 (1,2)와 연결하지요?

이는 1번에 연결되어있는 정점 ①과 ②로 구성된 트리에 연결할 수 있는 간선들 중 가중치가 제일 적은 것을 연결하는 것이지요.

세번째에서도 이처럼 정점 ①과 ②, ③으로 구성된 트리에서 연결할 수 있는 간선들 중 가장 가중치가 적은 (1,4)를 연결한 것입니다.

네번째도 결국 이어서 이런 모양이 되는 것이지요.

이런 식으로 별도의 트리를 만들어지지 않고 최소신장트리를 만드는 방법이 Prim식인 것이지요.


오늘은 여기까지입니다.
오늘도 혹시나 틀린 부분이나 오타 부분이 있다면 지적해 주시면 감사할 것입니다. 후훗

'(탈퇴) 테슬라's Post' 카테고리의 다른 글

음?... 후기랄까요?  (2) 2009.04.01
Tesla's post 연기 공지  (0) 2009.03.30
그래프 - Prim식 최소신장트리??  (2) 2009.03.25
Tesla's Post 연기 공지  (0) 2009.03.24
그래프 - Kruskal식 최소신장트리??  (1) 2009.03.20
Tesla's Post 연기 공지  (4) 2009.03.16
posted by 비회원

댓글을 달아 주세요

  1. prim 2009.03.25 20:19  Addr Edit/Del Reply

    tsp쪽에대해서 공부중인데요,,,
    "현재의 위치에서 가장 짧은 거리를 가지는
    정점순서대로 오름차순 정리를 하여 가장 짧은 경로부터 차례대로 경로를 설정하는 방법."

    이방법도 prim 식 MST 로 볼수가 있는건가요?

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2009.03.25 21:05  Addr Edit/Del

      약간 모호하네요. 현재의 위치에 대해 가장 짧은 정점을 1개 택하고, 그 정점으로 이동해 다시 반복하는 방식이라면 Prim알고리즘입니다. 반면 최초 위치를 기준으로 짧은 정점순으로 정렬한 후 그 정렬 순에 맞추어 고른다면 Kruskal식이구요.

2009.03.24 00:47 (탈퇴) 테슬라's Post
으악 요즘엔 제시간에 포스트를 한적이 굉장히 오래전으로 느껴지네요.
지금도 내일 시험이라 깜빡했다가 Dlbo군보고 떠올랐습니다. 요즘 정신을 어디다 두고 다니는지...
포스트는 수요일까지 올리도록 하겠습니다.
죄송합니다.
posted by 비회원

댓글을 달아 주세요

2009.03.20 00:21 (탈퇴) 테슬라's Post
안녕하세요~ 모두 잘 지내시죠~ 테슬라 입니다.

오늘은 저번 포스트에 이어 최소신장트리에 대해서 하고자 합니다.

오늘의 주제는 무엇인고 하니 최소신장트리를 구성하는 방법중에 하나인 Kruskal식의 최소신장트리입니다.


Kruskal식이란 무엇인가? 하니 가중치가 적은 순서대로 연결하는 방식을 말합니다.

각각의 간선마다 가중치가 존재하지요?

이 가중치들을 적은 순서대로 놓아보세요.

그 다음에 차근차근 작은 순서대로 간선들을 연결하지요.

단! 저번 포스트에서 말씀드린대로 최소신장트리는 사이클이 없어야겠죠?

오늘도 역시 예를 들어보지요~
사용자 삽입 이미지

자 이 그래프에는 5개의 간선들이 존재합니다. (저번거와는 가중치가 다릅니다. 네)

(1,2), (1,3), (1,4), (2,3), (3,4) 이렇게 5개가 있습니다.

이걸 가중치 순으로 늘여놓아보죠.
 (1,4), (3,4), (1,3), (2,3), (1,2) 이런 순입니다.

자, 연결해보죠.
사용자 삽입 이미지
왜 (2)에서 (3)으로 넘어갈 때 (1,3)으로 연결 안하느냐고 하시는 분들!!

아까 말씀드렸다시피 사이클이 생기면 안됩니다. 하지만 (1,4), (3,4)를 연결하었기 때문에 (1,3)을 연결하면
사이클이 생겨버리게 되는 것이지요.

그것을 막기 위해 (1,3)를 버리고 다음 간선인 (2,3) (이건 사이클이 안생기죠?)을 연결한 것입니다.

네, 그런식으로 정점보다 하나 적은 갯수를 연결합니다. 여기서 더 이으면 사이클이 생기지요.

이런식으로 그래프를 신장트리로 변환시키는 것입니다.

Kruskal식은 그렇게 어렵지 않지요?


자 Kruskal식은 이정도로 설명하겠습니다.
오타나 잘못된 부분은 지적해주시면 감사하겠습니다~
그럼 다음 포스트 때 만나요~
posted by 비회원

댓글을 달아 주세요

  1. 열혈학생 2009.06.02 01:45  Addr Edit/Del Reply

    공부에 많은 도움이 되었습니다 :)

2009.03.16 23:38 (탈퇴) 테슬라's Post
아아... 요즘에 다들 바쁜가 봅니다.
저도 휴가 나온 친구 만나는지라... 포스팅이 늦어질 것 같습니다. 죄송합니다.
내일은 개인적인 일이 있고...
수요일에 활기차게 다음 포스트를 들고 찾아오겠습니다.
posted by 비회원

댓글을 달아 주세요

  1. 문제도 좀 푸삼 ㅁ_ㅁ;

  2. 테슬라 2009.03.18 22:04  Addr Edit/Del Reply

    미안합니다 미안합니다 미안합니다 미안합니다 미안합니다 미안합니다 미안합니다 미안합니다
    하루만 더 시간을 미룰게요... 에 그리고 문제는... 언제 날 잡아서 미친듯이 풀게!!

  3. 학교를 다닌다는건 바쁜거야! 슬라군 안미안해해도 된다네!

    • 테슬라 2009.03.19 21:03  Addr Edit/Del

      오옷 알아주는거야~ 고마워~ ㅋㅋ

2009.03.11 18:40 (탈퇴) 테슬라's Post

안녕하세요~
오늘도 찾아왔습니다.
오늘은 굉장히 아주 굉장히 짧을 것 같습니다.

오늘은 저번에 말씀드린대로 최소신장트리(Minimum spanning tree)에 대해서 알아보고자 합니다.
저번시간에 신장트리에 대해서 말씀드렸었죠?
신장트리는 쉽게 말해 모든 정점을 연결한 트리를 말하는 것이지요? 연결을 최소로 한...

자 그럼 오늘 할 최소신장트리란 무엇인가?
신장트리에 최소가 들어갔네요.
음, 간단하게 해석하면 신장트리를 최소로 한다라고 할 수 있겠네요...
그런데 뭘 최소로 하는 걸까요?

여러분 지하철 타 보셨죠? 지하철로 예를 들어볼까요?
음 지하철을 타고 어떠한 지점에 간다고 할 때 최소한의 역을 통과해서 원하는 역에 도착할 수 있지요?
그런데 만약 다양한 길이 존재할 때 똑같은 정거장 수라도 가는 거리에 따라 걸리는 시간이 다르지요?
물론 약간 다른 예이긴 하지만요.

최소신장트리란 무엇인가?
지금까지 생각했던 신장트리는 어떤 간선이든 같은 것이라고 생각했지요? 물론 설명에도 별말이 없었고요.
하지만 그러한 간선에 가중치라는 것을 대입을 한다면 신장트리에 종류에 따라 다양한 총 가중치가 나오겠지요?
가중치라는 것은 쉽게 생각해서 걸리는 시간 정도로 생각하시면 편해요.

음 간단하게 예를 들어보지요.

사용자 삽입 이미지

저번에 했던 그래프를 예로 들어보죠. 옆에 써있는 빨간 숫자들이 가중치라고 하지요.
사용자 삽입 이미지
네~ 양쪽 모두 저번시간에 봤던데로 신장트리입니다.
하지만 왼쪽과 오른쪽은 가중치가 다르지요?
결국 총 가중치가 달라집니다. 왼쪽은 6, 오른쪽은 12네요.
오른쪽이 왼쪽보다 2배의 가중치가 드네요.

이처럼 각각에 가중치가 존재할 때 어떻하면 좀 더 적은 가중치로 신장트리를 구현하는 것이지요.
그것이 바로 최소신장트리입니다.
최소신장트리도 신장트리와 마찬가지로 사이클이 없어야 합니다. 뭐 트리니까요.
또한 최소의 간선을 연결하므로 결국 정점보다 하나 적은 갯수입니다.

최소신장트리를 구하는 방법이 몇가지가 있는데요.
그건 다음 포스트에 쓰도록 하겠습니다.
오타나 잘못된 부분은 지적해주심 감사하겠습니다~
그럼 다음 포스트 때 뵈요~

posted by 비회원

댓글을 달아 주세요

2009.03.09 23:14 (탈퇴) 테슬라's Post
아... 네... 안녕하세요~
잘 지내시죠?
이번에도 어김없이 새로운 학기가 시작되었군요...
(물론 아닌 분들도 계시지요...ㅎㅎ)

그래서 그런지 오늘과 내일은 좀 시간이 안될거 같아서요...

수요일에 시간이 될 듯 합니다. 포스팅은 그 때 하도록 하겠습니다.

시간을 지키지 못해서 죄송합니다.
posted by 비회원

댓글을 달아 주세요

  1. 기다리고 있심 -_-!

2009.03.02 23:46 (탈퇴) 테슬라's Post

네 안녕하심까~ 테슬라입니다.
자, 모두 개학 시즌이시죠? 새로운 마음으로 시작해볼까요?

오늘은 신장트리(Spanning tree)에 대해서 써볼까 합니다.

음 신장트리란 무엇인가?
임의의 그래프 G에 대한 부분그래프중에서 모든 정점과 연결된 부분 그래프를 말합니다.
부분그래프는 저번에 설명한 것과 같이 어떠한 그래프 G의 정점과 간선을 이용하여 만들수 있는 그래프를 말합니다.
집합에서 부분집합을 떠올리시면 되는것이지요.
단, 연결은 최소한으로 합니다. 괜시리 필요없이 간선을 사용 할 필요가 없다는 것이지요.

아무튼 이러한 부분그래프 중에서 이을 수 있는 모든 정점을 이으셔서 하나의 그래프를 만드시는 것이지요.
예를 들어볼까요?
 

사용자 삽입 이미지
자 요런 그래프가 있다고 하지요.
사용자 삽입 이미지

사용자 삽입 이미지

자 요런것들은 신장트리라고 할수 있을까요?
네, 당연히 가능합니다. 모든 정점들을 연결했으니까요.

그럼 아래것들은 어떨까요?
사용자 삽입 이미지
아쉽게도 둘 다 불가능 합니다.
왼쪽의 경우 최소의 간선을 이용하지 않았지요? ①, ③, ④ 부분에서 하나의 간선을 제거 할 수 있지요.
오른쪽의 경우는 ②, ④를 잇는 간선이 기본 그래프에 존재하지 않았기 때문에 존재하지 않는 간선을 사용할 수 없는것이지요.

음 그럼 잠시 생각해볼까요?
전에 포스팅했던 깊이우선과 너비우선 검색방식을 생각해봐요.
음 모두 최소의 간선을 이용해 모든 정점을 방문하려고했지요?
결국 각각을 깊이우선 신장트리, 너비우선 신장트리라고도 부르기도 하지요.
때문에 이 둘을 생각해보시면 신장트리가 좀 더 이해하기 쉬우실거에요.


에 오늘은 여기까지 입니다.
다음 포스팅은 아마도 최소신장트리가 되겠지요?
오타나 잘못된 부분은 지적해주심 감사하겠습니다~
posted by 비회원

댓글을 달아 주세요

2009.02.23 22:16 (탈퇴) 테슬라's Post
음 방학의 끝자락이라 그런지 정신없이 바뻐요...;;

이번주 내로 시간 내서 올리도록 하겠습니다.

으아 요즘에 제대로 시간을 못 맞추네요...죄송합니다.
posted by 비회원

댓글을 달아 주세요

  1. ... 난 휴학생이라 혼자 널널한건가.

  2. 테슬라 2009.02.24 14:04  Addr Edit/Del Reply

    그거보단 마지막이라 정리할게 좀 많네...ㅎㅎ;;

  3. 난 재학생임

2009.02.18 18:51 (탈퇴) 테슬라's Post

안녕하세요~
몰아하는 숙제에 치이며 사는 테슬라입니다.

오늘은 저번 시간에 이어 양대산맥중의 하나인
깊이우선검색(DFS = Depth First Search)에 대해서 포스팅하는군요.

깊이우선검색은 너비우선검색과는 다르게 시작 정점에서 하나만 죽어라 파고 들어가는 것이지요.
더 이상 파고 들어갈게 없으면 방문하지 않았던 남은 곳에서 이어서 다시 끝까지 파고드는 것을  반복하는 것이지요.

여기서도 방문했다는 체크는 필요합니다.
하지만 저번의 너비우선검색과는 약간 다릅니다.
왜 다를까요? 이유는 담아두는 방식의 차이입니다.
너비우선검색은 큐를 사용했지요? 그렇다면 깊이우선검색은 스택을 사용합니다.
큐는 먼저 들어가면 어떻게 되도 먼저 나올 수 밖에 없기 때문에 들어갈때 체크해도 상관없지만,
스택의 경우 먼저에 들어가는것이 나중에 나오니 먼저 들어간다 하더라도 그 경우보다 나중에 스택에 쌓이면서 더 일찍 방문 될 수 있는것이지요.

자 이렇게 말하니 설명이 이상하실수도 있으니 예를 들어가면서 볼까요?

사용자 삽입 이미지
 저번에 썼던 그래프입니다.
사용자 삽입 이미지

이것도 같지요.

자 저번처럼 A부터 시작합시다.
A를 방문합니다. 방문했다고 체크해줍니다.
그리고 A에 연결된 나머지 노드들을 스택에 넣어줍니다
사용자 삽입 이미지

A의 방문을 마쳤으니 스택에서 하나 꺼내주죠.
B가 나오는군요. B를 방문했습니다. 체크~
B를 보니 A 와만 연결됬는데 A는 체크되어 있으니 넣어줄게 없네요.
사용자 삽입 이미지

다음것을 꺼내니 C가 나오네요.
C에는 A와 D가 연결되어 있네요.
A는 체크되어있으니 D를 넣어줍니다. 스택 안에 들어있어도 먼저 처리되지는 않으니 넣어주세요.
사용자 삽입 이미지
자 꺼내줍시다. D가 나오는군요. D에는 A, C, G가 연결되어 있군요.
A와 C는 이미 방문 체크되어 있으니 G를 넣어줍니다.
사용자 삽입 이미지

자, 또 스택에서 꺼냅시다. 역시 방금 넣은 G가 나오는군요.
G의 연결 노드중 E만 아직 방문가 되지 않았네요.
넣어주세요.

사용자 삽입 이미지
이제 또 꺼냅시다. 이번엔 E군요.
E에는 F만 방문하지 않았네요. 스택에 넣으면
사용자 삽입 이미지
자 스택에서 꺼내면 F가 나오네요.
F에는 E만 연결되어있는데 아까 처리됬으니 넘어가겠군요.
그럼 스택에서 꺼내봅시다. D가 나오겠지요. 하지만 D는 아까 방문했으니 넘어가고, 다음것인 E도 방문했었지요.
더이상 스택에 남은것이 없네요. 그럼 방문이 완료된 것입니다.

방문 순서는 A-> B-> C-> D-> G-> E-> F 순이군요.
그림으로 보인다면
사용자 삽입 이미지
이렇게 되겠지요?

아 그리고 말씀드릴것이 있는데 꼭 모두 스택에 담을 필요는 없습니다.
현재 정점에서 연결되어있는 방문하지 않은 정점(노드)가 두 개 이상일 때 하나만 스택에 넣어주고 다른 하나를 방문해주면 됩니다.
만약 방문 안한 정점이 하나라면 바로 거기를 방문하면 되는 것이지요.
왜일까요?
ⓞ이라는 노드에 ①과 ②라는 노드가 연결되어 있다고 칩시다.
사용자 삽입 이미지

위에 것은 모두 스택에 넣었다가 하나를 꺼내는겁니다.
밑에것은 하나는 스택에 넣고, 다른 하나를 방문하는 겁니다.
보시다시피 결국은 ①이 방문되지요?
이런식으로 모두 스택에 넣을 필요는 없지요.

그럼 왜 저는 넣었을까요...음...그냥 설명하기 편하려고...크흠...
음음 아무튼 깊이우선검색은 스택을 이용하여 사용할 수 있습니다.

자 오늘도 틀린 부분이나 오타가 있다면 꼭꼭 알려주세요!!

posted by 비회원

댓글을 달아 주세요

  1. 정승훈 2009.06.11 02:39  Addr Edit/Del Reply

    와~~ 자료구조공부하는데 좋은 참고자료됬습니다~~~

  2. 쟈스민향 2010.05.29 22:40  Addr Edit/Del Reply

    저도저도~ 엄청엄청~

  3. 카르님 2011.12.10 23:20  Addr Edit/Del Reply

    작성자님..이해가 잘안되는게 있는데요..깊이 우선은. 스택이고 너비 우선은 큐 로 알고 있습니다.
    근데 지금 포스팅된 내용 너비랑 ,깊이 둘다 같은 연결리스트를 사용했는데요..
    스택이랑 큐랑은 나오는게 반대로 되야 할것같은데 왜 둘다 b부터 나오는거죠?

    • Favicon of https://studyinglw2.tistory.com BlogIcon Milkskin 2012.01.03 23:46 신고  Addr Edit/Del

      이건 아마 작성자분의 실수인 것 같습니다 ^^;

      "너비우선검색" 포스트에서는 A가 가리키는 순서대로 큐에 삽입을 하더니,
      이 포스트에서는 아무 언급 없이 A가 가리키는 순서의 역순으로 스택에 삽입을 해버렸네요 -_-;

      그점 참고하고 보시면 왜 이 포스트에서도 B부터 나오는지 이해가 되셨겠지요?

      --------------------------------

      만약 A가 가리키는 순서대로 스택에 삽입을 했다면

      A를 방문하고, 스택에 B C D E를 넣고
      E를 꺼내고(방문하고), 스택에 F G를 넣고
      G를 꺼내고(방문하고), 스택에 D를 넣고
      D를 꺼내고(방문하고), 스택에 C를 넣고
      C를 꺼내고(방문하고), 스택 변화없음
      F를 꺼내고(방문하고), 스택 변화없음
      D를 꺼내고(이미 방문함), 스택 변화없음
      C를 꺼내고(이미 방문함), 스택 변화없음
      B를 꺼내고(방문하고), 스택 변화없음
      이상 탐색 끝

      해서, 탐색 순서는 A→E→G→D→C→F→B 가 될 것 같네요 :)

  4. hinu 2014.06.18 23:04  Addr Edit/Del Reply

    솔직히 저희 교수님 설명보다 이해하기 쉽네요 한번에 알아챔 ㅋㅋ

2009.02.17 19:40 (탈퇴) 테슬라's Post

으아 죄송합니다.

방학이 막바지에 들어가니 할일이 산더미네요.

방학 과제 몰아서 하는 초등학생의 기분을 느끼고 있습니다.

포스트는 오늘 새벽이나 늦어도 내일까지는 올리겠습니다.

posted by 비회원

댓글을 달아 주세요

2009.02.13 00:00 (탈퇴) 테슬라's Post

자 돌아왔습니다. 점차 불량 마감 작가와 같이 변해가는군요...흑흑

자 오늘은 그래프에서 너비우선검색에 대해서 해보도록 하겠습니다.
자 저번시간에 표현법에 대해서 했지요?
그런데 컴퓨터로 표현해도 결국은 써먹어야겠지요?

트리에서도 했지만 만약에 모든 노드들을 방문해야 한다면...??
그렇지요. 결국은 검색하는 운행법이 있어야겠지요?

트리에는 전위, 중위, 후위, 레벨 운행법이 있었죠?
그런것처럼 그래프에도 크게 너비우선검색(BFS = Breadth First Search)와 깊이우선검색(DFS = Depth First Search)이 있습니다.
오늘은 너비우선검색에 대해서 하도록 하겠습니다.

자 방문을 하려고 한다면? 그렇죠. 시작점이 있어야겠죠?
그런데 우리의 그래프...트리와는 달리 이곳 저곳 연결이 되어있지요?
때문에 그래프는 노드에 방문했었다는 체크표시가 필요합니다.

자 아무튼 시작점에서 시작합니다.
이때 시작점을 방문하고 그 시작점에 연결된 정점들을 모두 방문합니다. 그 후에 방문하지 않은 연결된 정점들에 연결된 정점을 방문하는 것이죠. 음 설명이 짧군요.

자세히 설명한다면 시작점을 선택해서 방문합니다.
방문하는 정점에 연결된 다른 정점중에 방문하지 않은 정점을 큐에 담아둡니다.
큐에서 꺼내면서 이 짓을 반복하는것이지요.

그럼 예를 들어보도록 하도록 하겠습니다.

사용자 삽입 이미지

요런 그래프가 있습니다. 음 모양이 참 예쁘네요.
아무튼 이것을 인접리스트로 표현해보죠.
사용자 삽입 이미지

으아 완전 많군요... 에휴... 맞겠죠...?
자 시작은 친절히 A라고 합시다.
A를 방문합니다. A에 연결된 노드들을 큐에 넣어줍니다.
큐에 넣을때는 방문예정이니까 체크해주세요

사용자 삽입 이미지

A를 방문합니다. 방문한 뒤에 다음 것을 큐에서 꺼내보죠.

B가 나오겠네요. 아하 이런 B에 연결되있는 A는 이미 방문했군요. 다음것을 큐에서 꺼냅시다.

그럼 큐에서 C가 나오겠군요. C에는 A와 D가 연결되있군요.
A는 방문했으니 제외되고 D도 체크 되서 큐에는 안 들어갑니다.

다음에는 D군요. D에 연결되있는 A, C, G 중 A, C를 제외되고,
G는 아직 아무짓도 안했으니 큐에 넣어주고 체크합니다.
사용자 삽입 이미지
자 이제 E를 꺼내봅시다. A, F, G중 A, G를 제외하고 F가 큐에 들어가겠군요.

사용자 삽입 이미지
자 다음 G를 꺼냅니다. D, E 모두 방문했지요.
F를 꺼냅니다. E는 모두 방문했죠?
자 큐에 남은게 없군요. 모두 방문했지요. 순서대로 정리하면
A-> B-> C-> D-> E-> G-> F 겠죠?
음 그래프로 나타내면?

사용자 삽입 이미지
자 이렇게 되는것이죠. 네...맞겠죠...
자 이런식으로 방문하는것이죠...
자 오늘은 여기까지 입니다.
다음은 깊이우선검색을 다루도록 하지요.

오타나 제가 잘못 설명한 부분이 있으면 지적해주세요.
전 여러분의 지적을 받으며 자라난답니다...자라나겠죠? 상처받나...?
posted by 비회원

댓글을 달아 주세요

  1. 왜이리 글에 자신이 없어 -ㅁ- 그리고 다들 2월이라 바쁜지 마감 거의 못맞춰 ㅡ.,ㅡ;;

    • 테슬라 2009.02.13 01:19  Addr Edit/Del

      후훗 난 기억을 믿지 않아서...
      사실 다음주까지 끝낼게 많아서 정신이 없어...ㅎㅎ;;

  2. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2009.02.13 00:33  Addr Edit/Del Reply

    ㅋㅋ 언제나 쉽게 잘 읽고 있는 1人

    • 테슬라 2009.02.13 01:20  Addr Edit/Del

      오오 그렇군~ 감사하네~
      다행이도 읽어주는 사람이 있다니...ㅎㅎ

  3. 흐미.. 2009.06.15 23:10  Addr Edit/Del Reply

    어려워.. ㅡㅡ; 이해 안돼요.. ;; A 에 연결된 노드들을 큐에 넣을때는 어떤 순서로 넣는거에여? 자기 맘대로?? ;;

  4. 쟈스민향 2010.05.29 22:26  Addr Edit/Del Reply

    너무 쉽게 잘 공부하고 갑니다 ^^

  5. 빵똥 2011.12.04 01:02  Addr Edit/Del Reply

    좋은글 보고갑니다~ 덕분에 시험공부 잘 되네요 ㅎ

  6. aa 2012.06.17 21:42  Addr Edit/Del Reply

    드디어 이해했네요 너무 쉽게 알려주셔서 감사합니다! ㅠㅠㅠㅠㅠㅠ

2009.02.05 20:27 (탈퇴) 테슬라's Post

안녕하세요~ 무단이탈(????) 했던 테슬라입니다.
늦어서 죄송합니다.
요즘에 정신없는 나날들이여서 포스트 쓰는것도 깜빡했지 뭐겠어요...

저번시간에 그래프에 대해서 했었지요.
그런데!!! 그 그래프를 어떻게 컴퓨터로 표현해야 할까요?
그냥 그림처럼 편하게 넣을 수 있으면 좋겠지만 그게 말처럼 되는건 아니지요.
그래서 오늘은 그래프의 표현방법에 대해서 해볼게요.

자 컴퓨터로 표현하기 위한 방법으로 인접행렬(Adjacency Matrix)와 인접리스트(Adjacency List)가 있습니다.

우선 인접행렬에 대해서 알아볼까요?
만약 n개의 점을 갖는 그래프라면 인접행렬은 n*n행렬로 표현되고,
만약 두개의 점 Vi, Vj사이에 간선이 존재한다면 (i,j)에 값이 1이고 없다면 0으로 저장합니다.
배열을 이용해 표현이 가능하지요.
물론 방향성과 무방향성그래프가 차이가 있다는것은 당연지사 입니다.
예를 들어볼까요?
 

사용자 삽입 이미지

요런 그래프가 있다고 합시다.
저번에 했던 집합으로 표현해봅시다.
왼쪽의 무방향 그래프를 G1, 오른쪽의 방향성 그래프를 G2라고 한다면,

V(G1) = { 1, 2, 3, 4 }
E(G1) = { (1, 2), (1, 3), (1, 4), (2, 3), (3, 4) }

V(G2) = { 1, 2, 3, 4 }
E(G2) = { <1, 2>, <1, 4>, <2, 3>, <3, 1>, <3, 4> }

겠죠?

먼저 방향성 그래프 G2를 보도록 하지요.
사용자 삽입 이미지
자, 요런 모양이 되지요.
그럼 무방향 그래프 G1을 볼까요?
사용자 삽입 이미지
자 이렇게 됩니다. 왜 그럴까요?
정답은 무방향 그래프의 경우 양쪽 모두를 향했다고 생각하면 되기 때문에 ( (1,2) = (2,1) )
모두 채우면 이렇게 되는것이지요.
음... 그런데 눈치 채셨나요?
 
사용자 삽입 이미지
양쪽이 대칭이지요?
무방향 그래프는 방향성 그래프를 대칭으로 해서 0부분에 1이 대칭되고 있으면 1로 바꿔주면 됩니다.
아 물론 무방향 그래프와 방향성 그래프가 같은 형태라면 말이지요.
하아 그런데 이 인접행렬에도 문제가 있습니다.
이럴 경우를 생각해 봅시다.
사용자 삽입 이미지
자 우리에게 필요한 간선은 1로 표시되고 연결되지 않은 나머지 필요하지 않는 부분은 0으로 처리됩니다.
그런데, 이처럼 채워지는 간선이 적다면... 네, 기억장소에 낭비가 생기겠지요?

그래서 연결되는 간선이 적을 경우 기억장소의 낭비를 줄이기 위한 방법으로 인접리스트가 있습니다.
인접리스트는 인접행렬에서 n개의 행을 n개의 연결리스트로 표현한 것입니다.
즉 n개의 점을 n개의 연결리스트로 표현했다고 할 수도 있는 것이지요.

인접리스트는 연결 되어있는 점들만 리스트로 표현하므로 기억장소를 절약할 수 있지요.
하지만 연결 리스트는 연결주소를 가지고 있어야 하므로,
연결된 간선이 많아진다면면 기억장소의 낭비가 심해질 수 있는 문제를 가지고 있어요.
때문에 자신의 그래프에 따라 잘 선택해서 사용하는 것이 좋겠죠?

자 그럼 인접리스트를 예로 들어볼까요?
사용자 삽입 이미지
아까 예제로 사용했던 그림입니다.
왼쪽의 무방향 그래프를 G1, 오른쪽의 방향성 그래프를 G2라고 한다면,

V(G1) = { 1, 2, 3, 4 }
E(G1) = { (1, 2), (1, 3), (1, 4), (2, 3), (3, 4) }

V(G2) = { 1, 2, 3, 4 }
E(G2) = { <1, 2>, <1, 4>, <2, 3>, <3, 1>, <3, 4> }

이건 그대로지요?
자 우선 G2인 방향성 그래프를 인접리스트로 나타내면,
사용자 삽입 이미지
이 됩니다. 자 1에서 시작되는 간선들의 진입하는 2와 4가 연결리스트에 추가되는 것이지요.
다른것도 이와 마찬가지 입니다.
그럼 무방향 그래프 G1을 볼까요?

사용자 삽입 이미지
음 그냥 정점에 연결되어 있는 다른 모든 정점들을 가지는군요.
인접행렬이 가지고 있는 값을 그냥 연결리스트로 표현한 것입니다.

음 오늘은 여기까지 입니다.
틀린 부분이나 오타가 있으면 알려주세요~

'(탈퇴) 테슬라's Post' 카테고리의 다른 글

Tesla's Post 공지  (0) 2009.02.17
그래프(Graph) - 너비우선검색(BFS)??  (9) 2009.02.13
그래프(Graph) - 표현법??  (0) 2009.02.05
Tesla's Post 연기 됩니다.  (0) 2009.01.25
그래프(Graph) - 그래프??  (2) 2009.01.20
Tesla's post 연기 공지  (0) 2009.01.19
posted by 비회원

댓글을 달아 주세요

2009.01.25 10:49 (탈퇴) 테슬라's Post
일시 : 1/26

사유 : 민족의 명절 설이라서요...

에, 이번 설에는 포스트를 올리기 힘들겠어요. 이번 주 포스트는 쉬고 다음 주에 뵙도록 할게요.
모두 모두 새해 복 많이 받으세요~~
posted by 비회원

댓글을 달아 주세요

2009.01.20 15:16 (탈퇴) 테슬라's Post
안녕하세요~
오늘 이 시간에는 그래프에 대해서 알아볼까 합니다.
음 그래프란 무엇일까요?

그래프란 유한 개의 정점(V(G))과 유한개의 간선(E(G)) 구성된 집합입니다.
간선의 집합은 공집합일수도 있습니다. 즉 정점의 경우 하나도 존재하지 않는 그래프는 없지만 간선이 존재하지 않는 그래프는 존재할 수 있습니다.
사용자 삽입 이미지
예를 들어 이런 그래프가 있다고 한다면 각각의 점이라고 할수 있는 A, B, C, D는 정점이고,
이의 연결선이 간선입니다.

V(G) = {A, B, C, D}
E(G) = {(A,B), (A,C), (A,D), (B,D), (C,D)}

라고 할 수 있습니다.

사용자 삽입 이미지

또한 왼쪽의 경우 그래프라 할 수 있지만 오른쪽은 그래프라 할 수 없는것이지요.

그래프에는 방향성을 가지느냐 가지지 않느냐로 방향성 그래프(directed graph)와
무방향성 그래프(undirected graph) 두 가지로 나누어 집니다.
사용자 삽입 이미지

왼쪽이 무방향 그래프입니다. 간선에 방향성이 없지요? 이렇듯 두개의 정점을 연결하는 간선들에 방향성이 없는것을 무방향 그래프라고 합니다. 이때 (A,B)와 (B,A)는 같은 간선을 표현했다고 할 수 있습니다.
집합으로 표현하자면

V(G) = {A, B, C, D}
E(G) = {(A,B), (A,C), (A,D), (B,D), (C,D)}

가 될 수 있겠죠?

오른쪽의 경우를 볼까요? 네 화살표가 있네요. 이렇게 방향을 가지고 있는 그래프를 방향성 그래프라고 합니다.
이렇게 방향을 가진 그래프를 집합으로 표현할 때 ()가 아닌 <>를 사용합니다.

V(G) = {A, B, C, D}
E(G) = {<A,B>, <A,C>, <A,D>, <B,D>, <D,C>}

라고 표현합니다. 처음부분은 출발하는 정점, 뒤에는 도착하는 정점을 표현합니다.


또 그래프에는 루프(self loop)라는 것이 있습니다.
그냥 어떠한 정점에서 나와서 다시 그 정점으로 들어가는 간선을 말합니다.
사용자 삽입 이미지
이런것을 말이지요. 왼쪽의 경우 무방향성이므로 (A,A)이고 오른쪽은 방향성이므로 <A,A>라고 해야 겠지요?

그래프에는 완전그래프(complete graph)와 부분그래프(subgraph)라는 것이 있습니다.
완전그래프라는것은 이름에서 느껴지듯이 모든 정점이 다른 모든 정점으로 간선이 이어져 있는것을 말합니다.
사용자 삽입 이미지

위에 그림을 볼까요? 처음 그래프는 정점이 하나인 그래프이군요. 연결될 다른 정점이 없으니 간선은 없네요

두번째 그래프는 정점이 두개가 있군요. 이러면 그 둘의 정점을 이을 간선이 하나 존재하겠네요.

세번째그래프는 어떤가요? 세개의 정점을 모두 이어야 하므로 3개, 네번째그래프는 네개의 정점을 잇는 6개의
간선들이 존재하는군요. 정점의 갯수를 n이라고 할때, 완전그래프의 간선의 개수는 n(n-1)/2 이겠지요?
아 이건 무방향 그래프이지요?

방향 그래프라면 A라는 정점에서 B라는 정점으로 가는 간선과 B라는 정점에서 A라는 정점으로 가는 간선이 존재하므로 2개의 간선이 생기지요? 때문에 무방향 그래프보다 2개의 간선의 개수를 가지므로 n(n-1)이 되겠군요.

부분그래프를 N이라 하면 완전그래프 G에 대해서 V(N)⊆V(G) 이고 E(N)⊆E(G)인 그래프를 말합니다.
즉 완전그래프의 부분집합인 그래프인 것이지요.


그래프에 인접하다(adjacent)와 부속하다(incident)라는 말이 있습니다.

인접하다라는 것은 간선으로 이어진 정점들을 인접하다라고 합니다.
만약 간선이 (A,B)라고 한다면 A와 B는 인접한다고 할 수 있는것이지요.

부속하다라는 것은 정점에 이어져있는 간선들은 그 정점에 부속한다고 할 수 있는것입니다.
아까 예를 들었던 간선(A,B)는 정점 A와 B의 부속한다고 할 수 있습니다.

마지막으로 차수(degree)라는 것이 있습니다.
차수라는 것은 어떤 정점에 부속되어있는 간선의 개수를 차수라고 합니다.
사용자 삽입 이미지
이런 그래프가 있다고 해보지요. 왼쪽의 무방향성 그래프의 정점 A의 차수는 몇일까요?
A를 보시면 3개의 간선과 만나고 있지요?
왜 간선은 2개인데 3개랑 만나고 있다고 하냐고 궁금해 하실수도 있겠군요.
루프의 경우 두 부분 모두 A와 만나고 있기 때문이지요.
이렇게 루프의 경우 2개로 셉니다. 그러므로 왼쪽의 경우 A의 차수는 3입니다.

그럼 오른쪽의 방향성 그래프를 볼까요?
방향성 그래프는 무방향성과 다르게 진입차수(indegree)와 진출차수(outdegree)라는 것이 있습니다.
진입차수는 이름대로 그 정점으로 들어오는 즉 화살표의 촉 방향을 말합니다.
진출차수는 반대로 정점에서 시작하는 즉 화살표가 시작하는 부분인 것이지요.
그럼 오른쪽의 방향성 그래프의 정점 A의 차수를 세볼까요?
우선 진입차수는 A에 루프에서 오는 촉이 하나가 있으므로  1이고,
진출차수는 루프의 시작부분과 B로 향하는 화살표 총 2개가 있으므로 2가 되겠지요.



음 오늘은 그래프에 대하여 글을 써봤는데요.
고칠 부분이나 빠진 부분이 있으면 알려주시길 빌게요~
posted by 비회원

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.01.20 15:44  Addr Edit/Del Reply

    무향그래프랑 유향그래프 얘기할때

    undirected랑 directed가 바뀐듯?;

2009.01.19 20:41 (탈퇴) 테슬라's Post
으아 연구실에 있다보니 깜빡했습니다.

집에가면 11시가 넘어서 도착할거 같아요

음 내일 아침까지 꼭 올리도록 하겠습니다

정말이에요... 진짜입니다.
posted by 비회원

댓글을 달아 주세요

2009.01.06 17:16 (탈퇴) 테슬라's Post

안녕하세요~
이진 트리의 운행 두번째 시간이 돌아왔습니다.
오늘 아침까지 NAT씨께서 침묵상태에 빠졌어서 오늘에야 글을 쓰게 되었군요.
(으아 임시 저장된 줄 알고 막 닫았다가 다시 쓰게되네요...흠흠)

오늘 다룰 부분은 중위운행법과 후위운행법, 레벨운행법인데요.
모두 그렇게 어려운 내용이 아니기 때문에 저번 전위운행법을 이해하셨던 분이라면 충분히 이해하실 수 있으실겁니다. 자 그럼 시작할게요.

음 저번 포스트를 생각해보죠.

사용자 삽입 이미지

이런 트리가 있다고 생각해보죠~
이 트리의 경우 전위 운행법으로 운행했을때 어땠나요?
A노드가 먼저 방문되고, A노드의 왼쪽인 B노드, A노드의 오른쪽인 C 순으로 방문되었지요?
사용자 삽입 이미지
이런식으로 A->B->C 이지요?



그렇다면 지금 이야기할 중위 운행법(inorder traversal)은 어떨까요?
중위운행법은 특정한 노드를 기점으로 해서 그 노드의 왼쪽 서브트리를 먼저 방문하고, 그 다음 자기 자신,
그 후에 그 노드의 오른쪽 서브트리를 방문하게됩니다.

예를 들어 아까 예제를 가지고 한다면
A노드가 A노드의 왼쪽서브트리를 방문한 후에 방문됩니다. 즉, 이름에 걸맞게 A노드는 중간에 방문되는거지요.
그리고 그 후에 A노드의 오른쪽 서브트리를 방문하는 거지요. 위에 있는 예를 가지고 표현한다면
사용자 삽입 이미지
요런 식으로 방문되는 겁니다. 뭐 순서는 B->A->C순이겠네요.

그럼 좀 더 큰 예제를 가지고 생각해볼까요?
사용자 삽입 이미지
저번에 예제로 썼던 트리입니다.
이 트리를 가지고 예를 들어봐요.
우선 A노드의 왼쪽서브트리인 B노드부터 시작을 하려고 하는데...
어익후 B노드도 서브트리를 가지고 있네요.
그럼 B노드의 왼쪽서브트리인 D노드부터 시작해야겠네요.
D노드에는 서브트리가 없으니까 맨 왼쪽에 있는 D노드를 방문하며 시작됩니다.
그 다음엔 D노드의 부모노드인 B노드를 방문하겠지요?
그리고 B노드의 오른쪽서브트리인 E노드로 가겠지요?
A노드의 왼쪽 서브트리는 모두 방문 했습니다.
이제 A노드가 방문 되겠군요. 그 다음 오른쪽 서브트리를 방문하겠지요?
이때 오른쪽 서브트리를 생각해보죠.
C노드는 서브트리를 가지고 있습니다. 때문에 C노드의 왼쪽 서브트리인 F노드를 먼저 방문합니다.
그 후 C노드를 방문하고 C노드의 오른쪽  서브트리인 G노드가 방문됩니다.
사용자 삽입 이미지
순서대로 나열하면 D -> B -> E -> A -> F -> C -> G 순서겠죠?



다음으로 후위운행법(postorder traversal)을 설명드릴게요.
음 전위랑 중위를 보면 후위는 어떤식으로 운영될지 예상 되시죠?
후위운행법은 특정한 노드에서 자신의 왼쪽서브트리를 모두 방문하고, 그 다음에는 오른쪽 서브트리, 마지막에야 자기 자신이 방문되는 것입니다.
사용자 삽입 이미지
이런 식인거지요.

아까 큰 트리를 예로 들어보죠.
사용자 삽입 이미지
우선 A노드의 왼쪽서브트리인 B노드부터 시작을 하려고 하는데...
어익후 B노드도 서브트리를 가지고 있네요.
그럼 B노드의 왼쪽서브트리인 D노드부터 시작해야겠네요.
D노드를 방문하고 나서 B노드의 오른쪽서브트리인 E노드를 방문합니다.
이때 E노드에는 서브트리가 없으므로, 왼쪽, 오른쪽 서브트리들을 모두 방문한 부모노드인 B노드가 방문됩니다.
A의 왼쪽 서브트리들은 모두 방문했습니다. A의 오른쪽 서브트리인 C서브트리 차례군요.
C서브트리에는 F와 G노드를 가지고 있습니다. 때문에 C노드의 왼쪽 서브트리인 F노드로 향하는군요.
F노드는 서브트리를 가지지 않으므로 F노드가 방문 됩니다.
F노드 방문후 C노드의 오른쪽 서브트리인 G노드로 가는데 마찬가지로 서브트리가 없으므로 G노드를 방문합니다.
이제 C의 왼쪽, 오른쪽 서브트리를 모두 방문 했으므로 C노드를 방문합니다.
이제 A노드의 왼쪽 오른쪽 서브트리를 모두 방문했네요 마지막에야 A노드가 방문됩니다.
사용자 삽입 이미지
순서대로 쓰면 D -> E -> B -> F -> G -> C -> A 순이 되겠군요.


저번과 같이 표기식을 사용 예로 들어볼까요?
사용자 삽입 이미지

중위표기식(infix)는
사용자 삽입 이미지

A+B-C/D 순이겠죠?

후위표기식(postfix)으로는
사용자 삽입 이미지

AB+CD/-순 이겠네요.

마지막으로 그 세가지 운행법과 다른 방식인 레벨운행법(levelorder traversal)이 있습니다.
이건 쉬워요. 이름 그대로 레벨 순서대로 방문하는 겁니다. 높은 레벨에서 낮은 레벨 순이지요.
사용자 삽입 이미지
최상위 레벨인 A노드를 방문합니다.
다음 레벨인 B노드C노드를 방문합니다.
마지막 레벨인 D노드 E노드, F노드 G노드를 방문합니다.
순서대로 쓰면 A -> B -> C -> D -> E -> F -> G순입니다.
음 레벨운행법은 그래프에서의 너비우선검색과 비슷하게 운행된다고 할 수있습니다.



음 오늘은 세가지 운행법을 알아봤는데요. 오타나 실수는 지적해주세요~
만약 틀린 부분이 있다면 그 부분도 지적해 주심 감사하겠습니다.
posted by 비회원

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.01.07 03:07  Addr Edit/Del Reply

    후위표기식에서 postfox 오타;

  2. 우왕ㅋ굳ㅋ 2009.10.16 21:49  Addr Edit/Del Reply

    어려웠는데 이해하기 쉽게 설명 잘하신다 강사하세여

  3. ms.J 2011.12.07 11:23  Addr Edit/Del Reply

    정말 많은 도움이 되었습니다^^ 그런데요..
        A
        ㅅ
       B  C
      ㅅ   ㅅ
     D E  F  G
            ㅅ
           H I

    이런 트리가 있을 때, 중위 운행법에서는 어떻게 읽어야 할지요?

2008.12.30 10:49 (탈퇴) 테슬라's Post
안녕하세요~
깜빡 졸았다가 깨어보니 아침이라는 루트를 밟고 있는 테슬라입니다.
오늘은 이진 트리를 운행하는 방식에 대하여 알아볼까합니다...

음 트리를 운행한다에 대해서 말씀드릴께요.
트리를 운행한다가 무슨 말인고 하니 트리의 각 노드들을 한번씩은 방문한다는
모든 노드를 한번씩 지나가는 경우를 말합니다.

그럼 왜 운행해야 할까요?
음 트리에 있는 정보를 적절하게 골고루 모두모두 사용하려고 입니다.
또는 트리 안에 있는 정보를 찾고자 할 때도 쭉쭉 찾아볼 필요도 있고,
(트리가 이진 검색 트리처럼 정리가 안 되있을 수도 있지요.)
순서대로 자료들을 이동시켜야 할 때 (예컨데 트리를 리스트 형식으로 바꾼다던지...)
뭐 이럴 경우 한번씩은 확인 해야 하니까요.

음 그럼 이제 운행법에 대해서 알아볼까요?
사용자 삽입 이미지
이런 트리가 있다고 해봐요
이 3개의 노드를 각각 읽는 방법은 무엇이 있을까요?
음 ,A-B-C, A-C-B, B-A-C, B-C-A, C-A-B, C-B-A 6개 입니다. 3!이군요.
물론 이때는 방향을 고려하지 않은 아무렇게나 운행되는 운행방법입니다.
그럼 한쪽 방향으로만 운행한다고 치면 절반인 3개가 나오겠죠?
음 이때 여기서는 A노드인 루트노드가 언제 방문되는가에 따라서
전위운행법(preorder), 중위운행법(inorder), 후위운행법(postorder)
이 3가지로 나누어집니다.
루트노드가 먼저 방문되면 전위운행, 가운데에 방문되면 중위운행, 마지막에 방문되면 후위운행이라고 합니다.
자 그럼 각각에 대해 알아볼까요?

우선 전위운행법(preorder traversal)은
아까 말했듯이 어떤 노드가 자신의 노드(자기 관점으로 보면 루트노드지요?)를 먼저 방문하고,
왼쪽 서브트리를 방문하고, 그 후에 오른쪽 서브트리를 방문합니다.
음 왜 아까는 노드라고 해놓고 이번에는 서브트리라는 말이 나왔냐고 물으신다면,
아까의 예는 노드가 3개밖에 없는 작은 트리였지만, 이제부터 예를 들려는 트리는 그것보다는 레벨이 높은
트리에 대해서 말씀을 드리기 위해서 입니다. 뭐 그렇다고 크게 바뀌는건...없겠지요...?
사용자 삽입 이미지

요론 트리가 있다고 치죠.
A노드에서 자신을 읽고 B노드로 향하겠죠? 자 B노드 입장에선 밑에 노드 두개를 끼고 있지요?
그럼 B노드에서도 전위운행법을 사용해야 하기 때문에 B 다음은 D노드, D노드 다음 노드는 없으므로,
B노드의 오른쪽 노드인 E노드, 자 A노드의 왼쪽 노드들은 전위운행법으로 한번씩 방문했지요?
그럼 A노드의 오른쪽 노드 C을 방문하고나서는 아까 B노드 방문했을때처럼 F->G 노드를 방문하게 되겠지요?

그러니까 제 말은 루트에서 왼쪽 노드로 향하더라도 그 왼쪽노드에 부수적으로 노드들을 달고 있다면,
그 노드들도 전위운행법으로 방문을 하고 오른쪽 노드로 가야겠지요. 이때에는 왼쪽노드가 아~까 위쪽에서
예를 제시한 노드 3개짜리 트리에서 루트의 역할을 하게 되는 것이지요.

방향으로 나타내면
사용자 삽입 이미지

요런 모양이 나옵니다.
음 한가지 사용 예로 전위표기식(prefix)이라는 산술표기식을 들 수 있는데요.
사용자 삽입 이미지
요런 모양의 트리가 있다고 하지요
일반적으로 우리들이 쓰는 중위표기법(infix)로 나타내면 (A+B)-(C/D)의 식이 나옵니다.
요 식을 전위표기식(prefix)로 나타내면
사용자 삽입 이미지
이런식으로 운행하고 결론적으로 -+AB/CD라는 전위표기식이 나옵니다.

으아 원래 중위운행법과 후위운행법에 대해서 같이 쓰려고 했지만...중요한 약속이 있어서요
죄송하지만 중위운행법과 후위운행법은 다음 번에 쓰도록 하겠습니다.
아, 그리고 레벨운행법이라는 것에 대해서도 그때 설명드릴께요.
그럼 안녕히 계세요~

아! 수정할 부분 있으면 말씀해주세요~
posted by 비회원

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.12.30 11:04  Addr Edit/Del Reply

    preorder traversal 할 때

    노드에 붙은 번호 대신 알파벳을 썼으면 더 좋았을걸- 하는 생각이 드는군;


    잘못 읽으면 '노드에 붙은 번호'를 '노드를 읽는 순서'로 헷갈릴 수도 -_-;;

  2. 잘 보고 갑니다.^^

    다음에 이어질 중위운행법과 후위운행법도 기대가 됩니다.

    중요한 약속 잘 만나고 오시길..^^

  3. ㄲㄲㄲ Mr.K에 동감.

  4. 테슬라 2008.12.31 13:16  Addr Edit/Del Reply

    어익후 미안미안...ㅎㅎ;;
    수정할게,,,

2008.12.23 23:06 (탈퇴) 테슬라's Post

안녕하세요...늦어서 죄송합니다 테슬라입니다.
모종의 사유로 인해 이제서야 글을 올리게 되었네요.
오늘은 이진트리에 대하여 글을 쓰고자 합니다.

우선 이진트리가 무엇일까?
음 저번시간에 트리에 대해서 했죠?
음 부모에서 자식으로 노드가 연결되는 것이였지요?
일단 트리의 기본 법칙은 거의 그대로 갑니다.
하지만 이진트리는 0개이상의 노드들의 유한집합으로 된 루트라는 특벽한 노드가 있고,
나머지 노드들은 각각 교차하지 않는 2개의 분리집합으로 분할된다는 것이지요
음 분리집합이 언제나 2개로 나뉘는거랑 공집합일 수 점을 빼면 같은 내용입니다.
무슨말인고 하니 부모에서 자식으로 갈때 최대 2개까지 연결될 수 있는것이 이진노드입니다.
음...음...간단한걸까요?

사용자 삽입 이미지

뭐 이런거지요 음 이 이상으로 형제 노드가 생길수 없습니다. 그렇다면
사용자 삽입 이미지

이런식의 노드도 이진 노드일까요?
네 맞습니다. 이진노드입니다. 단지 한쪽 방향으로만 연결 되어있는 것뿐이지요.
좀 있다가 나오겠지만 이런 이진트리를 사향이진트리라고 하지요.
아 이진트리는 자식노드의 순서를 구별합니다. 뭐 이건 다음에 말씀드리겠습니다.
 
자 지금부터 여러가지 이진트리의 종류에 대해서 말해볼까요?
우선 포화이진트리(Full Binary Tree)라는 것이 있습니다.
이건 말그대로 꽉 차있는 상태, 즉 모든 레벨의 노드가 꽉 차있는 상태의 트리를 말합니다.
사용자 삽입 이미지
으아 그리기 귀찮았어요.
암튼 이런식으로 꽉꽉 차있는 이진트리를 말하는 것이지요
음 이것들은 1-> 2-> 4-> 8-> 16->...
이런식으로 노드가 증가합니다.
때문에 각 레벨에서는 2^(n-1)개이고 그 레벨까지는 2^n-1개의 노드들을 가집니다.
예를 들어 2레벨 까지라면 2^2-1=3개, 4레벨은 2^4-1=15
뭐 이런식이지요.

음 다음으로는 완전이진트리(Complete Binary Tree)가 있습니다.
이거는 포화이진트리처럼 마지막 레벨의 노드가 완벽하게 꽉꽉 차있지는 않더라도
대충 어느정도는 차례대로 채워져있는 형태의 트리를 말합니다.
몇 개씩 빠진다고 뭐라고 할 정도는 아니라는 것이지요.
사용자 삽입 이미지

뭐 이런식으로 대충 채워져있으면 완전이진트리라고 할수 있습니다.
음 포화이진트리는 완전이진트리라고 할수 있겠지요.
마지막레벨에 꽉차있는 형태의 완전이진트리라고 할수 있으니까요.
하지만 반대로는 안되겠지요?
완전이진트리는 마지막 레벨에 하나 있는거부터 꽉 차있는 거 까지니까
(2^(n-1)-1)+1 ~ (2^n-1)까지 라고 할 수 있겠죠?

음 마지막으로 아까 말했던 사향이진트리(Skewed Binary Tree)라는게 있는데요
뭐 이진트리인 주제에 한쪽방향으로만 모든 노드가 쏠려있는 모양이 되는 것 이지요.
사용자 삽입 이미지

이런 모양이지요 이러면 나중에 이진검색트리에서 나오겠는데요. 이진트리의 장점이 없어지는 결과를 가지지요.
뭐 이건 링크드리스트같은 모양이 되지요. 검색시간도 링크드리스트 같이 걸리게 됩니다.
이 이야기는 이진검색트리 할 때 다루도록 하겠습니다.
암튼 이진트리를 만들때에는 사향트리가 되지 않도록 조심해야 합니다.

posted by 비회원

댓글을 달아 주세요

  1. 흐음. 기능 알고리즘적 구현을 리턴군이 써야 서로 손발이 맞는데 리턴군의 진도는 아직 멀었군 -ㅁ-;

2008.12.23 01:08 (탈퇴) 테슬라's Post

으아 어떻하제... 컴터가 폭파된 관계로 학교에서 글쓰려고 책 가져갔다가...두고 왔네요...;;;
집에와서 가방을 열어보니 학교에서 쓸려고 빼둔 책을 그대로 놓고 왔는지... 없네요...;;
죄송합니다. 죄송합니다. 내일 학교 가서 쓰겠습니다. 죄송합니다. 죄송합니다.
꼭 내일 가서 쓰겠습니다...
내일 포스트와 프로그램 올리도록 하겠습니다. 정말 죄송합니다.
프로그램은 현재 컴터가 폭파되었다가 세팅되서 온 관계로 컴파일 프로그램이 하나도 없어서요...
다시 한번 사죄 드립니다.

posted by 비회원

댓글을 달아 주세요

2008.12.15 20:46 (탈퇴) 테슬라's Post
음 안녕하세요 테슬라 입니다.
다름이 아니오라 오늘 올리기로 되어있던 포스트를 연기하고자 합니다.
사유는 과제와 시험에 의해서이고, 시험이 끝나는대로 포스트 하도록 하겠습니다.
아마 예상으로는 금요일에서 토요일 즈음이 될 것 같습니다.
그리고 지금까지 딜레이 되고 있는 문제들도 같이 올리도록 하겠습니다.
posted by 비회원

댓글을 달아 주세요

  1. 기대하고 있겠어~~

2008.12.08 23:10 (탈퇴) 테슬라's Post
안녕하세요~
네 잊을만 하면 나타나는 테슬라입니다.
이번 시리즈는 이진트리에 대해서 다루어보겠습니다.
음 오늘은 간단하게 트리에 대해서 다루어 보겠습니다.
음 트리란 무엇인가... 우선 트리하면 크리스마스 트리가 떠오르지요? (크리스마스가 얼마 안 남아서요...ㅎㅎ)
네 트리하면 나무지요...네 맞아요...
음 자료구조의 트리도 나무와 비슷합니다.
루트라는 뿌리를 기점으로 가지가 뻗어나가고 끝에는 잎들이 달려있죠...

사용자 삽입 이미지


음 나무를 뒤집어 나뒀다고 해야 할 것 같군요.
맨 처음엔 뿌리(root)가 존재하고, 그곳에서 가지(branch)가 존재하며, 결국 끝에는 잎(leaf)가 붙어있습니다.
루트는 제일 상위레벨에 속하는 노드로써 그냥 맨처음에 시작하는 부분을 말합니다.
가지 즉 간선은 노드와 노드 사이를 연결하는 선들을 말합니다. 따라서 노드가 n개라면 간선은 n-1이지요
잎 그러니까 리프는 맨끝 밑에 아무런 가지가 안달려있으면 리프라고 합니다.
음 또한 트리에는 단어가 많습니다. 아 단어보다 먼저 트리의 정의를 알아봐야겠군요.


트리는 하나이상의 노드로 구성된 유한 집합으로 루트라는 특별한 노드가 있고, 나머지 노드들도 서로 교차하지 않고 분할될 수 있는거지요. 분할 되면 부트리(Subtree)라고 합니다. 노드A는 루트이고 만약 위에 그림을 분할 시키면 {B,D}와 {C,E,F} 두개의 집합으로 나눌 수 있겠죠?
위에 그림은 트리의 구조라고 할 수있습니다.
그럼 아래 그림을 보죠
사용자 삽입 이미지

위 그림은 트리가 아닙니다.
왤까요? 네 그렇습니다. 화살표가 맨 밑에 중간 노드에 2개가 가지요?
예 이런식으로 교차가 되면 트리라고 부를 수 없습니다.
왜냐하면 이런식으로 교차하면 부수적으로 분할 시킬수 없기 때문이지요.


이제 트리 정의 부분은 넘어가고, 단어 정의를 해볼까요?
우선적으로 부모 노드(Parent Node)와 자식 노드(Child Node)가 있습니다.
자식 노드는 부모 노드에서 내려온 노드를 뜻합니다.
음 간단하게 부모님에게서 자식들이 태어나듯이 말입니다.
위 그림에서 예를 들어본다면 노드C의 경우 부모노드는 무엇일까요? 네 간단하게도 노드A입니다.
음 그럼 자식 노드는 어떨까요? 네 그렇습니다. 노드E와 노드F입니다.
그냥 단순하게 생각하시면 됩니다.

형제 노드(Sibling Node)는 같은 부모노드에서 내려온 노드를 뜻합니다.
아까 노드C의 부모노드가 노드A였으므로 노드C의 형제노드는 노드B가 되는 것이지요.

조상 노드(Ancestor Node)와 후손 노드(Descendant Nose)라는 것들도 있습니다.
조상 노드는 루트까지 갈때 거치는 노드들입니다.
이번엔 노드F를 예로 들어보죠. 노드F에서 루트인 노드A까지 가려면 노드C와 노드A를 거치지요.
네 이 노드들이 조상노드입니다.
후손노드는 반대로 그 노드에서 끝까지 내려가는 노드입니다.
노드A의 후손노드들은 노드B,C,D,E,F군요

음 차수(Degree)란 말도 있군요
간단하게 설명하면 자신에 연결된 자식노드의 갯수라는 말로 할 수 있겠군요.
노드B의 차수는 1, 노드C의 차수는 2, 노드F의 차수는 0이군요.
트리의 차수는 각 노드들중에서 최대치를 트리의 차수라고 합니다.
위 그림에선 차수2가 가장 크므로 차수2인 트리라고 할수 있습니다.

마지막으로 레벨(Level)이 있습니다.
레벨은 루트를 최상위 레벨인 1로 하고,레벨 N의 자식노드는 N+1레벨입니다.
즉, 루트로부터 차근차근 레벨이 커지는 거지요.
노드F의 레벨은 몇일까요?
노드A은 레벨1, 노드C는 레벨2, 그리고 노드F는 레벨3이 되는것이지요.


음 우선 트리와 단어를 정리해봤는데요...으으 정신이 없군요....
다음 포스트는 이진트리에 대해 쓰도록 하겠습니다.
posted by 비회원

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.12.09 00:49  Addr Edit/Del Reply

    제목에 오타 하나, 부모노드에 오타 하나 =_=


    한가지 더 지적하려고 했는데 나랑 좀 다르게 배운 것 같아서 말았음;

  2. 제목은 확실히 오타고.. 부모노드도 오타네 -ㅁ-;;

  3. 우아 이런 오타군요...감사합니다...수정했어요

  4. ... 왜 내 블로거기자단으로 송고된거지.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.12.10 00:59  Addr Edit/Del

      .. 혹시 팀블로그라 주인을 구분하지 못하는게 아닐까 -_-;

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.12.10 07:27  Addr Edit/Del

      아니면
      팀블로그니까

      한명만 블로거기자단을 가입하면
      나머지 팀원들이 'Daum에 글보내기' 선택하는 순간 먼저 가입한 사람의 이름을 달고 나간다든지 -_-;

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2008.12.10 10:26  Addr Edit/Del

      ㄴㄴ 슬라가 가입을 안한 상태에서 내가 체크하다 보니 그렇게 날라갔음 ㄱ-

2008.11.17 18:26 (탈퇴) 테슬라's Post
-------------------------------------------------------

연기 일시 : 11. 17, 11. 24까지 2주간.

연기 사유 : 팀 프로젝트 과제

예상 복귀 일자 : 12. 2

-------------------------------------------------------

안녕하세요...이런 말씀을 전하게 되어 죄송합니다.
다름이 아니오라 이번 과목 중에 실습과목이 있는데...
한번에 터져버려서요...
DB 오라클이 과제에 들어가서 그런지 좀 오래 걸릴거 같아요.
팀 프로젝트라 아마 매우 늦게 다니게 될 거 같아서요.

음, 팀 프로젝트가 정리되는데로 포스팅을 쓰도록 하겠습니다.
그럼 다음에 뵙도록 하겠습니다.
posted by 비회원

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.11.17 18:38  Addr Edit/Del Reply

    .. Dlbo군이 쓴거 보고 이걸 보는 순간 같은 글인줄 -_-;

  2. 좋은데 규격화라.

  3. 테슬라 2008.11.18 15:03  Addr Edit/Del Reply

    음 이런식으로 쓰는게 괜찮은거 같아서 dlbo군 것을...ㅎㅎ;

2008.11.10 20:29 (탈퇴) 테슬라's Post
안녕하세요~ 오늘도 찾아온 테슬라입니다.
오늘은 큐에 대해서 할 텐데요. 저번에 올린 스택과 비슷한 수준입니다.

우선 큐에 대해 알아볼까요?
큐는 한쪽 끝에서 데이터가 삽입되고, 삭제는 반대쪽에서만 할 수 있도록 되어있는 순서리스트의 자료구조인데요.
입력과 삭제가 반대이기 때문에, 먼저 삽입된 것이 먼저 삭제되겠지요?
예를 들어 자판기에서 종이컵을 넣을 때 먼저 넣은 종이컵이 사용할때도 먼저 나오지요?
그런식으로 삽입과 삭제가 반대 방향으로 이루어 진 것을 큐라고 합니다.
때문에 큐는 선입 선출(FIFO : First In First Out)리스트 라고도 하지요.


그렇다면 이러한 큐는 어떤식으로 나타날까요?
음 아래의 그림을 보시죠...
사용자 삽입 이미지

위쪽이 연결리스트로 구현한 enqueue(큐 삽입) 밑의 그림이 개념적인 enqueue(큐 삽입)의 모습입니다.
front는 삭제될 부분, rear부분은 삽입되는 부분입니다.
연결리스트로 구현시 새로운 노드의 생성은 제일 마지막 부분에 합니다.
나중에 들어간 값이 마지막에 나오기 때문이죠

그렇다면 삭제는 어떻게 할까요? 아래의 그림을 보시죠
사용자 삽입 이미지
이것이 dequeue(큐 삭제)입니다. 음 어디서 많이 본 거 같지 않나요?
네...  저번에 보았던 스택과 같습니다.
삽입이 스택과 반대쪽이므로 삭제는 같은 것이지요.
다음 코드를 가리키고 free()해주는것이지요
 

자 그럼 이제 코드로 한번 볼까요?


네 우선 저번의 Pop과 이번의 dequeue와 별다른게 없습니다.
enqueue의 경우는 마지막 부분에 새로 삽입되는 것이기 때문에 NULL일 때까지 찾아가는 것이죠.
그 뒤에 새로운 노드를 생성시켜 이어 주는것입니다.
posted by 비회원

댓글을 달아 주세요

  1. 다음은 덱인가.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.11.10 23:39  Addr Edit/Del

      덱이 뭐임? 우리는 안배웠는데 -_-;

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2008.11.11 20:34  Addr Edit/Del

      Deque라고... 디큐라고도 하긴 하는데 보통 덱이라 읽음. 입력, 삭제를 양 끝에서 모두 수행 가능한 자료구조인데, 리스트와 다른 점은 중도 한복판 삽입은 불가능하단거.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.11.12 01:05  Addr Edit/Del

      아; double ended queue를 말하는거였군; 이거라면 배웠네

      잠깐 하고 넘어가서 이름은 잊어버린듯


      그걸 디큐라고 읽으면 난 dequeue() 함수가 생각나서 난감함 -_-;

2008.11.04 00:31 (탈퇴) 테슬라's Post

안녕하십니까~ 테슬라입니다
동적 단일 연결리스트의 응용이라 생각 할 수 있는 스택과 큐를 알아보도록 하겠습니다~
음 오늘은 우선 스택을 알아보도록 할게요.
그렇다면 우선 스택이란 무엇일까요?

스택이란 여러 개의 물건들이 쌓여있는 것을 말합니다.
예를 들어 어릴 때 가지고 놀던 블록을 위로 차곡차곡 쌓듯이 쌓는 것 말이지요.
제가 여기서 말하고자 하는 스택은 비슷한 개념이라 할 수 있지요.
컴퓨터의 자료구조에서 나오는 개념으로
스택에 저장된 데이터 항목 중에서 나중에 삽입된 것이 먼저 삭제(출력)되지요.
우리들이 식당의 배식판을 생각해보면 맨 위에 쌓인 것이 가장 마지막에 쌓였겠죠?
하지만 일반적으로 배식판들은 맨 위에서부터 사용되어가지요.
이처럼 나중에 삽입되고 먼저 삭제(출력)되므로 후입선출이라고도 불리우지요.

음 다시 돌아와서 그렇다면 어떻게 연결 리스트로 구현할까요?
아래의 그림을 봐주세요~

사용자 삽입 이미지


왼쪽이 단일 연결리스트로 표현한 Push입니다. 회색은 입력 되어있던 값이고,
흰색 노드와 검은 화살표가 새로 Push된 값의 노드와 연결입니다
오른쪽은 왼쪽의 연결을 개념적으로 나타낸 스택입니다.
원래 top이 가리키던 주소를 새로 생성한 노드 뒤에 연결하고 새로 생긴 노드의 주소를 top에게 줍니다.


Pop은
사용자 삽입 이미지

이번에도 역시 회색은 입력 되어있던 값이고,
흰색 노드와 검은 화살표가 Pop에 의해 변경된 노드와 연결입니다.
top를 다음 노드에 넘겨주고 맨 앞의 노드와의 연결을 free()와 같은 방식으로 제거합니다.

코드로 나타내본다면,

이런식으로 생각해볼 수 있겠지요?

그럼 단일 연결 리스트로 구현한 스택의 장점은 무엇일까요?
우선 배열을 생각해보지요.
Push할 경우 배열의 위치를 가리키는 값을 하나 증가시켜 다음 위치에 값을 저장하고,
Pop할 경우 위치를 가리키는 값을 하나 낮추어 그 전의 입력된 값의 위치를 가리키지요.
이러한 배열은 선언한 범위 내에서만 사용할 수 있기 때문에,
배열의 크기에 따라 적게 선언한다면 사용 할 시 부족하거나
 크게 선언 한다면 메모리가 낭비 되겠지요?

링크드 리스트로 구현한다면 어떨까요?
Push할 때 동적 메모리 할당을 하여 필요한 만큼만 사용하고,
Pop할 때에도 메모리를 free해주므로  메모리를 효율적으로 사용할 수 있지요.

음 오늘의 포스팅은 여기까지 입니다.
자 그럼 다음 시간엔 단일 연결 리스트를 이용한 큐에 대해 써보도록 하겠습니다.
posted by 비회원

댓글을 달아 주세요

2008.11.03 01:49 (탈퇴) 테슬라's Post
에에 안녕하세요...
월요일에 학교가 늦게 끝날 것 같습니다...
사실 지금 쓰려고 했지만 문득 내일까지 과제가 2개라는 사실이 기억나서...
아마 늦게 즈음에나 쓸 수 있을거 같아요...
되도록 빨리 시간 되는대로 쓰도록 하겠습니다...
posted by 비회원

댓글을 달아 주세요

2008.10.27 19:29 (탈퇴) 테슬라's Post
이야 안녕하십니까~? 테슬라입니다...
포스팅을 쓴지 오래된것 같군요...네 오래됬군요...
음음 각설하고 드디어 동적인 단일 연결리스트 2를 쓰게됬습니다...
이번 포스팅에서는 저번에 예고한대로 노드의 삭제와 리스트의 병합에 대하여 해볼까요?
음 우선 노드의 삭제는 연결리스트에서 필요없는 데이터가 있는 리스트를 삭제하는 것입니다.
음 예를 들어 1을 삭제하려고 한다면...
그림으로 표현하자면 이런식이겠군요...
사용자 삽입 이미지
음 그림처럼 1의 노드와의 연결을 끊어버리고 앞에서 다음 노드를 가리키면,
1의 노드와의 관계는 사라지겠죠?
이후 1의 노드를 free해주면 1의 노드와는 작별하게 되는거죠~
코드로 나타내면 다음과 같습니다...
음 이런식으로 표현이 가능하군요...
예를 들어 3의 노드를 삭제한다고 하면 그림으로 나타내면
사용자 삽입 이미지

이런식으로 3의 노드를 curr이 가리키고,
그 curr의 다음 노드의 주소를 curr를 가리키던 prev->next에 할당해주면
prev다음은 curr의 다음 부분을 가리키겠죠?
그럼 삭제할 노드 curr을 free해주는 것이죠...
이야, 참 쉽죠?(...)
자 그럼 다음으로 두 리스트의 결합을 생각해볼까요?
간단하게는 다른 리스트의 맨 뒤에 꼬리붙이듯이 연결 할 수도 있겠지만,
순서대로 정렬하며 넣는다면 리스트가 깔끔하겠죠?
길군요...
이 코드는 차례대로 두 노드를 비교해서 작은 값의 노드는 먼저 연결하고,
작은 부분의 노드의 다음 노드와 남아있던 노드를 다시 비교하는 형태입니다.
마지막에는 이 종합된 리스트의 맨 처음 노드의 주소인 r을 리턴하며 함수가 종료됩니다.
이런식으로 구현하면 순서대로 각 리스트의 노드들이 하나의 리스트로 연결이 되겠죠?
아 같은 값의 노드들은 하나만 연결하고 둘의 다음 노드를 가리킴으로써 중복되는 노드를 하나만 연결했습니다...
어때요? 참쉽..(히익, 죄송합니다...)
음...음...이렇게 아직도 어설픈 두번째 포스팅도 이렇게 끝이 났는데요...
다음 포스팅에는 지금까지의 응용으로 동적인 단일 연결 리스트를 이용한 스택과 큐를 다루겠습니다...
그럼 길고 산만한 포스팅을 읽어주신 여러분께 인사드리며 다음 이 시간에 다시 뵙겠습니다...
posted by 비회원

댓글을 달아 주세요

  1. 길진 않은데? ㅁ_ㅁㅋㅋ

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.10.28 06:09  Addr Edit/Del Reply

    복귀했네 ㅋㅋ

  3. 돌아오셨구려

2008.10.12 16:06 (탈퇴) 테슬라's Post

안녕하세요. 테슬라입니다...
이렇게 갑자기 글을 올리게 된 이유는 시험기간의 영향으로 한동안 포스팅을 못할거 같습니다.
이번주에도 불의의 사고(...)로 못 올렸기 때문인지 더욱 죄송한 마음입니다.
아마 시험은 24일 전후로 정리될 듯 합니다.
그 후에 포스팅을 꼭 올리겠습니다...죄송합니다.

posted by 비회원

댓글을 달아 주세요

  1. 이런 글은 공개로만 때려도 됨 ㅁ_ㅁ!

2008.09.29 23:56 (탈퇴) 테슬라's Post
안녕하세요~ 테슬라 입니다...
포스팅이 늦어서 죄송합니다...학교에 일이 있었거든요...

오늘 하고자 하는 부분은 단일 연결 리스트랍니다.
그럼 단일 연결 리스트란 무엇일까요?
노드들의 연속적인 연결을 뜻합니다.
그럼 노드란 무엇일까요~?
링크드 리스트에서 하나의 원소를 저장하는 공간으로 노드(Node)라고 합니다.
음 그림으로 볼까요?
사용자 삽입 이미지
이런 상자 모양으로 생각하시면 쉬울텐데요.
Data부분엔 원하는 정보를, Next부분엔 다음의 노드의 주소를 씁니다...
노드의 포인터 부분에 다음 노드의 주소를 넣으면 줄줄이 사탕처럼 이어지겠죠?

사용자 삽입 이미지

이렇게 말이죠 아래의 코드는 기본적인 노드의 구조체 코드입니다.

이런 코드를 쓰면 차곡차곡 앞에서부터 뒤로 노드가 연결되겠죠?
음 만약 크기순서대로 노드를 연결하고 싶다고 생각하신다면 어떻게 해야 할까요?
음 이 코드를 사용하면 된답니다.~
음 오늘은 단일 연결리스트의 노드 생성부분을 했는데요...
다음 시간에는 노드의 삭제와 두 연결리스트를 병합해서 하나의 연결 리스트를 만들어볼게요.
posted by 비회원

댓글을 달아 주세요

  1. 으으 늦어서 죄송합니다...학교에서 일이 좀 생겨서...
    앞으로는 미리미리 준비해두도록 하겠습니다....

  2. 그림 원츄 -_-)_b 심플한듸?

  3. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.30 00:23  Addr Edit/Del Reply

    오오 이것은;

    (개인적으로 연결리스트에 적응이 잘 안되어 공부가 필요한 1人)


    기대하고 있겠습니다 -_-乃

  4. 잘보고갑니다^^*
    근데 저 컴파일러는 무엇인가요 @_@; 깔끔하게 디자인되잇는거같은데 ㅎ_ㅎ;;

prev 1 2 next