본문 바로가기

📒 | Kotlin9

[알고리즘] 매내처 알고리즘(Manacher) 개념 매내처 알고리즘이란?문자열 S가 주어질 때, 팰린드롬 부분 문자열을 찾는 알고리즘을 뜻한다. 팰린드롬 부분 문자열은 S의 부분 문자열 중 팰린드롬인 경우를 의미한다(banana에서 anana가 부분 문자열 팰린드롬이다).모든 i에 대해 i번 문자가 중심인 최대 길이의 팰린드롬 부분문자열을 검색하는 알고리즘.팰린드롬의 길이는 주로 팰린드롬의 반지름의 형태로 저장된다(반지름이란, 팰린드롬의 중심으로부터 가장 먼 문자가 얼마나 떨어져 있는지를 확인하기 위한 것이다(aba에서 반지름은 1이 된다).팰린드롬의 길이가 i라면 반지름은 (i -1) / 2가 된다. 매내처 알고리즘을 알아보기 전에 팰린드롬이 정확히 무엇인지 짚고 넘어가자. 팰린드롬(회문, palindrome)뒤집어도 같은 문자열을 뜻한다.거꾸로 읽어도.. 2024. 6. 24.

[알고리즘] 그래프 탐색 알고리즘(DFS, BFS) 그래프 탐색이란?많은 양의 데이터들 중에서 원하는 데이터를 찾는 과정을 탐색이라고 하는데,그래프에서 원하는 데이터를 찾는 과정을 그래프 탐색이라 부른다. 그래프 탐색 알고리즘에는 DFS, BFS가 있다.DFS(Depth-First Search): 깊이 우선 탐색BFS(Breadth-First Search): 너비 우선 탐색 깊이 우선 탐색(DFS)깊이 우선 탐색 알고리즘은 그래프의 자식 데이터에 들어간 후, 자식의 자식 데이터를 자식의 자식의 자식 데이터를 들어가는 식으로, 한 가지를 끝까지 파고 들어가서 탐색하는 알고리즘을 뜻한다. 한 줄기를 끝까지 파고든 후, 다음 줄기로 이동해 다시 끝까지 파고드는 방식으로 작동하는 알고리즘이다. 너비 우선 탐색(BFS)너비 우선 탐색은 시작 데이터에서 자신의 자.. 2024. 6. 22.

[알고리즘] 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘이란?그리디 알고리즘(탐욕법)이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 뜻한다. 그리디 알고리즘은 동적 프로그래밍(DP)을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안해 고안되었다. 그리디 알고리즘은 현재 상황에서 가장 좋은 결과를 선택해 나가는 방식의 알고리즘 설계 기법이다.하지만 이 가장 좋은 결과는 항상 최종적인 결과 도출에 대한 최적해를 보장해 주는 것은 아니다. 위 그림에서 가장 큰 값이 최적의 값일 때, 그리디 알고리즘은 현재 상황에서 가장 최적의 값을 구하기 때문에최종적인 답은 23이 나오게 된다(최적의 값: 128). 그리디 알고리즘은 항상 최종적인 결과 도출에 최적해를 보장해 주는 것이 아니기 때문에 상황에 맞게 사용해야 한.. 2024. 6. 18.

[Kotlin] 상속(Inheritance) 상속이란?부모의 자원을 자식이 물려받아 사용하는 것을 상속이라고 한다. 상속은 클래스 간의 관계를 정의하고 코드의 재사용성을 높이기 위해 사용된다. 상속을 통해 하나의 클래스가 다른 클래스의 속성과 함수를 물려받아 사용할 수 있다. 상속이 필요한 경우상속이 필요한 경우는이미 존재하는 클래스를 확장해 새로운 속성이나 함수를 추가한 클래스를 만들어야 할 때,여러 개의 클래스를 만들었는데 클래스들의 공통점을 뽑아 코드 관리를 편하게 해야 할 때 사용된다. 상속의 구성속성과 함수를 물려주는 쪽을 슈퍼 클래스(부모 클래스), 물려받는 클래스를 서브 클래스(자식 클래스)라고 한다.상속을 하기 위해서는 자식 클래스의 끝에 콜론(:)을 달고 상속받을 부모 클래스의 이름과 파라미터를 정의해 주면 된다.class `자.. 2024. 6. 14.

[알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍(동적 계획법)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 알고리즘 설계 기법: 문제 해결을 위해 알고리즘을 설계하는 방법이나 접근 방식을 뜻한다.설계 기법은 알고리즘을 개발하고 구현하는 데 사용되는 전략과 원칙을 뜻한다. DP와 재귀 호출의 차이점DP와 재귀 호출의 차이점을 알기 전에 하향식 접근법과 상향식 접근법이 무엇인지 알아야 한다.1. 하향식(top-down) 접근법과 상향식(bottom-top) 접근법하향식 접근 방식은 큰 문제를 작은 하위 문제로 쪼개서 해결하는 방법이다. 주로 재귀 호출을 할 때 사용된다.상향식 접근 방식은 작은 문제들부터 시작해 작은 문제들의 결과를 이용해 점점 큰 문제의 결과를 구하는 방법. 2. 메모이제이션(Memo.. 2024. 6. 12.

[Kotlin] 배열과 Map에 대해 알아보기 요즘 필자는 알고리즘 문제를 풀고 있다. 알고리즘 문제를 풀다 보면 배열은 거의 대부분의 문제에서 사용하는 것 같고, HashMap도 종종 사용하는 것 같았다. 그래서 이번에 코틀린의 배열과 HashMap의 차이에 대해 간단히 설명해보고자 한다. 앞으로 이런 간단한 알고리즘 개념에 대한 포스팅이 올라올 것 같다. 1. 배열(Array) 배열은 코틀린을 공부하지 않은 사람이라도 프로그래밍 언어를 하나라도 공부해 본 경험이 있으면 바로 알 수 있을 것이다. 바로 데이터의 집합을 배열이라고 하는데 자바의 배열 선언과는 달리 코틀린의 배열은 상당히 편리하면서도 복잡(?)하다.(필자 기준) 필자가 왜 복잡하게 느꼈냐면, 코드로 설명해 주겠다. 자바의 경우에는 다음과 같이 배열을 만들 수 있다. int[] intA.. 2023. 10. 27.

[Kotlin] 유클리드 호제법 알고리즘 유클리드 호제법이란? 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 기본 과정 예시로 32와 24의 최대공약수를 구하면, 32는 24로 나누어 떨어지지 않기 때문에, 32를 24로 나눈 나머지를 구한다. => 8 32는 8로 나누어 떨어진다. 따라서 32와 24의 최대공약수는 8이다. 예제 코드1. 재귀 함수를 사용 package algorithm import java.io.BufferedReader import java.io.InputStreamReader fun main() { val bf = BufferedReader(InputStreamReader(System.`in`)) val number = bf.readLine().split(" ") val a = number[0].toInt() val .. 2022. 10. 24.

[Kotlin] 이진 탐색 알고리즘 이진 탐색이란? 정렬된 리스트의 중간 값을 이용해 검색 값을 줄여 가면서 원하는 값을 찾는 알고리즘 탐색 과정 정렬된 리스트의 중간값을 찾는다. 찾는 수가 중간값보다 크면 오른쪽으로, 작으면 왼쪽으로 검색 범위를 좁힌다. 1, 2번을 반복한다. 이 과정을 반복하면 그냥 반복문을 이용해 찾는 것보다 더 빠르게 원하는 숫자를 찾을 수 있다. 예제 코드 숫자의 범위와 원하는 숫자를 입력하고 이진 탐색으로 그 숫자를 찾는 알고리즘 package algorithm import java.io.BufferedReader import java.io.InputStreamReader fun main() { val bf = BufferedReader(InputStreamReader(System.`in`)) val array.. 2022. 10. 21.

[Kotlin] coroutine 개념 정리 오늘은 내가 공부했던 코루틴의 개념을 알아보겠다. 코루틴의(coroutine) 개념 코루틴은 kotlin에서 사용하는 동시성 프로그래밍의 일종이다. 최근에 코틀린을 사용하는 앱이 늘어남에 따라, 구글에서도 강력히 추천하는 실시간 처리 라이브러리 이다. 코루틴 코루틴(coroutine)은 루틴의 일종 코루틴의 "co" 는 with, together를 뜻한다. 협동 루틴이라 할 수 있다. 코루틴의 특징 코루틴은 이전에 자신의 실행이 마지막으로 중단된 지점의 바로 다음 장소에서 실행을 재개한다. 비동기 처리에 대한 코드를 간단히 작성해준다. 비동기 콜백 처리를 순차적으로 하게 해준다. 이제 개념을 알았으니, 간단한 코드를 보면서 이해해 보자. 코틀린 예제 GlobalScope.launch { // launch.. 2022. 4. 3.

이전 1 다음

728x90

티스토리툴바