2. 자료구조 / 알고리즘 - 코드

1. 배열 (Array)

void main() {
  // 배열 생성 및 초기화
  List<int> numbers = [1, 2, 3, 4, 5];

  // 특정 요소 접근
  print(numbers[2]); // 출력: 3

  // 배열 길이
  print(numbers.length); // 출력: 5

  // 배열의 요소 추가
  numbers.add(6);
  print(numbers); // 출력: [1, 2, 3, 4, 5, 6]
}

2. 연결 리스트 (Linked List)

class Node {
  int data;
  Node? next;

  Node(this.data);
}

class LinkedList {
  Node? head;

  void append(int data) {
    if (head == null) {
      head = Node(data);
    } else {
      Node current = head!;
      while (current.next != null) {
        current = current.next!;
      }
      current.next = Node(data);
    }
  }

  void display() {
    Node? current = head;
    while (current != null) {
      print(current.data);
      current = current.next;
    }
  }
}

void main() {
  LinkedList list = LinkedList();
  list.append(1);
  list.append(2);
  list.append(3);
  list.display(); // 출력: 1 2 3
}

3. 스택 (Stack)

class Stack<T> {
  List<T> _stack = [];

  void push(T value) => _stack.add(value);

  T pop() => _stack.removeLast();

  T get top => _stack.last;

  bool get isEmpty => _stack.isEmpty;
}

void main() {
  Stack<int> stack = Stack<int>();

  stack.push(10);
  stack.push(20);
  print(stack.top); // 출력: 20

  stack.pop();
  print(stack.top); // 출력: 10
}

4. 큐 (Queue)

import 'dart:collection';

void main() {
  Queue<int> queue = Queue<int>();

  // 요소 추가
  queue.add(1);
  queue.add(2);
  queue.add(3);

  print(queue.removeFirst()); // 출력: 1
  print(queue); // 출력: {2, 3}
}

5. 이진 탐색 트리 (Binary Search Tree)

class TreeNode {
  int data;
  TreeNode? left, right;

  TreeNode(this.data);
}

class BinarySearchTree {
  TreeNode? root;

  void insert(int value) {
    root = _insertRec(root, value);
  }

  TreeNode _insertRec(TreeNode? node, int value) {
    if (node == null) return TreeNode(value);
    if (value < node.data) node.left = _insertRec(node.left, value);
    else if (value > node.data) node.right = _insertRec(node.right, value);
    return node;
  }

  void inorder() {
    _inorderRec(root);
  }

  void _inorderRec(TreeNode? node) {
    if (node != null) {
      _inorderRec(node.left);
      print(node.data);
      _inorderRec(node.right);
    }
  }
}

void main() {
  BinarySearchTree bst = BinarySearchTree();

  bst.insert(50);
  bst.insert(30);
  bst.insert(70);
  bst.insert(20);
  bst.insert(40);
  bst.insert(60);
  bst.insert(80);

  bst.inorder(); // 출력: 20 30 40 50 60 70 80
}

6. 정렬 알고리즘 - 버블 정렬 (Bubble Sort)

void bubbleSort(List<int> list) {
  for (int i = 0; i < list.length - 1; i++) {
    for (int j = 0; j < list.length - 1 - i; j++) {
      if (list[j] > list[j + 1]) {
        int temp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = temp;
      }
    }
  }
}

void main() {
  List<int> numbers = [64, 34, 25, 12, 22, 11, 90];

  bubbleSort(numbers);
  print(numbers); // 출력: [11, 12, 22, 25, 34, 64, 90]
}

7. 탐색 알고리즘 - 이진 탐색 (Binary Search)

이진 탐색은 데이터가 정렬된 상태에서만 사용됩니다.

