본문 바로가기
728x90

자료구조&알고리즘15

[백준] 1260번 : DFS와 BFS (Kotlin) 코딩테스트에서 가장 출제율이 높다는 DFS와 BFS를 백준 대표 예제를 통해 공부해 보겠습니다. 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import java.util.* fun main() { val (n,m,v) = readLine()!!.split(" ").map {it.toInt()} val graph = Array(n+1) {IntArray(n+1)} var visit = ArrayList() repeat(m) { val (x,y) = readLine()!.. 2023. 2. 22.
[자료구조] Kotlin으로 자료구조 이해하기 - PriorityQueue(우선순위 큐) PriorityQueue PriorityQueue(우선순위 큐)는 Queue처럼 선입선출(FIFO)의 구조를 갖출 것 같지만 그렇지 않고 내부적으로 이진트리의 형식을 갖추고 있기 때문에 오름차순 혹은 내림차순으로 데이터를 저장합니다. 따라서 일반적인 Queue(큐)는 가장 먼저 들어간 데이터가 가장 먼저 나오는 방식이지만 PriorityQueue(우선순위 큐)는 들어간 순서에 관계없이 오름차순의 경우 가장 작은 값이, 내림차순의 경우 가장 작은 큰 값이 반환되는 방식입니다. 우선순위 큐의 데이터에 접근하는 방법은 큐와 유사하며 이전 포스팅에서 확인할 수 있습니다. 사용예시와 함께 자세히 알아보겠습니다. [자료구조] Kotlin으로 자료구조 이해하기 - Queue(큐) Queue Queue의 사전적 정의는.. 2023. 2. 9.
[알고리즘] 그리디 알고리즘 (Kotlin) 그리디 알고리즘 그리디(Greedy) 알고리즘, 탐욕 알고리즘이라고도 합니다. 그리디 알고리즘은 여러 가지 경우 중 현재 상황에서 최적의 경우를 선택해 최종적인 결과를 도출해 내는 알고리즘입니다. 이때, 최적의 경우는 문제에 제시된 '최대/최소, 오름차순/내림차순' 같은 조건을 따르면 됩니다. 매 순간 '최적'의 경우를 선택하는 알고리즘이기 때문에 어느 순간 최적의 선택일지라도 전체의 경우에서 최적의 선택이 아닐 수도 있습니다. 따라서 현재의 선택이 전역적으로도 최적의 선택인지를 확인하는 과정이 필요합니다. 대표적인 예시로 거스름돈과 관련된 [백준 11047번 : 동전0] 문제를 해결해 보겠습니다. 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000.. 2023. 1. 30.
[백준] 1929번 : 소수 구하기, 에라토스테네스의 체 (Kotlin) 에라토스테네스의 체 에라토스테네스의 체는 2~N의 수 중 소수를 판별하는 알고리즘입니다. 해당 알고리즘의 정의를 요약하자면 2부터 N까지의 수 중 2의 배수, 3의 배수, 4의 배수 ... 제곱근N의 배수까지 나눠서 걸러지지 않고 남아 있는 수들이 모두 소수가 된다는 내용입니다. 기존의 소수를 구하는 방식인 소수는 1과 자기 자신만을 약수로 가진다는 조건에 따라 범위 내의 모든 수를 판별하는 방식보다 훨씬 실행속도가 빠르다는 장점이 있습니다. ☞ 예를 들어, 2부터 16까지의 수 중 소수를 찾아보겠습니다. 16의 제곱근은 4이므로 2부터 4까지의 배수를 검사합니다. 2의 배수인 4, 6, 8, 10, 12, 14, 16 / 3의 배수인 6, 9, 12, 15 / 4의 배수인 8, 12, 16 가 모두 걸.. 2023. 1. 27.
[백준] 1918번 : 후위 표기식 (Kotlin) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 나의 풀이 import java.lang.StringBuilder import java.util.Stack fun main() { val str = readLine()!! val sb = StringBuilder() val stack = Stack() str.forEach { // 알파벳의 경우 바로 문자열에 추가 if (it in 'A'..'Z') { sb.append(it) } else { // 연산자의 경우 when (it) { // +, -는 괄호 밖.. 2023. 1. 26.
[알고리즘] 유클리드 호제법 + [백준 2609번] (Kotlin) 유클리드 호제법이란? 2개의 자연수쌍의 최대공약수를 구하는 알고리즘입니다. 또한, 최대공약수를 이용하여 최소공배수를 구할 수 있습니다. 최대공약수 (GCD, Greatest Common Divisor) 2개의 자연수 a, b에 대해 a를 b로 나눈 나머지를 r이라 할 때, a와 b의 최대공약수는 a와 r의 최대공약수와 같습니다. 이 과정을 반복하여 나머지가 0이 되었을 때 나누었던 수가 a와 b의 최대공약수입니다. ☞ 예를 들어 (a= 24, b= 18)에 대해 최대공약수를 구해보겠습니다. 이때, r= a%b = 6이고 다시 b를 r(a%b)로 나누면 나머지가 0이 되어 최대공약수는 6이 됩니다. 최소공배수 (LCM, Least Common Multiple) 최소공배수는 위에서 구한 최대공약수를 활용해 .. 2023. 1. 25.
728x90
반응형

티스토리툴바