본문 바로가기
반응형

[Public] 컴퓨터공학/자료구조8

[자료구조] 그래프 #4 (가중치가 있는 최소신장트리, 다익스트라, 벨만포드) 2011. 9. 25.
[자료구조] 그래프 #3 (최소신장트리, 크루스칼, 프림) 2011. 9. 25.
[자료구조] 그래프 #2 (깊이우선탐색 넓이우선탐색) 지난 번에는 그래프의 정의를 내리고 표현하는 법을 배웠다. 그래프만 잘 표현하면 뭐하나 그래프의 기능을 제대로 사용할려면 실질적으로 그래프를 잘 탐색해야 한다. 그래프의 탐색하는 방법에 대해서 알아보자. 그래프의 탐색 방법에는 크게 2가지로 나뉜다. 1. 깊이 우선탐색 (Depth First Search) 2. 넓이 우선탐색 (Breadth First Search) 많이 들어 보았을 것이다. 먼저 깊이 우선 탐색방법이다. 방식은 다음과 같다. 1. 시작되는 정점을 결정하고 방문한다. (시작점을 설정한다는 말이다.) 2. 시작정점에 인접된 정점중 방문되지 않는 정점을 선택 (인접한 정점중 방문하지 않는 곳으로 진행한다는 말이다.) 3. 모든 인접 정점을 스택에 저장 (시작점도 스택에 넣고 방문을 통한 모든.. 2010. 7. 12.
[자료구조] 그래프 #1 (그래프의 정의) 오늘은 그래프 알고리즘에 대해서 알아보자. 동영상을 통하여 이야기를 할 것인데 필자의 HTML 기술 부족으로 동영상은 고정하고 글만 내리는 기능을 할 줄 모른다. 인터넷창 2개를 뛰우고 보는게 편할듯 싶다. 먼저 그래프에 대해서 알아보자 자료구조 시험시간이면 항상 트리와 한 묶음으로 나오는 단골 출제 문제 중 하나이다. 내가 생각하는 공부 방법은 이게 왜 배우고 어떻게 생겼는지를 가장 먼저 이해하는 것이다. 그래야 우리가 이를 왜 배우고 왜 해야하는지를 알기에 공부의 효율도 극대가 된다. 먼저 그래프가 어떻게 만들어 졌는지 알아보자 먼저 세계지도가 동영상에서 나올것이다. 우리나라 월드컵 첫을을 안겨준 유럽의 폴란드로 한번 가보자 폴란드 안에서 좀더 들어가 칼리니그라드 라는 곳에 가보자 여기에서 보이는 위.. 2010. 7. 7.
[자료구조] 해시 함수 (Hash) #1 해시 함수 한 동안 글을 안올리고 방황하는 시기가 있었다. 다시 마음을 가다 듬고 올릴려고 한다. 이번에 소개할 내용은 해시 함수이다. 보통 자료구조 시간에 많이 들어봤을 것이다. 해시함수 이게 무엇일가 ? 해시의 어원부터 알아보자 해시를 사전에서 찾아보면 3가지가 나온다. 1. 해시시 ( 대마의 잎으로 만든 마약 ) 2. 그 일을 망쳐 놓는다 3. 잘게 자른 고기를 양파나 감자와 같은 재료와 함께 튀겨 한덩어리로 만든 요리 여기서 보면 "마약" 이건 아닐테고 "그 일을 망쳐놓는다." 이것 역시 알고리즘과 뭔 상관 ? 마지막 잘게 자른 고기를 하나로 합친다. 이게 좀 유사하겠다. 한마디로 원재료를 다른 재료와 함께 다지고 썩고 볶고 .... 등등 해서 완전히 새로운 다른 형태의 요리로 만든다는 것인데 한.. 2010. 6. 14.
[자료구조] 3. 스택 스택 (Stack) 2009. 10. 19(月) 1. 스택의 개요 1) 스택의 정의 - 여러 개의 데이터 항목들이 일정한 순서로 나열된 자료 구조에서 한쪽 끝에서만 새로운 항목을 삽입하거나 기존 항목을 삭제하는 자료구조의 한 형태를 말한다. 보통 나중에 들어온 데이터가 가장 먼저 나가는 형태라 하여 LIFO(Last In First Out)이라는 말을 많이 쓰기도 한다. 이는 데이터가 입력되는 위치와 출력되는 위치가 같은 특징을 지니고 있다. 2) 스택의 예 - 스택은 우리 일상에서 많이 볼 수 있다. 음료수 자판기에 음료수를 집어 넣으면 먼저 넣으면 앞에 있는 음료수를 먼저 빼 먹는 이런 원리와 비슷하다고 할 수 있다. 이 뿐만 아니라 골목길 안에 주차를 할 때 나중에 먼저 주차를 한 차가 나가야지만 .. 2009. 10. 19.
반응형