Algorithm Study #2 (Data Structure-1.2)

큐 (Queue)

• 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조
• 먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out (FIFO) 라고도 한다.
• 큐의 주요 메소드
  - push
  - 큐에 자료를 넣는 연산
  • pop
    • 큐에서 자료를 빼는 연산
  • front
    • 큐의 가장 앞에 있는 자료를 보는 연산
  • back
    • 큐의 가장 뒤에 있는 자료를 보는 연산
  • empty
    • 큐가 비어있는지 아닌지를 알아보는 연산
  • size
    • 큐에 저장되어 있는 자료의 개수를 알아보는 연산

큐를 직접 구현하는 경우

• 배열을 이용하여 구현 가능
  - 시작하는 index인 begin, 마지막 index인 end가 필요하다.
  • push 연산은 end번째 index에 자료를 넣는 것을 의미한다.
    • queue[end++] = 자료;
  • pop 연산은 begin 인덱스에 있는 값을 리턴하고 begin 인덱스를 하나 증가시키면 된다.
    • return queue[begin++];
  • size 연산은 end에서 begin을 빼면 된다.
    • return end - begin;
  • isEmpty 연산은 end == begin인지 체크하면 된다.

큐의 예제

• 조세퍼스 문제 boj.kr/1158
  - 1번부터 N번까지 N명의 사람들이 원을 이루면서 앉아있고, 양의 정수 M(<=N)이 주어진다.

  • 순서대로 M번째 사람을 제거한다.

  • 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속한다.

  • 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.

  • 원에서 사람들이 제거되는 순서를 (N,M) - 조세퍼스 순열이라고 한다.

    • 아이디어 1
      - 큐를 이용한 문제 해결
      1. 지나친 사람은 언젠가 다시 만나야 한다.
      2. 매 3번째 사람은 제거되며 다신 만날 일이 없다.
      3. 큐의 처음에서 사람을 만날 때 마다 다시 만날 가정을 하고 맨 끝으로 넣으면 된다.
      - 구현

          ```java
      				import java.io.BufferedReader;
          import java.io.IOException;
          import java.io.InputStreamReader;
          import java.util.Queue;
          import java.util.StringTokenizer;
          import java.util.concurrent.ArrayBlockingQueue;
      
          public class Main{
              public static void main(String args[]) throws IOException {
                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                  StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                  int n = Integer.parseInt(st.nextToken());
                  int m = Integer.parseInt(st.nextToken());
                  Queue<Integer> in_q = new ArrayBlockingQueue<>(n);
      
                  for(int i=1; i<=n; i++)
                      in_q.add(i);
      
                  StringBuffer sb = new StringBuffer();
      
                  while(!in_q.isEmpty())
                      for(int i=0; i<m; i++)
                          if(!(i==(m-1)))
                              in_q.add(in_q.poll());
                          else
                              sb.append(in_q.poll() + ", ");
      
                  System.out.println("<" + sb.toString().substring(0, sb.length()-2) + ">");
              }
          }
      				```
      - ArrayList를 이용한 문제 해결
      	1. 한 사람을 제거하고 난 뒤에 지나친 사람을 만나야 한다는 특성을 이용
          	1. 1 Mod(%) 연산을 이용하여 해당 특성을 구현 가능하다.
          2. ArrayList로 인덱스의 처음 위치부터 이동 위치를 기록한다.
          3. m-1만큼 이동하고 해당 원소를 삭제한다. 
          4. size가 전부 줄어들 때까지 반복한다.
      	- 구현
          ```java
      				import java.io.BufferedReader;
          import java.io.IOException;
          import java.io.InputStreamReader;
          import java.util.*;
          
          public class Main{
              public static void main(String args[]) throws IOException {
                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                  StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                  int n = Integer.parseInt(st.nextToken());
                  int m = Integer.parseInt(st.nextToken());
                  List<Integer> ll = new ArrayList<>();
          
                  for(int i=1; i<=n; i++)
                      ll.add(i);
          
                  StringBuffer sb = new StringBuffer();
                  sb.append("<");
                  int cursor = 0;
          
                  while(!ll.isEmpty()) {
                      cursor = (cursor + (m-1)) % n;
          
                      if(ll.size() != 1)
                          sb.append(ll.get(cursor) + ", ");
                      else
                          sb.append(ll.get(cursor) + ">");
          
                      ll.remove(cursor);
                      n--;
                  }
          
                  System.out.println(sb.toString());
              }
          }
          ```
          

덱 (Deque)

• Double-ended queue의 약자
• 양쪽 끝에서 자료를 넣고 양쪽 끝에서 자료를 뺄 수 있는 구조
• 주요 메소드
  - push_front
  - 덱의 앞에 자료를 넣는 연산
  • push_back
    • 덱의 뒤에 자료를 넣는 연산
  • pop_front
    • 덱의 앞에서 자료를 빼는 연산
  • pop_back
    • 덱의 뒤에서 자료를 빼는 연산
  • front
    • 덱의 가장 앞에 있는 자료를 보는 연산
  • back
    • 덱의 가장 뒤에 있는 자료를 보는 연산

문자열

• 아스키코드 (ASC II)
  - 문자 인코딩 방법
  • 대표적인 아스키 코드
    • '0', 48
      • 'A', 65
      • 'a', 97
      • NULL, 0
  • 숫자가 저장되어 있는데, 출력만 글자로 해주는 것으로 이해하면 편하다.
• 예제 문제
  - boj.kr/2743