C로 배우는 알고리즘 - 복습 겸 요약 3

제 3장. 자료구조 - 배열, 연결 리스트

1. 자료구조란..

앞에서 구조화 프로그래밍이란 개념을 배웠다고 한다. 생각해보니 내가 본 옛날 C코드 중에 코드와 데이터를 구분하지 않고 실행하는 것 같은 소스가 있었다. 아마 비구조적 프로그래밍이 이런 것이 아닐까 싶은데, 마침 찾을 수 있었으니 첨부한다.

/* 지금의 컴파일러도 해석할 수 있게 살짝 수정했다. Visual studio에선 돌아간다. */

/* http://www.cs.cf.ac.uk/Dave/C/node4.html#SECTION00400000000000000000 */

#include <stdio.h>

int main(int t,int _,char* a)

{return!0<t?t<3?main(-79,-13,a+main(-87,1-_,

main(-86, 0, a+1 )+a)):1,t<_?main(t+1, _, a ):3,main ( -94, -27+t, a

)&&t == 2 ?_<13 ?main ( 2, _+1, "%s %d %d\n" ):9:16:t<0?t<-72?main(_,

t,"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+\

,/+#n+,/#;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/\

+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){n\

l]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#\

n'wk nw' iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \

;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;\

#'rdq#w! nr'/ ') }+}{rl#'{n' ')# }'+}##(!!/")

:t<-50?_==*a ?putchar(a[31]):main(-65,_,a+1):main((*a == '/')+t,_,a\

+1 ):0<t?main ( 2, 2 , "%s"):*a=='/'||main(0,main(-61,*a, "!ek;dc \

i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1);}

실행 결과

On the first day of Christmas my true love gave to me
a partridge in a pear tree.

On the second day of Christmas my true love gave to me
two turtle doves
and a partridge in a pear tree.

On the third day of Christmas my true love gave to me
three french hens, two turtle doves
and a partridge in a pear tree.

On the fourth day of Christmas my true love gave to me
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the fifth day of Christmas my true love gave to me
five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the sixth day of Christmas my true love gave to me
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the seventh day of Christmas my true love gave to me
seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the eighth day of Christmas my true love gave to me
eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the ninth day of Christmas my true love gave to me
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the tenth day of Christmas my true love gave to me
ten lords a-leaping,
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the eleventh day of Christmas my true love gave to me
eleven pipers piping, ten lords a-leaping,
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the twelfth day of Christmas my true love gave to me
twelve drummers drumming, eleven pipers piping, ten lords a-leaping,
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

요즘의 C소스와 비교해보면 딱 감이 올 것이다. 구조적이라는 개념에 대해서.

이 구조적이라는 개념을 성립시키기 위해 저 혼란스러운 코드를 2가지로 분리할 필요가 있다고 한다. 바로 알고리즘(코드)과  자료구조(데이터).

이번엔 자료구조를 먼저 살펴보기로 한다.

2. 배열

Array

C에서의 배열의 정의는 "연속된 메모리 공간을 차지하는 같은 데이터형들의 집합"이라고 한다.

꼭 C뿐만 아니라 다른 프로그래밍 언어를 둘러보아도 "연속된 같은 데이터"들이란 것은 바뀌지 않을 듯 하다.

파이썬은 얼핏보면 다른 데이터를 집어넣는 것 같아도 Py_Object라는 단위로 본다면 같은 데이터로 칠 수 있지 않은가.

맨 처음 맞닥뜨리는 자료구조이고 그만큼 직관적이고 단순한 구조로 이루어져 있다.

배열이 C에서 가지는 특성은 앞서 나온 "연속된 메모리 공간"을 차지한다는 것과, 배열의 첨자 검사를 안 한다는 것이 있다.

나머지는 C의 세부적인 문법에 관한 사항 (배열 인자로 넘기는 방법, 문법적 특징 등등...)이업고, 배열의 사용 예를 보자.

행렬

행렬의 각 원소의 자료형은 같다. 꼭 배열로 구현할 필요는 없겠지만, 왜 배열로 구현을 했을까?

배열의 특성을 짚어볼 필요가 있다. C에서의 기본배열은 고정된 크기를 가자고, 원소의 추가·제거가 힘들다. 행렬의 크기가 변하는 경우는 없으므로 적합하다.

책에서는 행렬을 자료구조로, 행렬의 곱하기 연산을 알고리즘으로 예제를 두었다

미로, 우선법

이것도 내가 직접 작성해보는 것은 생략할 것이다. (지금보니까 옛날에 정렬까지 예제를 직접 타이핑 해 봤었다;; 다시 공부해서 효과 얻으려면 직접 짜봐야 하는 건가..)

미로도 배열을 자료구조로 채택하는 것은 좋다. 하지만 우선법의 알고리즘은 가장 최선은 아니다.

책이 오래돼서 하드웨어 자원을 아끼는 것을 미덕으로 삼아선지는 몰라도, 최단경로를 찾는 방법은 BFS가 가장 적당하다.

순서대로, 책의 예제부터 보자.

예제를 실행하면 1이 이동한다. 처음은 우선법을 따른다. 두번째 최단경로 이동부분에서 미로가 연결되지 않은 부분에서 경로 단축을 못 하는 문제가 있는 걸 알 수 있다.

기존 알고리즘에서 개선시키는 방법은, 좌선법 추가정도가 있다. 더 이상 개선하려면 복잡해질 테니 속 편하게 BFS를 쓰는게 나을 것 같다.

3. 연결 리스트

Linked iist

배열과 달리 연결 리스트부터는 C가 기본지원하지 않기 때문에 직접 구현해야 한다. (STL은 빼자)

개념은 알고있었고, 구현을 해보기로 했다.

개념.. 장점은 메모리 소모가 동적이고, 삽입, 삭제가 빈번한 자료에 유용하다.

단점은 검색하기 힘들다. (순차검색만 되니)

단순 연결 리스트

이거 구현은 혼연C교재가 최곤 것 같다.

만든 다음 비교해 봤더니 내가 짠 코드는

1. Deleteall함수에 NULL체크를 중복했다.

2. Insert_after, Delete_after에 NULL체크를 추가로 했다.

이런 차이점이 있었다.

짜면서 쓴 주석

// 단순 연결 리스트에서 head가 가리키는 노드는 쓰지 않는 게 좋다. 일관성을 위해서라는데, 살펴보자.

// 일단 head가 가리키는 값도 쓰려면 insert_after나 Delete_after에 NULL을 처리하는 부분이 반드시 필요하다.

// 쓰지 않아도 safe-coding을 위해 NULL처리 구문은 그래도 들어가겠지만, 논리적으로는 필요가 없다.

// 그리고 head가 가리키는 값은 head를 직접 조작해야 제거할 수 있기 때문에, C++에서는 제거에 포인터를 넘겨줄 것을,

// 포인터에 대한 레퍼런스를 넘겨주는 것으로 약간 비효율적이 된다.

// 결론은, 앞의 노드를 이용하는 모든 동작에서 추가적인 코드가 필요해진다. (head는 예외니까.)

// 여기선 head노드는 쓰지 않음과 동시에 현재 노드대신 이전노드를 쓰는데, 그걸 하려면 차라리 더블 링크드 리스트를 쓰는게 낫기 때문이라고 생각해서다.

Find_node()

// 값을 찾은 노드 바로 이전 노드 주소를 리턴합니다. 검색할 때 목적은 존재 여부확인 or 삭제니까...

// 결과적으로 Find_Node를 쓸 때 Get_before가 필요 없습니다.

// p부터가 아니라 p다음부터 찾습니다. 계속 검색할 때 유용하고, 단순 연결 리스트 특성 때문이기도 합니다.

// head부터 검색할 땐 문제 없지만, 도중부터 검색하려면 추가적인 코드가 필요하겠네...

교재에 있는 C책하고 구현이 좀 다르게 되었는데, 그 이유가 위의 주석이다.

다음은 실습한 소스

my_linkedlist.cpp

이중 연결 리스트

짜면서 쓴 주석

난감한 점. 구현 방식이 2가지 있다.

하나는 직접 자료를 다루게 하는 것. head가 NULL일 때도 예외처리로 노드 하나 만들어주고 하는 방식.

다른 하나는 단순 연결 리스트처럼 head지정 노드를 접근 불가하게 하기.

전자의 방식은 직관적, 원소 0개 가능이라는 장점이 있고, 헤드의 왼쪽에도 노드 삽입이 가능하다.

후자의 방식은 head가 유지되고(=원소 수 세기가 쉽다), 구현이 간단하다.

혼연C/C++을 보니까 후자로 구현했던데... 헤드의 왼쪽에 삽입할 경우 무시해 버린다.

... 합리적이었다. 역시. 알아서 조심하면 되는건가.

그럼, 혼연을 참고로해서 다시 만들자.

혼연에는 AppendNode(), GetListCount(), GetNodeIndex(), FindNodeByIndex()도 있었다.

내가 부족했던 점은

1. Insert_before을 prev->Insert_after로 간단히 구현할 수 있는 걸 비슷한 코드 2개를 만들어버렸다.

   원인을 꼽자면, 저 2가지 방식 중 하나를 명확히 정하지 않고 생각없이 짠 것이겠지.

2. Ordered_Insert만들 때 많이 해멨다. 너무 최적하하려다가 ㄱ-.

my_doublelinkedlist.cpp

(이번에는 자료구조 정의는 많이 안 쓰고, 내 생각만 적었는데, 공개하게 되면 그 때 정의를 적든지 하자.)

그리고 예제는 단순연결리스트의 경우 명함관리가 있었는데, 순차검색만 되는 리스트로 그걸 구현할 필요를 못 느껴서 패스.

이중연결리스트의 경우 텍스트 뷰어가 있는데, 이건 한 번 시도할 만 한 것 같다.

...근데 함수의 실제적 구현부분에서 케케묵은 냄새가 풍긴다. 아예 새로 구현할 거니까 상관은 없지만,

filename[13](8.3 DOSname)이라든가 textattr... WinAPI중에 그런 함수가 있을 진 몰라도, 일단은 이건 불가다.

그리고 \r\n을 \n\r도 된다고 하다니, 커리지 리턴과 라인피드가 도스 시절엔 정말 각자 기능이 있었던건가.

텍스트뷰어를 짜 보았다. 아 코딩 속도가 넘 느리다.. ㅠㅠ

너무 최적화 생각해서 그런가. 그래 놓고도 미완성스러운데.

만들어 놓고 혼연C의 JusoList예제를 보니... 아. FirstNode, LastNode는 그럴 때 쓰라고 있는 거구나.. 하는 생각이 들었다 ㅡㅡ;

 난 또 삽질한 거였어...

더 수정하기 귀찮아서 일단 소스는 올려둔다. 특징은 아무리 큰파일이라도 부분만 읽어서 보여 줌.

하지만 한글출력과 정상동작 보장 불가. (로직...)

3-2-1_my_textviewer.cpp