Home > Algorithm > 2024 > ๐Ÿ“ฆ[DS,Algorithm] ์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ - ๋ฐฐ์—ด

๐Ÿ“ฆ[DS,Algorithm] ์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ - ๋ฐฐ์—ด
DataStructure Algorithm

1๏ธโƒฃ ์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ - ๋ฐฐ์—ด.

์ž๋ฃŒ๊ตฌ์กฐ ๊ด€์ ์—์„œ ๋ฐฐ์—ด์„ ์ดํ•ดํ•˜๊ณ  ์—ฌ๋Ÿฌ ๋ฐฉ๋ฒ•์œผ๋กœ ๊ตฌํ˜„ ๊ฐ€๋Šฅ

1๏ธโƒฃ ๋ฐฐ์—ด(Array).

์ž๋ฃŒ๊ตฌ์กฐ ๊ด€์ ์—์„œ ๋ฐฐ์—ด(Array)์€ ๋™์ผํ•œ ํƒ€์ž…์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์—ฐ์†๋œ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์— ์ €์žฅํ•˜๋Š” ์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.

๋ฐฐ์—ด์€ ์กฐ์ •๋œ ํฌ๊ธฐ๋ฅผ ๊ฐ€์ง€๋ฉฐ, ์ธ๋ฑ์Šค๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๊ฐ ์š”์†Œ์— ๋น ๋ฅด๊ฒŒ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋Š” ํŠน์ง•์ด ์žˆ์Šต๋‹ˆ๋‹ค.

๋ฐฐ์—ด์€ ๊ฐ€์žฅ ๊ธฐ๋ณธ์ ์ด๊ณ  ๋„๋ฆฌ ์‚ฌ์šฉ๋˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ ์ค‘ ํ•˜๋‚˜์ž…๋‹ˆ๋‹ค.

ํŠน์ง•.

  1. ๊ณ ์ •๋œ ํฌ๊ธฐ(Fixed Size)
    • ๋ฐฐ์—ด์€ ์„ ์–ธ ์‹œ ํฌ๊ธฐ๊ฐ€ ๊ฒฐ์ •๋˜๋ฉฐ, ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๋Š” ๋ณ€๊ฒฝํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ์ด ํฌ๊ธฐ๋Š” ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜๋Š” ๋™์•ˆ ๊ณ ์ •๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.
    • ์˜ˆ: โ€˜int[] numbers = new int[10];โ€˜(ํฌ๊ธฐ๊ฐ€ 10์ธ ์ •์ˆ˜ํ˜• ๋ฐฐ์—ด)
  2. ์—ฐ์†๋œ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„(Contiguous Memory Allocation)
    • ๋ฐฐ์—ด์˜ ์š”์†Œ๋“ค์€ ๋ฉ”๋ชจ๋ฆฌ์ƒ์— ์—ฐ์†์ ์œผ๋กœ ๋ฐฐ์น˜๋ฉ๋‹ˆ๋‹ค. ์ด๋Š” ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•œ ๋น ๋ฅธ ์ ‘๊ทผ์„ ๊ฐ€๋Šฅํ•˜๊ฒŒ ํ•ฉ๋‹ˆ๋‹ค.
    • ์ฒซ ๋ฒˆ์งธ ์š”์†Œ์˜ ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ธ๋ฑ์Šค๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๋‹ค๋ฅธ ์š”์†Œ์˜ ์ฃผ์†Œ๋ฅผ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  3. ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•œ ์ ‘๊ทผ(Indexing)
    • ๋ฐฐ์—ด์˜ ๊ฐ ์š”์†Œ๋Š” ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•ด ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ธ๋ฑ์Šค๋Š” 0๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ๋ฐฐ์—ด์˜ ํฌ๊ธฐ -1๊นŒ์ง€์˜ ๊ฐ’์„ ๊ฐ€์ง‘๋‹ˆ๋‹ค.
    • ์˜ˆ: โ€˜numbers[0]โ€™,โ€™numbers[1]โ€˜,โ€ฆ,โ€™numbers[9]โ€˜
  4. ๋™์ผํ•œ ๋ฐ์ดํ„ฐ ํƒ€์ž…(Homogeneous Data Type)
    • ๋ฐฐ์—ด์€ ๋™์ผํ•œ ๋ฐ์ดํ„ฐ ํƒ€์ž…์˜ ์š”์†Œ๋“ค๋กœ ๊ตฌ์„ฑ๋ฉ๋‹ˆ๋‹ค. ์ฆ‰, ๋ฐฐ์—ด ๋‚ด ๋ชจ๋“  ์š”์†Œ๋Š” ๊ฐ™์€ ๋ฐ์ดํ„ฐ ํƒ€์ž…์ด์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
    • ์˜ˆ: ์ •์ˆ˜ํ˜• ๋ฐฐ์—ด, ๋ฌธ์ž์—ด ๋ฐฐ์—ด ๋“ฑ.

