기록

다익스트라 알고리즘 대표적인 최단경로 알고리즘 특정 노드에서 출발하여, 다른 모든 노드로 가는 최단경로 계산 그리디로 분류 (매 상황마다 가장 비용이 적은 노드를 선택하고 이를 반복하기 때문) 동작 과정 출발 노드를 설정한다 최단거리 테이블을 초기화한다 (출발 노드 자기 자신 0, 나머지는 무한) 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다 3번과 4번 과정을 반복한다 Kotlin 우선순위 큐로 구현한 다익스트라 알고리즘 (백준 1753번) import java.util.* import kotlin.collections.ArrayList const val INF = 1000000 fun main() { val ..

시간초과 코드 fun main() { val s = Solution() //println(s.solution(intArrayOf(1, 2, 1, 3, 1, 4, 1, 2))) println(s.solution(intArrayOf(1, 2, 3, 1, 4))) } class Solution { fun solution(topping: IntArray): Int { var answer: Int = 0 for(point in 0..topping.size-1) { val leftTopping = topping.copyOfRange(0, point + 1) val rightTopping = topping.copyOfRange(point + 1, topping.size) val leftToppingCount = le..

import java.util.LinkedList import java.util.Queue fun main() { val graph = arrayOf( intArrayOf(), intArrayOf(2,3,8), intArrayOf(1,7), intArrayOf(1,4,5), intArrayOf(3,5), intArrayOf(3,4), intArrayOf(7), intArrayOf(2,6,8), intArrayOf(1,7) ) val visited = BooleanArray(graph.size){ false } bfs(graph, 1, visited) } fun bfs(graph: Array, node: Int, visited: BooleanArray) { val queue: Queue = LinkedLi..

fun main() { val graph = arrayOf( intArrayOf(), intArrayOf(2,3,8), intArrayOf(1,7), intArrayOf(1,4,5), intArrayOf(3,5), intArrayOf(3,4), intArrayOf(7), intArrayOf(2,6,8), intArrayOf(1,7) ) var visited = BooleanArray(9){ false } dfs(graph, 1, visited) } fun dfs(graph: Array, v: Int, visited: BooleanArray) { visited[v] = true print("$v ") for(node in graph[v]) { if(!visited[node]) { dfs(graph, nod..

fun main() { var n = readLine()!!.toInt() var str = "" while(n > 0) { str = (n % 2).toString() + str n /= 2 } println(str) }

fun main() { val arr = intArrayOf(2,5,3,1,6,7,0,4,8,9) for(i in 0 until arr.size - 1){ for(j in 1 until arr.size -i) { if(arr[j-1] > arr[j]) { val temp = arr[j-1] arr[j-1] = arr[j] arr[j] = temp } } } println(arr.contentToString()) }

fun main() { val arr = intArrayOf(2,5,3,1,6,7,0,4,8,9) for(i in 0 until arr.size) { var minIndex = i for(j in i+1 until arr.size) { if(arr[minIndex] > arr[j]) { minIndex = j } } val tmp = arr[i] arr[i] = arr[minIndex] arr[minIndex] = tmp } println(arr.contentToString()) } 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복 현재 데이터의 상태와 상관 없이 무조건 모든 원소를 비교하고 위치를 바꾼다.

맨 왼쪽의 원소는 이미 정렬되어 있다고 가정하고, 두번째 원소부터 시작해서 왼쪽으로 순차적으로 현재 원소보다 큰 원소가 있다면 교체를 해주고, 또 다음 반복에서 그 왼쪽의 원소와 비교하여 또 큰 원소가 있다면 교체를 해주고, 이 작업을 반복하다가 마침내 현재 원소의 왼쪽 원소가 현재 원소보다 작은 경우를 만날 시에 브레이크로 중단하는 정렬 방식입니다. fun main() { val arr = intArrayOf(2,5,3,1,6,7,0,4,8,9) for(i in 1 until arr.size) { for(j in i downTo 1) { if(arr[j] < arr[j-1]) { val temp = arr[j] arr[j] = arr[j-1] arr[j-1] = temp } else break } } ..

기준데이터(피벗)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 일반적인 상황에서 제일 많이 사용되는 정렬 알고리즘 중 하나. 평균적으로 O(NlogN)의 시간복잡도를 가지며, 최악의 경우 O(N^2)의 시간복잡도를 가진다. fun main() { val array = intArrayOf(5,7,9,0,3,1,6,2,4,8) quickSort(array, 0, array.size - 1) // array.forEach { print("$it ") } print(array.contentToString()) } fun quickSort(arr: IntArray, start: Int, end: Int) { if(start >= end) return val pivot = start var..

https://school.programmers.co.kr/learn/courses/30/lessons/118666 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 요즘 유행하는 MBTI 관련 문제여서 재미있게 풀었다. 문제 접근 - 동점일 때 사전순 처리를 어떻게 할 것인가? class Solution { fun solution(survey: Array, choices: IntArray): String { var answer = "" val standardZeroJipyo = mapOf(0 to "RT", 1 to "CF", 2 to "JM", 3 to ..