꿈을 보는 개발자

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

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

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

기본 자료구조 복습을 위해 연계되어있는 상단의 세문제들을 풀어보았습니다. 이 과정에서 시간초과의 중요성을 알게 되었습니다. 

가장 처음 문제인 stack문제의 경우 시간을 크게 생각하지 않고 kotlin의 대표적은 collection중 비교적 느린 MutableList를 통해 구현하고 입출력도 kotlin Console I/O와 print 함수를 사용하였습니다. 아슬아슬하게 시간이 초과되지는 않았습니다. 

fun main() {
    val n = readLine()!!.toInt()
    val stack = mutableListOf<Int>()
    for (i in 1..n) {
        val command = readLine()!!.split(" ")
        when (command[0]) {
            "push" -> stack.add(command[1].toInt())
            "pop" -> if (stack.isEmpty()) println("-1") else {
                println(stack.last())
                stack.removeLast()
            }
            "size" -> println(stack.size)
            "empty" -> if (stack.isEmpty()) println("1") else println("0")
            "top" -> if (stack.isEmpty()) println("-1") else println(stack.last())
        }
    }
}

스택 문제를 풀때 처럼 시간을 고려하지 않았더니 시간초과가 나오게 되었습니다. 따라서 이번에는 O(n)의 시간복잡도를 가진 MutableList보다는 메모리 효율은 떨어지지만 시간복잡도는 O(1)인 LinkedList를 사용하였습니다. 그제서야 문제해결을 할 수 있었습니다.

import java.util.*

fun main() { 10845
    val n = readLine()!!.toInt()
    val queue = LinkedList<Int>()
    for (i in 1..n) {
        val command = readLine()!!.split(" ")
        when (command[0]) {
            "push" -> queue.add(command[1].toInt())
            "pop" -> if (queue.isEmpty()) println("-1") else {
                println(queue.first())
                queue.removeFirst()
            }
            "size" -> println(queue.size)
            "empty" -> if (queue.isEmpty()) println("1") else println("0")
            "front" -> if (queue.isEmpty()) println("-1") else println(queue.first())
            "back" -> if (queue.isEmpty()) println("-1") else println(queue.last())
        }
    }
}

마지막으로 덱 문제를 풀때도 역시 시간초과가 발생하였습니다. LinkedList를 통해서 시간초과를 해결하였으니 마지막으로는 입출력 부분에서의 시간낭비를 줄여야 했습니다. Kotlin Console I/O가 아닌 BufferedReader와 StringBuilder를 사용한 입출력을 통해서 성공 할 수 있었습니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.StringBuilder
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val n = readLine()!!.toInt()
    val deque = LinkedList<Int>()
    val sb = StringBuilder()
    for (i in 1..n) {
        val command = readLine()!!.split(" ")
        when (command[0]) {
            "push_front" -> deque.add(0, command[1].toInt())
            "push_back" -> deque.add(deque.lastIndex+1, command[1].toInt())
            "pop_front" -> if (deque.isEmpty()) sb.append("-1\n") else {
                sb.append("${deque.first()}\n")
                deque.removeFirst()
            }
            "pop_back" -> if (deque.isEmpty()) sb.append("-1\n") else {
                sb.append("${deque.last()}\n")
                deque.removeLast()
            }
            "size" -> sb.append("${deque.size}\n")
            "empty" -> if (deque.isEmpty()) sb.append("1\n") else sb.append("0\n")
            "front" -> if (deque.isEmpty()) sb.append("-1\n") else sb.append("${deque.first()}\n")
            "back" -> if (deque.isEmpty()) sb.append("-1\n") else sb.append("${deque.last()}\n")
        }
    }
    print(sb)
}

결론적으로는 StringBuilder부분에서의 시간효율이 많이 개선되었던 것 같지만 Kotlin 기본 Collection들에 대한 시간복잡도도 다시 한번 상기 할 수 있었습니다.

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

Dp 문제중 Bottom-Up방식을 사용해서 해결한 문제입니다.

Bottom-up 방식이므로 규칙중 가장 나중 규칙인 1로 빼는 계산부터 시작하여 각각 배열에 최대값을 저장해줍니다. 

이후 2로 나누는 경우 3으로 나누는 경우를 각각 생각하여 각 배열에 저장된 값중 최소값을 다시 배열에 저장해주면서 1로 만드는 계산을 해줍니다.

fun main() {
    val n = readLine()!!.toInt()
    val num = IntArray(n+1)
    num[1] = 0
    num[0] = 0
    for(i in 2..n){
        num[i] = num[i - 1] + 1
        if(i%2 == 0) num[i] = Math.min(num[i],num[i / 2] + 1)
        if(i%3 == 0) num[i] = Math.min(num[i],num[i / 3] + 1)
    }
    println(num[n])
}

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

처음 시도에서는 가장 보편적인 방법인 재귀를 통해서 문제풀이를 시도하였습니다. 하지만 시간초과의 결과가 나오게 되었습니다.

fun main() {
    val n = readLine()!!.toInt()
    fun fibo(n: Int): Int {
        if (n == 0) return 0
        if (n == 1) return 1
        return fibo(n - 1) + fibo(n - 2)
    }
    print(fibo(n))
}

따라서 재귀호출이 끝나고 현재 함수에서는 추가적인 연산을 하지 않게끔 해주어 마치 for loop와 동일한 효과를 발생하는 tailrec 키워드의 꼬리재귀를 사용하였습니다. 

fun main() {
    val n = readLine()!!.toInt()

    tailrec fun fibo(n: Int , pre:Int, next:Int): Int {
        if (n <= 0) return pre
        return fibo(n - 1, next, pre +next)
    }
    print(fibo(n,0,1))
}

