알고리듬 Floyd's Tortoise and Hare Algorithm을 알아보겠습니다. ​ 플로이드의 거북이와 토끼 알고리듬입니다. 이름이 너무 재미있지요. 순환을 찾는(Circle detect) 알고리듬 중 하나입니다. 토끼는 두 칸씩 뛰어가고 거북이는 한 칸씩 이동하면서 순환되는 부분을 찾는 알고리듬입니다. ​ 이렇게 순환이 생기는 링크드 리스트가 있습니다. 여기서 플로이드 거북이와 토끼 알고리듬을 이용해서 순환이 발생하는지 확인하고, 그 시작 위치를 찾는 법을 알아봅시다. 거북이는 한 칸, 토끼는 두 칸씩 나아갑니다. 토끼와 거북이가 5에서 만났기 때문에 이 링크드 리스트는 순환하는 구조입니다. 여기서 재미있는 성질이 있습니다. ​ 처음 순환이 발생하는 위치는 어떻게 구할까요? 우리가 보기에 3에서 순환이 발생하잖아요. 이것을 어떻게 찾냐하면 다음과 같이 찾습니다. 거북이를 원래 위치로 보내고, 거북이와 토끼를 한 칸씩 만날 때까지 움직이면 됩니다. 짜잔. 이것이 어떻게 가능한지 증명해 볼까요? ​ 순환이 시작되는 점까지의 거리를 l 순환 시작점부터 거북이와 토끼가 만나는 점까지를 m 순환하는 전체 부분을 c라고 표기합니다. 거북이가 이동한 거리를 t라고 한다면, t = l + c * x + m입니다. 토끼가 이동한 거리를 h라고 한다면, h = l + c * y + m입니다. ​ 토끼는 거북이보다 2 배 이동하니까 2t = h가 성립되어서 2(l + c * x + m) = l + c * y + m이 됩니다.

알고리듬 Find higher number in the next element를 알아보겠습니다. ​ 배열에서 각 숫자마다 뒤에 올 숫자 중에 큰 숫자가 있는지 확인하는 알고리듬을 알아봅시다. 8, 4, 2, 5가 들어있다고 칩시다. 4와 2가 큰 숫자가 나옵니다. 이것을 구하기는 쉽지 않습니다. 8의 결과를 보려면 5가 나올 때까지 기다려야 하기 때문이죠. ​ ​ 그래서 뒤집어서 생각합니다. 5 다음에 작은 숫자가 나오면, 5가 이전보다 큰 숫자라는 의미가 되니까요. 먼저 스택(Stack)에 5를 집어넣습니다. 2가 5 보다 작으므로 2를 집어넣습니다. 4는 2 보다 큼으로 2는 비교 대상에서 제거합니다. 4는 5 보다 작으므로 스택에 넣습니다. 8은 4 보다 큼으로 4를 비교 대상에서 제거합니다. 8은 5 보다 큼으로 5를 비교 대상에서 제거합니다. 아무것도 남아있지 않으므로 8보다 큰 값은 여기에 없습니다. 스택에 들어갔던 2와 4만이 다음 값에 큰 값을 가지고 있습니다. ​ 이것은 함축적으로 모든 배열 값들과 비교하는 것과 같습니다. 8과 4를 비교하는 것은 8과 2를 비교하는 것을 포함하는 결과이기 때문입니다. ​ ​ 코드로 한 번 봅시다. 6 번째 줄에서 배열을 거꾸로 반복합니다. 7 번째 줄에서 스택이 비어있으면 큰 값이 없다는 뜻이므로 False를 넣습니다. 12 번째 줄에서 스택의 위에 값과 현재 배열의 값을 비교해서 현재 값이 작다면 스택에 넣습니다. 16 번째 줄에서 만약

알고리듬 Merge sort를 알아보겠습니다. ​ 합병 정렬(Merge sort)는 숫자를 잘게 분할해서 정렬을 하면서 다시 합치는 알고리듬입니다. 그냥 정렬하면 되는데, 왜 분할을 하냐 하면, 작은 문제를 풀면 큰 문제가 풀리는 놀라운 인생의 진리가 아닐까요? 걸리는 시간 Big O는 n log n입니다. ​ 글로 설명하기보다는 아래 그림을 통해서 설명을 해볼게요. 1, 3, 7, 4, 6, 2, 8 배열이 있습니다. 합병 정렬(Merge sort)를 진행해 봅시다. 1, 3, 7, 4와 6, 2, 8로 나눕니다. 그리고 다시 1, 3, 7, 4는 다시 1, 3과 7, 4로 나눕니다. 6, 2, 8은 다시 6, 2와 8로 나눕니다. 다음은 1, 3, 7, 4, 6, 2, 8 모두 각각 한자리로 나눕니다. 더 이상 나눌 수가 없으니 합칩니다. 다시 합치면서 정렬합니다.  1, 3과 4, 7과 2, 6과 8로 정리되었습니다. 합칩니다. 순서가 오름차순으로 잘 되어있어서 달라질 게 없군요. 짜잔. 1, 2, 3, 4, 6, 7, 8로 정리가 됩니다. 이것을 코드로 한번 봅시다. merge_sort라는 함수를 만듭니다. 인자로는 배열, 왼쪽, 오른쪽을 받습니다. 3 번째 줄에서는 왼쪽이 오른쪽보다 크거나 같으면 종료합니다. 위의 사진에서 보듯이 반을 나눠서 정렬을 진행해야 하므로 6 번째 줄에서 가운데를 찾습니다. 그리고 다시 가운데를 기준으로 앞뒤로 나눠 merge_sort를 진행합니다. 위의 작업은 작은 단위로 나누는 작업만 포함되어 있습니다. 실제적으로 정렬하면서 합치는 과정을 다룰

