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

 

10828번: 스택

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

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

 

10845번: 큐

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

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

 

10866번: 덱

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

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

 

 

10828 스택 제출 결과

가장 처음 문제인 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를 사용하였습니다. 그제서야 문제해결을 할 수 있었습니다.

10845 큐 제출결과

 

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를 사용한 입출력을 통해서 성공 할 수 있었습니다.

10866 덱 문제 제출결과

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들에 대한 시간복잡도도 다시 한번 상기 할 수 있었습니다.

'Kotlin(PS) > 기타' 카테고리의 다른 글

11652 카드(Kotlin)  (1) 2022.09.23

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

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

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

 

2747번: 피보나치 수

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

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

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

 

1330번: 두 수 비교하기

두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오.

www.acmicpc.net

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

 

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의 편차는 발생할 수 있지만, 평균적인 속도는 다음과 같았습니다.

위에서 부터 Scanner, Kotlin Console I/O, BufferedReader순

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

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

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

 

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

 

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

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

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

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

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

 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

백트래킹의 연습을 위해서 문제를 풀었습니다. 가장 중요한 구조는 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

 

[실전 알고리즘] 0x0C강 - 백트래킹

이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는

blog.encrypted.gg

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

 

[알고리즘] 백준 N과 M (1) -백트랙킹- 자바 코틀린

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

youngest-programming.tistory.com

 

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

 

11052번: 카드 구매하기

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.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이 나왔습니다. 

 

'C++ > DP' 카테고리의 다른 글

DP - 2225(합분해)  (0) 2021.01.16
DP - 9461(파도반 수열)  (0) 2021.01.16
DP-2133(타일 채우기)  (0) 2021.01.16
DP-1699(제곱수의 합)  (0) 2021.01.16
DP - 2579_계단 오르기  (0) 2021.01.13

+ Recent posts