알고리즘 Repo
본 알고리즘 시리즈는 하스켈을 위주로 사용하여 포스팅 되고 있습니다. 자세한 설명 보다는 공부하고 있는 하스켈 언어를 공부하기 위한 목적으로 포스팅을 하고 있으므로 누락되어 있거나 틀린 부분이 다소 존재할 수 있습니다.

원래 다익스트라 부터 포스팅 하려고 했는데 아무래도 생소한 언어를 사용하다 보니 코드 꼬라지 보고 갑자기 이거 포스팅하기 귀찮아서 그냥 기초부터 하려구요 ㅋㅋㅋㅋㅋㅋ

사실 다익스트라를 하스켈로 구현하면서 큐를 구현해야 하는 시점(BFS로 그래프 탐색)이 있었는데 간단한 문제임에도 불구하고 많은 시행착오를 겪었습니다. 그래서 기본 적인 자료구조부터 코딩할 줄 알아야 다른 알고리즘도 무리없이 구현할 수 있을 것 같아서 밑바닥 부터 시작하려고 합니다.

자료구조 포스팅 리스트

• 하스켈에서의 "배열"과 "리스트"
• 스택, 큐 1 (리스트 사용)
• 환형 덱
• 연결리스트 1 - 단일연결리스트
• 스택, 큐 2 (연결리스트 사용)
• 연결리스트 2 - 이중연결리스트, 원형연결리스트
• 연결리스트 3 - 연결리스트 활용
• 이진 트리, 다중 트리
• 힙 (우선순위 큐)
• 그래프 이론
• 그래프 활용
• 해시 테이블

하스켈에서의 "배열"과 "리스트"

소개

하스켈에서는 Array(배열)과 List(리스트)를 지원합니다. 이를 이용해 다양한 알고리즘이나 다른 자료구조를 구현할 수 있습니다. 보통 Array와 List의 차이점이라고 하면 데이터의 길이가 정해져 있는지에 대한 여부가 대표적입니다. Array는 데이터의 길이를 미리 정하지만 리스트는 정하지 않는 경우도 있습니다. 하스켈에서의 배열과 리스트는 조금 다른 차이점을 보여줍니다. 원래 스택, 큐 부터 시작하려고 했으나 배열과 리스트는 모든 언어에서도 그랬듯이 가장 빈번하게 쓰이기 때문에 다시 한번 정리 하려고 합니다.

List(리스트)

선언

ghci> a = [1,2,3,4,5]
ghci> a
[1,2,3,4,5]

파이썬에서의 리스트 선언 방식과 차이점이 없습니다. 또한 파이썬 처럼 조건 제시식 으로도 선언이 가능합니다. 심지어 파이썬 보다 더 조건 제시식에 가깝게 작성할 수 있습니다.

python

>>> a = [i for i in range(1, 10) if i > 5]
>>> a
[6, 7, 8, 9]

Haskell

ghci> a = [x| x <- [1..9], x > 5]
ghci> a
[6,7,8,9]

접근

하스켈에서 인덱스로 접근할 때 a[idx]가 아닌 a !! idx로 선언해서 접근합니다. 그러나 인덱스 접근을 통해 값을 수정하는 것은 불가능 합니다.

ghci> a = [1,2,3,4]
ghci> a !! 1
2

인덱스가 아니어도 첫 부분과 끝부분도 접근할 수 있습니다. 대신 last 함수일 경우 알고리즘 시간이 $O(n)$이기 때문에 사용하는데 있어서 신중하게 고려를 해야 할 필요가 있습니다. 개인적으로 last는 거의 쓰지 않는 함수 입니다. 나중에 스택, 큐에서도 언급을 하겠지만 거기에서도 쓰지 않습니다.

ghci> a = [1,2,3,4]
ghci> head a
1
ghci> last a
4

수정

List에서 특정 인덱스를 접근하여 수정할 수 있는 방법은 없습니다. List에서 특정 인덱스의 값을 수정하려면 따로 함수를 직접 구현해야 합니다.

modify :: (Num a, Ord a) => a -> b -> [b] -> [b]
modify _ _ [] = []
modify idx v (x:xs)
	--- idx: 수정해야 될 위치
    	--- v: 새로 수정할 값
        --- (x:xs) 리스트
    | idx < 0       = x : xs  -- error
    | idx == 0      = v : xs  -- 수정해야 할 지점
    | otherwise     = x : (modify (idx - 1) v xs)
    
