๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ž๋ฃŒ๊ตฌ์กฐ ๋ฐ ์‹ค์Šต

์ž๋ฃŒ๊ตฌ์กฐ ๋ฐ ์‹ค์Šต - [4] ๋ฆฌ์ŠคํŠธ (1)

๋ฆฌ์ŠคํŠธ ADT

๋จผ์ € ADT์— ๋Œ€ํ•ด ์•Œ์•„๋ณด์ž.

ADT (์ถ”์ƒ์ž๋ฃŒํ˜•, Abstract data type) : ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์˜ ์ถ”์ƒํ˜• 

์ด๋ผ๊ณ  ์ •์˜ํ•˜๋ฉฐ ADT๋Š” ๋‹ค์Œ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค.

- ์ €์žฅ๋œ ๋ฐ์ดํ„ฐ
- ๋ฐ์ดํ„ฐ์— ๋Œ€ํ•œ ์ž‘์—…๋“ค
- ์ž‘์—… ์ค‘ ๋ฐœ์ƒ ๊ฐ€๋Šฅํ•œ ์—๋Ÿฌ ์ƒํ™ฉ๋“ค

์ด๊ฒƒ์„ ๋ฆฌ์ŠคํŠธ๋กœ ํ‘œํ˜„ํ•˜๋ฉด ๋ฆฌ์ŠคํŠธ ADT๊ฐ€ ๋˜๋Š” ๊ฒƒ์ด๋‹ค. ์‚ฌ์‹ค ๋ง์ด ์กฐ๊ธˆ ์–ด๋ ต๊ธด ํ•œ๋ฐ ์—ฐ์†์ ์ธ ์ž„์˜ ๊ฐœ์ฒด๋“ค์„ ๋ชจ๋ธ๋งํ•œ ๊ฒƒ์ด๋ผ๊ณ  ๋ณผ ์ˆ˜ ์žˆ๋‹ค. ๋ฆฌ์ŠคํŠธ์˜ ์›์†Œ์— ๋Œ€ํ•œ ์ ‘๊ทผ ๋„๊ตฌ๋กœ๋Š” ์ˆœ์œ„(rank)๊ฐ€ ์žˆ๋‹ค. 


๋ฆฌ์ŠคํŠธ ADT ๋ฉ”์„œ๋“œ

๋ฆฌ์ŠคํŠธ ADT์—์„œ ์›์†Œ๋Š” ์ˆœ์œ„ (rank), ์ฆ‰ ๊ทธ ์›์†Œ ์•ž์˜ ์›์†Œ ๊ฐœ์ˆ˜๋ฅผ ํŠน์ •ํ•˜์—ฌ ์ ‘๊ทผ, ์‚ฝ์ž…, ๋˜๋Š” ์‚ญ์ œํ•œ๋‹ค. ๋ง๋กœ๋Š” ์–ด๋ ต์ง€๋งŒ ๊ทธ๋ฆผ์„ ๊ทธ๋ ค๋ณด๋ฉด ๋”์šฑ ์ดํ•ด๊ฐ€ ์‰ฌ์šธ ๊ฒƒ์ด๋‹ค.

๋ฆฌ์ŠคํŠธ ADT ๋ฉ”์„œ๋“œ
- ์ผ๋ฐ˜ ๋ฉ”์„œ๋“œ
  boolean isEmpty() #๋ฆฌ์ŠคํŠธ๊ฐ€ ๋น„์—ˆ๋Š”์ง€ ํ™•์ธ
  integer size() #๋ฆฌ์ŠคํŠธ์˜ ์‚ฌ์ด์ฆˆ ๋ฐ˜ํ™˜
  iterator elements() #๋ชจ๋“  ๋ฆฌ์ŠคํŠธ ์›์†Œ ์ถœ๋ ฅ

- ์ ‘๊ทผ ๋ฉ”์„œ๋“œ
  element get(rank) # ํ•ด๋‹น rank์— ์žˆ๋Š” ์›์†Œ ๋ฐ˜ํ™˜

