그림으로 배우는 데이타구조와 알고리즘 in C (1) 큐.

프로그래밍/데이타구조-알고리즘 2006/08/03 01:30

그림으로 배우는 데이타구조와 알고리즘 in C
에피소드 1.  큐(queue)
 
버전: 1.0 가. 최초 작성일 2006년 8월 1일
                 수정일        2006년 8월 2일
원URL및 문서의 최신버젼의 URL: http://www.xevious7.com/113
작성자: Xevious7 (황의범)

대상 : 초보자의 학습용부터 중수의 진지한 복습용, 고수의 심심풀이용 복습.
        대가의 휴식용 복습.
주의 : 이과계열과 상관없는 사람에게는 머리에 쥐가 날수 있슴.
경고 : 설렁한 유머에 땀이 날 수 있슴.



들어가는글

최근에 TAOCP(The Art of Computer Programming)와 C언어 그리고 자료구조를
복습하면서 문득 이 세가지와 그림에 대한 감각을 잃어버리지 않는 작업 그리고
복습의 효율까지 효과적으로 할 수 있는 방법이 떠올렸다. 개인적인 목적과 공익
까지 추구할 수 있는 '강좌'를 쓰는 것이었다. 그것도 그림이 들어간 강좌라면
1석 4조의 효과를 누릴 수 있을 것 같았다.

(그림) 타이틀?

사실 , 인터넷의 글에서 최소한의 예의로 '존대말'을 쓰는 것을 선호하는 사람이지만
이 강좌에서는 존대말체를 쓰지 않기로 했다. 아직은 존대말을 쓰면서 좀더 재미있는
글을 쓰기에는 내공이 부족함을 느꼈기 때문이다. OTL (절망은 도전하는 자만의
특권이다 - Xevious7의 말)

인터넷의 글이라는게 인쇄된 책과는 달리 체계적이지 못한 단점이 존재한다.
여러가지 이유가 있겠지만 책 처럼 체계적으로 쓰기에는 공이 많이 들어간다는
이유일 것이다. 그래서 인터넷의 오픈프로젝트 처럼 규모가 크거나 하는 경우에는
체계잡힌 문서가 존재하지만 , 대부분은 '조각지식' 형태의 글들이 많다. 하지만
이러한 글들도 책이 주지 못하는 장점이 있으며 매우 유용한 것들이 많다.

나는 이러한 인터넷 글의 장점을 최대한 살리면서 어느정도 볼륨있는 강좌를
목적으로 시작한다.
이 강좌들은 마치 한편한편 에피소드들이 모여서 이루어지는 드라마형식처럼
만들어 볼까 한다.

일러두기

정말로 배우기를 원한다면 정독하라 !

이 강좌에서 쓰이는 소스는 C를 기준으로 작성된다. 주로 gcc와 vc 그리고
turbo c에서 테스트할 것이다.  그러나 실제 코드는 웬만하면 기재하지 않을
것이다. 구현은 여러분의 몫이다.

이 강좌에서 쓰이는 의사코드는 특별한 형식이 없는 형태로 이루어진다.

이 강좌의 온전한 재게시(펌)는 자유롭다. 하지만 수정형태는 허용되지 않는다.
되도록이면 링크를 추천한다.

이 강좌는 되도록 은어/속어/욕설/통신어를 자제할 것이지만 가끔의 경우는 사용되어
질 것이다. 이러한 것을 싫어하는 네티즌들에게는 미리 사죄를 드린다.

이 강좌에서 쓰이는 그림/글 등의 무단복제및 상업적 이용은 엄격히 금한다.
이러한 말을 쓰는 이유는 당한적이 있기 때문이다.
이 강좌는 나의 시간을 들여 생각하고 편집하고 그려서 만든 노력의 산물임을
고려해주기 바란다. 낮에 일하고 밤에 남는 시간을 쪼개고 쪼개서 만든것이다.

이 강좌 포스트에 대한 댓글과 트랙백은 환영한다. 하지만 스팸이나 쓸모없는
비방류글 욕설류의 글들은 물론 통보없이 삭제될 것이다. 당연한 것이지만..
블로그는 공개되어 있는 개인공간이라는 것을 명심하기 바란다. 언제든지
들어올수 있는 공간이지만 쓰레기를 버리고 간다면 공간을 관리하는 관리자는
쓰레기를 치워야 한다.