==== ghci ====
ghci>:load modify.hs
[1 of 1] Compiling Main             ( modify.hs, interpreted )
Ok, one module loaded.
ghci> a = [1,2,3,4,5]
ghci> modify (-1) 100 a
[1,2,3,4,5]
ghci> modify 300 100 a 
[1,2,3,4,5]
ghci> modify 1 100 a  
[1,100,3,4,5]

그런데 이 경우, 재귀 방식을 사용하여 인덱스를 1씩 내리면서 0에 도달할 때 까지 일일히 순회해야 하기 때문에 $O(n)$ 이라는 시간이 걸립니다. 그렇기 때문에 배열의 데이터를 수정해야 하는 상황이 올 경우 List가 아닌 Map이나 밑에 후술할 Array를 사용하는 것이 유리합니다.

삽입

(++)

++ 함수를 사용하여 리스트 끼리 이어붙일 수 있습니다.

ghci> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]

제거

가능은 하지만 리스트의 맨 끝부분만 제거할 수 있습니다. 개인적으로 잘 사용하지 않는 함수 입니다.

ghci> a = [1,2,3,4,5]
ghci> b = init a
ghci> b
[1,2,3,4]

(:) 함수

하스켈 리스트의 핵심 함수 입니다. 수정 항목의 코드에서도 보시다시피 리스트와 맨 앞의 데이터를 합치거나 분리하는데 매우 유용한 함수 입니다. 하스켈은 함수형 프로그래밍 특성상 함수 안의 변수들은 절대 변경할 수 없기 때문에 For문이나 While 문이 없습니다. 대신 재귀를 이용해서 리스트의 데이터를 순회하는데 (:) 함수가 이에 대한 역할을 수행합니다. 언젠간 포스팅할(?) map, foldr, foldl 같은 리스트를 순회해서 연산하는 함수도 (:)를 사용하여 직접 구현할 수 있습니다.

ghci> a = [2,3] 
ghci> 1:a   
[1,2,3]

위와 같이 리스트의 맨 앞에 데이터를 추가할 수도 있고

ghci> x:xs = [1,2,3,4]
ghci> x
1
ghci> xs
[2,3,4]

반대로 맨 앞의 데이터를 분리할 수 있습니다.

Array(배열)

배열은 리스트보다 사용법이 조금 까다롭습니다. 하지만 리스트와는 달리 해당 인덱스에 대한 데이터 수정이 가능합니다. 저도 이 구조체에 대해 공부한 지 얼마 안되었기 때문에 다소 틀린 부분이 있을 수 있습니다.
배열을 선언하려면 먼저 모듈 Data.Array를 먼저 import 해야 합니다.

선언

배열의 선언 문법부터 조금 난해 합니다. 하스켈의 선언 문법을 보기 전에 다른 언어들의 배열 선언 문법을 알아봅시다.

// c
int a[4] = {1,2,3,4};

// go
var a [4]int = {1,2,3,4}

배열 구조체를 가지고 있는 언어들은 대괄호 사이에 배열의 크기를 선언함으로써 배열을 선언합니다. 그런데...

# haskell
ghci> :m +Data.Array (코드에서는 import Data.Array)
ghci> a = array (0, 2) [(0, 1), (1, 2), (2, 3)]
ghci> a
array (0,2) [(0,1),(1,2),(2,3)]

?????
배열을 선언할 때 두 개의 인자가 들어옵니다.

• (0, 2): 튜플 형태로 왼쪽은 시작 인덱스, 오른쪽은 마지막 인덱스 입니다.
• [(0,1), (1,2), (2,3)]: 튜플을 요소로 하는 리스트입니다. 튜플의 왼쪽 값은 인덱스, 튜플의 오른쪽 값은 데이터가 됩니다. 튜플의 왼쪽 값들의 범위는 반드시 왼쪽 인자의 범위 안에 들어와야 합니다. 그렇지 않으면 에러를 발생시킵니다.

그런데 만약에 길아가 100인 배열을 0으로 초기화 해서 선언할 때 이렇게 일일이 [(0, 0), (1, 0), (2, 0) ... ] 이런식으로 코드를 작성하는 것은 매우 불편합니다. 아래와 같이 조건 제시식으로도 선언할 수 있습니다.

