>알고리즘 문제
1. 멀리 뛰기
1)문제
문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.
- n은 1 이상, 2000 이하인 정수입니다.
2)솔루션
class Solution {
fun solution(n: Int): Long {
val tmp=ArrayList<Long>()
tmp+=1
tmp+=2
tmp+=3
if(n<=3) return tmp[n-1]
for(i:Int in 4..n){
val tmpp:Long=tmp[2]
tmp[2]=tmp[2]+tmp[1]
tmp[0]=tmp[1]
tmp[1]=tmpp
tmp[2]%=1234567L
}
return tmp[2]
}
}-점화식 이용: fn을 n칸 뛰는 가지수라고 하면 fn은 fn-1에서 한칸 더뛰고, fn-2에서 두칸 더뛰는 경우의 수를 합친것이기에 fn=fn-1 + fn-2로 풀이함
2. 에어컨
1)문제
문제 설명
현대모비스에서 개발한 실내공조 제어 시스템은 차내에 승객이 탑승 중일 때 항상 쾌적한 실내온도(t1 ~ t21)를 유지할 수 있도록 합니다. 현재(0분) 실내온도는 실외온도와 같습니다.
실내공조 제어 시스템은 실내온도를 조절하기 위해 에어컨의 전원을 켜 희망온도를 설정합니다. 희망온도는 에어컨의 전원이 켜져 있는 동안 원하는 값으로 변경할 수 있습니다. 실내온도와 희망온도가 다르다면 1분 뒤 실내온도가 희망온도와 같아지는 방향으로 1도 상승 또는 하강합니다. 실내온도가 희망온도와 같다면 에어컨이 켜져 있는 동안은 실내온도가 변하지 않습니다.
에어컨의 전원을 끄면 실내온도가 실외온도와 같아지는 방향으로 매 분 1도 상승 또는 하강합니다. 실내온도와 실외온도가 같다면 실내온도는 변하지 않습니다.
에어컨의 소비전력은 현재 실내온도에 따라 달라집니다. 에어컨의 희망온도와 실내온도가 다르다면 매 분 전력을 a만큼 소비하고, 희망온도와 실내온도가 같다면 매 분 전력을 b만큼 소비합니다. 에어컨이 꺼져 있다면 전력을 소비하지 않으며, 에어컨을 켜고 끄는데 필요한 시간과 전력은 0이라고 가정합니다.
실내공조 제어 시스템은 차내에 승객이 탑승 중일 때 실내온도를 t1 ~ t2도 사이로 유지하면서, 에어컨의 소비전력을 최소화합니다.
다음은 실외온도가 28도, t1= 18, t2 = 26, a = 10 b = 8인 예시입니다.
시간(분)/승객 탑승| 0 | x |
| 1 | x |
| 2 | o |
| 3 | o |
| 4 | o |
| 5 | o |
| 6 | o |
- 승객이 탑승 중인 2 ~ 6분의 실내온도를 18 ~ 26도 사이로 유지해야 합니다.
다음은 2 ~ 6분의 실내온도를 쾌적한 온도로 유지하는 방법 중 하나입니다.
시간(분)/승객 탑승/실내온도/희망온도| 0 | x | 28 | 26 |
| 1 | x | 27 | 26 |
| 2 | o | 26 | 26 |
| 3 | o | 26 | 26 |
| 4 | o | 26 | 26 |
| 5 | o | 26 | 26 |
| 6 | o | 26 | off |
- 0분의 실내온도는 항상 실외온도와 같습니다.
- 6분에 에어컨의 전원을 껐습니다.
0 ~ 5분에 에어컨의 희망온도를 26도로 설정했습니다. 0 ~ 1분에 희망온도와 실내온도가 다르므로 전력을 매 분 10씩, 2 ~ 5분에 희망온도와 실내온도가 같으므로 전력을 매 분 8씩 소비했습니다. 이때 총 소비전력은 52(= 2 × 10 + 4 × 8)입니다.
다음은 2 ~ 6분의 실내온도를 쾌적한 온도로 유지하는 또 다른 방법입니다.
시간(분)/승객 탑승/실내온도/희망온도| 0 | x | 28 | 24 |
| 1 | x | 27 | 24 |
| 2 | o | 26 | 24 |
| 3 | o | 25 | 24 |
| 4 | o | 24 | off |
| 5 | o | 25 | off |
| 6 | o | 26 | off |
0 ~ 3분에 에어컨의 희망온도를 24도로 설정해 전력을 매 분 10씩 소비했습니다. 이때 총 소비전력은 40(= 4 × 10)이며, 이보다 소비전력이 적어지는 방법은 없습니다.
실외온도를 나타내는 정수 temperature, 쾌적한 실내온도의 범위를 나타내는 정수 t1, t2, 에어컨의 소비전력을 나타내는 정수 a, b와 승객이 탑승 중인 시간을 나타내는 1차원 정수 배열 onboard가 매개변수로 주어집니다. 승객이 탑승 중인 시간에 쾌적한 실내온도를 유지하기 위한 최소 소비전력을 return 하도록 solution 함수를 완성해 주세요.
제한사항
- -10 ≤ temperature ≤ 40
- -10 ≤ t1 < t2 ≤ 40
- temperature는 t1 ~ t2 범위 밖의 값입니다.
- 1 ≤ a, b ≤ 100
- a는 에어컨의 희망온도와 실내온도가 다를 때의 1분당 소비전력을 나타냅니다.
- b는 에어컨의 희망온도와 실내온도가 같을 때의 1분당 소비전력을 나타냅니다.
- 2 ≤ onboard의 길이 ≤ 1,000
- onboard[i]는 0 혹은 1이며, onboard[i]가 1이라면 i분에 승객이 탑승 중이라는 것을 의미합니다.
- onboard[0] = 0
- onboard에 1이 최소 한 번 이상 등장합니다.
- 승객이 탑승 중인 시간에 쾌적한 실내온도를 유지하는 것이 불가능한 경우는 주어지지 않습니다.
2) 솔루션
class Solution {
fun solution(temperature: Int, t1: Int, t2: Int, a: Int, b: Int, onboard: IntArray): Int {
var answer: Int = 0
val max=maxOf(t2,temperature)+10
val min=minOf(t1,temperature)+10
val maxcost=maxOf(a,b)*onboard.size
val dp=Array<IntArray>(onboard.size+1){IntArray(51){maxcost}} //[시간][온도]
dp[0][temperature+10]=0
for(i in 1..dp.size-1){
for(j in min..max){
if(onboard[i-1]==1&&(j<t1+10||j>t2+10)){
dp[i][j]=maxcost
continue
}
val offcosts=ArrayList<Int>()
if(j-1<temperature+10&&j-1>=0) offcosts+=dp[i-1][j-1]
if(j+1>temperature+10&&j+1<=50) offcosts+=dp[i-1][j+1]
if(j==temperature+10) offcosts+=dp[i-1][j]
val offcost=offcosts?.minOrNull() ?:maxcost
val onUp=if(j+1<=50) dp[i-1][j+1]+a else maxcost
val onDown=if(j-1>=0) dp[i-1][j-1]+a else maxcost
val onEqual=dp[i-1][j]+b
dp[i][j]=minOf(offcost,onUp,onDown,onEqual)
}
}
answer=dp[dp.size-1].minOrNull() as Int
println(dp[dp.size-1].contentToString())
return answer
}
}-다이나믹 프로그래밍(DP)이용
-종류: Bottom-Up: 반복문 사용, Top-Down: 재귀함수이용
=>재귀함수이용시 시간초과가 뜨므로 반복문으로 풀었음
-온도 범위가 -10부터 40인데 dp배열에 넣으려면 음수는 안되므로 0에서 50으로 온도 축을 옮김.
-dp[i][j]에서 i는 시간, j는 온도 값은 이 좌표에 올때까지 든 총 코스트라고 할시, dp[i][j]는 dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1] 이 셋중 하나에서 오게 된다.
-경우의 수를 에어컨이 꺼진경우(온도 유지, 상승, 하강), 에어컨이 켜진경우(온도 유지, 상승, 하강)의 코스트들을 계산해서 최솟값이 dp[i][j]가 되도록 한다.
-그렇게 for문을 돌며 마지막까지 작성하면 시간이 마지막인 열에서 최솟값이 결과가 된다.
3. 아방가르드 타일링
1)문제
문제 설명
정우는 예술적 감각이 뛰어난 타일공입니다. 그는 단순한 타일을 활용하여 불규칙하면서도 화려하게 타일링을 하곤 합니다.
어느 날 정우는 가로 길이 n, 세로 길이 3 인 판을 타일링하는 의뢰를 맡았습니다. 아방가르드한 디자인 영감이 떠오른 정우는 다음과 같은 두 가지 종류의 타일로 타일링을 하기로 결정했습니다.
각 타일은 90도씩 회전할 수 있으며 타일의 개수는 제한이 없습니다.
n이 주어졌을 때, 이 두 가지 종류의 타일로 n x 3 크기의 판을 타일링하는 방법의 수를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 1 ≤ n ≤ 100,000
- 결과는 매우 클 수 있으므로 1,000,000,007 로 나눈 나머지를 return합니다.
2) 솔루션
class Solution {
fun solution(n: Int): Int {
//fn=afn-1 + bfn-2 +cfn-3 +...꼴의 점화식
//여기서 계수는 fn-t가 n개짜리를 만들려면 unique한 t개짜리를 붙여줘야 하므로 unique한 t개의 개수만큼 곱해준다.
//1-1, 2-2, 3-5, 4-2, 5-2, 6-4
//4부터 6까지는 반복
//즉 f(n)=f(n-1)+2f(n-2)+5f(n-3)+2f(n-4)+2f(n-5)+4f(n-6)+...
// f(n)-f(n-3)을 해주면 f(n)=f(n-1)+2f(n-2)+6f(n-3)+f(n-4)-f(n-5)
//4~6은 직접 구하고 그 뒤는 점화식으로 품
if(n==1) return 1
if(n==2) return 3
if(n==3) return 10
if(n==4) return 23
if(n==5) return 62
if(n==6) return 170
val dp=LongArray(n+1)
dp[1]=1L
dp[2]=3L
dp[3]=10L
dp[4]=23L
dp[5]=62L
dp[6]=170L
for(i in 7..n){
dp[i]=(dp[i-1]%1000000007L+(2*dp[i-2])%1000000007L+(6*dp[i-3])%1000000007L+dp[i-4]%1000000007L-dp[i-6]%1000000007L+1000000007L)%1000000007L
}
return dp[n].toInt()
}
}-풀이 방식은 주석에 달린대로
3)느낀점: 유니크한 타일링 방법을 직접 찾는것이 관건인 문제라 알고리즘보단 도형맞추기 문제같아서 조금 별로였다.
4. 숫자 타자 대회
1)문제
위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.
대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.
- 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
- 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
- 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
- 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.
예를 들어 1 위에 있던 손가락을 0 으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.
숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ numbers의 길이 ≤ 100,000
- numbers는 아라비아 숫자로만 이루어진 문자열입니다.
2) 솔루션
class Solution {
fun solution(numbers: String): Int {
var answer: Int = 0
val weight=Array(10){IntArray(10)}
//이동별 cost값 미리 저장
for(i in 0..9){
for(j in 0..9){
if(i==j){
weight[i][j]=1
continue
}
var tmpi=i
var tmpj=j
if(tmpi==0) tmpi=11
if(tmpj==0) tmpj=11
var ix=(tmpi-1)%3
var iy=(tmpi-1)/3
var jx=(tmpj-1)%3
var jy=(tmpj-1)/3
var total=0
while(ix!=jx||iy!=jy){
if(ix!=jx&&iy!=jy){
total+=3
ix+=if(ix>jx) -1 else 1
iy+=if(iy>jy) -1 else 1
}else if(ix!=jx){
total+=2
ix+=if(ix>jx) -1 else 1
}else if(iy!=jy){
total+=2
iy+=if(iy>jy) -1 else 1
}
}
weight[i][j]=total
}
}
val queue=ArrayDeque<Node>()
queue.addLast(Node(4,6,0,-1))
val costs=IntArray(numbers.length){7*numbers.length+1}
while(queue.isNotEmpty()){
val curNode=queue.removeFirst()
val idx=curNode.idx+1
if(idx>numbers.length-1) continue
val next=numbers[idx].toString().toInt()
//왼쪽 이동
if(next!=curNode.right){
val tmpcost=curNode.cost+weight[curNode.left][next]
var flag=true
//같은 것을 찾아 코스트가 들어가있는것 보다 현재것이 작으면 해당 노드 제거
//flag로 현재 노드보다 코스트가 작거나 같은 노드가 있는지 체크해 있으면 노드 추가 안함.
if(queue.isNotEmpty()){
val removed=ArrayDeque<Node>()
for(i in queue){
if(curNode.equal(i)&&curNode.cost<i.cost){
removed.addLast(i)
}else if(curNode.equal(i)&&curNode.cost>=i.cost){
flag=false
}
}
for(i in removed) queue.remove(i)
}
if(flag){
queue+=Node(next,curNode.right,tmpcost,idx)
if(tmpcost<costs[idx]) costs[idx]=tmpcost
}
}
//오른쪽 이동
if(next!=curNode.left){
val tmpcost=curNode.cost+weight[curNode.right][next]
var flag=true
//같은 것을 찾아 코스트가 들어가있는것 보다 현재것이 작으면 해당 노드 제거
//flag로 현재 노드보다 코스트가 작거나 같은 노드가 있는지 체크해 있으면 노드 추가 안함.
if(queue.isNotEmpty()){
val removed=ArrayDeque<Node>()
for(i in queue){
if(curNode.equal(i)&&curNode.cost<i.cost){
removed.addLast(i)
}else if(curNode.equal(i)&&curNode.cost>=i.cost){
flag=false
}
}
for (i in removed) queue.remove(i)
}
if(flag){
queue+=Node(curNode.left,next,tmpcost,idx)
if(tmpcost<costs[idx]) costs[idx]=tmpcost
}
}
}
return costs[numbers.length-1]
}
}
class Node(var left:Int, var right:Int, var cost:Int, var idx:Int){
fun equal(node:Node):Boolean{
if(idx!=node.idx) return false
val setA=setOf(left,right)
val setB=setOf(node.left,node.right)
if(setA==setB) return true
else return false
}
}
-좌측, 우측 엄지 위치와 현재까지 총 코스트, 현재 읽고있는 숫자 인덱스를 담은 노드를 클래스로 정의
-좌측, 우측 엄지가 겹치지 않도록 하면서 매 숫자마다 좌측이 움직이는 경우, 우측이 움직이는 경우로 나누어 탐색
-각 경우마다 앞서 큐에 들어간 노드들과 비교하여 현재 읽는 인덱스가 같고 좌우 손가락 위치가 동일할때(앞우측=뒤좌측&&뒤우측==앞좌측 인 경우도 동일하다 판별) 코스트를 비교하여 더 작은 값만 큐에 남아있도록 함.
-노드를 추가할때마다 인덱스별로 최소 코스트값을 갱신시킴
-큐가 빌때까지 반복하여 나온 마지막 최소 코스트값이 답
'코틀린-안드로이드' 카테고리의 다른 글
| 25일차)알고리즘 문제(연속 부분 수열 합의 개수, H-Index, 인사고과), 입문 강의 1~3주차 (0) | 2024.06.18 |
|---|---|
| 24일차)알고리즘 문제(고고학 최고의 발견, n + 1 카드게임, 귤 고르기, 괄호 회전하기) (1) | 2024.06.16 |
| 22일차)알고리즘 문제(N개의 최소공배수), 복습(배열생성, ArrayDeque,repeat,forEachIndexed) 개인과제(키오스크) (1) | 2024.06.13 |
| 21일차)알고리즘 문제(예상 대진표), 복습 및 과제 피드 (0) | 2024.06.12 |
| 20일차)알고리즘 문제(카펫, 행렬과 연산, 올바른 괄호의 갯수, 무지의 먹방 라이브), 복습(추상 클래스와 인터페이스) (1) | 2024.06.11 |