Algorithm

Algorithm
백준[1182] - 부분수열의 합 (Kotlin)
import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter fun main() { val br = BufferedReader(InputStreamReader(System.`in`)) val bw = BufferedWriter(OutputStreamWriter(System.out)) val (N, S) = br.readLine().split(" ").map { it.toInt() } val nums = arrayListOf() br.readLine().split(" ").map { nums.add(it.toInt()) } var count ..
→2022.01.02
Algorithm
[Kotlin] 정렬 2 (병합정렬, 퀵정렬)
1. 병합정렬 (Merge Sort) 배열을 균등한 크기의 두 배열로 나누어 분할된 각 배열을 정렬한 다음 합하여 정렬하는 형태이다. 재귀함수와 분할정복을 사용하여 구현한다. 정렬은 항상 느끼지만 글로 설명하는 것 보단 아래 애니메이션을 통해 직접 동작을 확인하는 것이 이해가 빠른 것 같다. 병합정렬 Kotlin Code // mergedList = split(arr) fun split(arr: ArrayList): ArrayList { if (arr.size
→2021.12.16
Algorithm
[Kotlin] 동적 계획법 (Dynamic Programming, DP) (+ 분할 정복과의 차이)
1. 동적 계획법(Dynamic Programming, DP) 주어진 문제를 작은 문제로 나누어 푸는 알고리즘. 작은 문제를 해결한 후, 해결한 작은 문제의 해답을 활용하여 주어진 문제를 해결하는 방식을 말한다. 피보나치 수열을 해결 할 때 f(n) = f(n-1) + f(n-2) 와 같은 점화식을 가지게 되는데, 이는 f(n)을 구하기 위한 하위 문제들 (f(n-1), f(n-2)..) 의 해가 중복된다. f(6)을 구하기 위해 하위 문제들의 해를 중복으로 구하게 됨으로써, 비효율적인 시간 복잡도를 가지게 된다. 이렇게 답을 구하기 위해 했던 계산을 반복해야 하는 문제에서 하위 문제의 해를 재사용해 문제를 해결하는 DP가 효율적으로 동작한다. 2. 동적 계획법의 조건 최적 부분 구조(Optimal Su..
→2021.12.16
Algorithm
[Kotlin] 정렬 1 (버블정렬, 선택정렬, 삽입정렬)
1. 버블정렬 (Bubble Sort) 인접한 두 값을 비교하여 뒤의 값이 더 작을 시 swap을 수행하는 정렬이다. 배열을 한 번 순회 할 때마다 배열의 맨 뒤 index부터 가장 큰 값이 정렬된다. 버블정렬 Kotlin Code // 바깥쪽 loop(배열을 순회할 횟수) for (i in 0 until n - 1) { var isSwap = false // 안쪽 loop(swap 여부를 판단할 횟수) // 바깥쪽 loop가 한 번 돌 때마다 배열의 끝에 정렬된 값이 들어오므로 n - 1 - i for (j in 0 until n - 1 - i) { if (array[j] > array[j + 1]) { swap(array, j, j + 1) isSwap = true } } // 정렬이 완료된 경우 바..
→2021.12.15
Algorithm
[Kotlin] 자료구조 2 (해쉬 , 트리, 힙)
1. 해쉬 (Hash) 해쉬 함수 (Hash function) : 임의의 데이터를 고정된 길이의 데이터로 매핑시키는 함수. 해쉬 (Hash) : 해쉬 함수를 통해 매핑된 고정된 길이의 데이터 해쉬의 특징은 다음과 같다. 1. 결과값이 중복될 가능성의 거의 없다. 2. 입력값을 알 수 없으며, 결과값을 알아도 이를 통해 입력값을 유추할 수 없다. 해쉬 테이블 (Hash table) : 해쉬값을 index로 사용하여 key, value 형태로 값을 저장하는 자료구조. 해쉬 충돌 (Hash Collision) : 고정된 길이의 데이터로 변환하는 해쉬의 한계로 인해, 서로 다른 두 개의 key가 동일한 hash 값을 갖게 되는 것. 이러한 해쉬 충돌을 해결하기 위한 방법으로는 두 가지가 존재한다. 1. Chai..
→2021.12.15
Algorithm
[Kotlin] 자료구조 1 (배열, 스택, 큐, 링크드리스트)
1. 배열 (Array) 같은 type의 연관된 데이터를 효율적으로 관리하기 위한 자료구조. 장점 : index를 통해 원하는 위치에 있는 값에 대해 효율적으로 접근 할 수 있음. 단점 : 크기가 정해져 있으므로 유동적인 데이터의 추가, 삭제가 어려움. 시간 복잡도 : 접근 - O(1) [Index를 통해 값에 바로 접근] 검색 - O(n) [처음 Index부터 순회] 추가, 삭제 - 맨 뒤에 추가, 삭제 시 O(1), 중간 값일 시 추가, 삭제 후 데이터를 한칸씩 밀어야 하므로 O(n) 코틀린에서의 Array는 다음과 같이 사용할 수 있다. // 크기 3의 배열 [1, 2, 3] val array: Array = arrayOf(1, 2, 3) // 크기 5의 배열 [0, 0, 0, 0, 0] val a..
→2021.12.15

• 이전
• 1
• 2
• 3
• 다음