- ๊ฐฑ์‹  ๋ฉ”์„œ๋“œ
  element set(rank, element) # ํ•ด๋‹น rank์˜ ์›์†Œ๋ฅผ set
  add(rank, element) # ํ•ด๋‹น rank์— ์ƒˆ๋กœ์šด ๋…ธ๋“œ๋ฅผ ์ถ”๊ฐ€
  addFirst(element) # rank 1์— ์ƒˆ๋กœ์šด ๋…ธ๋“œ ์ถ”๊ฐ€
  addLast(element) # rank Last์— ์ƒˆ๋กœ์šด ๋…ธ๋“œ ์ถ”๊ฐ€
  element remove(rank) #ํ•ด๋‹น rank์— ์žˆ๋Š” ๋…ธ๋“œ ์ œ๊ฑฐ
  element removeFirst() # rank 1์— ์ƒˆ๋กœ์šด ๋…ธ๋“œ ์ œ๊ฑฐ
  element removeLast() # rank Last์— ์ƒˆ๋กœ์šด ๋…ธ๋“œ ์ œ๊ฑฐ

 

๋ฆฌ์ŠคํŠธ ADT๋ฅผ ๊ตฌ์„ฑํ•˜๋ฉด์„œ ์˜ˆ์™ธ๋ฅผ ๊ตฌ์„ฑํ•ด์ค˜์•ผ ํ•œ๋‹ค. ์—ฌ๊ธฐ์„œ ์˜ˆ์™ธ๋ž€ ์–ด๋–ค ADT์ž‘์—…์„ ์‹คํ–‰ํ•˜๊ณ ์ž ํ•  ๋•Œ ๋ฐœ์ƒํ•  ์ˆ˜๋„ ์žˆ๋Š” ์˜ค๋ฅ˜ ์ƒํ™ฉ์„ ๋œปํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด rank์— ์Œ์ˆ˜๊ฐ€ ์ž…๋ ฅ๋˜๋Š” ์ƒํ™ฉ์ด ์žˆ๋‹ค. ๋ฆฌ์ŠคํŠธ ADT์—์„œ ๋ฐœ๋ น ๊ฐ€๋Šฅํ•œ ์˜ˆ์™ธ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

invalidRankException() # ์œ ํšจํ•˜์ง€ ์•Š์€ rank
fullListException() # ๋ฆฌ์ŠคํŠธ๊ฐ€ ๊ฝ‰ ์ฐจ์žˆ์„ ๋•Œ
emptyListException() # ๋ฆฌ์ŠคํŠธ๊ฐ€ ๋น„์—ˆ๋Š”๋ฐ get or remove ๋“ฑ..

 

๋ฆฌ์ŠคํŠธ ADT๋Š” ๋ฐฐ์—ด๊ณผ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ํ™œ์šฉํ•˜์—ฌ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.


๋ฐฐ์—ด์„ ์ด์šฉํ•œ ๊ตฌํ˜„

๋จผ์ € N๊ฐœ์˜ ์›์†Œ๋“ค๋กœ ๊ตฌ์„ฑ๋œ ๋ฐฐ์—ด V๋ฅผ ํ™œ์šฉํ•œ๋‹ค. ๊ฐ€์žฅ ์ค‘์š”ํ•œ ๊ฒƒ์€ get ๋ฉ”์„œ๋“œ, set ๋ฉ”์„œ๋“œ ๋“ฑ ํ•„์š”ํ•˜๋‹ค๋ฉด r < 0 ๋˜๋Š” r > n – 1 ์ธ ๊ฒฝ์šฐ ์˜ˆ์™ธ์ฒ˜๋ฆฌ๋ฅผ ํ•ด์•ผํ•œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค.

 

์ดˆ๊ธฐํ™” (initailization)

์ดˆ๊ธฐ์—๋Š” ์•„๋ฌด ์›์†Œ๋„ ์กด์žฌํ•˜์ง€ ์•Š๋Š” ์ƒํƒœ์ด๋‹ค. O(1) ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค.

