>알고리즘 문제
1. 여행경로
1)문제
문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
2)솔루션
class Solution {
data class Node(val route:Array<String>, val used:BooleanArray)
fun solution(tickets: Array<Array<String>>): Array<String> {
var answer = arrayOf<String>()
val q=ArrayDeque<Node>()
q.addLast(Node(arrayOf("ICN"),BooleanArray(tickets.size){false}))
while(q.isNotEmpty()){
val cur = q.removeFirst()
if(!cur.used.contains(false)){
answer = if(answer.isEmpty()) cur.route else compares(answer,cur.route)
continue
}
for(i in tickets.indices){
if(!cur.used[i]&&tickets[i][0]==cur.route.last()){
val new=Node(cur.route+tickets[i][1],cur.used.copyOf().also{it[i]=true})
q.addLast(new)
}
}
}
return answer
}
fun compares(str1:Array<String>,str2:Array<String>):Array<String>{
for(i in str1.indices){
val tmp = str1[i].compareTo(str2[i])
if(tmp!=0){
return if(tmp<0) str1 else str2
}
}
return str1
}
}-노드에 여행 경로와 사용 티켓정보를 저장
-BFS로 구하여 결과를 찾는다.
2. 입국심사
1)문제
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
2)솔루션
class Solution {
fun solution(n: Int, times: IntArray): Long {
var answer: Long = 0
//기준: 각 심사관별 총 심사시간중 최대값이 최소가 되는 것
//총 심사시간: 인원을 분배하여 심사기간에 곱해준다.
//최대 시간은 심사관 최대시간*입국심사 기다리는 전체 인원수
//각 루프별로 체크해서 최대시간을 이진 탐색으로 찾아간다.
times.sort()
var left=0L
var right=times.last()*n.toLong()
while(left<right){
val mid=(left+right)/2L
var total = 0L
//최대값 이하중 최대가 되도록 인원분배
for(i in times){
total+=mid/i.toLong()
}
//총 인원수와 같으면 최대값을 더 내렸을때 총인원수가 같을수 있다
//예를 들어 [3,5] 11이면 3명 2명으로 총 5명인데 10이면 3명 2명으로 여전히 5명임
if(total==n.toLong()){
right=mid
}
//총 인원수가 n보다 작으면 최대값을 늘려야 한다
else if(total<n.toLong()){
left=mid+1
}
//총 인원수가 n보다 크면 최대값을 줄여야 한다.
else{
right=mid
}
}
return right
}
}-심사를 받는데 걸리는 시간, 즉 심사관들의 총 심사시간중 최대값을 이진탐색의 기준으로 한다.
-처음 최대 최소는 가장 오래걸리는 심사관의 심사시간 * 전체 인원수
-이진탐색을 하며 최대시간을 만족하는 최대 인원을 구해 주어진 인원과 비교하며 이진탐색 구간을 찾아간다.
-그렇게 주어진 인원과 같아지면 결과가 나옴
>Compose수업
1. Recomposition
1)명령형 UI
-어떻게 UI를 표시하고 업데이트할지 명령 =>UI상태변경을 직접 처리해야함
-setter를 이용해서 직접 업데이트 해줘야함
-예시: 텍스트를 변경할시 setter인 setText()를 이용해서 직접변경을 해줘야 함
2)선언형 UI
-무엇을 표시하고 싶은지 선언 =>상태가 변하면 UI는 자동으로 업데이트 됨
-상태기반으로 UI가 정의되며, 상태 변경시 UI가 자동으로 다시 랜더링됨
=>Recomposition: 상태가 변경된 지점의 Composable함수에 대하여 해당 Composable과 하위 Composable 함수들이 새데이터로 다시 호출되어 그려짐. 단, 해당 상태를 사용하지 않는 함수들은 재구성되지 않음.
@Smart recomposition
1)변경 상태 기반 재구성: 상태 변경시 해당 상태를 사용하는 함수들만 재구성
2)선택적 재구성: 루트Composable함수부터 시작하지 않고 상태 변경 지점부터 시작하여 필요부분만 다시 그림
=>전체 UI 재구성을 피함
3)효율적 변경 감지: 상태변경을 감지해 동일상태 재설정이나 변경 X인 경우 재구성을 건너뜀
4)호출된 함수간의 분리: 상태 변경이 발생하는 Composable함수는 독립적으로 재구성되며 다른 composable함수에 영향을 주지 않음
-예시: A안에 B와 C가 있고 A는 상태 t를 가진다 하자. 여기서 B는 static component이고 C만 상태t에 영향을 받으면 재구성시 B는 재구성에서 제외된다.
@Composable
fun Parent(){
val state = remember {mutableStateOf(0)}
Column{
Text("Static")
Child(state.value)
Button(onClick = {state.value +=1}){
Text("increase")
}
}
}
@Composable
fun Child(value:Int){
Text("Value: $value")
}
@Static과 stateless
-Static은 component를 칭함: 상태를 가지지 않는 component
-Stateless: 상태를 가지지 않는 Composable 함수를 칭함
=>Recomposition시 Static은 제외되고 Stateless는 재구성에 포함되긴 하지만 성능에 영향이 적음
2. State:하위 composable은 상위 composable에게 event를 보내고, 그 반대로는 state를 보낸다.
1) remember:
<1>특징
-Composable함수는 remember API를 사용해 메모리에 객체를 저장
-Recomposition이 일어날때 remember에 저장된 값은 그대로 유지됨.
-remember의 수명은 Composable이 호출한 시점부터 해당 Composable이 Composition에서 삭제될때까지
<2>선언 방법: 3가지 모두 동일한 방식임
val name = remember { mutableStateOf(default) }
var name by remember { mutableStateOf(default) } //이걸 추천
val (name, setValue) = remember { mutableStateOf(default) }
@주의점: ArrayList나 mutableListOf같은 변경가능 객체를 상태로 사용하면 Compose에서 관찰이 불가능 하거나 오래되거나 잘못된 데이터가 표시될 수 있음
=>되도록이면 listOf같은 Immutable한 객체를 사용
@MutableStateOf의 원리: 관찰가능한 MutableState<T>를 생성해서 사용
interface MutableState<T> : State<T> {
override var value: T
}
2)Flow
val state by viewModel.viewState.collectAsStateWithLifecycle()
3)LiveData
val state by viewModel.observeAsState()
3. State Hoisting(상태 끌어올림)
1)UI State는 해당 UI State를 읽고 쓰는 모든 Composable의 공통 상위 요소로 Hoisting해야 함
2)재사용성 증가, 테스트에 유용
3)구현 방식: 람다 함수로 인자를 끌어올리도록 만들음
-예시
@Composable
private fun Parent(){
var name by remember{ mutableStateOf("")}
Child(
name = name,
onValueChange = {
name = it
},
)
}
@Composable
private fun Child(
name: String,
onValueChange: ((String) -> Unit),
){
OutlinedTextField(
value =name
onValueChange = {
onValueChange(it)
}
)
}-OutlinedTextField에서 타자를 치면 람타함수를 통해 Parent로 값이 끌어 올려진다.
4)구조 예시
>Hilt
1. Scope: 스코프를 사용하면 해당 스코프동안 인스턴스가 유지.
=>Usecase처럼 한번 생성하면 한 인스턴스로만 유지되면 되는 것들중 최상위에 위치한 부분만 Scope를 사용하고 그 아래에는 Scope 사용x
=>왜냐하면 어차피 Usecase가 한번 생성되면 그 이후 더이상 생성될일이 없기 때문에 그아래의 종속관계에 있는 객체들은 자동으로 더이상 생성되지 않음. 그때문에 그 이상의 Scope설정은 필요 없음
=>걔다가 Scope는 메모리 문제로 사용을 필요할때 이외엔 지양해야 하므로 안써도 되면 안쓰는게 좋음
2. Singleton
:만약 서로다른 뷰모델에서 사용해야 하거나 뷰모델의 오너가 달라지는 경우에서 공통된 인스턴스를 사용해야 하면 Singleton으로 하기