매개변수로는 n-1 n-2 변수 대용으로 n-1 next와 이전에 계산한 합을 넘겨줍니다.

Koltlin을 통해서 백준을 준비하던중 하나 궁금한 점이 생겼습니다. 

기본적으로 Kotlin을 통해서 사용할 수 있는 입출력 함수는 다음 세가지 입니다. 

1. Scanner

2. BufferedReader

3. Java라이브러리를 확장한 Kotlin 자체 Console I/O

총 세가지 입니다. 자체적으로 입력을 받는다면 속도측정에 편차가 발생하는 것이 우려되어서 백준의 간단한 입출력 문제를 기준으로 속도측정 해봤습니다. 

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

다음 문제를 풀기 위해서 총 세가지 형태로 입출력을 받는 코드를 작성해봤습니다. 

1. Scanner

import java.util.*

fun main()  = with(Scanner(System.`in`)){
    val (n,m)= readLine()!!.split(" ").map { it.toInt() }
    if(n>m) println(">")
    else if(n<m) println("<")
    else println("==")
}

2.BufferedReader

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val (n,m)= readLine()!!.split(" ").map { it.toInt() }
    if(n>m) println(">")
    else if(n<m) println("<")
    else println("==")
}

3. Kotlin Console I/O

fun main(){
    val (n,m)= readLine()!!.split(" ").map { it.toInt() }
    if(n>m) println(">")
    else if(n<m) println("<")
    else println("==")
}

해당 코드들을 각각 실행시켜봤습니다. 플랫폼 특성항 4~5ms의 편차는 발생할 수 있지만, 평균적인 속도는 다음과 같았습니다.

BufferdReader가 메모리와 시간순으로는 가장 효율적이었으며,

Kotlin Console은 시간면에서는 근소하게 느렸으며 메모리측면으로는 BufferdReader보다 효율적이지 못했습니다.  

Scanner는 시간, 메모리 측면에서 모두 좋지 않은 성능을 보여주었습니다. 

하지만, 개인적으로는 BufferedReader를 with 함수로 main함수 전체에서 쓸 수 있도록 해주었지만 다른 경우에는 객체를 선언하고 메모리 누수방지를 위해 객체 반환을 해주어야하므로 코드의 가독성 측면에서는 Kotlin Console I/O가 우수한 상황이 나올수도 있기 때문에 각자의 상황에 따라 적절하게 사용하는 것이 중요할 것입니다.

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

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

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

백트래킹의 연습을 위해서 문제를 풀었습니다. 가장 중요한 구조는 N과 M(1) 의 문제를 기초로 문제에서 원하는 조건 과 분기를 설정하여 백트래킹을 하는 것입니다.

fun main(){
    val (n,m) = readLine()!!.split(" ").map{it.toInt()}
    val num = IntArray(m) {0}
    val used = BooleanArray(n+1) {false}


    fun bt(par : Int){
        if(m==par) {
            println(num.joinToString(" "))
            return
        }
        
        for(i in 1..n){
            if(!used[i]){
                num[par] =  i
                used[i]= true
                bt(par+1)
                used[i]=false
            }
        }
    }
    bt(0)
}

n을 사용되는 숫자의 범위 m을 출력될 자리수로 생각하면 bt함수의 첫번째에서는 우선 자리수(m)만큼 bt함수가 재귀 되었는가를 판단하고 만약 그만큼 재귀되었다면 채워진 num IntArray를 출력하는 것입니다. 

이후 for문에서는 used라는 BoolenArray를 통해서 해당 숫자가 사용되었는가 아닌가를 판단하면서 사용되지 않았다면 해당 숫자를 num에 채우고 다음 숫자를 매개변수로 재귀 호출 합니다. 

이와 같은 구조를 기초로 N-Queen, 부분수열의 합등의 문제를 풀었습니다.

이외 풀이 코드는 https://github.com/IslandofDream/Baekjoon_Practice/tree/main/%EB%B0%B1%EC%A4%80 를 참고해주시면 감사하겠습니다.

참고링크

https://blog.encrypted.gg/945

https://youngest-programming.tistory.com/221

11052번: 카드 구매하기 (acmicpc.net)

카드 구매하기 입니다. 문제에서는 최대한 비싼 가격으로 카드를 구매해야하기 아래의 배열부터 올라와서 높은 값을 갱신해 주어야 합니다. 따라서 아래에서 부터 최대값을 갱신해주어야 합니다. 

package com.company;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {



    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int t = Integer.parseInt(br.readLine());
        long dp[] = new long[t+1];
        long number[] = new long[t+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i<=t; i++){
            number[i] = Integer.parseInt(st.nextToken());
        }

        for(int i =1; i<=t; i++){
            for(int j = 1; j<=i; j++){
                dp[i] = Math.max(dp[i], dp[i-j] + number[j]);
            }
        }
        System.out.println(dp[t]);
    }
}

부족했던 점

처음에는 다음과 같은 점화식을 사요했습니다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {



    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int t = Integer.parseInt(br.readLine());
        long dp[] = new long[t+1];
        long number[] = new long[t+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i<=t; i++){
            number[i] = Integer.parseInt(st.nextToken());
        }

        dp[1] = number[1];
        if(t>1){ dp[2] = Math.max(number[2],dp[1]*2);}
        if(t>2){dp[3] = Math.max(number[3], number[1] +dp[2]);}
        for(int i =4; i<=t; i++){
                dp[i] = Math.max(number[i], Math.max(dp[i-1]+number[1], dp[i-2]+dp[2]));
        }
        System.out.println(dp[t]);
    }
}

하지만 코드는

1 100 160 1 1 1 1 1 1 1 의 반례가 존재하였습니다. 

해당 케이스의 답은 520이 나와야 하지만 제가 구성한 위의 코드는 최대값이 500이 나왔습니다.