본문 바로가기

코딩테스트 준비(kotlin)61

[자료구조] 이분 그래프(Bipartite Graph)란 ? 이분 그래프의 개념이분 그래프(Bipartite Graph)는 정점을 두 개의 집합으로 나눌 수 있고, 같은 집합에 속한 정점끼리는 간선이 연결되지 않는 그래프입니다. 즉, 모든 간선이 한 집합의 정점에서 다른 집합의 정점으로만 연결됩니다이분 그래프의 특징- 이분 그래프인지 확인하는 방법은 BFS, DFS 탐색을 이용하면 된다.- 이분 그래프는 BFS를 할 때 같은 레벨의 정점끼리는 모조건 같은 색으로 칠해진다.- 사이클의 길이가 홀수이면 이분 그래프가 아니다. (예: 3개의 정점으로 이루어진 삼각형(사이클 길이 3)은 이분 그래프가 아니다)- 연결 성분의 개수(Connected Component)를 구하는 방법과 유사하다.- 모든 정점을 방문하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래.. 2025. 5. 8.
[백준 1697] 숨바꼭질 with kotlin 문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.출력수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.package com.chanhue.algorithm.백준.실버import jav.. 2025. 5. 4.
[kotlin 프로그래머스] 우주신과의 교감 1774 (with kotlin) package com.chanhue.algorithm.백준.골드import kotlin.math.sqrtfun main() { // N: 우주신의 수, M: 이미 연결된 통로 수 val (n, m) = readLine()!!.split(" ").map { it.toInt() } // 각 우주신(혹은 황선자)의 좌표 정보를 저장하는 리스트 val node = mutableListOf>() // 이미 연결된 통로 정보 (정점 번호 쌍) val alreadyConnected = mutableListOf>() // 좌표 입력 받기 repeat(n) { val (x, y) = readLine()!!.split(" ").map { it.toInt() } .. 2025. 4. 19.
[kotlin] 별자리 만들기 별자리 만들기 문제 및 입출력 풀이 접근 별자리를 잇는다? -> 그래프 형식으로 나오겠구나 ?선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용 -> 최소신장트리(MST)를 구축하면 되겠구나? 풀이 코드  package com.chanhue.algorithm.백준.골드import java.util.PriorityQueueimport kotlin.math.sqrtfun main() { val n = readLine()!!.toInt() val node = mutableListOf>() repeat(n) { val (x, y) = readLine()!!.split(" ").map { it.toDouble() } node... 2025. 4. 12.

티스토리툴바