Algorithm Study #2 (Data Structure-1.2)

jakeseo_me·2019년 2월 14일
1

java algorithm study

목록 보기
7/18

큐 (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. 큐의 처음에서 사람을 만날 때 마다 다시 만날 가정을 하고 맨 끝으로 넣으면 된다.
        - 구현

덱 (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
profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다.

0개의 댓글