큐(queue)란 무엇인가?

조엘온 소프트웨어를 읽어본 사람이라면 왜 쉽고 재밌는 글이 중요한지를 알 수
있으리라 생각한다. 사실 어떤 스토리는 순전히 글로만 써져 있는 것이 훨씬
재미있을 수 있다.
그림은 상상력을 고정시키는 효과가 있기 때문이다. 그러나
어떤 설명의 서적또는 글은 그림이 많을 수록 좋은 것이다.

정말 어처구니 없게도 이야기의 책들은 그림이 많이 들어가는데 정작 그림이
들어가야할 학술 서적류는 그림이 적다. 상당히 아이러니 한 일이 아닐 수 없다.
하지만 요즈음 그러한 허세가 사라지면서 과학,역사서 등 전반에 걸쳐서
화보를 동반한 책들이 나오고 있는 추세에 있다.


그림 ( 화보를 동반한 책들)

왜 큐이야기에 이러한 것들이 들어가느냐? 라고 혹시나 궁금해 하거나 조급한
분들을 위해서 한가지 더 이야기를 하고자 한다.

공부를 해본 경험이 있다면 어떤 수업은 재미가 있고 어떤 수업은 정말 따분해서
아무리 눈을 떠보려고 해도 조는 경우가 있다. 왜 그런 것일까?
재미가 없다? 관심이 없다?(하지만 강제로 배우는게 아니라 찾아서 듣는것이라면
관심하고는 거리가 멀다) 이해도의 차이?
어찌되었든 굉장히 많은 이유가 존재하겠지만 , 조금 다르게 표현하자면
능동적인지,수동적인지의 차이가 크다고 볼 수 있다. 어떤 것을 배우려면
능동적인 수업을 하고 있어야 가장 큰 효율을 보게 된다.

능동적이라는 것이 무엇일까?

예를 들어 다음의 경우 어떤 사람이 길을 제일 잘 기억할 것인가?
누군가 데려다준 길인데 데려다줄때 자고 있던
사람 A와 안자고 창밖을 열심히 본사람 B 대충 길거리를 본사람 C
과연 어떤사람이 길을 잘 기억할까?

일반적으로 즉 A,B,C가 사전지식이 같다고 한다면 B가 된다.

여기에서 만약 C는 이미 길을 어느정도 알고 있다라고
한다면 B와C가 기억하는것은 비슷하거나 C가 더 나을 수 있다.
그리고 만약 A는 공간감각에 탁월한 능력이 있다면 (길 눈이 밝다는 의미이다.)
B,C보다 나을 수 있다.
그러나 그 어떤 경우라도 즉 사전지식과 능력과 상관없이 각각의 개인이
이전상태보다 길을 더 자세히 기억하려면 B의 자세가 필요한 것이다.


(그림 , 누가 길을 더 잘 기억할까? )

위의 글은 능동적 수업이 무엇인지를 쉽게 알게 한다. 만약 위의
'능동적이라는 것이 무엇일까?' 문장 뒤에 다음처럼 설명했다면 어떻게 되었을까?

능동적이라는 것은 수동적인것이 아닌 즉 따라가는 것이 아니고 적극적으로
참여하는 것을 의미한다. 따라서 능동적 수업이라는 것은 단순히 듣는 것이
아닌 적극적으로 수업의 내용을 이해하려고 하는 것이다.

내가 써놓았지만 어렵다 !!. 그리고 좀 더 재미없다. 아마 시간이 지나고 나면
금새 잊어버릴 문구이다. 하지만 아마도 이 위의 길 기억하기 이야기는 잘
잊어지지 않을 것이다. 왜 그럴까?
자연스러운 능동적인 학습을 유도했기 때문이다.

나는 되도록이면 쉽고 재밌는 글을 쓰고 싶다. 그래서 좀더 자연스럽게
이야기하듯이 글을 쓰려고 한다. 그래서 어찌보면 '쓸데없는' 이야기들이 난무
할찌도 모르지만 적어도 나는 그 이야기들이 필요없는 이야기가 아니라고 생각한다.
하지만 세상에는 철을 간식으로 먹고 , 맨손으로 뜨거운 기름을 만져도 이상하지
않는 사람들도 ,나이도 각색이고 성별도 다르고 인종도 어찌되었든 다양하기
때문에 이러한 형식의 글을 좋아하지 않는 사람도 있다.

