[프로그래머스 kotlin] 합승 택시 요금

문제 시작지점 S에서 출발하여 2명의 사람이 각각 A지점과 B지점에 가야할 때 최단거리를 구하는 문제이다. 풀이 시작지점에서 출발하여 A, B를 돌도록 최단거리를 구하면 안된다. 그 이유는 한 지점에서 각각의 사람이 갈라져서 이동하기 때문이다. 예를들어 위의 사진의 경우 S에서 출발하여 1번노드로 이동후 B는 5 -> 3 -> 2 노드로 이동하고 A는 5 -> 6 노드로 이동하므로 각각의 경우를 따로따로 구해야 한다. 여기서 봐야할 점은 S에서 출발하여 A, B 로 각각 간다는점인데 이를 다시생각하면 한 지점에서 S, A, B지점으로 이동한 거리를 모두 합한 값이 된다. 따라서 각 지점에 대해 S, A, B 까지의 최단거리를 합한 후 가장 작은 값을 구하면 된다. data class Node(val en..

• format_list_bulleted 알고리즘
• · 2024. 4. 20.
• textsms

[백준 kotlin] 1753 최단경로

문제 수열의 부분수열중 일정값을 넘는 부분수열의 가장 짧은 길이를 구한다. 풀이 최단거리를 구해야하기 때문에 다익스트라를 이용하였다. 먼저 우선순위 큐에 들어갈 데이터를 정의하였다. 데이터는 index와 거리가 필요하므로 다음과 같이 data class를 정의하였다. data class Node(val index: Int, val distance: Int): Comparable { override fun compareTo(other: Node): Int = distance - other.distance } distance값을 기준으로 정렬한다. val (V, E) = readLine().split(" ").map { it.toInt() } val K = readLine().toInt() val dis..

• format_list_bulleted 알고리즘
• · 2024. 4. 18.
• textsms

[백준 kotlin] 1806 부분 합

문제 수열의 부분수열중 일정값을 넘는 부분수열의 가장 짧은 길이를 구한다. 풀이 투포인터를 사용하면 간단히 해결할 수 있다. start와 end를 각각의 포인터로 하여 해결한다. val (N, M) = readLine().split(" ").map { it.toInt() } val nums = readLine().split(' ').map { it.toInt() } var ans = Int.MAX_VALUE var end = 0 var tmp = 0 var start = 0 N, M값을 입력받고 필요한 변수를 선언한다. kotlin 에서 최대값의 경우 Int.MAX_VALUE로 설정할 수 있다. while (end < N) { while (end < N && tmp < M) { tmp += nums[en..

• format_list_bulleted 알고리즘
• · 2024. 4. 15.
• textsms

[백준 kotlin] 1260 DFS와 BFS

서론 코딩테스트 언어를 파이썬에서 코틀린으로 변경하였다. 가장큰 이유는 바로 안드로이드 직군에서 kotlin코테를 더 많이 본다는점... 코틀린과 파이썬의 문법은 천차만별이고 문법을 익힐 필요가 있기 때문에 이미 풀어본 문제들을 코틀린을 사용해서 다시 해결하였다. 문제 DFS및 BFS를 이용하여 문제를 해결한다. 풀이 기본적인 구현은 간단하기 때문에 사용한 문법을 정리하면서 알아본다. var graph = arrayOf() var visited = booleanArrayOf() var dfsAns = ArrayList() var bfsAns = ArrayList() 먼저 필요한 전역변수들을 선언한다. 그래프와 방문여부를 담을 변수, 정답을 출력할 변수이다. fun solve() = with(Buffer..

• format_list_bulleted 알고리즘
• · 2024. 4. 13.
• textsms

[프로그래머스 파이썬] 올바른 괄호

문제 풀이 스택을 이용하여 간단하게 해결할 수 있다. 먼저 "("의 경우와 ")"의 경우를 나눠서 생각한다. for i in s: if i == "(": stack.append("(") 반복문을 사용하여 s(여기서는 전체 괄호)중 하나씩 뽑아 진행한다. 만약 "("가 들어올 경우 스택에 그대로 추가시켜준다. else: if not stack: answer = False break if stack.pop() == ")": answer = False break ")"가 들어온 경우도 두가지 경우로 나누어 생각한다. 만약 )가 들어왔지만 스택이 비어있는 경우 이전에 "("가 없이 ")"가 들어온 경우이므로 괄호가 짝지어지지 않은 경우이다. 따라서 정답이 아니므로 False로 설정하고 break한다. 또한 po..

• format_list_bulleted 알고리즘
• · 2024. 4. 10.
• textsms

[코드트리 파이썬] 삼 오 무

문제 풀이 이분탐색을 이용해 해결하였다. 임의의 숫자 하나를 정한 후 해당 숫자가 우리가 구하려는 답보다 큰지 작은지만 판별하면 된다. 주어진 N은 Moo값을 건너뛴 숫자이므로 1, 2, Moo, 4, Moo, Moo, 7 의 순서로 진행하였을 때 N이 4라면 답은 7이된다. 따라서 N이 주어졌을 때 내가 가진 숫자가 N이 가리키는 숫자보다 큰지 작은지 판별한다. 판별법은 다음과 같아 Moo는 3과 5의 배수로 진행한다. 임의의 값이 주어졌을 때 해당값을 3으로 나눈 나머지는 1부터 해당 값까지의 숫자 중 3의배수의 숫자의 개수이므로 임의의 수를 3으로 나눈 나머지와 5로 나눈나머지를 뺀 후 공통된 15로 나눈 나머지를 더한 뒤 나온 수를 N값과 비교하여 판단하면 된다. 예를들어 주어진 N은 4 즉 7을..

• format_list_bulleted 알고리즘
• · 2024. 4. 7.
• textsms