Home > Algorithm > 2024 > ๐Ÿ“ฆ[DS,Algorithm] Java์˜ ๋ฐฐ์—ด.

๐Ÿ“ฆ[DS,Algorithm] Java์˜ ๋ฐฐ์—ด.
DataStructure Algorithm

1๏ธโƒฃ Java์˜ ๋ฐฐ์—ด.

1๏ธโƒฃ ๋ฐฐ์—ด์ด๋ž€ ๋ฌด์—‡์ธ๊ฐ€?

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

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

2๏ธโƒฃ ๋ฐฐ์—ด์˜ ์„ ์–ธ๊ณผ ์ดˆ๊ธฐํ™”.

Java์—์„œ ๋ฐฐ์—ด์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์„ ์–ธํ•˜๊ณ  ์ดˆ๊ธฐํ™”ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

int[] array = new int[5]; // ํฌ๊ธฐ๊ฐ€ 5์ธ ์ •์ˆ˜ํ˜• ๋ฐฐ์—ด ์„ ์–ธ.
int[] array = {10, 20, 30, 40, 50}; // ์ดˆ๊ธฐํ™”์™€ ๋™์‹œ์— ๋ฐฐ์—ด ์„ ์–ธ

3๏ธโƒฃ ๋ฐฐ์—ด์˜ ์š”์†Œ์™€ ์ ‘๊ทผ.

๋ฐฐ์—ด์˜ ๊ฐ ์š”์†Œ๋Š” ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•ด ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ธ๋ฑ์Šค๋Š” 0๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.

int firstElement = array[0]; // element = 10, ์ฒซ ๋ฒˆ์งธ ์š”์†Œ์— ์ ‘๊ทผ
array[1] = 25; // [10, 25, 30, 40, 50], ๋‘ ๋ฒˆ์งธ ์š”์†Œ์— ๊ฐ’ 25๋ฅผ ์ €์žฅ

4๏ธโƒฃ ๋ฐฐ์—ด์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„.

๋ฐฐ์—ด์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ์—ฐ์‚ฐ์˜ ์ข…๋ฅ˜์— ๋”ฐ๋ผ ๋‹ค๋ฆ…๋‹ˆ๋‹ค.

์•„๋ž˜๋Š” ์ผ๋ฐ˜์ ์ธ ๋ฐฐ์—ด ์—ฐ์‚ฐ๊ณผ ๊ทธ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์„ค๋ช…ํ•œ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

1. ์ ‘๊ทผ(Access)

  • ํŠน์ • ์ธ๋ฑ์Šค์˜ ์š”์†Œ์— ์ ‘๊ทผํ•˜๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(1)์ž…๋‹ˆ๋‹ค.
    • ์ด์œ  : ๋ฐฐ์—ด์€ ์—ฐ์†๋œ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์— ์ €์žฅ๋˜๋ฏ€๋กœ ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•ด ๋ฐ”๋กœ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
// ์ ‘๊ทผ(Access)
int element = array[2]; 
// element = 30,  time complexity = O(1)
// [10, 25, 30, 40, 50]

2. ํƒ์ƒ‰(Search)

  • ๋ฐฐ์—ด์—์„œ ํŠน์ • ๊ฐ’์„ ์ฐพ๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(n)์ž…๋‹ˆ๋‹ค.
    • ์ด์œ : ์ตœ์•…์˜ ๊ฒฝ์šฐ ๋ฐฐ์—ด์˜ ๋ชจ๋“  ์š”์†Œ๋ฅผ ๊ฒ€์‚ฌํ•ด์•ผ ํ•  ์ˆ˜๋„ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
boolean found = false;
int target = 30;

for (int i = 0; i < array.length; i++) {
    if (array[i] == target) { // i = 2, array[i] = 30
        found = true;
        break;
    }
}
// [10, 25, 30, 40, 50]

3. ์‚ฝ์ž…(Insertion)

  • ๋ฐฐ์—ด์˜ ๋์— ์š”์†Œ๋ฅผ ์ถ”๊ฐ€ํ•˜๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(1)์ž…๋‹ˆ๋‹ค.
  • ๋ฐฐ์—ด์˜ ํŠน์ • ์œ„์น˜์— ์š”์†Œ๋ฅผ ์‚ฝ์ž…ํ•˜๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(n)์ž…๋‹ˆ๋‹ค.
    • ์ด์œ : ํŠน์ • ์œ„์น˜์— ์‚ฝ์ž…ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ํ•ด๋‹น ์œ„์น˜ ์ดํ›„์˜ ๋ชจ๋“  ์š”์†Œ๋ฅผ ํ•œ ์นธ์”ฉ ๋’ค๋กœ ๋ฐ€์–ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
// ์‚ฝ์ž…(Insertion)