a = array (0, 99) [(x, 0)| x <- [0..99]]

시작 인덱스를 0이 아닌 다른 정수로 시작해도 문제 없습니다.

ghci> a = array ((-10), (-7)) [(x, x*10)| x <- [(-10)..(-7)]]
ghci> a
array (-10,-7) [(-10,-100),(-9,-90),(-8,-80),(-7,-70)]

접근

인덱스 접근

인덱스로 접근을 하며 a ! idx로 데이터에 접근합니다.

ghci> a = array (-1, 99) [(x, x*10)| x <- [-1..99]]
ghci> a ! 0
0
ghci> a ! 1
10
ghci> a ! (-1)
-10

인덱스, 값 따로 접근

인덱스 따로, 값 따로 해서 리스트로 출력하는 함수도 있습니다. 파이썬의 enumerate와 비슷한 개념이라고 보시면 됩니다. 인덱스 따로 출력은 indices, 값 따로 출력은 elems 입니다

ghci> a = array (1,3) [(x, x*10)| x <- [1..3]]
ghci> a
array (1,3) [(1,10),(2,20),(3,30)]
ghci> indices a
[1,2,3]
ghci> elems a
[10,20,30]

삽입

길이가 정해져 있기 때문에 데이터 삽입은 불가능 합니다.

수정

리스트와는 다르게 해당 인덱스의 값들을 수정할 수 있으며 //와 accum을 사용합니다.

(//)

해당 인덱스로 접근해서 값을 변경하는 방식입니다.

ghci> a
array (1,3) [(1,10),(2,20),(3,30)]
ghci> a // [(1, 140)]
array (1,3) [(1,140),(2,20),(3,30)]

//의 왼쪽은 해당 리스트 오른쪽은 변경 할 데이터의 리스트가 되는데 튜플 안에 왼쪽은 인덱스, 오른쪽은 변경 할 값입니다. 리스트로 되어있기 때문에 한번에 여러 데이터들을 처리할 수 있습니다

ghci> a
array (1,3) [(1,10),(2,20),(3,30)]
ghci> a // [(1, 140), (3, 140)]
array (1,3) [(1,140),(2,20),(3,140)]

accum

// 와 같이 인덱스로 접근해서 데이터를 수정하는 함수이지만 //는 변수로 값을 바꾼다면 accum은 함수를 추가해서 데이터를 변경합니다. 예를 들어 기존 데이터에 5를 곱해서 변경할 수 있습니다

ghci> a
array (1,3) [(1,10),(2,20),(3,30)]
ghci> accum (*) a [(1,5)]
array (1,3) [(1,50),(2,20),(3,30)]

accum의 인자는 아래와 같습니다
1. (*): 데이터 변경에 사용할 함수 입니다. 여기서는 곱셈을 사용했습니다
2. a: 변경할 대상 배열 입니다.
3. [(1,5)] 변경할 인덱스와 데이터 변경을 위한 추가 변수를 튜플로 저장되어 있는 리스트 입니다. 위 코드에서는 인덱스 1의 위치에 5를 곱하겠다는 의미와 같습니다.

그러나 값 수정에 사용될 함수의 형태는 한정되어 있습니다

ghci> :t accum
accum
  :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e

(e -> a -> e) 형태의 함수만 적용할 수 있는데 이는 인자를 두개 받고 배열의 데이터 타입과 일치하는 타입의 변수를 출력한다는 의미가 됩니다. 아까 위의 예시의 (*)는 두개의 정수(다른 타입도 가능하지만 예시에서는 배열 값이 정수이기 때문에 정수로 가정) 인자로 받고 곱해서 정수 값을 리턴하기 때문에 accum에서 적용할 수 있었습니다.

삭제

수정과 마찬가지로 불가능 합니다

요약

하스켈에서의 배열과 리스트의 기능 차이는 꽤나 커서, 목적에 따라서 신중하게 선택을 해야 합니다. 데이터의 길이가 수시로 변하지만 그 안의 데이터의 수정 빈도가 낮은 경우는 리스트를, 데이터의 길이는 유지되지만 수정이 잦은 경우는 배열을 선택해야 합니다. 예를 들어 다음 포스터에 후술할 스택과 큐에서는 데이터의 길이가 상시로 변하고, 그 안의 데이터를 수정하지 않기 때문에 리스트로 구현합니다.