추천한다! '다른 글을 보라!' 좋아하지 않는 형식의 글을 보면서 스트레스 받으면서
절대 공부 안된다!.  의무교육을 받는다면 싫어도 앉아있어야 하는 경우가 있겠지만
여기는 자유다. 학점을 따야 하는 것도 아니다.

그리고! 적어도 강좌 글을 보는 바로 그 순간에는 나를 스승으로 생각하라 여러분의
위치와 상관없이 배우고자 한다면 말이다. 그것이 바로 배우는 자세이다. 그리고
나는  항상 그 사람이 어떤 사람이든지 무엇을 배운다면
그 사람을 스승으로 대하곤 했다. 중고생의 블로그에 쓰인 글을 읽을 때도 배우려
갔다면 그분이 스승이라고 생각하고 정독하고 이해하려 하는 것이 바로 자세이다.

나는 대표적인 소도시  J시에서 학창시절의 대부분을 지냈다  갑자기 도시이야기
왜 나오냐고 생각이 들면 다시 위로 올라가서
왜 큐이야기에 이러한 것들이 들어가느냐?
다음부터 다시 읽어 내려오기 바란다!. 꼭이요!!!!                 ....꼬꼬댁...


(그림 닭)

그 도시 J시에서 중학생이 되기 이전까지 엘리베이타를 타본적이 없었다. 에스칼레이터
라는 것은 더욱더 볼 수가 없었다. 대형 슈퍼마켓(요즈음 마트하고 약간 비슷한..)은
있었지만 백화점은 없었다.(서울에도 몇 안되었던 시절로 생각한다.) 어느 시점에
사실 언제인지 정확히 기억이 안난다. 어찌되었든 J시에  C 백화점이 생겼다.
우리친구들은 얼룩말 백화점이라고도 했다 -.-


그림(J시)

그 백화점이 오픈했을때 많은 사람들은 백화점에 물건을 사러 가기 보다는 백화점
구경을 하기위해서 또 그 많은 사람들 중의 많은 수가 에스칼레이터를 타기 위해서
백화점 구경을 갔다. !!


그림 (에스칼레이터)

에스칼레이터는  한쪽 끝에서 타면 다른 쪽 끝으로 나온다. 사람들이 워낙 많아서
에스칼레이터는 꽉꽉 들어찼었다.
사람들은 에스칼레이터를 타려고 줄을 서서 기다려야 했다. 물론 지금도 지하철
내리고 에스칼레이터를 타려면 줄을 서서 기다려야 하는 풍경은 아주 쉽게 볼  수
있다.

나는 숫자를 좋아했다. 어디서든지 숫자세기를 좋아했다. 내가 처음 다닌 회사
의 입사문제는 이런문제도 나왔었다. 심리평가 문제였다.

자신과 해당하는 상황을 고르시오.

나는 계단을 세거나 전등을 세거나 주변의 사물을 자주 세보곤 한다. << 요런 항목

에스칼레이터 안의 계단을 세면 에스칼레이터안에 들어가는 사람수가 나온다.
물론 계단에 서있는 사람이 1명일수도 있고 2명일수도 있겠지만 1명이라고 가정하고
10계단이면 10명이 있게된다. 최대 수용인원이 10명인 것이다.

시간이 지나고 에스칼레이터를 일부러 타기 위해서 백화점에 오는 사람은 사라졌다.
(가끔 있기도하다.)

여러분은 지금까지 자연스럽게 큐를 배웠다 !.  헉 ! 언제?
그러면 지금부터 그것에 대해서 설명해보겠다.

큐는 앞서 설명한 에스칼레이터와 흡사하다. 앞서 에스칼레이터에서는 사람이 서있지만
컴퓨터에서는 데이타가 서있을 뿐이다.

