[자료구조] 001. 자료구조와 알고리즘

참고한 사이트
"자료구조를 3분만에 이해해보자 | 자료구조 1강"
https://youtu.be/bh23BDYOry8

---

■ 자료구조
자료구조란 무엇인가?

자료구조 : 여러 개의 데이터를 저장하고 관리하는 방식

---

■ 전화번호부 예시
전화번호부를 만든다고 해 보자.

전화번호부는 '전화번호'라는 데이터 여러 개를 저장한다.
자료구조에서 살펴보는 것은 '전화번호를 어떻게 저장 할 것인가?' 이다.

저장할 전화번호가 아래의 순서로 되어 있다고 하자.
전화번호를 어떻게 저장할 수 있을까?

Carol    010-0000-0000
Peggy    010-2222-2222
Zoe      010-0000-1111
Mallory  010-3333-3333
Dave     010-9999-9999
Alice    010-1234-5678
Bob      010-1111-1111

---

1) 단순하게 저장할 전화번호를 순서대로 적어볼 수 있다.

Carol    010-0000-0000
Peggy    010-2222-2222
Zoe      010-0000-1111
Mallory  010-3333-3333
Dave     010-9999-9999
Alice    010-1234-5678
Bob      010-1111-1111

2) 이름을 알파벳 순으로 정렬해서 적어볼 수 있다.

Alice    010-1234-5678
Bob      010-1111-1111
Carol    010-0000-0000
Dave     010-9999-9999
Mallory  010-3333-3333
Peggy    010-2222-2222
Zoe      010-0000-1111

3) 전화번호 순으로 적어볼 수도 있다.

Carol    010-0000-0000
Zoe      010-0000-1111
Bob      010-1111-1111
Alice    010-1234-5678
Peggy    010-2222-2222
Mallory  010-3333-3333
Dave     010-9999-9999

자료구조는 이렇게 데이터(전화번호)를 저장하는 공간(전화번호부)의 방식에 대한 것이다.

---

■ 알고리즘
그렇다면 알고리즘은 무엇일까?

알고리즘 : 문제를 해결하기 위한 절차들을 나열한 것

---

■ (다시) 전화번호부 예시

다시 전화번호부 예시로 돌아가보자.
전화번호부를 사용하면서 해결해야 할 '문제'들은 아래와 같은 것들이 있다.

• '새로운 전화번호를 추가하려면, 어떤 과정을 거쳐야 하는가?'
• '내가 원하는 전화번호를 찾으려면, 어떤 과정을 거쳐야 하는가?'

---

- 1번 방식

이전에 살펴봤던 1)번 방식의 전화번호부를 보자.

Carol    010-0000-0000
Peggy    010-2222-2222
Zoe      010-0000-1111
Mallory  010-3333-3333
Dave     010-9999-9999
Alice    010-1234-5678
Bob      010-1111-1111

우리는 1)번에 전화번호를 추가할때 추가되는 순서대로 쓰는 방식을 택했다.
여기에서 "Trudy 010-1234-1234"를 추가하려면 아래와 같은 방식을 취하면 된다.

1. 가장 마지막에 저장된 전화번호를 찾는다.
2. 해당하는 전화번호의 아래에 공간이 남아있다면, 그곳에 "Trudy 010-1234-1234"를 추가한다.

---

한편 "Dave"의 전화번호를 찾으려면 아래와 같이 해야 한다.

1. 맨 위에서부터 한 칸씩 내려오면서 이름이 "Dave"인지 확인한다.
2. 이름이 "Dave"이면 해당하는 곳의 전화번호를 읽는다.

1)번 방식의 경우 새로운 데이터를 추가할 때는 편하다.
하지만 기존의 데이터를 검색하려면 맨 위에서부터 하나씩 데이터를 찾아봐야 한다.
만약 7개가 아닌 1000개의 전화번호가 적힌 전화번호부라면, 빠르게 데이터를 찾기는 어려울 수 있다.

---

- 2번 방식_ 전화번호 추가
2)번 방식은 이름을 알파벳순으로 정렬하는 방식이었다.

Alice    010-1234-5678
Bob      010-1111-1111
Carol    010-0000-0000
Dave     010-9999-9999
Mallory  010-3333-3333
Peggy    010-2222-2222
Zoe      010-0000-1111

여기에서 "Trudy 010-1234-1234"를 추가하려면 아래와 같은 방식을 사용해볼 수 있다.

1. 맨 마지막 전화번호의 위치로 간다.
2. 해당 위치의 이름과 'Trudy'를 비교해서,
   'Trudy'가 더 위에 저장되어야 하면 해당 위치의 이름을 한 칸 아래로 내린다.
3. 새롭게 비워진 칸의 한 칸 위로 가서,
   'Trudy'가 아래에 저장되어야 할 때까지 2번을 반복한다.
4. 해당 공간에 "Trudy 010-1234-1234"를 추가한다.

복잡해졌으므로 한 번 실제로 해보자.

Alice    010-1234-5678
Bob      010-1111-1111
Carol    010-0000-0000
Dave     010-9999-9999
Mallory  010-3333-3333
Peggy    010-2222-2222
Zoe      010-0000-1111

1번 단계) 맨 마지막 Zoe와 Trudy의 이름을 비교한다.
2번 단계) 알파벳 순으로 하면 "...sTuvwxyZ" 이므로 Trudy는 Zoe보다 위에 저장되어야 한다.
Zoe를 한 칸 아래로 내린다.