์ดˆ๊ธฐํ™” ์˜์‚ฌ์ฝ”๋“œ
์ดˆ๊ธฐํ™” ๋ฐฐ์—ด์˜ ์ƒํƒœ

์ˆœํšŒ (Traversal)

Traverse๋Š” array์˜ ๋ชจ๋“  ์›์†Œ V[0], V[1], V[2], …, V[n – 1]์„ ๋ฐฉ๋ฌธํ•œ๋‹ค. (์ถ”๊ฐ€๋กœ ์ถœ๋ ฅํ•ด๋„ ์ข‹๋‹ค) 

์กด์žฌํ•˜๋Š” ๋ชจ๋“  ์›์†Œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋ฏ€๋กœ O(n) ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค.

์ˆœํšŒ ์˜์‚ฌ์ฝ”๋“œ
๋ฐฐ์—ด์„ ์ˆœํšŒํ•˜๋Š” ๋ชจ์Šต

์‚ฝ์ž… (Insertion)

์ž‘์—… add(rank, element)์—์„œ๋Š”, rank ์ˆœ์œ„๋กœ ์ƒˆ ์›์†Œ element๊ฐ€ ๋“ค์–ด๊ฐˆ ๋นˆ ์ž๋ฆฌ๋ฅผ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด V[n – 1], … , V[r]๊นŒ์ง€์˜ n – r๊ฐœ์˜ ์›์†Œ๋“ค  ์ˆœ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™(shift forward)ํ•œ๋‹ค. ์ด ๊ฒฝ์šฐ rank ๊ฐ€ 0์ด๋ฉด, n๊ฐœ์˜ ์›์†Œ๊ฐ€ ํ•œ ์นธ์”ฉ ์˜ฎ๊ฒจ์•ผ ํ•˜๋ฏ€๋กœ O(n) ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค. ๊ตฌํ˜„ํ•˜๋ฉด์„œ ์˜ˆ์™ธ์— ์ฃผ์˜ํ•˜์ž!

์‚ฝ์ž…์˜ ์˜์‚ฌ์ฝ”๋“œ
rank์— element๋ฅผ ์‚ฝ์ž…ํ•˜๋Š” ๋ชจ์Šต

์‚ญ์ œ (Deletion)

์‚ฝ์ž…๊ณผ ๋ฐ˜๋Œ€๋กœ ์ž‘์—… remove(rank)์—์„œ๋Š”, ์‚ญ์ œ๋œ ์›์†Œ์— ์˜ํ•ด ์ƒ๊ธด ๋นˆ ์ž๋ฆฌ๋ฅผ ์ฑ„์šฐ๊ธฐ ์œ„ํ•ด V[r + 1], … , V[n – 1]๊นŒ์ง€์˜ n – r – 1๊ฐœ์˜ ์› ์†Œ๋“ค์„ ์—ญ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™(shift backward)ํ•œ๋‹ค. ์ด ๊ฒฝ์šฐ rank ๊ฐ€ 0์ด๋ฉด, n๊ฐœ์˜ ์›์†Œ๊ฐ€ ํ•œ ์นธ์”ฉ ์˜ฎ๊ฒจ์•ผ ํ•˜๋ฏ€๋กœ O(n) ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค. ๊ตฌํ˜„ํ•˜๋ฉด์„œ ์˜ˆ์™ธ์— ์ฃผ์˜ํ•˜์ž!

์‚ญ์ œ ์˜์‚ฌ์ฝ”๋“œ
rank์— ํ•ด๋‹นํ•˜๋Š” element๋ฅผ ์‚ญ์ œํ•˜๋Š” ๋ชจ์Šต

 

์„ฑ๋Šฅ (Performance)

* ๋ฐฐ์—ด์„ ์ด์šฉํ•˜์—ฌ ๋ฆฌ์ŠคํŠธ ADT๋ฅผ ๊ตฌํ˜„ํ•  ๊ฒฝ์šฐ

