개발해요

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

프로세스

1. 재귀(백트래킹)를 사용해서 9에서 오른쪽 or 0에서 왼쪽으로 감소/증가 하는 방향으로 감소하는 수를 모두 구한다.
2. 오름차순으로 정렬한다.
3. n > 1023이라면 -1을, 그렇지 않다면 n번째 수를 출력한다.

풀이

처음엔 앞에 있는 수로 다음 수를 구하는 것 같아서 DP를 떠올렸지만 경우의 수가 아닌 n번째 수를 구하는 방법을 생각해내지 못했다.

다음은 완전 탐색으로 풀 수 있는지 생각해본다. 수의 범위: 0 ~ 9876543210, 하지만 이 숫자를 전부 확인하면 시간 초과다. 

어떻게 해야할까

각 자릿수는 일정한 방향성을 갖는다. 왼쪽의 수가 7이라면 오른쪽에 올 수 있는 수는 6~0이다. 이 아이디어에 착안하면 재귀적으로 감소하는 수만 골라서 모두 구할 수 있다. 그리고 이것을 정렬하면 n번째 감소하는 수를 구할 수 있다.

재귀 함수의 구체적인 구현은 다음과 같다

 1. 이전 수의 마지막 자리 숫자보다 작은 수를 오른쪽에 추가해서 새로운 숫자를 구한다. -> 나머지 연산 사용

 2. 새로 구한 숫자로 재귀 함수를 호출한다

for (i in lastDigit - 1 downTo 0) {
	val newNumber = number * 10 + i  // 오른쪽에 감소하는 수 추가
	addDecreasingNumber(newNumber)
}

 3. 호출된 함수는 숫자를 감소하는 수에 추가한다

 4. 마지막 자리 수가 0이라면 재귀 함수를 종료한다.

재귀 함수 소스 코드

fun addDecreasingNumber(number: Long) {
    decreasingNumbers.add(number)

    val lastDigit = number % 10

    if (lastDigit <= 0) {
        return
    }

    for (i in lastDigit - 1 downTo 0) {
        val newNumber = number * 10 + i
        addDecreasingNumber(newNumber)
    }
}

위 방식은 왼쪽에서 오른쪽으로 숫자를 추가하면서 감소하는 방향으로 수를 구하고 있다. 반대로, 오른쪽에서 증가하는 방향으로 왼쪽에 숫자를 추가하는 방식도 가능하다.

감소하는 수를 구할 수 있을지 없을지는 어떻게 판단할까?

9 8 7 6 5 4 3 2 1 0에서 9531을 도출하는 방법을 경우의 수 관점에서 생각해볼 수 있다.

9, 5, 3, 1을 선택, 8, 7, 6, 4, 2, 0은 선택하지 않는 것이다. 각 자릿수를 선택/선택하지 않는 모든 경우의 수는 2^10개이고, 모두 선택하지 않는 경우는 없기 때문에 2^10 - 1 = 1023 개가 나온다. 따라서, n > 1022라면 감소하는 수를 구할 수 없다.

코드 (Kotlin)

1. 감소하는 방향으로 백트래킹

/**
 * 1. 백트래킹으로 0 ~ 9876543210까지 감소하는 수를 구한다
 * 2. 정렬한다
 * 3. n번째 값을 출력한다
 * 4. 정수 범위에 주의한다
 */

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

val decreasingNumbers = mutableListOf<Long>()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val targetIndex = readLine().toInt()

    if (targetIndex <= 10) {
        println(targetIndex)
    } else if (targetIndex >= 1023){ // 감소하는 수의 개수는 1023개다
        println(-1)
    } else {
        for (i in 0..9) {
            addDecreasingNumber(i.toLong())
        }
        decreasingNumbers.sort()
        println(decreasingNumbers[targetIndex])
    }
}