Alice    010-1234-5678
Bob      010-1111-1111
Carol    010-0000-0000
Dave     010-9999-9999
Mallory  010-3333-3333
Peggy    010-2222-2222
                           < 새롭게 비워진 칸
Zoe      010-0000-1111

3번 단계) 새롭게 비워진 칸의 한 칸 위, 즉 Peggy의 위치에서 2번 단계로 간다.
2번 단계) 알파벳 순으로 하면 "...oPqrsTu..." 이므로 Trudy는 Peggy보다 아래에 저장되어야 한다. 따라서 4번 단계로 간다.
4번 단계) 해당 공간에 "Trudy 010-1234-1234"를 추가한다.

Alice    010-1234-5678
Bob      010-1111-1111
Carol    010-0000-0000
Dave     010-9999-9999
Mallory  010-3333-3333
Peggy    010-2222-2222
Trudy    010-1234-1234
Zoe      010-0000-1111

---

- 2번 방식_ 전화번호 검색
한편 "Dave"의 전화번호를 찾으려면 아래와 같이 해야 한다.

1. 맨 위에서부터 한 칸씩 내려오면서 이름이 "Dave"인지 확인한다.
2. 이름이 "Dave"이면 해당하는 곳의 전화번호를 읽는다.

그런데 사실, 나중에 볼 이진 탐색(Binary Search)를 이용하면 아래와 같이 해도 된다.

1. 중간에 있는 전화번호를 찾는다.
2. 찾은 곳의 이름이 "Dave"이면 해당하는 곳의 전화번호를 읽고 알고리즘을 끝낸다.
3. "Dave"가 찾은 곳의 이름보다 위에 있다면,
   현재 찾은 곳을 기준으로 위에 있는 전화번호들에서 중간에 있는 전화번호를 찾는다.
   더이상 위에 있는 전화번호가 없을 때까지 2번을 반복한다.
4. "Dave"가 찾은 곳의 이름보다 아래에 있다면,
   현재 찾은 곳을 기준으로 아래에 있는 전화번호들에서 중간에 있는 전화번호를 찾는다.
   더이상 아래에 있는 전화번호가 없을 때까지 2번을 반복한다.

이진탐색으로 Dave를 찾는 과정은 좀 짧으므로 이진 탐색으로 Bob을 찾아보자.
1번 단계) 먼저 전화번호부 중간의 이름을 읽는다.

Alice    010-1234-5678
Bob      010-1111-1111
Carol    010-0000-0000
Dave     010-9999-9999 <- 중간
Mallory  010-3333-3333
Peggy    010-2222-2222
Trudy    010-1234-1234
Zoe      010-0000-1111

2번 단계) 찾은 곳의 이름이 "Bob"인지 본다. "Dave"를 찾았으므로 3번으로 간다.
3번 단계) "Bob"은 "Dave"보다 위에 있어야 한다.
현재 찾은 곳을 기준으로 위에 있는 전화번호 (Alice / Bob / Carol) 중 가운데를 선택한다.

Alice    010-1234-5678
Bob      010-1111-1111 <- 중간
Carol    010-0000-0000
Dave     010-9999-9999 <- (이전 단계의 중간)
Mallory  010-3333-3333
Peggy    010-2222-2222
Trudy    010-1234-1234
Zoe      010-0000-1111

그 후 2번으로 다시 간다.
2번 단계) 선택된 이름은 "Bob"이므로 우리가 찾는 전화번호를 보여주고 끝낸다.

---

2)번 방식의 경우, 새로운 전화번호를 넣을 때는 1)번 방식에 비해 복잡해졌다.
만약 100만개의 전화번호가 있는데, 새로운 사람의 이름을 맨 위에 넣어야 한다고 해보자.
그렇다면 기존의 전화번호 100만개를 전부 아래로 한 칸씩 밀어야 할 것이다.
반면 이름을 검색할 때는 전화번호가 많아질 수록 1)번 방식에 비해 장점을 가진다.
찾을 부분이 계속 절반이 되므로, 전화번호가 100만개여도 찾을 부분이 50만개 -> 25만개 -> 12.5만개 ... 가 되기 때문이다.
(log 형태가 되는 것)

---

- 3번 방식
3)번 방식은 어떠할까?
3)번 방식은 이름이 아닌 전화번호 순서로 정렬하는 방식이었다.
전화번호를 가지고 이름을 찾는 경우에는 3)번 방식이 도움이 될 수 있다.
또는, 예를 들어 010-0000- 까지는 생각이 나는데 뒷 번호가 생각이 안 난다고 해보자.
그럴 경우에는 3)번 방식에서 데이터를 찾는 것이 훨씬 편하다.

---

그 외에도 내가 참고한 유튜브 영상에서는 칸을 미리 비워 두는 방식이 있었다.
(아마도 Array / Linked List 같은 형식 설명에 좋을 것 같은...)

정리

나름대로 정리해 보면서 중요한 것은 이런 것이라고 느꼈다.

"자료구조"는 여러 개의 데이터를 저장하고 관리하는 방식이다.
"알고리즘"은 문제를 해결하기 위한 절차들을 나열한 것이다.
상황에 맞는 자료구조를 선택하는 것이 중요하다.
자료구조에 따라, 같은 문제에도 다른 알고리즘이 필요하다.
⇒ 따라서 알고리즘은 자료구조에 "종속적"이다.