[2023.07.24] 자료구조 / 알고리즘

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

 

 

1. 알고리즘?

•  알고리즘의 정의는 문제를 해결하는 절차나 방법을 설명하는 과정이다.
• 좋은 알고리즘은 말 그대로 성능이 좋아야 하며 점근 표기법으로 효율성을 평가할 수 있다.
  • Big-O 표기법
    • 최악의 성능 → 연산량 계산
    • 표기법 → O(N)
  • Big-Ω 표기법이 있다.
    • 최선의 성능 → 연산량 계산
    • 표기법 → Ω(1)
• 알고리즘의 성능은 입력값에 따라 달라질 수 있다.
  • 입력값이 최선의 경우일 가능성이 적기 때문에 대부분 최악의 경우를 대비하여 Big-O 표기법으로 분석한다.
• 시간복잡도
  • 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계
• 공간복잡도
  • 입력값과 문제를 해결하는데 걸리는 공관과의 상관관계
  • 사용되는 메모리

 

2. 자료구조 (Stack & Queue)

public class Main {
    public static void main(String[] args) throws IOException {
        Stack<Integer> stack = new Stack<>();
        stack.push(3); // 값 집어 넣기
        stack.push(1);
        stack.push(3);
        stack.push(5);

        System.out.println("stack : " + stack); // 

        stack.pop(); // 값 꺼내기
        System.out.println("stack.pop() : " + stack);


        Queue<Integer> queue = new LinkedList<>();
        queue.add(3); // 값 집어 넣기
        queue.add(1);
        queue.add(3);
        queue.add(5);

        System.out.println("queue : " + queue);
        queue.poll(); // 값 꺼내기

        System.out.println("queue.poll() : " + queue);

 

코드의 결과

스택을 선언하고 값을 집어 넣은 다음 pop을 했을 때 나중에 들어간 값이 먼저 제거됨을 확인했다.

큐를 선언하고 값을 집어 넣고 poll을 했을 때 먼저 들어간 값이 먼저 제거됨을 확인했다.