fun addDecreasingNumber(number: Long) {
    decreasingNumbers.add(number)

    val lastDigit = number % 10

    if (lastDigit <= 0) {
        return
    }

    for (i in lastDigit - 1 downTo 0) {
        val newNumber = number * 10 + i
        addDecreasingNumber(newNumber)
    }
}

2. 증가하는 방향 

/**
 * 1. 백트래킹으로 0 ~ 9876543210까지 감소하는 수를 구한다
 * 2. 정렬한다
 * 3. n번째 값을 출력한다
 * 4. 정수 범위에 주의한다
 */

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

val decreasingNumbers = mutableListOf<Long>()
    
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val targetIndex = readLine().toInt()

    if (targetIndex <= 10) {
        println(targetIndex)
    } else {
        addDecreasingNumber(0, 0, 0)
        decreasingNumbers.sort()

        if (targetIndex > decreasingNumbers.lastIndex) {
            println(-1)
        } else {
            println(decreasingNumbers[targetIndex])
        }
    }
}

fun addDecreasingNumber(startNumber: Int, beforeLength: Int, beforeNumber: Long) {
    if (beforeLength >= 10 || startNumber >= 10) {
        return
    }

    for (i in startNumber..9) {
        val newNumber = i * (10.0).pow(beforeLength).toLong() + beforeNumber
        decreasingNumbers.add(newNumber)
        addDecreasingNumber(i + 1, beforeLength + 1, newNumber)
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42587

프로세스

1. 단순 연결 리스트 사용: O(N^2)

1. 큐(연결 리스트)에서 문서를 꺼낸다. (total O(N))
2. 우선순위가 더 큰 문서가 있는지 연결 리스트의 모든 문서를 확인한다. (total O(N^2))
   1. 있다 -> 문서를 큐에 다시 넣는다.
   2. 없다 -> 문서를 출력(삭제)하고 removeCount++
3. 출력 문서 == location 문서 -> removeCount 반환

2. 우선순위 큐, 출력 확인용 배열 사용: O(NlogN)

1. 우선순위 큐(PQ)에 문서를 모두 넣는다. (total O(NlogN))
2. 큐에서 문서를 꺼낸다.
3. PQ에서 우선순위가 더 높은 문서가 있는지 확인한다. (total O(N))
   1. 우선순위 큐 제일 위에 있는 문서를 확인한다.
   2. 이미 출력한 문서라면(isPrinted 확인) PQ에서 제거하고 다시 확인한다.
   3. 더 높은 문서가 있다 -> 큐에 다시 넣는다
   4. 없다 -> 문서 출력, removeCount++, isPrinted에 체크
4. 출력한 문서 == location 문서 -> removeCount 반환

풀이

1. 연결 리스트 사용

가장 쉬운 방법은 큐에서 문서를 꺼낼 때마다 우선 순위가 더 높은 문서가 있는지 모두 확인하는 것이다. 끝에 어떤 문서서가 있을지 알 수 없어서 매번 연결 리스트를 끝까지 탐색(O(N))해야 하므로 총 O(N^2)이 걸린다. 하지만 문서가 최대 100개이므로 O(N^2)으로 해결할 수 있다. 

2. 우선순위 큐와 출력 확인용 배열 사용

우선순위 큐와 출력 확인용 배열을 사용하면 O(nlogn)으로 좀 더 빠르게 해결할 수 있다.

O(N^2)이 걸렸던 이유는 매번 다른 문서를 전부 확인해야 했기 때문이다. 따라서 다른 문서의 우선 순위를 더 빠르게 확인할 수 있다면 시간 복잡도를 줄일 수 있다. 

우선순위 큐

문서를 우선순위 큐(PQ)에 따로 넣어놓으면,  PQ의 맨 위에 있는 문서를 통해 순위가 더 높은 문서가 있는지 바로 확인이 가능하다.

val doc = queue.poll()
 // 우선 순위가 더 높은 문서가 있는지 확인
 if (doc.priority >= pq.peek().priority) {
 	removeCount++
    isPrinted[doc.id] = true
 }

하지만 문제는 문서를 출력할 때 PQ에서 해당 문서를 삭제하기가 번거롭다는 것이다. 왜냐면 맨 위에 있는 문서가 우선 순위가 같은 다른 문서일 수도 있기 때문이다. PQ에서 일일이 삭제를 할 수도 있는데, 그러면 총 O(nlogn)의 시간이 걸린다.

출력 확인 배열

좀 더 빠른 방법은 출력됐음을 확인하는 배열을 사용하는 것이다. 출력할 때 PQ에서 삭제하는 것이 아니라 배열에 체크를 하고, 다음 문서를 확인할 때 PQ의 맨 위에 있는 것이 이미 출력된 문서라면 제거하고 다음 문서를 가져온다. 이렇게 하면 PQ에서 문서를 제거하는 데 총 O(N)이 걸린다.

 // 출력된 문서 제거
while (isPrinted[pq.peek().id]) {
	pq.poll()
}

코드 (우선순위 큐)

import java.util.*

data class Document(val id: Int, val priority: Int)

class Solution {
    fun solution(priorities: IntArray, location: Int): Int {
        var removeCount = 0
        val queue: Queue<Document> = LinkedList()
        val pq = PriorityQueue(compareByDescending<Document>{it.priority})
        val documents = Array<Document>(priorities.size) { i ->
            Document(i, priorities[i])
        }
        val isPrinted = BooleanArray(documents.size)
        
        for (doc in documents) {
            queue.add(doc)
            pq.add(doc)
        }

        while(queue.isNotEmpty()) {
            
            // 출력된 문서 제거
            while (isPrinted[pq.peek().id]) {
                pq.poll()
            }

            val doc = queue.poll()

            // 우선 순위가 더 높은 문서가 있는지 확인
            if (doc.priority >= pq.peek().priority) {
                removeCount++
                isPrinted[doc.id] = true // 출력 체크

                if (doc.id == location) break
            } else {
                queue.add(doc)
            }
        }

        return removeCount
    }
}

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

프로세스

1. 완전 탐색을 떠올린다. 연산자 4개, 자리는 10개이므로 시간 복잡도(경우의 수)는 4^10 = 1,048,576이다.
2. 재귀 함수를 사용한다.
   1. calculate(왼쪽 피연산자(operand), 오른쪽 피연산자를 가리킬 인덱스)로 구성한다.
   2. 마지막 인덱스까지 계산할 때마다 최대 값, 최소 값을 갱신한다.
   3. 각 연산자마다 operand와 현재 피연산자를 계산해서 재귀함수를 호출한다.

풀이

어렵지 않았지만 재귀 함수를 연습하기 좋았다.

가장 먼저 완전 탐색을 떠올릴 수 있는데, 연산자 들어갈 자리가 최대 10자리이고 연산자가 4개 뿐이다. 따라서 모든 자리에 연산자를 한 번씩 넣어서 모든 경우의 수를 확인할 경우 4^10 = 1,048,576개 라서 충분히 완전 탐색으로 해결할 수 있다.

재귀 함수

재귀 함수 구성은 배열 1 2 3 4 5 6이 있다고 가정했을 때, (1 2) (연산자) (3 4 5 6)와 같이 나눌 수 있다. 즉, 지금까지 계산한 왼쪽 피연산자와 배열의 나머지에서 그 다음에 계산할 숫자의 현재 인덱스를 인자로 갖게 한다.

fun calculate(operand1: Int, idx: Int)

그리고 인덱스가 마지막 인덱스를 넘으면 전부 계산한 것이기 때문에 최대 값, 최소 값과 비교하여 정답을 갱신한다.

if (idx >= numbers.size) {
        maxValue = max(maxValue, operand1)
        minValue = min(minValue, operand1)
        return
    }

종료 조건이 아니라면, 각 연산자마다 계산해서 다음 자리에 해당하는 연산자를 넣어보기 위해 재귀 함수를 호출한다.

 for (i in operators.indices) {
        if (operators[i] <= 0) continue

        operators[i]--
        when(i) {
            0 -> calculate(operand1 + numbers[idx], idx + 1)
            1 -> calculate(operand1 - numbers[idx], idx + 1)
            2 -> calculate(operand1 * numbers[idx], idx + 1)
            else -> {
                if (operand1 < 0) {
                    calculate(-(-operand1 / numbers[idx]), idx + 1)
                } else {
                    calculate(operand1 / numbers[idx], idx + 1)
                }
            }
        }
        operators[i]++
    }

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max
import kotlin.math.min

lateinit var numbers: IntArray
lateinit var operators: IntArray // +, -, *, /
var maxValue = Int.MIN_VALUE
var minValue = Int.MAX_VALUE

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    numbers = with(StringTokenizer(readLine())) {
        IntArray(size) { this.nextToken().toInt() }
    }
    operators = with(StringTokenizer(readLine())) {
        IntArray(4) { this.nextToken().toInt() }
    }

    calculate(numbers[0], 1)

    println(maxValue)
    println(minValue)
}

fun calculate(operand1: Int, idx: Int) {
    if (idx >= numbers.size) {
        maxValue = max(maxValue, operand1)
        minValue = min(minValue, operand1)
        return
    }

    for (i in operators.indices) {
        if (operators[i] <= 0) continue

        operators[i]--
        when(i) {
            0 -> calculate(operand1 + numbers[idx], idx + 1)
            1 -> calculate(operand1 - numbers[idx], idx + 1)
            2 -> calculate(operand1 * numbers[idx], idx + 1)
            else -> {
                if (operand1 < 0) {
                    calculate(-(-operand1 / numbers[idx]), idx + 1)
                } else {
                    calculate(operand1 / numbers[idx], idx + 1)
                }
            }
        }
        operators[i]++
    }
}

안드로이드

리눅스 기반의 오픈소스 모바일 운영체제

Java와 Kotlin이 호환되는 이유

두 소스 코드 모두 Java 컴파일러와 Kotlin 컴파일러에 의해 .class파일(바이트 코드)로 변환되기 때문이다.

Kotlin 파일 안에 Java 코드가 있을 경우, Java 컴파일러가 컴파일된 Kotlin 코드의 클래스 패스에 Java 코드를 컴파일한다.

안드로이드 컴파일 과정

1. Java or Kotlin 파일을 바이트 코드로 변환
2. 바이트 코드와 컴파일된 리소스 파일을 묶어서 dex파일로 변환(컴파일)
3. ART에서 dex 파일을 실행 (💡 ART(Android Run Time): JVM처럼 dex 파일을 실행시켜주는 런타임 라이브러리)

Minimum sdk

앱이 최소로 서비스하는 API level(안드로이드 버전)을 의미한다. 예를 들어, min sdk가 21이면 API level 20 이하는 해당 앱을 설치할 수 없다. 왜냐면 그 이하에서는 지원하지 않는 API를 사용하기 때문이다.

프로젝트와 모듈

프로젝트 안에는 여러 모듈이 들어갈 수 있다. 안드로이드 프로젝트를 처음 시작하면 자동으로 프로젝트 이름으로 된 폴더와 그 안에 app이라는 폴더가 생성되는데, 이 app이 모듈을 의미한다. app외에도 추가적으로 모듈을 생성할 수 있다.

모듈이 여러 개면 모듈 수준의 gradle 파일도 여러 개가 되는 건가??

build.gradle 파일

Gradle 빌드 툴이 프로젝트를 빌드하기 위해 참조하는 파일이다. 빌드 환경 설정 파일이라고 볼 수 있다.

참고

https://sesac.seoul.kr/course/active/detail.do

https://stonybean.github.io/Kotlin-and-Java-compatible/

https://diqmwl-programming.tistory.com/115