운영 체제: macOS Ventura 13.1 사용 버전: Xcode 14.2, Swift, SwiftUI ​ iOS How to get a direction based on locale을 알아보겠습니다. ​ 언어에 따라서 오른쪽에서 왼쪽으로 읽는 언어가 있습니다. 이번 시간에는 사용자 언어가 어느 방향의 언어인지 알아보는 시간을 가져보겠습니다. ​ ​ locale, languageCode, direction을 차례로 얻습니다. 15 번째 줄에서 NSLocale.current로 현재 Locale을 받습니다. 16 번째 줄에서 languageCode로 현재의 언어 코드를 받습니다. 17 번째 줄에서 NSLocale.characterDirection(forLanguage:)를 사용해서 forLanguage에 들어가는 언어의 방향을 얻습니다. 22 번째 줄에서부터 31 번째 줄까지 출력을 해줍니다. 끝. 카테고리: iOS

사용 버전: Python 3.7.9 ​ 파이썬 Change a str with index를 알아보겠습니다. ​ 파이썬에서 str 타입을 인덱스를 써서 변경하려고 하면 다음과 같은 오류가 납니다. TypeError: 'str' object does not support item assignment 즉, str에는 값을 재정의 할 수 없다는 뜻입니다. ​ ​ ​ 이때는 list롤 사용합니다. list로 만든 다음에 다시 합쳐주는 과정을 거쳐주면 됩니다. ​ 3 번째 줄에서 list로 만들어 줍니다. 5 번째 줄에서 인덱스로 값을 변경해줍니다. 7 번째 줄에서 ''.join()을 사용해서 전부 합쳐줍니다. 끝. 카테고리: Python

알고리듬 Find all primes in a range를 알아보겠습니다. ​ 특정 범위 안에서 소수를 찾는 알고리듬입니다. ​ 0과 1은 소수가 아닙니다. 소수는 자기 자신과 1을 약수로 가지는 숫자를 말합니다. 이 특성을 이용해서 구해봅니다. ​ ​ 0~100까지의 숫자 중에서 소수만 찾아봅니다. 1 번째 줄에 소수인지 확인하는 리스트를 하나 만듭니다. 2 번째 줄과 3 번째 줄에 0과 1은 소수가 아니므로 False를 미리 넣습니다. 6 번째 줄에서 1부터 100까지 모두 찾아봅니다. 만약 소수를 만나게 되면, 소수에다가 2부터 100까지 숫자를 곱해서 소수가 아닌 것을 표시합니다. 이게 가능한 이유는 소수 정의가 1과 자기 자신을 약수로 가지는 것이기 때문입니다. 결과를 볼까요? 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97가 소수로 나왔습니다. 끝. 카테고리: Algorithm

사용 언어: Kotlin 1.8.0 사용 버전: Android Studio Electric Eel 2022.1.1 Patch 1 ​ 안드로이드 Handling Lifecycles를 알아보겠습니다. ​ Activity와 Fragment에는 생명 주기(Lifecycle)가 있습니다. 이 생명 주기를 잘 알아야지 개발할 수 있는데요. onCreate, onStart, onResume 등이 생명 주기를 나타냅니다. ​ https://developer.android.com/topic/libraries/architecture/lifecycle 이 생명주기 함수에 바로 무엇인가 오래 걸리는 작업을 override 하는 것은 권장하지 않습니다. ​ 그래서 안드로이드에서는 DefaultLifecycleObserver를 제공해 줍니다. 생명주기에 바로 덮어쓰는 것이 아니라, 따로 그 생명주기가 실행되는 것을 관찰하다가 실행되면 실행하는 역할을 합니다. ​ ​ 아래와 같은 코드가 있습니다. 파일을 하나 더 만듭니다. 마우스 우 클릭 - New - Kotlin Class/File 대충 아무 이름으로 만듭니다. 저는 LifecycleObserver로 만들었습니다. DefaultLifecycleObserver를 상속받습니다. 그리고 MainActivity에 있는 onStart와 onStop을 대신할 onStart와 onStop을 override 합니다. MainActivit