오늘 공부한 내용 정리(2024년 6월 25일)
코드카타 문제풀이
트리의 부모 찾기(Silver 2, 11725번)
문제 내용
문제 풀이 방법
루트가 1인 트리가 있고 트리 상 연결된 노드들의 정점이 주어질 때, 2번 노드부터 각 노드의 부모 노드를 순서대로 출력.
해결 코드(스포 주의)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import java.util.Queue
private var graph = arrayOf<MutableList<Int>>()
private var visited = booleanArrayOf()
private var parentNode = arrayOf<Int>()
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val nodeCnt = readLine().toInt()
graph = Array(nodeCnt +1) { mutableListOf() }
visited = BooleanArray(nodeCnt +1)
parentNode = Array(nodeCnt +1) { 0 }
for (i in 1 until nodeCnt) {
val relationship = readLine().split(" ").map { it.toInt() }
graph[relationship[0]].add(relationship[1])
graph[relationship[1]].add(relationship[0])
}
search()
val result = StringBuilder()
for (i in 2 until parentNode.size) {
result.append(parentNode[i]).append("\n")
}
println(result)
}
private fun search(start: Int = 1) {
val queue: Queue<Int> = LinkedList()
queue.add(start)
visited[start] = true
while (queue.isNotEmpty()) {
val data = queue.poll()
for (node in graph[data]) {
if (!visited[node]) {
queue.add(node)
visited[node] = true
parentNode[node] = data
}
}
}
}
풀이 과정
노드들의 관계를 보여줄 이중리스트 graph를 생성하고,
노드 방문 여부를 체크할 visited를 생성,
index번째 노드에 부모 node를 저장할 parentNode를 생성한다.
노드의 개수를 입력받은 nodeCnt를 생성한다. graph와 visited, parentNode의 길이를 nodeCnt +1로 정의한다. array와 list는 index 0부터 시작하기 때문에 혼동을 방지하기 위함이다.
nodeCnt번 반복하면서 노드 간의 관계(relationship)를 각 그래프의 index번째에 해당하는 곳에 서로의 데이터를 넣어준다. 그다음 search() 함수를 수행한다.
search함수에서는 bfs를 이용해 문제를 풀이한다. 큐를 생성해 주고, 첫 데이터인 1을 큐에 넣어준다. 방문 여부도 체크한다.
큐가 빌 때까지 그래프를 돈다.
큐에 제일 먼저 들어간 데이터를 빼주고(data),
graph의 data번째 데이터의 관계를 체크한다. 이미 한 번 방문한 데이터는 다시 체크하지 않는다.
처음 방문한 데이터의 visited를 true로 설정한다. 그리고 parentNode의 node번째 index를 data로 설정한다.
data가 부모이고, 반복하면서 도는 node가 자식 노드가 되기 때문이다.
search 함수 호출 후 데이터가 들어온 parentNode를 2번째 데이터부터 순서대로 출력한다.
문제 해결 과정
parentNode를 출력할 때 그냥 println()을 쓰면 시간 초과가 발생한다. 그 점만 주의하면 되겠다.
그리고 bfs와 dfs 모두 가능한데 부모 데이터를 찾아야 하니까 bfs 방식이 더 쉽게 문제를 해결할 수 있을 것 같다.
물론 dfs 풀이는 안 해봤지만 이론적으로만 보면 bfs가 더 편할 듯하다.
적록색약(Gold 5, 10026번)
문제 내용
문제 풀이 방법
적록색약인 사람은 빨간색과 초록색을 구분하지 못한다.
N x N의 리스트 형태의 입력이 주어질 때, 적록색약이 아닌 사람과 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력.
해결 코드(스포 주의)
import java.io.BufferedReader
import java.io.InputStreamReader
private val dx = listOf(-1, 1, 0, 0)
private val dy = listOf(0, 0, -1, 1)
private var graph = arrayOf<MutableList<Int>>()
private var colorBlindGraph = arrayOf<MutableList<Int>>()
private var visited = arrayOf<Array<Boolean>>()
private var searchNum = 1
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val size = readLine().toInt()
graph = Array(size) { mutableListOf() }
colorBlindGraph = Array(size) { mutableListOf() }
visited = Array(size) { Array(size) { false } }
for (i in 0 until size) {
val input = readLine()
val list = input.map { when (it) { 'R' -> 1 'G' -> 2 'B' -> 3 else -> 0 } }
val colorBlindList = input.map { when (it) { 'R' -> 2 'G' -> 2 'B' -> 3 else -> 0 } }
graph[i].addAll(list)
colorBlindGraph[i].addAll(colorBlindList)
}
var graphZoneCnt = 0
var colorBlindZoneCnt = 0
for (c in 1 .. 3) {
searchNum = c
for (i in graph.indices) {
for (j in graph[i].indices) {
if (graph[i][j] == searchNum && !visited[i][j]) {
visited[i][j] = true
graphZoneCnt++
search(i, j, graph)
}
}
}
}
// visited 초기화
visited = Array(size) { Array(size) { false } }
for (c in 2 .. 3) {
searchNum = c
for (i in colorBlindGraph.indices) {
for (j in colorBlindGraph[i].indices) {
if (colorBlindGraph[i][j] == searchNum && !visited[i][j]) {
visited[i][j] = true
colorBlindZoneCnt++
search(i, j, colorBlindGraph)
}
}
}
}
println("$graphZoneCnt $colorBlindZoneCnt")
}
private fun search(x: Int, y: Int, graph: Array<MutableList<Int>>) {
for (i in dx.indices) {
val nx = x + dx[i]
val ny = y + dy[i]
if (nx in graph.indices && ny in graph[0].indices) {
if (graph[nx][ny] == searchNum && !visited[nx][ny]) {
visited[nx][ny] = true
search(nx, ny, graph)
}
}
}
}
풀이 과정
리스트의 상하좌우를 탐색할 변수(dx, dy)를 생성하고, 정상인의 그래프(graph)와 적록색약의 그래프(colorBlindGraph)를 구분해서 생성한다. visited는 두 개에서 같이 쓰게 할 예정이다. searchNum은 R, G, B값을 찾기 위한 변수이다.
맵의 크기를 입력받는다(size).
graph, colorBlindGraph, visited를 size에 맞게 초기화한다.
size만큼 반복한다.
input(입력값)을 list와 colorBlindList로 각각 map을 이용해 list로 변환한다.
list에서는 R: 1, G: 2, B: 3으로 들어가는 값을 변경해 주고, colorBlindList에서는 R, G를 2로, B를 3으로 받아준다. 여기서 변경한 RGB값의 숫자로 searchNum을 변경해 가면서 탐색할 것이다.
일반인의 구역의 개수를 셀 변수(graphZoneCnt)와 적록색약의 구역의 개수를 셀 변수(colorBlindZoneCnt)를 생성한다.
이제 searchNum을 모두 탐색해 준다. 새로운 구역을 발견할 때마다 graph(colorBlide) ZoneCnt를 1씩 증가시키고, search()를 수행한다.
이중 for문으로는 하나의 searchNum을 모두 탐색해 주는 것이기 때문에 일반인은 1부터 3까지, 적록색약은 2부터 3까지 for를 돌려서 반복해 준다.
2번의 삼중 for문이 모두 종료되면 최종적인 graphZoneCnt와 colorBlindZoneCnt가 나온다. 그것을 출력하면 끝이다.
문제 해결 과정
Gold 5문제 치고는 어려움 없이 풀었던 문제이다. 그래도 골드라 실버보다는 어려웠지만 할만했다.
앱 개발 입문 개인 추가 도전과제(Lv.5)
버튼 액션
활동 내용 간단 정리
나만의 커스텀 버튼을 만들어서 버튼이 클릭되면 버튼 안에 들어 있는 image와 text가 변경되도록 해야 한다.
drawable 파일에 selector의 item에 state_pressed(클릭 상태에 따라 변경됨)를 설정해 준다.
state_pressed가 true, false에 따른 drawable을 각각 정의해 준다.
bg_home_finish_button.xml
<?xml version="1.0" encoding="utf-8"?>
<selector xmlns:android="http://schemas.android.com/apk/res/android">
<item android:state_pressed="true">
<shape>
<solid android:color="#FFEB3B" />
<corners android:radius="10dp"/>
</shape>
</item>
<item android:state_pressed="false">
<shape>
<solid android:color="#00BCD4" />
<corners android:radius="10dp"/>
</shape>
</item>
</selector>selector 안에 item을 만들어서 state_pressed를 설정할 수 있다.
설정한 item의 내부에 자신이 원하는 레이아웃을 구상하면 된다.
이제 생성한 drawable을 적용한다.
내가 만든 파일은 background용 drawable이기 때문에, xml의 background에 설정해 준다.
android:background="@drawable/bg_home_finish_button"background 외에도 imageView의 src, textView의 text, textSize 등등에도 drawable을 넣을 수 있다.
bg를 만들었으니 image와 text도 같이 생성해 적용해 주었다.
구현 결과
가입 정보를 data class에 담아서 intent로 전달하기
활동 내용 간단 정리
사용자의 정보를 담은 data class를 생성해 intent로 데이터를 전달해 최종적으로는 homeActivity에 받은 데이터를 띄워야 한다.
우선 User 클래스를 만들어 주겠다.
import android.os.Parcelable
import kotlinx.parcelize.Parcelize
@Parcelize
data class User(
val name: String?,
val id: String?,
val password: String?,
): ParcelableParcelable을 상속받는 데이터 클래스를 만들어 준다. 위의 @Parcelize 어노테이션은 Parcelable을 더 간단하게 구현하게 해주는 기능을 가지고 있다.
@Parcelize가 없으면 Pacelable의 함수들을 override 해서 데이터를 정의해 주어야 하는데 귀찮은 과정을 생략해 주는 것이다.
이제 User 데이터를 intent로 넘겨주는 작업을 한다.
val intent = Intent(this, SignInActivity::class.java)
val user = User(signUpNameEditText.text.toString(), signUpIdEditText.text.toString(), signUpPwEditText.text.toString())
intent.putExtra("user", user)putExtra()를 사용하는 것은 동일하다.
이제 데이터를 받는 부분에서는 다른 getExtra() 함수를 써야 한다.
userData = result.data?.getParcelableExtra("user", User::class.java) ?: User("", "", "")
idEditText.setText(userData.id)
pwEditText.setText(userData.password)Parcelable을 상속받았으니 getParcelableExtra()를 사용해 준다. 받아올 데이터의 id와 어떤 데이터 클래스로 받아올 건지 설정해 주면 된다.
이제 받아온 데이터를 사용해서 과제를 완료한다.
개인 공부(알고리즘 문제 풀이)
랜선 자르기(Silver 2, 1654번)
문제 내용
문제 풀이 방법
K개의 랜선이 주어지고 필요한 랜선의 개수 N이 주어질 때, K개의 랜선을 잘라서 N개의 랜선을 만들 수 있는 경우의 최댓값을 출력.
잘라서 만드는 랜선의 개수가 N개와 같을 수 없다면 N보다 커도 상관없다.
해결 코드(스포 주의)
import java.io.BufferedReader
import java.io.InputStreamReader
private var lan = mutableListOf<Int>()
private var cnt = 0
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val input = readLine().split(" ").map { it.toInt() }
val case = input[0]
cnt = input[1]
var max = 0
for (i in 0 until case) {
val num = readLine().toInt()
if (max < num) max = num
lan.add(num)
}
binarySearch(1, max / 2, max)
}
private fun binarySearch(start: Int, mid: Int, end: Int) {
if (start >= mid) {
var resultCut = 0
for (i in 0 until lan.size) {
resultCut += lan[i] / end
}
if (resultCut < cnt) println(start)
else println(end)
return
}
var cut = 0 // midValue로 자른 값의 합.
for (i in 0 until lan.size) {
cut += lan[i] / mid
}
// 자른 값(cut)이 구해야 하는 양(cnt)보다 크거나 같으면 mid를 기준으로 이전의 값들은 모두 정답이 아니게 된다.
if (cut >= cnt) {
// mid 이후의 값으로 범위를 다시 설정해 재귀 함수 호출
binarySearch(mid, mid + (end - mid) / 2, end)
}
// 자른 값(cut)이 구해야 하는 양(cnt)보다 작은 경우 mid를 기준으로 이후의 값들은 모두 정답이 아니게 된다.
else {
// mid 이전의 값으로 범위를 다시 설정해 재귀 함수 호출
binarySearch(start, start + (mid - start) / 2, mid)
}
}
풀이 과정
각각의 랜선의 길이를 불러올 lan 변수를 생성한다.
잘라야 할 랜선의 개수를 담을 cnt 변수를 생성한다.
input의 0번째 index를 case 변수로 저장해 for문으로 반복한다.
for문을 돌면서 최댓값을 구하기 위해 max 변수를 생성한다.
lan에 입력받은 값을 넣어 준다.
binarySearch() 함수를 수행한다.
binarySearch에 사용하기 위해 start를 1로, end를 max로 mid를 max / 2로 설정해 이분 탐색을 활용할 준비를 한다.
start가 mid보다 크거나 같은 경우는 mid가 0인 경우와 탐색으로 인해 start와 mid가 같아진 경우에 위 조건에 걸리게 된다.
resultCnt를 생성하고 lan의 각각의 데이터에 end를 나눠준 값을 resultCnt에 더해준다.
start와 mid가 같은 경우에는 탐색을 마쳐서 end가 start, mid와 1밖에 크지 않다.
resultCnt가 cnt보다 크면 자른 값의 최댓값은 start가 되기 때문에 출력해 주고 아닌 경우는 end를 출력하고 return 한다.
조건에 걸리지 않았을 때는 mid를 기준으로 lan의 각 데이터를 나눈 값을 더한 값을 cut를 생성한다.
자른 값 cut가 구해야 하는 양 cnt보다 크거나 같으면 mid를 기준으로 한 이전의 값들은 모두 정답이 아니게 된다(계속 작아져 봤자 cut만 커진다).
이럴 때는 start를 mid로 설정하고, mid를 mid + (end - mid) / 2로 설정하고, end는 그대로 둔 상태의 파라미터로 재귀를 돌린다..
위 조건에 부합하지 않으면 mid를 기준으로 이후의 값은 정답이 아니다(값이 계속 커져 봤자 cut가 계속 줄어들어서 볼 필요도 없다).
이 때는 start를 그대로 두고, mid와 end만 변경해 줘서 재귀를 돌리면 된다.
문제 해결 과정
바이너리 서치와 파라매트릭 서치를 이용해서 문제를 푸는 방법이 일반적이다. 나도 그렇게 풀었고.
바이너리 서치는 알고 있던 개념인데 실제로 써본 건 이번이 처음이다. 내일 알고리즘을 풀 때는 바이너리 서치 문제 좀 풀어봐야겠다.
파라매트릭 서치는 바이너리 서치와 밀접한 관계에 있다고 들었다. 내일 그에 대한 개념을 공부해 블로그에 올리겠다.
오늘 공부 내용 정리 및 회고
추가적으로 온 개인 과제 후딱 해치우고 알고리즘 문제만 풀었던 날이다
solved ac class 2 문제를 모두 마무리했다.
class 2문제 마무리하면서 본 랜선 자르기 문제에 쓰인 알고리즘들을 내일 공부해 볼 생각이다.
'♞ | 공부일지' 카테고리의 다른 글
| [Kotlin, 내일배움캠프] 공부일지(2024-06-27) (0) | 2024.06.27 |
|---|---|
| [Kotlin, 내일배움캠프] 공부일지(2024-06-26) (0) | 2024.06.26 |
| [Android, 내일배움캠프] 공부일지(2024-06-24) (0) | 2024.06.24 |
| [Android, 내일배움캠프] 공부일지(2024-06-21) (0) | 2024.06.21 |
| [Android, 내일배움캠프] 공부일지(2024-06-20) (0) | 2024.06.20 |
댓글