๋ฐ์ดํ„ฐ๊ตฌ์กฐ์— ์˜ํ•œ ๊ธฐ์–ต์žฅ์†Œ ์‚ฌ์šฉ๋Ÿ‰: O(n)
size, isEmpty, get, set: O(1)
add, remove: O(n)
addFirst, removeFirst: O(n)
addLast, removeLast: O(1)


* ๋ฐฐ์—ด์„ ์›ํ˜•์œผ๋กœ ์ด์šฉํ•˜๋ฉด
addFirst, removeFirst: O(1)

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์šฉํ•œ ๊ตฌํ˜„

๋‹จ์ผ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ํ™œ์šฉํ•˜์—ฌ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, ์ด๋ฒˆ์—๋Š” ์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์šฉํ•ด ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ๋ฐฐ์›Œ๋ณด์ž.

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ(doubly linked list)๋ฅผ ์ด์šฉํ•˜๋ฉด ๋ฆฌ์ŠคํŠธ ADT๋ฅผ ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. ์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ๋…ธ๋“œ ๊ตฌ์„ฑ๊ณผ ํŠน์ง•์€ ์ด์ „ ํฌ์ŠคํŒ…์„ ์ฐธ๊ณ ํ•˜์ž.

 

https://mainyoung.tistory.com/21

 

์ž๋ฃŒ๊ตฌ์กฐ ๋ฐ ์‹ค์Šต - [3] ๊ธฐ์ดˆ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ (๋ฐฐ์—ด, ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ) (1)

๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์˜ ๊ธฐ๋ณธ ์žฌ๋ฃŒ ๋ฐ์ดํ„ฐ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ๊ธฐ๋ณธ ์žฌ๋ฃŒ๋กœ๋Š” ๋ฐฐ์—ด๊ณผ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๊ฐ€ ์กด์žฌํ•œ๋‹ค. ์ด๋Š” ๊ณ ๊ธ‰ ๋ฐ์ดํ„ฐ๊ตฌ์กฐ๋ฅผ ๊ตฌ์ถ•ํ•˜๋Š” ๊ธฐ๋ณธ ์žฌ๋ฃŒ๋กœ ์“ฐ์ด๊ธฐ ๋•Œ๋ฌธ์— ์ž˜ ์•Œ์•„๋‘์–ด์•ผ ํ•œ๋‹ค! ๋ฐฐ์—ด (array) ์ˆœ์ฐจ

mainyoung.tistory.com

 

์ด๋ฅผ ๊ตฌํ˜„ํ•˜๋ฉด์„œ Header ๋…ธ๋“œ์™€ Trailer ๋…ธ๋“œ๋ฅผ ์ ๊ทน์ ์œผ๋กœ ํ™œ์šฉํ•˜๊ฒ ๋‹ค.

์ž‘์—… get(r) ๋˜๋Š” set(r, e)๋Š” O(n) ์‹œ๊ฐ„์— ์ง€์ •๋œ ์ˆœ์œ„ r์˜ ์›์†Œ๋ฅผ ๋ฐ˜ํ™˜ ๋˜๋Š” ์ €์žฅํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ๋˜ํ•œ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์—์„œ ์ˆœ์œ„๋Š” 1์—์„œ ์ถœ๋ฐœ๋กœ ์ „์ œํ•œ๋‹ค.

get๊ณผ set ๋ฉ”์„œ๋“œ์˜ ์˜์‚ฌ์ฝ”๋“œ

์—ฌ๊ธฐ์„œ ์ฃผ์˜ํ•ด์•ผ ํ•  ์ ์€ ๊ตฌํ˜„ํ•˜๋ฉด์„œ ์˜ˆ์™ธ(Exception)๋ฅผ ์ฃผ์˜ํ•ด์•ผํ•œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ์‹œ๊ฐํ™” ํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์‹œ๊ฐํ™”

์ดˆ๊ธฐํ™” (initailization)

