>알고리즘 문제
1. 테이블 해시 함수
1)문제
문제 설명
완호가 관리하는 어떤 데이터베이스의 한 테이블은 모두 정수 타입인 컬럼들로 이루어져 있습니다. 테이블은 2차원 행렬로 표현할 수 있으며 열은 컬럼을 나타내고, 행은 튜플을 나타냅니다.
첫 번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장됩니다. 완호는 이 테이블에 대한 해시 함수를 다음과 같이 정의하였습니다.
- 해시 함수는 col, row_begin, row_end을 입력으로 받습니다.
- 테이블의 튜플을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.
- 정렬된 데이터에서 S_i를 i 번째 행의 튜플에 대해 각 컬럼의 값을 i 로 나눈 나머지들의 합으로 정의합니다.
- row_begin ≤ i ≤ row_end 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환합니다.
테이블의 데이터 data와 해시 함수에 대한 입력 col, row_begin, row_end이 주어졌을 때 테이블의 해시 값을 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 1 ≤ data의 길이 ≤ 2,500
- 1 ≤ data의 원소의 길이 ≤ 500
- 1 ≤ data[i][j] ≤ 1,000,000
- data[i][j]는 i + 1 번째 튜플의 j + 1 번째 컬럼의 값을 의미합니다.
- 1 ≤ col ≤ data의 원소의 길이
- 1 ≤ row_begin ≤ row_end ≤ data의 길이
2)솔루션
class Solution {
fun solution(data: Array<IntArray>, col: Int, row_begin: Int, row_end: Int): Int {
var answer: Int = 0
data.sortWith(compareBy({it[col-1]},{-it[0]}))
answer=data[row_begin-1].map{it%(row_begin)}.sum()
for(i in row_begin+1..row_end){
println(answer)
answer= answer xor data[i-1].map{it%i}.sum()
}
return answer
}
}-문제 조건 대로 정렬
-이후 나머지 합을 가지고 xor연산
2. 주사위 고르기
1)문제
문제 설명
A와 B가 n개의 주사위를 가지고 승부를 합니다. 주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다. 각 주사위는 1 ~ n의 번호를 가지고 있으며, 주사위에 쓰인 수의 구성은 모두 다릅니다.
A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다. 각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다. 점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다.
A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다.
다음은 n = 4인 예시입니다.
주사위구성| #1 | [1, 2, 3, 4, 5, 6] |
| #2 | [3, 3, 3, 3, 4, 4] |
| #3 | [1, 3, 3, 4, 4, 4] |
| #4 | [1, 1, 4, 4, 5, 5] |
- 예를 들어 A가 주사위 #1, #2를 가져간 뒤 6, 3을 굴리고, B가 주사위 #3, #4를 가져간 뒤 4, 1을 굴린다면 A의 승리입니다. (6 + 3 > 4 + 1)
A가 가져가는 주사위 조합에 따라, 주사위를 굴린 1296가지 경우의 승패 결과를 세어보면 아래 표와 같습니다.
A의 주사위승무패| #1, #2 | 596 | 196 | 504 |
| #1, #3 | 560 | 176 | 560 |
| #1, #4 | 616 | 184 | 496 |
| #2, #3 | 496 | 184 | 616 |
| #2, #4 | 560 | 176 | 560 |
| #3, #4 | 504 | 196 | 596 |
A가 승리할 확률이 가장 높아지기 위해선 주사위 #1, #4를 가져가야 합니다.
주사위에 쓰인 수의 구성을 담은 2차원 정수 배열 dice가 매개변수로 주어집니다. 이때, 자신이 승리할 확률이 가장 높아지기 위해 A가 골라야 하는 주사위 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 승리할 확률이 가장 높은 주사위 조합이 유일한 경우만 주어집니다.
제한사항
- 2 ≤ dice의 길이 = n ≤ 10
- n은 2의 배수입니다.
- dice[i]는 i+1번 주사위에 쓰인 6개의 수를 담고 있습니다.
- dice[i]의 길이 = 6
- 1 ≤ dice[i]의 원소 ≤ 100
2)솔루션
class Solution {
fun solution(dice: Array<IntArray>): IntArray {
var answer: IntArray = intArrayOf()
val divs=div(dice.size)
var maxA=0
var maxAdices=divs[0]
for(i in divs){
var win=0
val A=ArrayList<IntArray>()
val B=ArrayList<IntArray>()
i.forEachIndexed{idx,el -> if(el) A+=dice[idx] else B+=dice[idx]}
val aResults=results(A)
val bResults=results(B)
for((ka,va) in aResults){
for((kb,vb) in bResults){
if(ka>kb) win+=va*vb
}
}
if(maxA<win){
maxA=win
maxAdices=i
}
}
for((i,v) in maxAdices.withIndex()){
if(v) answer+=i+1
}
return answer
}
fun results(dices:ArrayList<IntArray>):HashMap<Int,Int>{
val result=HashMap<Int,Int>() //값, 경우의 수
val q=ArrayDeque<Pair<Int,Int>>() //idx, sum
q.addLast(Pair(0,0))
while(q.isNotEmpty()){
val (idx, sum) = q.removeFirst()
if(idx==dices.size){
result.put(sum, result.getOrDefault(sum,0)+1)
continue
}
for(i in dices[idx]){
q.addLast(Pair(idx+1,sum+i))
}
}
return result
}
//주사위 나누기
fun div(size:Int):ArrayList<BooleanArray>{
val result=ArrayList<BooleanArray>()
val a= Triple(BooleanArray(size){false},0,0) //sum,idx
val q=ArrayDeque<Triple<BooleanArray,Int,Int>>()
q.addLast(a)
while(q.isNotEmpty()){
val (cur,sum,idx) = q.removeFirst()
if(sum==size/2){
result+=cur
continue
}
if(idx==size) continue
val next=cur.copyOf().also{ it[idx]=true }
q.addLast(Triple(next,sum+1,idx+1))
q.addLast(Triple(cur,sum,idx+1))
}
return result
}
}-BFS로 주사위를 반으로 나누는 경우를 모두 뽑아냄
-이후 주사위를 굴려서 나오는 값을의 경우의 수를 값- 경우의수 쌍으로 해시맵을 만든다
-각 해시맵에 대하여 비교해서 이기는 경우의 수를 구한다
>챌린지반 강의
1. 라이플 사이클
@on이 붙는 메소드는 보통 라이프사이클에 연관되어있는 메소드임.
가끔 onPause에서 메모리 부족시 앱이 죽었다가 onCreate로 돌아가기도함
이런경우를 대비해 종료시 View에 적힌 데이터가 저장되었다가 재시작시 onViewStateRestored()가 실행된다
스크롤해서 리사이클러뷰에선 더이상 보이지 않는 뷰홀더에 대해 onViewDetachedFromWindow가 실행된다.
스크롤해서 리사이클러뷰에 보이면 onViewAttached가 실행된다
onViewRecycled: 디테치된뷰에 대해 재사용될때 불림
2. 함수형 프로그래밍
1)종류
-절차지향: C
-객체지향: C++,Java
-함수형 프로그래밍:Kotlin, JavaScript
2)함수형 프로그리맹: 함수를 변수처럼 사용가능
-예시
fun something(){}
val some = ::something
fun main(){
some()
}
-예시2
val lambda1 = {num1:Int, num2:Int -> num1 + num2}
3)변수의 요소: 이름, 값, 타입
=>함수도 변수처럼 사용시 타입지정 가능
-예시: val lambda: (Int) -> Int = {num1:Int -> num1 * 10
4)Pure function: 파라미터만으로 함수동작이 결정되는것
-예시: 외부 값을 사용하거나 외부에 데이터를 저장하는 행위를 하려 할때
=>아닌경우: 외부 변수 num에 의해 영향을 받음
var num=0
fun add(x:Int) : Int{
val result = num + x
return result
}
=>아닌경우 외부 저장소에 파일을
=>맞는 경우: 순수 파라미터만으로 결정됨
fun add(x:Int, y:Int):Int{
return x+y
}
-Pure function이 중요한 이유: side Effect발생
-함수형 프로그래밍은 사이드 이펙트가 없는 퓨어 펑션을 만들기 위해 사용함
=>side Effect가 날만한 행위를 분리해서 최대한 몰아서 나중에 함.
sideEffect: 데이터 저장, 외부 값 사용, API 불러오기, 데이터 불러오기, Permission등 외부의 요소에 영향을 받는 것이 SideEffect발생시킴
5)순서: 함수형 프로그래밍은 각 함수의 실행 순서가 상관없음
=>어차피 사이드이펙트가 날만한 행위는 분리해서 따로 마지막에 실행하므로
-이점: 순서가 상관없이면 비동기로 동시에 실행이 가능해서 속도가 빨라짐
3. 확장 함수
-class A에 대하여 새로운 기능을 만들고 싶으면 생성하는것
-fun A.함수명(): 반환타입 = {}
=>A:수신객체: 클래스나 String같은 것도 A에 들어갈 수 있음
=>함수 본문에 this가 있으면 this는 수신객체를 의미함
>팀프로젝트
https://appdevelopjava.tistory.com/81
알람, 권한 부여, 애니매이션, 착발신 기록 가져오기
1. 알람1) 알람 추가 다이얼로그mainFbtnAddalarm.setOnClickListener { val builder = AlertDialog.Builder(this@MainActivity) builder.setTitle("알림 추가") builder.setIcon(R.mipmap.ic_launcher) val bindingDialog = DialogAlarmBinding.inflate(layou
appdevelopjava.tistory.com