>알고리즘 문제
1. 코딩 테스트 공부
1)문제
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.
알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다.
문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.
예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.
- A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
- B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.
풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.
- 알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
- 코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
- 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.
- 문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.
당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.
초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.
모든 문제들을 1번 이상씩 풀 필요는 없습니다. 입출력 예 설명을 참고해주세요.
제한사항
- 초기의 알고력을 나타내는 alp와 초기의 코딩력을 나타내는 cop가 입력으로 주어집니다.
- 0 ≤ alp,cop ≤ 150
- 1 ≤ problems의 길이 ≤ 100
- problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
- alp_req는 문제를 푸는데 필요한 알고력입니다.
- 0 ≤ alp_req ≤ 150
- cop_req는 문제를 푸는데 필요한 코딩력입니다.
- 0 ≤ cop_req ≤ 150
- alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
- 0 ≤ alp_rwd ≤ 30
- cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
- 0 ≤ cop_rwd ≤ 30
- cost는 문제를 푸는데 드는 시간입니다.
- 1 ≤ cost ≤ 100
정확성 테스트 케이스 제한사항
- 0 ≤ alp,cop ≤ 20
- 1 ≤ problems의 길이 ≤ 6
- 0 ≤ alp_req,cop_req ≤ 20
- 0 ≤ alp_rwd,cop_rwd ≤ 5
- 1 ≤ cost ≤ 10
2)솔루션
class Solution {
fun solution(alp: Int, cop: Int, problems: Array<IntArray>): Int {
var answer: Int = 0
val maxAlp=problems.map{it[0]}.maxOrNull() as Int
val maxCop=problems.map{it[1]}.maxOrNull() as Int
//초기 150, 0 에 req 150,150, 문제풀이시 30,2 씩 준다고 가정
//그러면 최대 150+2250 = 2400
val dp = Array(2401){IntArray(2401){Int.MAX_VALUE}}
for(i in alp..maxOf(maxAlp,alp)){
for(j in cop..maxOf(maxCop,cop)){
dp[i][j]=i+j-alp-cop
}
}
var min=Int.MAX_VALUE
for(i in alp..2400){
for(j in cop..2400){
if(i>=maxAlp&&j>=maxCop){
min=minOf(min,dp[i][j])
continue
}
if(dp[i][j]>=min) continue
for(k in problems){
if(k[0]>i||k[1]>j) continue
val ni=i+k[2]
val nj=j+k[3]
if(ni>2400||nj>2400) continue
dp[ni][nj]=minOf(dp[ni][nj],dp[i][j]+k[4])
}
}
}
return min
}
}-초기값이 150, 0 이고 req가 150,150이고 cost가 1에 reward가 30,2인 경우 최대 150+30*75=2400까지 올라갈 수 있으므로 dp의 크기를 2401로 정하였다
-초기값은 공부로 alp와 cop를 올리는 방식으로 dp값을 설정
-dp에서 i,j가 max req값 이상이면 min을 갱신하는 식으로 체크하여 min값이 결과가 된다.
2. 베스트앨범
1)문제
문제 설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
제한사항- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.
2)솔루션
class Solution {
fun solution(genres: Array<String>, plays: IntArray): IntArray {
var answer = intArrayOf()
//장르별로 나누기
val map= HashMap<String,List<Pair<Int,Int>>>()
for((idx,v) in genres.withIndex()){
val list = map.getOrDefault(v,listOf())
map.put(v,listOf(list,listOf(Pair(idx,plays[idx]))).flatten())
}
val result=ArrayList<List<Pair<Int,Int>>>()
for((k,v) in map){
result+=v.sortedWith(compareBy<Pair<Int,Int>>{-it.second}.thenBy{it.first})
}
result.sortByDescending{list -> list.map{it.second}.sum()}
answer= result.map{it.slice(0..minOf(1,it.size-1))}.flatten().map{it.first}.toIntArray()
return answer
}
}-장르별로 나눈뒤 각 장르별 음악을 재생수에 내림차순 이후 인덱스에 오름차순정렬하여 모아둔다.
-이후 각 장르별 재생수합을 기준으로 정렬후 각 장르별로 2개 이하만 남겨서 모은다.
>Compose특강
@flowWithLifecycle(lifecycle): 액티비티나 프래그먼트의 생명주기와 연결되어 정보를 수집하도록 하는 역할
-두번째 인자로 Lifecycle.State.STARTED같은 거를 넣으면 어느 시점에 정보를 수집할지 정할 수 있다.
-없으면 기본이 STARTED나 그 이후(RESUME이나 DESTROY제외)에서 일때 데이터를 수집하도록 한다.
-예시
lifecycleScope.launch {
viewModel.someFlow
.flowWithLifecycle(lifecycle, Lifecycle.State.STARTED)
.collect { data ->
// 데이터를 UI에 반영
}
}
1. Composable
-함수 위에 @Composable 어노테이션을 적어 선언하여 만들다.
-인터페이스를 만들고 동작방식을 정의하는 역할
(1)StateFul Composable
-앱 실행중 변경할 수 있는 모든 값으로 정의.
=>텍스트 필드 문자열, 체크박스 상태등
-데이터 변화에 따라 UI가 반응하도록 상태관리가 핵심
<1>상태(state): 변경 가능한 값. 주로 MutableState나 State를 다룸
<2>Stateful Composable: 상태 유지 관리 함수. 상태변경시 UI자동 없데이트
<3>상태 Hoisting: 상태를 상위로 이동시켜 여러 composable에서 상태를 공유하거나 관리가 쉽게 만드는것
-예시:
@Composable
fun Counter() {
var count by remember { muableStateOf(0) }
Button(onClick = { count.value++ }) {
Text("Clicked ${count.value} times")
}
}
-remember: 컴포서블이 재구성동안 상태를 유지하게 해줌
-mutableStateOf: 값이 변경될때마다 UI를 다시 그리도록 상태 관찰
(2)Stateless Composable
-내부적으로 자체 상태를 유지하지 않는 컴포저블 함수
-모든 필요 데이터를 인자로 받아 UI랜더링
=>장점: 상태가 외부인자로 관리되므로 재사용성 높고 단순함
2. Layout
-정렬 방식에 대한 가이드가 없으면 Compose는 요소를 겹치게 표현하므로 레이아웃이 필요
(1)Column: 항목을 세로로 배치
-요소 위치 설정
<1>verticalArrangement: Arrangement. ~
<2>horizontalAlignment: Alignment.~
(2)Row: 항목을 가로로 배치
-요소 위치 설정
<1>verticalAlignment: Alignment.~
<2>horizontalArrangement: Arrangement.~
(3)Box: 요소를 다른 요소 위에 놓음
3. Componet
(1)Scaffold: 상하단 앱바와 플로팅버튼을 제공하는 레이아웃역할
-예시
@Composable
fun ScaffoldExample() {
var presses by remember { mutableIntStateOf(0) }
Scaffold(
topBar = {
TopAppBar(
colors = topAppBarColors(
containerColor = MaterialTheme.colorScheme.primaryContainer,
titleContentColor = MaterialTheme.colorScheme.primary,
),
title = {
Text("Top app bar")
}
)
},
bottomBar = {
BottomAppBar(
containerColor = MaterialTheme.colorScheme.primaryContainer,
contentColor = MaterialTheme.colorScheme.primary,
) {
Text(
modifier = Modifier
.fillMaxWidth(),
textAlign = TextAlign.Center,
text = "Bottom app bar",
)
}
},
floatingActionButton = {
FloatingActionButton(onClick = { presses++ }) {
Icon(Icons.Default.Add, contentDescription = "Add")
}
}
) { innerPadding ->
Column(
modifier = Modifier
.padding(innerPadding),
verticalArrangement = Arrangement.spacedBy(16.dp),
) {
Text(
modifier = Modifier.padding(8.dp),
text =
"""
This is an example of a scaffold. It uses the Scaffold composable's parameters to create a screen with a simple top app bar, bottom app bar, and floating action button.
It also contains some basic inner content, such as this text.
You have pressed the floating action button $presses times.
""".trimIndent(),
)
}
}
}
-Scaffold( topBar = { ~ }, bottomBar = { ~ }, floatingActionButton = { ~ } ){ innerPadding -> ~} 의 형식
-innerPadding의 경우 디폴트로 사용할 수 있는 패딩값. 말그대로 가이드라인역할을 하는 패딩값임. 사용하든 안하든 상관 없음
=>내부 컨텐츠에 패딩을 넣는다면 innerPadding값을 사용하도록 제안하는 역할
(2)앱바
<1>상단 앱바
-기본형태: TopAppBar( colors = TopAppBarDefaults.topAppBarColors( containerColor = ~, titleContentColor = ~,), title = { ~})
-내부 컨텐트 정렬 위치에 따라 CenterAlignedTopAppBar, MediumTopAppBar, 그리고 높이가 큰 앱바를 원하면 TopAppBarDefaults
@Composable내에서 val scrollBehavior = TopAppBarDefaults.enterAlwaysScrollBehavior(rememberTopAppBarState()를 선언하면 아래로 스크롤시 앱바가 펼쳐짐
<2>하단 앱바
-기본 형태
BottomAppBar(
actions = {
IconButton(onClick = { /* do something */ }) {
Icon(Icons.Filled.Check, contentDescription = "Localized description")
}
IconButton(onClick = { /* do something */ }) {
Icon(
Icons.Filled.Edit,
contentDescription = "Localized description",
)
}
IconButton(onClick = { /* do something */ }) {
Icon(
Icons.Filled.Mic,
contentDescription = "Localized description",
)
}
IconButton(onClick = { /* do something */ }) {
Icon(
Icons.Filled.Image,
contentDescription = "Localized description",
)
}
},
floatingActionButton = {
FloatingActionButton(
onClick = { /* do something */ },
containerColor = BottomAppBarDefaults.bottomAppBarFabColor,
elevation = FloatingActionButtonDefaults.bottomAppBarFabElevation()
) {
Icon(Icons.Filled.Add, "Localized description")
}
}
)
=>아이콘과 플로팅 버튼이 떠있는 형태로 클릭동작을 설정 할 있다.
(3)버튼
<1>종류: 일반, 전환, 슬라이더, 칩, 플로팅작업 버튼등이 있다.
[1]일반버튼
-채워진 버튼: Button
-채워진 색조버튼: FilledTonalButton
-윤곽선 버튼: OutlinedButton
-돌출 버튼: ElevatedButton
-텍스트 버튼: TextButton
<2>구조
Button(onClick = { onClick() }) {
Text("Filled")
}
(4)텍스트
:Text(modifier =~, text =~ )
<1>text필드:
-문자열: " ~ "
-리소스: stringResource(R.string.~)
<2>color =
<3>fontSize
<4>fontStyle: 이텔릭같은것
<5>fontWeight: FontWeight.Bold =>굵기
<6>fontFamily: FontFamlily.~ =>폰트
=>다른것들도text처럼 리소스에서 가져오기도 가능
(5)텍스트필드: 텍스트 입력, 수정 가능
:TextField(value = text, onValueChange = {text = it}, label = {Text("Label")})
-value= text
-onValueChange = {text =it
-label ={ Text("label") }: 상단에 작게 제목처럼 뜸
(6)이미지
<1>Image: 이미지 로드
Image(
painter = painterResource(id = R.drawable.dog),
contentDescription = stringResource(id = R.string.dog_content_description)
)<2>AsyncImage: 인터넷 이미지 로드
AsyncImage(
model = "https://example.com/image.jpg",
contentDescription = "Translated description of what the image contains"
)
(7)스위치: 스위치 형태의 버튼
@Composable
fun SwitchMinimalExample() {
var checked by remember { mutableStateOf(true) }
Switch(
checked = checked,
onCheckedChange = {
checked = it
}
)
}
(8)체크박스: 체크박스로 체크여부 확인
@Composable
fun CheckboxMinimalExample() {
var checked by remember { mutableStateOf(true) }
Row(
verticalAlignment = Alignment.CenterVertically,
) {
Text(
"Minimal checkbox"
)
Checkbox(
checked = checked,
onCheckedChange = {
checked = it
},
)
}
Text(
if (checked) {
"Checkbox is checked"
} else {
"Checkbox is unchecked"
}
)
}
(9)리스트: 어댑터뷰같은 역할을 하는
<1>일반형태: Column 혹은 Row를 반복해서 표시
@Composable
fun MessageList(messages: List<Message>) {
Column(...) {
messages.forEach { message ->
Text(message)
}
}
}<2>Lazy: 수없이 많은 항목이나 길이를 모르는 목록 표시할때 이용. 성능상 문제 해결
=>LazyColumn, LazyRow, LazyVerticalGrid, LazyHorizontalGrid, LazyVerticalStaggeredGrid, LazyHorizontalStaggeredGrid,
[1] item으로 표시하는 방법: 단일, 다중, 다중 by collection
LazyColumn {
items(messages) { message ->
MessageRow(message)
}
items(10){ index ->
Text(text = "Item: $index")
}
item {
Text(text = "Last item")
}
}[2]그리드 뷰의 열의 너비나 행의 높이 설정&셀의 확장 방식
LazyVerticalGrid(
columns = GridCells.Adaptive(minSize = 30.dp)
) {
item(span = {
// LazyGridItemSpanScope:
// maxLineSpan
GridItemSpan(maxLineSpan)
}) {
CategoryCard("Fruits")
}
// ...
}[3]스테글드 그리드뷰 - 아이템간 거리, 정렬방식
LazyVerticalStaggeredGrid(
columns = StaggeredGridCells.Adaptive(200.dp),
verticalItemSpacing = 4.dp,
horizontalArrangement = Arrangement.spacedBy(4.dp),
content = {
items(randomSizedPhotos) { photo ->
AsyncImage(
model = photo,
contentScale = ContentScale.Crop,
contentDescription = null,
modifier = Modifier.fillMaxWidth().wrapContentHeight()
)
}
},
modifier = Modifier.fillMaxSize()
)
3. modifier
(1)역할
-컴포저블 크기, 레이아웃, 동작 및 모양 변경
-접근성 라벨같은 정보 추가
-사용자 입력 처리
-요소 클릭가능, 스크롤 가능, 드래그 가능, 확대 축소 가능
(2)유의점: 순서에따라 결과가 달라질 수있으므로 주의해야 함
=>예시: clickable().padding()하면 전체클릭이 되나 padding().clickable()하면 클릭 범위가 패딩만큼 줄어들음
(3)종류
-padding(): 패딩을 줌
-fillMaxWidth(), fillMaxHeight, fillMaxSize: 상위요소로 부터 부여받은 최대 크기를 채움
-clickable( onClick = ~): 클릭 가능하도록 함
-size(width =~, height =~): 고정 너비값을 만들음
-requiredSize(): 상위 요소로 부터 받은 제약조건을 만족 못하는경우(더 큰경우)제약을 무시하고 사이즈 고정을 원하면 사용
-weight( ~f): Row나 Column에서 사용가능. layout_weight랑 같은 기능
-background( , shape= ~):
=>Color뿐만 아니라 Brush를 이용해 그라데이션이나 패턴, ImageBitmap적용 가능
=>background에서 설정한 shape는 배경만 바꾸고 내부에 담긴 컨텐츠에는 영향을 주지못함
-clip(): 내부 컨텐츠까지 잘라낸다
@Shape인스턴스:
<1>RoundedCornerShape(topStart=,topEnd=,bottomEnd=,bottomStart=): 모서리가 둥근 사각형을 만들음. 각 모서리마다 설정도 가능. dp값 하나만 쓰면 전체 적용
<2>CircleShape: 기본형이 정사각형이면 원형, 아니면 타원형이 된다.
<3>CutCornerShape( topStart=,topEnd=,bottomEnd=,bottomStart=):모서리가 잘린 형태의 도
-paddingFromBaseline(top= ,bottom= , start= , end= ):
-offset(x= , y= ): 원래위치를 기준 (0, 0)으로 레이아웃 배치
=>양수는 오른쪽, 아래 / 음수는 왼쪽, 위
@dp값 설정을 하려면 숫자.dp로 중간에 .을 넣어야한다.
4. Resources 사용법
(1) stringResource
<1>가져가 쓰기: stringResource(R.string.compose)
<2>Formatting:
<string name="congratulate">Happy %1$s %2$d</string>
stringResource(R.string.congratulate, "New Year", 2021)@%1, %2는 언어에 따른 순서가 달라질 수 있으므로 입력 순서를 의미한다.
(2) Dimension:dp값 같은것
<dimen name="padding_small">8dp</dimen>
dimensionResource(R.dimen.padding_small)
(3) Colors
<color name="purple_200">#FFBB86FC</color>
color = colorResource(R.color.purple_200)
(4) ColorScheme :내장된 색상값
-예시
HorizontalDivider(color = MaterialTheme.colorScheme.primary)