์žฅ์ .

  1. ๋น ๋ฅธ ์ ‘๊ทผ ์†๋„(Fast Access) :
    • ์ธ๋ฑ์Šค๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ O(1) ์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ๋ฐฐ์—ด์˜ ์ž„์˜์˜ ์š”์†Œ์— ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋Š” ๋ฐฐ์—ด์˜ ์ฃผ์š” ์žฅ์  ์ค‘ ํ•˜๋‚˜์ž…๋‹ˆ๋‹ค.
  2. ๊ฐ„๋‹จํ•œ ๊ตฌํ˜„(Simple Implementation) :
    • ๋ฐฐ์—ด์€ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๊ฐ€ ๊ฐ„๋‹จํ•˜์—ฌ ๊ตฌํ˜„์ด ์šฉ์ดํ•ฉ๋‹ˆ๋‹ค. ๊ธฐ๋ณธ์ ์ธ ์ž๋ฃŒ๊ตฌ์กฐ๋กœ, ๋‹ค๋ฅธ ๋ณต์žกํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ๊ธฐ์ดˆ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

๋‹จ์ .

  1. ๊ณ ์ •๋œ ํฌ๊ธฐ(Fixed Size) :
    • ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๋Š” ์„ ์–ธ ์‹œ ๊ฒฐ์ •๋˜๋ฉฐ, ํฌ๊ธฐ๋ฅผ ๋ณ€๊ฒฝํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ์ด๋Š” ํฌ๊ธฐ๋ฅผ ์‚ฌ์ „์— ์ •ํ™•ํžˆ ์˜ˆ์ธกํ•˜๊ธฐ ์–ด๋ ค์šด ๊ฒฝ์šฐ ๋น„ํšจ์œจ์ ์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  2. ์‚ฝ์ž… ๋ฐ ์‚ญ์ œ์˜ ๋น„ํšจ์œจ์„ฑ(Inefficient Insertions and Deletions) :
    • ๋ฐฐ์—ด์˜ ์ค‘๊ฐ„์— ์š”์†Œ๋ฅผ ์‚ฝ์ž…ํ•˜๊ฑฐ๋‚˜ ์‚ญ์ œํ•  ๊ฒฝ์šฐ, ์š”์†Œ๋“ค์„ ์ด๋™์‹œ์ผœ์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— O(n) ์‹œ๊ฐ„์ด ์†Œ์š”๋ฉ๋‹ˆ๋‹ค. ์ด๋Š” ํฐ ๋ฐฐ์—ด์˜ ๊ฒฝ์šฐ ์„ฑ๋Šฅ ์ €ํ•˜๋ฅผ ์ดˆ๋ž˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  3. ๋ฉ”๋ชจ๋ฆฌ ๋‚ญ๋น„(Memory Waste) :
    • ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๋ฅผ ๋„ˆ๋ฌด ํฌ๊ฒŒ ์„ค์ •ํ•˜๋ฉด ์‚ฌ์šฉ๋˜์ง€ ์•Š๋Š” ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ ๋‚ญ๋น„๋  ์ˆ˜ ์žˆ๊ณ , ๋„ˆ๋ฌด ์ž‘๊ฒŒ ์„ค์ •ํ•˜๋ฉด ์ถฉ๋ถ„ํ•œ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

๋ฐฐ์—ด์˜ ์‚ฌ์šฉ ์˜ˆ์‹œ.

  • ์ •์ˆ˜ํ˜• ๋ฐฐ์—ด ์„ ์–ธ ๋ฐ ์ดˆ๊ธฐํ™”
    int[] numbers = new int[5];
    numbers[0] = 10;
    numbers[1] = 20;
    numbers[2] = 30;
    numbers[3] = 40;
    numbers[4] = 50;
    
  • ๋ฐฐ์—ด์˜ ์š”์†Œ ์ ‘๊ทผ
    int firstElement = numbers[0]; // 10
    int lastElement = numbers[4]; // 50
    
  • ๋ฐฐ์—ด์˜ ์ˆœํšŒ
    for (int i = 0; i < numbers.length; i++) {
      System.out.println(numbers[i]);
    }
    

๋งˆ๋ฌด๋ฆฌ.

๋ฐฐ์—ด์€ ๋‹ค์–‘ํ•œ ์ƒํ™ฉ์—์„œ ๊ธฐ๋ณธ์ ์ธ ๋ฐ์ดํ„ฐ ์ €์žฅ๊ณผ ์ ‘๊ทผ ๋ฐฉ๋ฒ•์„ ์ œ๊ณตํ•˜๋ฉฐ, ํŠน์ • ์š”๊ตฌ์‚ฌํ•ญ์— ๋งž์ถฐ ๋‹ค๋ฅธ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ํ•จ๊ป˜ ์‚ฌ์šฉ๋˜๊ธฐ๋„ ํ•ฉ๋‹ˆ๋‹ค.

