배열과 리스트

배열

• 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조

배열의 특징

• 인덱스를 사용하여 값에 바로 접근할 수 있다.
• 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.
• 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
• 구조가 간단하므로 코딩 테스트에서 많이 사용

리스트

• 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조

리스트의 특징

• 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. 다시 말해 값에 접근하는 속도가 느리다.
• 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.
• 선언할 때 크기를 별도로 지정하지 않아도 된다. 다시 말해 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.
• 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.

구간 합

• 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

합배열 S 정의

S[i] = A[0] + A[1] + ... + A[i-1] + A[i]

합 배열 S를 만드는 공식

S[i] = S[i-1] + A[i];

구간 합을 구하는 공식

S[j] - S[i-1] // i에서 j까지 구간 합

투 포인터

• 2개의 포인터로 알고리즘의 시간 복잡도를 최적화

슬라이딩 윈도우

• 2개의 포인터로 범위를 지정한 다음 범위(Window)를 유지한 채로 이동(Sliding)하며 문제를 해결

스택, 큐

• Stack 클래스의 주요 메서드는 push, pop, peek, isEmpty 등이 있다.

• push 메서드는 스택의 맨 위에 새로운 요소를 추가한다.

• pop 메서드는 스택의 맨 위에서 요소를 제거하고 반환한다.

• peek 메서드는 스택의 맨 위에서 요소를 제거하지 않고 반환한다.

• isEmpty 메서드는 스택이 비어 있는지 여부를 확인한다.

• Queue 클래스의 주요 메서드는 add, poll, peek, isEmpty 등이 있다.

• add 메서드는 지정된 요소를 큐에 추가한다.

• poll 메소드는 큐의 맨 앞에서 요소를 제거하고, 제거된 요소를 반환한다. - peek 메소드는 요소를 제거하지 않고 큐의 맨 앞 요소의 값을 읽어온다.

• isEmpty 메서드는 큐가 비어 있는지 여부를 확인한다.

우선순위 큐

• Java에서 우선순위 큐(PriorityQueue)는 Queue 인터페이스를 구현한 클래스 중 하나이다. 우선순위 큐는 일반적인 큐와 달리, 저장된 요소들이 우선순위에 따라 정렬되어 저장되는 자료구조이다.

• 우선순위 큐는 일반적으로 힙(heap)이라는 자료구조를 사용하여 구현된다. Java에서 PriorityQueue 클래스는 힙 기반으로 구현되어 있으며, 큐에 추가된 요소들은 힙 내부의 특정 위치에 저장된다. 이 때, 우선순위가 높은 요소는 힙의 루트에 위치하게 되고, 삭제될 때 먼저 제거된다.

• 우선순위 큐는 기본적으로 오름차순으로 정렬되며, 이외에도 Comparator 인터페이스를 구현하여 원하는 우선순위로 정렬할 수도 있다.

PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2) -> {
      int first_abs = Math.abs(o1);
      int second_abs = Math.abs(o2);
      if (first_abs == second_abs)
        return o1 > o2 ? 1 : -1;// 절대값이 같은 경우 음수 우선 정렬
      else
        return first_abs - second_abs;// 절대값을 기준으로 정렬
    });

위에서는 절댓값이 높은 순으로, 만약 절댓값이 같다면 음수를 우선 정렬하는 우선순위 큐이다.