>알고리즘 문제
1. 피보나치 수
1) 문제
문제 설명
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
- F(2) = F(0) + F(1) = 0 + 1 = 1
- F(3) = F(1) + F(2) = 1 + 1 = 2
- F(4) = F(2) + F(3) = 1 + 2 = 3
- F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
- n은 2 이상 100,000 이하인 자연수입니다.
2) 솔루션
class Solution {
fun solution(n: Int): Int {
return matmult(n)%1234567
}
fun matmult(n:Int):Int{
var tmp=arrayOf(arrayOf(1,1),arrayOf(1,0))
for(i in 1..n-1){
tmp=arrayOf(arrayOf(tmp[0][0]+tmp[0][1],tmp[0][0]),
arrayOf(tmp[1][0]+tmp[1][1],tmp[1][0]))
if(tmp[1][1]>1234567){
for(j in 0..1){
for(k in 0..1){
tmp[j][k]%=1234567
}
}
}
}
return tmp[1][0]
}
}-행렬식으로 바꾸어 F_n+1=AF_n 꼴이 되므로 F_n=A^nF_0 임을 이용
-그대로 진행시 오버플로우가 나오므로 합동식을 이용
=>a≡b(mod p), c≡d (mod p) 이면 a+c ≡ b+d (mod p)임을 이용
2. 1, 2, 3 떨어트리기
1)문제
문제 설명
춘식이는 트리의 1번 노드에 숫자 1, 2, 3 중 하나씩을 계속해서 떨어트려 트리의 리프 노드1에 숫자를 쌓는 게임을 하려고 합니다.
아래 그림은 게임의 예시를 나타냅니다.
- 트리의 모든 간선은 부모 노드가 자식 노드를 가리키는 단방향 간선입니다.
- 모든 부모 노드는 자식 노드와 연결된 간선 중 하나를 길로 설정합니다.
- 실선 화살표는 길인 간선입니다.
- 점선 화살표는 길이 아닌 간선입니다.
- 모든 부모 노드는 자신의 자식 노드 중 가장 번호가 작은 노드를 가리키는 간선을 초기 길로 설정합니다.
[게임의 규칙]은 아래와 같습니다.
- 1번 노드(루트 노드)에 숫자 1, 2, 3 중 하나를 떨어트립니다.
- 숫자는 길인 간선을 따라 리프 노드까지 떨어집니다.
- 숫자가 리프 노드에 도착하면, 숫자가 지나간 각 노드는 현재 길로 연결된 자식 노드 다음으로 번호가 큰 자식 노드를 가리키는 간선을 새로운 길로 설정하고 기존의 길은 끊습니다.
- 만약 현재 길로 연결된 노드의 번호가 가장 크면, 번호가 가장 작은 노드를 가리키는 간선을 길로 설정합니다.
- 노드의 간선이 하나라면 계속 하나의 간선을 길로 설정합니다.
- 원하는 만큼 계속해서 루트 노드에 숫자를 떨어트릴 수 있습니다.
- 단, 앞서 떨어트린 숫자가 리프 노드까지 떨어진 후에 새로운 숫자를 떨어트려야 합니다.
[게임의 목표]는 각각의 리프 노드에 쌓인 숫자의 합을 target에서 가리키는 값과 같게 만드는 것입니다.
예를 들어, target이 [0, 0, 0, 3, 0, 0, 5, 1, 2, 3]일 경우 아래 표와 같은 의미를 가집니다.
| 1 | 0 |
| 2 | 0 |
| 3 | 0 |
| 4 | 3 |
| 5 | 0 |
| 6 | 0 |
| 7 | 5 |
| 8 | 1 |
| 9 | 2 |
| 10 | 3 |
target대로 리프 노드에 쌓인 숫자의 합을 맞추기 위해서는 [2, 1, 2, 2, 1, 3, 3]순으로 숫자를 떨어트리면 됩니다.
아래 두 그림은 순서대로 1, 2번째 숫자 [2, 1]을 떨어트린 뒤의 길 상황을 나타냅니다.
- 숫자 2는 떨어지면서 1번 노드와 2번 노드를 지나갔습니다.
- 1번 노드는 3번 노드를 가리키는 간선을 길로 설정합니다.
- 2번 노드는 5번 노드를 가리키는 간선을 길로 설정합니다.
- 숫자 1은 떨어지면서 1번 노드, 3번 노드, 6번 노드를 지나갔습니다.
- 1번 노드는 3번 노드보다 번호가 큰 노드를 가리키는 간선이 없으므로 다시 2번 노드를 가리키는 간선을 길로 설정합니다.
- 3번 노드는 간선이 하나이므로 계속해서 6번 노드를 가리키는 간선을 길로 설정합니다.
- 6번 노드는 9번 노드를 가리키는 간선을 길로 설정합니다.
아래 두 그림은 순서대로 3, 4번째 숫자 [2, 2]를 떨어트린 뒤의 길 상황을 나타냅니다.
아래 세 그림은 순서대로 5, 6, 7번째 숫자 [1, 3, 3]을 떨어트린 뒤의 길 상황을 나타냅니다.
각 리프 노드에 쌓인 숫자를 모두 더해 배열로 나타내면 target과 같습니다.
트리의 각 노드들의 연결 관계를 담은 2차원 정수 배열 edges, 각 노드별로 만들어야 하는 숫자의 합을 담은 1차원 정수 배열 target이 매개변수로 주어집니다. 이때, target 대로 리프 노드에 쌓인 숫자의 합을 맞추기 위해 숫자를 떨어트리는 모든 경우 중 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우를 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. 만약, target대로 숫자의 합을 만들 수 없는 경우 [-1]을 return 해주세요.
제한사항
- 1 ≤ edges의 길이 ≤ 100
- edges[i]는 [부모 노드 번호, 자식 노드 번호] 형태로, 단방향으로 연결된 두 노드를 나타냅니다.
- 1 ≤ 노드 번호 ≤ edges의 길이 + 1
- 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
- 항상 하나의 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
- 1번 노드는 항상 루트 노드입니다.
- edges[i]는 [부모 노드 번호, 자식 노드 번호] 형태로, 단방향으로 연결된 두 노드를 나타냅니다.
- target의 길이 = edges의 길이 + 1
- target[i]는 i + 1번 노드에 쌓인 숫자의 합으로 만들어야 하는 수를 나타냅니다.
- 0 ≤ 리프 노드의 target값 ≤ 100
- 리프 노드를 제외한 노드의 target값 = 0
- target의 원소의 합은 1 이상입니다.
- target[i]는 i + 1번 노드에 쌓인 숫자의 합으로 만들어야 하는 수를 나타냅니다.
2. 솔루션
class Solution {
fun solution(edges: Array<IntArray>, target: IntArray): IntArray {
var answer: IntArray = intArrayOf()
var nodes=ArrayList<Node>()
var visits=mutableMapOf<Int,ArrayList<Int>>() //키는 노드 번호, 어레이리스트는 방문 순서들
var visitNum=ArrayList<Int>()
var check=ArrayList<Int>() //0은 언더 1은 부합 2는 오버로
var idx=0 //넣은 순서
var result=mutableMapOf<Int,Int>() //키는 방문순서 값은 사전식배열된 숫자카드
for(i in target.indices){
nodes+=Node(i+1)
visitNum+=0
check+=0
}
for(i in edges){
nodes[i[0]-1].edge.add(nodes[i[1]-1])
}
for(i in nodes){
if(i.edge.isEmpty()){
i.leaf=true
continue
}
if(i.edge.size==1){
i.edge[0].side=i.edge[0]
}
else{
i.edge.sortBy{it.num}
for(j in 0..i.edge.size-2){
i.edge[j].side=i.edge[j+1]
}
i.edge[i.edge.size-1].side=i.edge[0]
}
i.next=i.edge[0]
}
//leaf node만 방문map에 추가
for(i in nodes){
if(!i.leaf) continue
visits.put(i.num,ArrayList<Int>())
}
//계속 leaf를 방문하면서 방문횟수와 순서를 쌓음
while(true){
var tmpNode=nodes[0]
while(!tmpNode.leaf){
var befNode=tmpNode
tmpNode=tmpNode.next as Node
befNode.next=befNode.next!!.side
}
visitNum[tmpNode.num-1]++
visits[tmpNode.num]?.add(idx++)
//모든 leaf체크
for(i in check.indices){
if(visitNum[i]*3<target[i]){
check[i]=0
}else if(target[i]>=visitNum[i]){
check[i]=1
}else{
check[i]=2
}
}
val checks=checkLeaf(check)
if(checks==1){
break
}else if(checks==2){
return intArrayOf(-1)
}
}
for((key, value) in visits){
result.putAll(findList(visitNum[key-1],target[key-1],value))
}
for(i in 1..result.size){
answer+=result[i-1]!!
}
return answer
}
//0: 진행, 1:전부 매치로 종료, 2:오버가 나서 종료
fun checkLeaf(arr:ArrayList<Int>):Int{
var under=false
var match=false
var over=false
for(i in arr){
if(i==0) under=true
else if(i==1) match=true
else over=true
}
if(!over){
//오버는 안났지만 아직 모든 타겟이 범위에 들어오지 않은 경우
if(under){
return 0
}
//전부 매치인 경우
else{
return 1
}
}
//오버가 난 경우
else{
return 2
}
}
//target값을 완성시켜주는 리스트를 찾음
//cnt는 방문 횟수
fun findList(cnt:Int, target:Int, visits:ArrayList<Int>):MutableMap<Int,Int>{
var arr=ArrayList<Int>()
var result=mutableMapOf<Int,Int>()
for(i in 1..cnt){
arr+=3
}
while(sum(arr)!=target){
for(i in arr.indices){
if(arr[i]>1){
arr[i]--
break
}
}
}
for(i in 1..cnt){
result.put(visits[i-1],arr[i-1])
}
return result
}
fun sum(arr:ArrayList<Int>):Int{
var sum=0
for(i in arr){
sum+=i
}
return sum
}
}
class Node(num:Int){
val num:Int
var leaf=false
var edge=ArrayList<Node>()
var side:Node?=null
var next:Node?=null
init{
this.num=num
}
}-리프노드들은 방문하면서 방문 순서와 방문 횟수를 저장
-방문횟수로 만들어질 수 있는 값에 target이 들어가는지 모든 리프노드 검사
-방문횟수가 x면: x <= target <=3x
-전부 만족하는 순간 중지하고 방문 순서에 사전식으로 값을 넣음
-안되는 경우:아직 방문횟수 범위보를 부합하지 않는 노드가 있는데 방문범위를 벗어나는 노드가 생기는 경우
-즉, 언더, 부합, 오버 세 경우로 나누어서 언더와 부합만 있는동안 사이클을 돌리다가 언더와 오버가 같이 생기는 순간 -1 리턴
3)느낀점: 처음으로 풀어보는 난이도 4레벨 문제였는데 조금 어렵지만 그래도 할만했던것 같다.
>계산기 과제 보충&특강
1. abstract class
- 기존
open class AbstractOperation() {
open fun operation(num1:Int, num2:Int):Int{return 0}
}-바꾼것
abstract class AbstractOperation() {
abstract fun operation(num1:Int, num2:Int):Int
}1)추상 클래스:
-class앞에 abstract를 붙이는 클래스로 스스로는 인스턴스화 될 수 없고 상속에 쓰임. 오버라이드를 위해 선
=>즉 여러 클래스의 공통부분을 뽑아내 추상화 시키는데 사용
-추상 메소드를 가짐
=>fun앞에 abstract를 붙이는 메소드로 본문인 {}부분이 없음.
2. calculator 구현방식
1)내 방식
class Calculator() {
val add=AddOperation()
val sub=SubstractOperation()
val mul=MultiplyOperation()
val div=DivideOperation()
fun operation(num1:Int,num2:Int,op:String):Int{
if(op=="%"){
return num1%num2
}
else{
val obj=when(op){
"+" ->add
"-" ->sub
"*" ->mul
else -> div
}
return obj.operation(num1, num2)
}
}
.
.
.
2)해설 방식
class Calculator(private val operator: AbstractOperation) {
fun operate(num1: Int, num2: Int): Double {
return operator.operate(num1, num2)
}
}Main.kt
fun main() {
val addCalc = Calculator(AddOperation())
val minusCalc = Calculator(SubstractOperation())
val multipleCalc = Calculator(MultiplyOperation())
val divideCalc = Calculator(DivideOperation())
val myStack = MyStack()
val calResult = myStack.getPostFixExpressionOperation("(2 + 4) * 4 / 2 * 12")
println("결과: ${calResult}입니다")
}-나는 Calculator()내에 연산 클래스를 넣어 작동하게 하였지만
-해설은 Calculator()가 연산클래스를 인자로 받아서 생성마다 각 연산을 하도록 하였음
=>의존성 주입: Calculator내에서 연산 클래스를 생성하는게 아닌 외부에서 생성해서 Calculator가 생성될때 연산클래스의 인스턴스를 인자로 받는것=>외부에서 주입
의존성 주입은 세 가지 유형
- 생성자 주입(Constructor Injection): 객체를 생성할 때 의존성을 주입합니다. 주로 코틀린, 자바 등의 객체 지향 프로그래밍 언어에서 사용됩니다.
- 속성 주입(Property Injection): 의존성을 객체의 속성으로 주입합니다. 주로 스프링 프레임워크와 같은 DI 컨테이너를 사용하는 프레임워크에서 사용됩니다.
- 메서드 주입(Method Injection): 의존성을 메서드의 매개변수로 전달하여 주입합니다. 주로 함수형 프로그래밍에서 사용됩니다.
=>이중 사용된 방식은 생성자 주입.
@이점
- 테스트 용이성: 의존성 주입형태는 대체용 가짜 객체를 넣어 테스트 하기 용이한 구조
- 코드 재사용: 하나의 객체를 여러 객체에 재사용 가능
- 유연성: 코드 결합도를 줄여줌
@코드 결합도: 결합도가 낮을 수록 좋음. 일부분을 변경 및 업데이트시 다른 부분에 영향이 덜 감.
'코틀린-안드로이드' 카테고리의 다른 글
| 21일차)알고리즘 문제(예상 대진표), 복습 및 과제 피드 (0) | 2024.06.12 |
|---|---|
| 20일차)알고리즘 문제(카펫, 행렬과 연산, 올바른 괄호의 갯수, 무지의 먹방 라이브), 복습(추상 클래스와 인터페이스) (1) | 2024.06.11 |
| 18일차)알고리즘 문제(이진 변환 반복하기) (1) | 2024.06.09 |
| 17일차)알고리즘 문제(JadenCase 문자열 만들기) (0) | 2024.06.08 |
| 16일차)알고리즘 문제(최댓값과 최솟값), 코드카타 리뷰, 코틀린 문법 강의 5주차(자료형 변환, 여러 인스턴스 리턴, scope function, 확장함수, 비동기 프로그래밍, 쓰레드와 코루틴) (0) | 2024.06.07 |