방구석프로의 이야기

이 포스팅은 고돈호님의 이것이 안드로이드다 with 코틀린(한빛미디어)을 기반으로 작성되었습니다.

1.1 새 프로젝트 생성

[Create New Project] - [Empty Activity] - [NEXT] 새로운 프로젝트 생성

1.2 로그의 활용 

(d는 debug를 의미, 첫 번째 매개변수는 검색 용도로 사용되는 태그, 두 번째 매개변수는 출력할 메시지 입력)

MainActivity.kt을 다음과 같이 수정 단 import android.util.Log는 직접 import 해주기

package kr.co.kibeom.basicsyntax

import androidx.appcompat.app.AppCompatActivity
import android.os.Bundle
import android.util.Log

class MainActivity : AppCompatActivity() {
    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)

        Log.d("BasicSyntax", "로그를 출력합니다. method = Log.d")
    }
}

이를 실행시키면 다음과 같다.

이 후 안드로이드 스튜디오 하단의 [Logcat] 탭을 클릭해서 창을 연 후 Log.d의 태그로 입력했던 BasicSyntax를 검색하면 여러 로그 중 BasicSyntax에 해당하는 로그만 볼 수 있다.

1.3 결론

따라서 우리는 다음의 정보들을 알 수 있다.

Log : 코딩 시 코드의 흐름을 파악하기 위해 앱 외부에 출력하는 정보. 

Logcat : 출력되는 로그를 모아서 보는 도구

여러 로그들은 다음과 같다. (외울 필요는 없다.)

개념

크루스컬 알고리즘은 대표적인 최소 신장 트리 알고리즘입니다. 최소 신장 트리란 그래프가 주어져 있을 때 모든 노드들을 포함하고 있으며 사이클이 존재하지 않는 무방향 그래프를 의미합니다. 즉 모든 노드가 연결이 되어있어야 한다는 점과 사이클이 존재하지 않는다는 조건의 교집합이라고 할 수 있습니다. 다음 그림을 보겠습니다. (그림은 나동빈 님의 이것이 취업을 위한 코딩 테스트이다. 를 참고하였습니다.) 

위 그림의 경우 모든 노드들은 연결이 되어있고 사이클이 존재하지 않으므로 신장 트리 입니다. 간선의 개수는 노드의 개수 -1 인 것을 확인할 수 있습니다. 크루스컬 알고리즘은 가능한 신장 트리 중 가장 최소의 비용으로 신장 트리를 연결하는 알고리즘입니다. 과정은 다음과 같습니다.

1. 모든 간선 정보를 따로 리스트에 저장한다. 

2. 리스트에 저장된 간선 정보를 cost가 작은순으로 정렬한 후 사이클의 존재 유무를 파악한다.

3. 사이클이 아닐경우 두 노드를 연결한다.

4. 사이클일 경우 넘어간다. 

소스코드

https://www.acmicpc.net/problem/18352

문제 

문제 해결을 위한 과정

이 문제의 경우 BFS를 통해서 쉽게 해결할 수 있는 문제였습니다. 정답률은 32퍼센트로 좀 낮은 편인데 난이도에 비해서는 정답률이 조금 낮게 나온 것 같습니다. BFS라는 개념을 정확히 알면 쉬운 문제입니다. 만일 BFS를 잘 모르시겠다면 https://bgspro.tistory.com/15?category=981927

한번 보고 오시는걸 추천드립니다. 예시의 그림을 보면 노드가 양방향으로 연결이 된 것이 아닌 단방향으로 연결이 되어있는 것을 확인할 수 있습니다.  시작 지점부터 BFS방식을 통해 탐색을 해 나아가면 예시의 그림을 예로 들면 첫 번째로 탐색이 되는 2, 3 그리고 두 번째로 탐색이 되는 4를 통해 몇 번째로 탐색이 되느냐가 시작 지점 노드 1부터 얼마만큼의 거리가 떨어져 있는지를 의미하는 것이라고 보면 되겠습니다. 따라서 몇 번째로 탐색이 되는지 확인을 한 뒤 입력받은 k와 같다면 어떠한 리스트에 추가를 한 뒤 오름차순으로 정렬을 하면 되는 문제였습니다.

소스코드