본문 바로가기

코딩테스트 준비(kotlin)/자료구조12

[자료구조] 이분 그래프(Bipartite Graph)란 ? 이분 그래프의 개념이분 그래프(Bipartite Graph)는 정점을 두 개의 집합으로 나눌 수 있고, 같은 집합에 속한 정점끼리는 간선이 연결되지 않는 그래프입니다. 즉, 모든 간선이 한 집합의 정점에서 다른 집합의 정점으로만 연결됩니다이분 그래프의 특징- 이분 그래프인지 확인하는 방법은 BFS, DFS 탐색을 이용하면 된다.- 이분 그래프는 BFS를 할 때 같은 레벨의 정점끼리는 모조건 같은 색으로 칠해진다.- 사이클의 길이가 홀수이면 이분 그래프가 아니다. (예: 3개의 정점으로 이루어진 삼각형(사이클 길이 3)은 이분 그래프가 아니다)- 연결 성분의 개수(Connected Component)를 구하는 방법과 유사하다.- 모든 정점을 방문하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래.. 2025. 5. 8.
[백준 / 골드4] 문자열폭발 with kotlin 문자열 폭발 풀이 과정 처음에 풀이를 진행했을 때 단순하게 replace를 사용하였다 ->  문제 조건 : 문자열의 최대 크기가 1000000이었고, 계속해서 최대 길이의 문자열을 만들어내야 함으로 메모리 초과가 발생하였다스택을 이용하여 풀이를 진행하였다. package com.chanhue.algorithm.백준.골드fun main(){ val s = readLine()!! // 원본 문자열 입력 val bomb = readLine()!! // 폭발 문자열 입력 // 스택으로 사용할 MutableList 생성 val stack = mutableListOf() // 원본 문자열의 각 문자를 순회하며 스택에 push for(c in s){ sta.. 2025. 2. 5.
[프로그래머스,kotlin] 디스크 컨트롤러 (우선순위 큐로 구현) import java.util.PriorityQueueclass Solution { fun solution(jobs: Array): Int { // Job 데이터 클래스 정의 data class Job(val requestTime: Int, val duration: Int, val id: Int) // 요청 시간 순으로 정렬된 큐 val requestQueue = PriorityQueue(compareBy({ it.requestTime }, { it.id })) // 작업 시간이 짧은 순서로 정렬된 작업 대기 큐 val taskQueue = PriorityQueue(compareBy({ it.duration }, { it.r.. 2025. 1. 12.
[프로그래머스 kotlin] 프로세스 문제 설명운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다. 3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.현재 실행 .. 2025. 1. 7.

티스토리툴바