에스칼레이터와 같은 구조로 데이타를 가지는 데이타구조를 큐라고 명명한
것이다
. 즉 먼저 들어온 데이타가 먼저 처리되는 구조이다. 표를 사려고 기다리는
줄 , 놀이기구를 타려고 기다리는 줄  모두 먼저 온사람이 먼저 표를 사고 먼저
놀이기구를 타게 되어있다. 이러한 형태의 데이타저장 구조를 큐라고 한다.
그래서 영어로 First In First Out 구조라고 하면 줄여서 FIFO 피포 라고 한다.
피파가 아니다. ~ 사실 FIFO라는 말을 왜 쓰는 지 생각해보면 영어권에서는
큐의 구조를 가장 손쉽게 표현하는 말이기 때문이다. 외우기도 쉽고 말이다.
그런데 한국어권으로 오면 FIFO가 조금 어려워진다.(물론 영어능숙자는 쉽다.)
사실 큐 하면 에스칼레이터를 떠올리면 된다. 먼저 탄놈이 먼저 내린다 라고 말이다.

하지만 시험이나 기타 서적에서 나오는 것을 쉽게 이해하려면 FIFO 라는 단어를
기억하고 있는것이 현명하다. FIFO를 에스칼레이터 라고 쓴 서적은 없기 때문이다.


(그림) FIFO 구조.

큐의 간단 구현의 예

프로그래밍 언어로 실제 구현을 해보자. 구현을 할때는 머리속으로 먼저 생각하고
그리고 그것이 수월하지 않는다면 연습장에 그리기 바란다.
바로 모니터 앞어서 코딩을 해도 괜찮을 수 있겠지만 (이것은 가장 흔히 보이는
일이다. 고로 즉 누구나가 하는 것인데.. 사실은 적어도 내가 생각하기에는
비 추천이다. 만약 당신이 나를 아주 신뢰하는 후배라면 난 이렇게 말했을것이다.
" 아주 잘 났다. 물 나른지 1년도 안된놈이 궁극기를 하려고 하면 주화입마에 빠진단다 "
" 어차피 선택은 자유지만 나 한테 배울 생각은 하지 말아라 "

먼저 디자인을 한 다음 의사코드 생각해보자.

Queue_Create()

일정크기의 메모리 버퍼를 생성한다.
버퍼를 초기화한다.
큐의 데이타의 시작위치(Front)와 끝위치(Rear)를 초기화 한다.

EnQueue(Data)

큐가 꽉찼는지 체크한다.
  (Rear)위치에 데이타를 집어넣고 Rear 증가한다.

DeQueue(Data)
  (Front)위치에서 데이터를 꺼내고 Front위치를 증가한다.
 
위의 의사코드는 큐의 정의와 작동원리를 기초로 만든것이다.
하지만 조금만 생각해보면 문제가 있다는 것을 알 수 있다.

문제는  데이타를 몇번 집어놓고 몇번 꺼내는 작업을
반복하고 나면 큐가 실제로 비어있어도 더이상 작업을 할 수 없게 된다.
Rear와 Front가 계속 증가하기 때문이다.

이러한 방법을 해결하기 위해서 소위 말하는 원형큐 개념을 쓴다.
Rear위치가 끝에 다다르면 버퍼의 처음으로 돌아가게 하는 방법이다.

연습문제및 과제

  연습문제   원형큐를 구현하라.
  과제  - 큐를 이용한 간단한 프로그램의 작성또는 생각해보기.

  "여러분이 과제를 풀었다면 트랙백을 해주기 바란다."

여러분이 글을 읽을 때 처음부터 차근차근 정독을 하면서
능동적으로 읽어왔다면 큐에 대해서 조금은 잘 알게 되었으리라 자신한다.!
하지만 마우스로 쭉 내려서 그림이나 진한부분 대략 스킵하면서 글을 읽었다면
여러분은 윗 글의 중간에 나오는 대충 길거리를 보고 온 사람과 같을 것이다. !!

학이시습지라는 말이 있듯이 복습은 최고의 학습이다. From Xevious7
top

Trackback Address :: http://xevious7.com/trackback/113

  1. rufia 2006/08/10 14:58 MODIFY/DELETE REPLY

    아... 상당히 재미있게 읽었습니다. ^^

  2. 임성훈 2012/03/07 11:50 MODIFY/DELETE REPLY

    큐와 포물선 공식 둘다 잘보고 갑니다.

Write a comment