[알고리즘] 알고리즘 뽀개기(1) : 자료구조

알고리즘 뽀개기 Step 1 : 자료구조

알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :)

추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다.

스택

스택 (Stack)은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다.

• 마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out (LIFO)라고도 한다.
• 연산
  • push, pop, top(가장 위의 자료를 보는 연산), empty(비어있는지 아닌지 확인하는 연산), size(저장된 자료의 개수를 반환하는 연산)
• 문제 추천
  • 괄호 : https://www.acmicpc.net/problem/9012

큐

큐 (Queue)는 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있도록 하는 자료구조이다.

• 먼저 넣은 것이 먼저 나오기 때문에, First In First Out (FIFO)라고도 한다.
• 연산
  • push, pop, front(가장 앞의 자료를 보는 연산), back(가장 뒤에 있는 자료를 보는 연산), empty(비어있는지 아닌지 확인하는 연산), size(저장된 자료의 개수를 반환하는 연산)
• 문제 추천
  • 조세퍼스 문제(풀이 있음) : https://www.acmicpc.net/problem/1158

덱

덱(Deque)은 양 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다.

• Double-ended queue의 약자이다.
• 연산
  • push_front(덱의 앞에 자료를 넣는 연산), push_back(덱의 뒤에 자료를 넣는 연산), pop_front(덱의 앞에서 자료를 빼는 연산), pop_back(덱의 뒤에서 자료를 빼는 연산), front, back, empty, size
• 문제 추천
  • 덱 : https://www.acmicpc.net/problem/10866

복습 문제

조세퍼스 문제 (1158)

• https://www.acmicpc.net/problem/1158

코틀린에서의 큐

• 코틀린에서는 기본 라이브러리로 큐/스택을 제공하지 않는다. 따라서, 자바의 큐/스택을 사용해야하므로 java.util.*을 import 하도록 한다.
• ArrayList 만으로도 큐/스택의 성질을 구현할 수 있다.
• 참고 링크 : https://hanyeop.tistory.com/115

코드

import java.util.*

fun main(){
    val scr = Scanner(System.`in`)
    val N = scr.nextInt()
    val K = scr.nextInt()

    val queue = LinkedList<Int>()
    for (i in 1..N) {
        queue.add(i)
    }

    var resultString = "<"
    var sequence : Int = 1
    while (queue.isNotEmpty()) {
        val element = queue.poll()
        if (sequence == K) {
            sequence = 1
            resultString += ("$element, ")
        } else {
            sequence++
            queue.add(element)
        }
    }

    print("${resultString.substring(0, resultString.length-2)}>")
}