알고리즘과 자료구조 특강(24.04.25)

---

알고리즘

알고리즘이란?

작업을 수행하기위해 입력을 받아 원하는 출력을 받는 것을 뜻한다.

왜 필요한거지?

정확하고 효율적으로 결과값을 얻기 위해서!

활용 예시

• 탐색 알고리즘
  • 포털 사이트의 검색 기능
  • 데이터베이스의 조회 쿼리
• 정렬 알고리즘
  • 데이터 정렬
  • 운영 체제의 메모리 관리
• 최단 경로 알고리즘
  • 가장 빠른 길찾기

이 처럼 효율적인 결과값을 얻기 위해 위와 같은 알고리즘이 쓰인다~ 라고 생각하면 된다!

자료구조

자료구조란?

자료구조 포스트를 통해서는 자료구조란 무엇인가에 대한 정의를 했었고 그에 대한 종류인 배열과 컬렉션에 대한 설명을 했었다.
다시한번 정리하자면
자료구조란 데이터 값의 모임, 데이터간의 관계, 데이터에 적용할 수 있는 함수나 명령을 의미한다.
이 자료구조를 어떤 것을 사용하냐에 따라 효율적인 알고리즘 사용이 가능해진다.

자료구조의 필요성

• 데이터를 효율적으로 저장하고 검색 가능하게 하여 시간을 줄이고 성능을 향상시키기 위해
• 데이터를 논리적으로 구성하여 이해하고 접근하기 쉽게 만들기 위해
• 데이터의 추상화
• 재사용성이 높아 개발시간, 노력을 절약
• 알고리즘 최적화

형태

• 배열과 리스트, 큐, 셋, 맵에 대해서는 이전포스트인 배열과 컬렉션을 보면 알테지만 이외의 것들도 설명해주셔서 이외의 것들만 설명해보려한다.

해시 테이블(Hash table)

해시 함수를 사용한다.
해시함수가 키를 입력받고 그 키에 알맞는 인덱스를 알려줘 키와 인덱스를 빠르게 매핑해주는 자료구조 형태이다.

그래프

각 노드들이 그물망처럼 간선으로 연결된 자료구조이다.

여기서 잠깐!

노드에 대해서 알아보자
자료구조들을 정의하기위해 사용된 개념(데이터타입)을 말하며,
각 노드는 데이터 와 다른 노드를 참조할 공간으로 정의 되어있다.

트리

• 말 그대로 나무에서 나뭇가지가 뻗어나가는 형태로 이루어진 자료구조이다.
• 각 노드가 부모-자식 관계처럼 간선으로 연결되어있고,
  가장 상단에 있는 노드는 root노드 가장 하단에 아무런 자식을 가지고있지않은 노드는 leaf노드라고 부른다.
• 같은 부모를 가진 노드들은 형제(siblings) 관계라고 하며, 트리의 노드는 또다른 작은 형태의 트리인 서브트리를 가질 수 있다.
  
  (출처 - https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/)

  ALT

노드를 이용해 stack을 구현해보자!

강사님께서 예시로 노드를이용해 stack 구현하는 것을 보여주셨다.
우선 stack이란 바구니에 담고 빼는 것으로 나중에 들어간것이 처음으로 나오는 자료구조이다.
아래 3가지 클래스를 만들 예정이다.
Node.java , StackNode.java, Main.java

1. 노드는 위에서 말한대로 본인이 가지고있는 데이터, 그리고 다음 노드를 참조하는 공간으로 되어있다고 했으니 그에 맞게 코드를 짜주면 될것이다.

public class Node<T> {
  
  protected T data;
  protected Node<T> next;

  public Node() {
    this.data = null;
    this.next = null;
  }
}

2. 스택노드는 생각할 것이 좀 많다.

• 빈 스택인지 확인하는 메서드(isEmpty)
• 스택에 집어넣는 메서드(push)
• 꺼내는 메서드(pop)
• 조회만 하는 메서드(peek)
• 이렇게만 해도 되지만 전체 스택을 돌아가며 top부터 순서대로 출력하는 메서드도 추가할 것이다.

public class StackNode<T> {

  private Node<T> top;

  private boolean isEmpty() {
  //스택이 비어있는지 확인
    return this.top == null;
  }

  public void push(T data) {
  //스택에 집어넣기
    Node<T> newNode = new Node<>();
    //새 노드를 만들어서
    newNode.data = data;
    newNode.next = this.top;
    //스택에 값을 집어넣고 다음 주소값을 현재 top의 next로 지정
    this.top = newNode;
    //그리고 현재 top의 주소값을 새노드로 바꾼다.
  }

  public T pop() {
  //스택에서 꺼내기
    if (this.isEmpty()) {
      return null;
      //비어있으면 null return
    }

    T data = this.top.data;
 //data변수에 현재 top의 데이터만을 넣어 초기화시킨다.
    this.top = this.top.next;
//값이 있다면 현재 top의 값을 next의 값으로 바꾼다.
    return data;
  }

  public T peek() {
  //조회만하기(삭제X)
    if (isEmpty()) {
      return null;
    }

    return this.top.data;
    //현재 top의 data만을 return
  }

  public void print() {
    System.out.println("\n현재 스택의 내용을 top부터 출력합니다.");

    if (this.isEmpty()) {
      System.out.println("스택이 비어 있습니다.");
    } else {
      Node<T> currentNode; //현재노드 변수 선언
      currentNode = this.top; //현재노드를 지금 스택의 top으로 초기화

      while (currentNode != null) {
      //반복문을 통해 현재 노드가 null값이 아니면 실행한다.
        System.out.print("[ " + currentNode.data + " ]  ");
        currentNode = currentNode.next;
      }
    }
    System.out.println("\n");
  }
}

3. Main은 각각의 메서드가 잘 작동되는지 점검하는 클래스라고 보면된다.

• push, pop, peek, print

package exercise1;

public class Main {

  public static void main(String[] args){
    StackNode<Integer> stack = new StackNode<>();
    stack.push(1);
    stack.push(3);
    stack.push(7);
    stack.push(5);
    stack.push(2);
    stack.push(10);
    
    stack.print(); // 10, 2, 5, 7, 3, 1 순으로 출력

    System.out.println("현재 스택의 top을 출력합니다: " + stack.peek() + "\n"); //10출력

    System.out.println("pop: "+stack.pop()); // 10
    System.out.println("pop: "+stack.pop()); // 2
    System.out.println("pop: "+stack.pop()); // 5

    stack.print(); // 7, 3, 1 순으로 출력

    System.out.println("pop: "+stack.pop()); // 7
    System.out.println("pop: "+stack.pop());//  3
    System.out.println("pop: "+stack.pop()); // 1

    stack.print(); // 스택이 비어 있습니다.
  }
}

이렇게 완성! 할 수 있다!