// ๋ฐฐ์—ด ์‚ฝ์ž…์‹œ index๊ฐ€ array.length๊ฐ€ ์•„๋‹ˆ๊ณ  array.length - 1์ธ ์ด์œ ๋Š”
// array.length๋Š” ๋ฐฐ์—ด์˜ ํฌ๊ธฐ, ์ฆ‰ 5๋ฅผ ๋‚˜ํƒ€๋‚ด๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
// index๋Š” 0๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๊ฐ€ 5์ธ ๋ฐฐ์—ด์˜ ๋ index๋Š” 4์ž…๋‹ˆ๋‹ค.
// ๋•Œ๋ฌธ์— array.length - 1์„ ํ•ด์ค๋‹ˆ๋‹ค.

array[array.length - 1] = 60; // ๋ฐฐ์—ด ๋์— ์‚ฝ์ž… (O(1)), [10, 25, 30, 40, 60]

// ๋ฐฐ์—ด ์ค‘๊ฐ„์— ์‚ฝ์ž…ํ•˜๋Š” ๋ฉ”์„œ๋“œ
public static void insertion(int[] array, int index, int insertValue) {
  // ๋ฐฐ์—ด ์ค‘๊ฐ„์— ์‚ฝ์ž…(O(n))
  for (int i = array.length - 1; i > index; i--) {
    array[i] = array[i - 1];
  }
  array[index] = insertValue;
  System.out.println(Arrays.toString(array));
}

4. ์‚ญ์ œ(Deletion)

  • ๋ฐฐ์—ด์˜ ๋์—์„œ ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ•˜๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(1)์ž…๋‹ˆ๋‹ค.
  • ๋ฐฐ์—ด์˜ ํŠน์ • ์œ„์น˜์˜ ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ•˜๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(n)์ž…๋‹ˆ๋‹ค.
    • ์ด์œ : ํŠน์ • ์œ„์น˜์˜ ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ•œ ํ›„์—๋Š” ํ•ด๋‹น ์œ„์น˜ ์ดํ›„์˜ ๋ชจ๋“  ์š”์†Œ๋ฅผ ํ•œ ์นธ์”ฉ ์•ž์œผ๋กœ ๋‹น๊ฒจ์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
// ์‚ญ์ œ(Deletion)
    array[array.length - 1] = 0; // ๋ฐฐ์—ด์˜ ๋์—์„œ ์‚ญ์ œ ((O(1)), [10, 25, 30, 77, 0]
    System.out.println(Arrays.toString(array));

    // ๋ฐฐ์—ด ์ค‘๊ฐ„์—์„œ ์‚ญ์ œํ•˜๋Š” ๋ฉ”์„œ๋“œ
    int deletionValue = deletion(array, 2);
    System.out.println(deletionValue); // 30

// ๋ฐฐ์—ด ์ค‘๊ฐ„์— ์‚ญ์ œํ•˜๋Š” ๋ฉ”์„œ๋“œ
  public static int deletion(int[] array, int index) {
    // ๋ฐฐ์—ด ์ค‘๊ฐ„์— ์‚ญ์ œ(O(n))
    int[] returnValue = new int[array.length];

    for (int i = index, j = 0; i < array.length - 1 ; i++) {
      returnValue[j] = array[i];
      j++;
      array[i] = array[i + 1];

    }
    array[array.length - 1] = 0; // ๋งˆ์ง€๋ง‰ ์š”์†Œ ์ดˆ๊ธฐํ™”.
    int deletionValue = returnValue[0]; // ๋ฐฐ์—ด์„ ๋ฉ”๋ชจ๋ฆฌ์—์„œ ์ง€์šฐ๊ธฐ
    returnValue = null;
    return deletionValue;
  }

5๏ธโƒฃ ๋ฐฐ์—ด์˜ ์žฅ์ ๊ณผ ๋‹จ์ .

์žฅ์ .

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

๋‹จ์ .

  • ๊ณ ์ •๋œ ํฌ๊ธฐ : ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๋Š” ์„ ์–ธ ์‹œ์— ๊ณ ์ •๋˜๋ฏ€๋กœ, ์‹คํ–‰ ์ค‘์— ํฌ๊ธฐ๋ฅผ ๋ณ€๊ฒฝํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.
  • ์‚ฝ์ž… ๋ฐ ์‚ญ์ œ์˜ ๋น„ํšจ์œจ์„ฑ : ๋ฐฐ์—ด ์ค‘๊ฐ„์— ์š”์†Œ๋ฅผ ์‚ฝ์ž…ํ•˜๊ฑฐ๋‚˜ ์‚ญ์ œํ•  ๋•Œ O(n)์˜ ์‹œ๊ฐ„์ด ์†Œ์š”๋ฉ๋‹ˆ๋‹ค.
  • ์—ฐ์†๋œ ๋ฉ”๋ชจ๋ฆฌ ํ• ๋‹น ํ•„์š” : ํฐ ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•  ๋–„๋Š” ์—ฐ์†๋œ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์ด ํ•„์š”ํ•˜์—ฌ ๋ฉ”๋ชจ๋ฆฌ ํ• ๋‹น์— ์ œํ•œ์ด ์žˆ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

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