๋ฐฐ์—ด์˜ ๋น ๋ฅธ ์ ‘๊ทผ ์†๋„์™€ ๊ฐ„๋‹จํ•œ ๊ตฌ์กฐ ๋•๋ถ„์—, ๋งŽ์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ํ”„๋กœ๊ทธ๋žจ์—์„œ ํ•ต์‹ฌ์ ์ธ ์—ญํ• ์„ ํ•ฉ๋‹ˆ๋‹ค.


2๏ธโƒฃ ๋ฐฐ์—ด ์ง์ ‘ ๊ตฌํ˜„.

// CustomArray ํด๋ž˜์Šค
public class CustomArray {
  private int[] data;
  private int size;

  // ํŠน์ • ์šฉ๋Ÿ‰์œผ๋กœ ๋ฐฐ์—ด์„ ์ดˆ๊ธฐํ™”ํ•˜๋Š” ์ƒ์„ฑ์ž
  public CustomArray(int capacity) {
    data = new int[capacity];
    size = 0;
  }

  // ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๋ฅผ ๊ฐ€์ ธ์˜ค๋Š” ๋ฉ”์„œ๋“œ
  public int size() {
    return size;
  }

  // ๋ฐฐ์—ด์ด ๋น„์–ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๋ฉ”์„œ๋“œ
  public boolean isEmpty() {
    return size == 0;
  }

  // ํŠน์ • ์ธ๋ฑ์Šค์˜ ์š”์†Œ๋ฅผ ๊ฐ€์ ธ์˜ค๋Š” ๋ฉ”์„œ๋“œ
  public int get(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("Index out of bounds");
    }
    return data[index];
  }

  // ํŠน์ • ์ธ๋ฑ์Šค์— ์š”์†Œ๋ฅผ ์„ค์ •ํ•˜๋Š” ๋ฉ”์„œ๋“œ
  public void set(int index, int value) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("Index out of bounds");
    }
    data[index] = value;
  }

  // ๋ฐฐ์—ด์— ์š”์†Œ๋ฅผ ์ถ”๊ฐ€ํ•˜๋Š” ๋ฉ”์„œ๋“œ
  public void add(int value) {
    if (size == data.length) {
      throw new IllegalStateException("Array is full");
    }
    data[size] = value;
    size++;
  }

  // ํŠน์ • ์ธ๋ฑ์Šค์˜ ์š”์†Œ๋ฅผ ์‚ญ์ œํ•˜๋Š” ๋ฉ”์„œ๋“œ
  public void remove(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException("Index out of bounds");
    }

    for (int i = index; i < size - 1; i++) {
      data[i] = data[i + 1];
    }
    size--;
  }

  // ๋ชจ๋“  ์š”์†Œ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฉ”์„œ๋“œ
  public void print() {
    for (int i = 0; i < size; i++) {
      System.out.print(data[i] + " ");
    }
    System.out.println();
  }
}

์„ค๋ช….

  • ํ•„๋“œ:
    • โ€˜dataโ€™ : ์‹ค์ œ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฐ์—ด.
    • โ€˜sizeโ€™ : ํ˜„์žฌ ๋ฐฐ์—ด์— ์ €์žฅ๋œ ์š”์†Œ์˜ ๊ฐœ์ˆ˜.
  • ์ƒ์„ฑ์ž:
    • โ€˜CustomArray(int capacity)โ€™ : ์ดˆ๊ธฐ ์šฉ๋Ÿ‰์„ ์„ค์ •ํ•˜์—ฌ ๋ฐฐ์—ด์„ ์ดˆ๊ธฐํ™” ํ•ฉ๋‹ˆ๋‹ค.
  • ๋ฉ”์„œ๋“œ:
    • โ€˜size()โ€™ : ํ˜„์žฌ ๋ฐฐ์—ด์— ์ €์žฅ๋œ ์š”์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.
    • โ€˜isEmpty()โ€™ : ๋ฐฐ์—ด์ด ๋น„์–ด์žˆ๋Š”์ง€ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค.
    • โ€˜get(int index)โ€™ : ํŠน์ • ์ธ๋ฑ์Šค์˜ ์š”์†Œ๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.
    • โ€˜set(int index, int value)โ€™ : ํŠน์ • ์ธ๋ฑ์Šค์˜ ์š”์†Œ๋ฅผ ์„ค์ •ํ•ฉ๋‹ˆ๋‹ค.
    • โ€˜add(int value)โ€™ : ๋ฐฐ์—ด์˜ ๋งˆ์ง€๋ง‰์— ์š”์†Œ๋ฅผ ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.
    • โ€˜remove(int index)โ€™ : ํŠน์ • ์ธ๋ฑ์Šค์˜ ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ•˜๊ณ , ์ดํ›„์˜ ์š”์†Œ๋“ค์„ ์•ž์œผ๋กœ ์ด๋™์‹œํ‚ต๋‹ˆ๋‹ค.
    • โ€˜print()โ€™ : ๋ฐฐ์—ด์˜ ๋ชจ๋“  ์š”์†Œ๋ฅผ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.