int binarySearch(List<int> list, int target) {
  int left = 0;
  int right = list.length - 1;

  while (left <= right) {
    int mid = (left + right) ~/ 2;

    if (list[mid] == target) {
      return mid;
    } else if (list[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1; // 찾지 못한 경우
}

void main() {
  List<int> sortedList = [1, 3, 5, 7, 9, 11];

  int result = binarySearch(sortedList, 7);
  print(result); // 출력: 3
}

그럼 주요 자료구조와 알고리즘에 대한 예시 코드를 각각 간단하게 보여드릴게요.

1. 배열 (Array)

void main() {
  // 배열 생성 및 초기화
  List<int> numbers = [1, 2, 3, 4, 5];

  // 특정 요소 접근
  print(numbers[2]); // 출력: 3

  // 배열 길이
  print(numbers.length); // 출력: 5

  // 배열의 요소 추가
  numbers.add(6);
  print(numbers); // 출력: [1, 2, 3, 4, 5, 6]
}

2. 연결 리스트 (Linked List)

Dart에는 기본 연결 리스트가 없으므로, 간단한 연결 리스트를 구현해보겠습니다.

class Node {
  int data;
  Node? next;

  Node(this.data);
}

class LinkedList {
  Node? head;

  void append(int data) {
    if (head == null) {
      head = Node(data);
    } else {
      Node current = head!;
      while (current.next != null) {
        current = current.next!;
      }
      current.next = Node(data);
    }
  }

  void display() {
    Node? current = head;
    while (current != null) {
      print(current.data);
      current = current.next;
    }
  }
}

void main() {
  LinkedList list = LinkedList();
  list.append(1);
  list.append(2);
  list.append(3);
  list.display(); // 출력: 1 2 3
}

3. 스택 (Stack)

class Stack<T> {
  List<T> _stack = [];

  void push(T value) => _stack.add(value);

  T pop() => _stack.removeLast();

  T get top => _stack.last;

  bool get isEmpty => _stack.isEmpty;
}

void main() {
  Stack<int> stack = Stack<int>();

  stack.push(10);
  stack.push(20);
  print(stack.top); // 출력: 20

  stack.pop();
  print(stack.top); // 출력: 10
}

4. 큐 (Queue)

import 'dart:collection';

void main() {
  Queue<int> queue = Queue<int>();

  // 요소 추가
  queue.add(1);
  queue.add(2);
  queue.add(3);

  print(queue.removeFirst()); // 출력: 1
  print(queue); // 출력: {2, 3}
}

5. 이진 탐색 트리 (Binary Search Tree)

class TreeNode {
  int data;
  TreeNode? left, right;

  TreeNode(this.data);
}

class BinarySearchTree {
  TreeNode? root;

  void insert(int value) {
    root = _insertRec(root, value);
  }

  TreeNode _insertRec(TreeNode? node, int value) {
    if (node == null) return TreeNode(value);
    if (value < node.data) node.left = _insertRec(node.left, value);
    else if (value > node.data) node.right = _insertRec(node.right, value);
    return node;
  }

  void inorder() {
    _inorderRec(root);
  }

  void _inorderRec(TreeNode? node) {
    if (node != null) {
      _inorderRec(node.left);
      print(node.data);
      _inorderRec(node.right);
    }
  }
}

void main() {
  BinarySearchTree bst = BinarySearchTree();

  bst.insert(50);
  bst.insert(30);
  bst.insert(70);
  bst.insert(20);
  bst.insert(40);
  bst.insert(60);
  bst.insert(80);

  bst.inorder(); // 출력: 20 30 40 50 60 70 80
}

6. 정렬 알고리즘 - 버블 정렬 (Bubble Sort)

void bubbleSort(List<int> list) {
  for (int i = 0; i < list.length - 1; i++) {
    for (int j = 0; j < list.length - 1 - i; j++) {
      if (list[j] > list[j + 1]) {
        int temp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = temp;
      }
    }
  }
}

void main() {
  List<int> numbers = [64, 34, 25, 12, 22, 11, 90];

  bubbleSort(numbers);
  print(numbers); // 출력: [11, 12, 22, 25, 34, 64, 90]
}

7. 탐색 알고리즘 - 이진 탐색 (Binary Search)

이진 탐색은 데이터가 정렬된 상태에서만 사용됩니다.

int binarySearch(List<int> list, int target) {
  int left = 0;
  int right = list.length - 1;

  while (left <= right) {
    int mid = (left + right) ~/ 2;

    if (list[mid] == target) {
      return mid;
    } else if (list[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1; // 찾지 못한 경우
}

void main() {
  List<int> sortedList = [1, 3, 5, 7, 9, 11];

  int result = binarySearch(sortedList, 7);
  print(result); // 출력: 3
}

요약

배열은 인덱스로 접근이 빠르지만 크기가 고정됨.
연결 리스트는 삽입/삭제가 쉽지만, 특정 위치 접근이 느림.
스택은 후입선출, 큐는 선입선출.
이진 탐색 트리는 정렬된 데이터의 삽입/검색에 효율적임.
버블 정렬은 가장 간단한 정렬, 이진 탐색은 정렬된 데이터에서 빠르게 값을 찾음.

저작자표시 비영리 동일조건 (새창열림)

'CS > 짤막지식' 카테고리의 다른 글

WebRTC with ChatGPT (2)	2024.10.02
restful API vs websocket (0)	2024.09.25
2. webRTC의 SDP, ICE, 시그널링에 대해서 (0)	2024.09.20
1. webRTC 기초 정리 (0)	2024.09.19
변수 쓸 때 숫자는 Int, Double로 다양하게 받으면서, 왜 문자는 String으로 퉁치죠? (0)	2024.07.30

1. 배열 (Array)

2. 연결 리스트 (Linked List)

3. 스택 (Stack)

4. 큐 (Queue)

5. 이진 탐색 트리 (Binary Search Tree)

6. 정렬 알고리즘 - 버블 정렬 (Bubble Sort)

7. 탐색 알고리즘 - 이진 탐색 (Binary Search)

1. 배열 (Array)

2. 연결 리스트 (Linked List)

3. 스택 (Stack)

4. 큐 (Queue)

5. 이진 탐색 트리 (Binary Search Tree)

6. 정렬 알고리즘 - 버블 정렬 (Bubble Sort)

7. 탐색 알고리즘 - 이진 탐색 (Binary Search)

요약

'CS > 짤막지식' 카테고리의 다른 글

티스토리툴바