์ดˆ๊ธฐ์—๋Š” ์•„๋ฌด ๋…ธ๋“œ๋„ ์—†๋‹ค. ๋”ฐ๋ผ์„œ Header ๋…ธ๋“œ์™€ Trailer๋…ธ๋“œ๋งŒ ์„œ๋กœ ์—ฐ๊ฒฐํ•œ๋‹ค. O(1) ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค.

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์ดˆ๊ธฐํ™” ์˜์‚ฌ์ฝ”๋“œ
์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์ดˆ๊ธฐํ™”

์ˆœํšŒ (Traversal)

์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ๋ชจ๋“  ์›์†Œ๋“ค์„ ๋ฐฉ๋ฌธํ•˜๋ฉฐ, Printํ•ด๋„ ์ข‹๋‹ค. O(n) ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค.

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์˜์‚ฌ์ฝ”๋“œ

์ด๋•Œ ํฌ์ธํ„ฐ์— Header์˜ next๋ฅผ ์ €์žฅํ•ด์„œ ์‚ฌ์šฉํ•œ๋‹ค!

 

์‚ฝ์ž… (Insertion)

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์ง€์ •๋œ ์ˆœ์œ„ r์— ์›์†Œ e๋ฅผ ์‚ฝ์ž…ํ•˜๋Š” ์ž‘์—…์ด๋‹ค. O(n) ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค.

์ด๋ฒˆ์—๋Š” ์ž‘์—… add(rank, X)์˜ ์‹œ๊ฐํ™”fmf ๋ณด์ž – ์—ฌ๊ธฐ์„œ rank = 3์œผ๋กœ ์„ค์ •ํ–ˆ๋‹ค.

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์‚ฝ์ž…

๊ธฐ์กด์—๋Š” rank 3 ์— C๊ฐ€ ์žˆ์—ˆ์ง€๋งŒ, ์‚ฝ์ž…์„ ์œ„ํ•ด B์™€ C์˜ ์ด์ค‘์—ฐ๊ฒฐ์„ ๋Š๊ณ  B์™€ X, X์™€ C์— ์ด์ค‘์—ฐ๊ฒฐ์„ ๊ตฌ์„ฑํ•œ๋‹ค.

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์‚ฝ์ž… ์˜์‚ฌ์ฝ”๋“œ

 

์‚ญ์ œ (Deletion)

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์ง€์ •๋œ ์ˆœ์œ„ r์˜ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•˜๊ณ  ์›์†Œ๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค. O(n) ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค.

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์‚ญ์ œ ์˜์‚ฌ์ฝ”๋“œ

rank 3๊ณผ ์—ฐ๊ฒฐ๋œ B์™€ Trailer์˜ ์ด์ค‘์—ฐ๊ฒฐ์„ ๋Š๊ณ  B์™€ Trailer๋ฅผ ์ด์ค‘์—ฐ๊ฒฐํ•œ๋‹ค. ์ดํ›„ C๋ฅผ ์‚ญ์ œํ•œ๋‹ค.

 

์„ฑ๋Šฅ (Performance)

์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์šฉํ•œ ๋ฆฌ์ŠคํŠธ ADT๋ฅผ ๊ตฌํ˜„ํ•  ๊ฒฝ์šฐ ์„ฑ๋Šฅ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ๊ฐ ์›์†Œ์— ์‚ฌ์šฉ๋˜๋Š” ๊ธฐ์–ต์žฅ์†Œ: O(1)
N๊ฐœ์˜ ์›์†Œ๋กœ ๊ตฌ์„ฑ๋œ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์— ์˜ํ•ด ์‚ฌ์šฉ๋˜๋Š” ๊ธฐ์–ต์žฅ์†Œ: O(n)
size, isEmpty: O(1)
get, set, add, remove: O(n)
addFirst, addLast, removeFirst, removeLast: O(1)

 

๋ฐฐ์—ด๊ณผ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ์„ฑ๋Šฅ์„ ์š”์•ฝํ•˜์ž๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

์ž‘์—… ๋ฐฐ์—ด ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ
size, isEmpty 1 1
get, set 1 n
add, remove n n
addFirst, removeFirst n 1
addLast, removeLast 1 1
728x90