알고리듬 Make a linked list를 알아보겠습니다. ​ 링크드 리스트는 일반 배열과 달리 주소가 분산되어서 저장됩니다. 일반 배열은 같은 저장 공간 안에 옹기종기 모여있습니다. 그래서 검색과 메모리 측면에서는 좋지만, 삽입, 삭제가 어렵습니다. 링크드 리스트는 다음 주소를 가지고 있기 때문에, 중간에 삽입, 삭제가 자유롭습니다. 저장된 다음 배열의 주솟값만 변경시키면 되기 때문입니다. ​ 0, 1, 2, 3으로 구성된 링크드 리스트가 있다고 칩시다. 아래의 그림과 같습니다. HEAD는 처음을 가리킵니다. 오늘은 삽입, 삭제 이러한 부분을 다루는 것이 아니라 그냥 기초적인 동작 구조를 구현할 겁니다. 사실 파이썬의 list 자체가 링크드 리스트라서 구현할 필요는 없지만, 개념은 알아두면 좋으니까요. ​ ​ 먼저 노드를 만듭니다. 여기에는 값과 다음 노드가 저장됩니다. 링크드 리스트를 만듭니다. 여기에는 헤더와 나머지 노드들을 저장합니다. 14 번째 줄에서 처음 입력되는 값이면 head와 rest에 모두 처음 노드를 넣습니다. 두 번째부터는 18 번째 줄에서 처음 node의 next에 두 번째 노드가 들어가고 그다음 rest를 두 번째 노드로 만듭니다. 세 번째에는 두 번째 노드의 next에 세 번째가 들어가고, rest가 세 번째 노드로 됩니다. 이런 식으로 계속 추가해 줍니다. 출력해 봅시다. 끝. 카테고리: Algorithm

알고리듬 Find maximum value with given formula를 알아보겠습니다. 배열 arr[]이 주어지고 배열의 index i, j 가 있을 때, 다음 주어진 공식을 사용해서 최대가 되는 값을 구해봅시다. i에 있는 값과 j에 있는 값을 뺀 절댓값과 i - 2의 절댓값을 더한 값이 최대가 되어야 합니다. 이렇게 수식이 주어진 문제는 수식을 간단하게 만드는 것으로 쉽게 해결 수 있습니다. ​ 절댓값을 풀어줍시다. 이런 경우의 수로 4 가지 경우가 나옵니다. i와 arr[i]는 같이 변화하기 때문에 i끼리 묶어줍니다. 두 수의 뺄셈 관계는 반비례 관계라서 가장 큰 값이 나오려면 a가 가장 크고, b가 가장 작아야 합니다. 이것을 코드에 잘 녹여주면 됩니다. lagrest에는 작은 값으로, smallest에는 큰 값으로 초기화합니다. largest, smallest 세트마다 하나의 경우의 수를 대입하여 실행하고 마지막에 가장 큰 값을 반환하면 됩니다. 위의 경우, 12와 -8을 선택한 게 커 보이지만 12 - (-8) + 3 - 2 = 21 -8과 9를 선택한 게 더 큽니다. 9 - (-8) + 8 - 2 = 23 ​ 끝. 카테고리: Algorithm

알고리듬 Find coprime integers를 알아보겠습니다. ​ 이번 시간에는 서로소인 숫자를 찾아볼 건데요. 서로소란 두 수를 각각 나눌 수 있는 숫자들을 나열했을 때, 공통된 숫자가 1 밖에 없는 경우를 말합니다. 4와 3이 서로소라고 할 수 있죠. 4는 1, 2, 4 3은 1, 3 ​ ​ 찾는 방법은 간단합니다. 최대공약수가 1인 것을 찾으면 됩니다. 끝. 카테고리: Algorithm

알고리듬 Dijkstra algorithm with direction을 알아보겠습니다. ​ Dijkstra(다익스트라, 데이크스트라) 알고리듬은 최단거리를 구할 때 사용합니다. 각 지점 간의 거리를 계속해서 업데이트합니다. 이번 시간에는 방향성이 있는 경우를 다뤄봅니다. ​ 개념은 간단합니다. 미탐험 지역은 큰 값을 주고, 탐험한 지역은 가중치에 따라서 업데이트합니다. 더 작은 값이 발견되면 작은 값으로 수정합니다. 프로그램이 종료되면 전체 노드에 대한 최소 가중치를 얻을 수 있습니다. ​ ​ ​ 아래와 같은 지점이 표시되어 있는 방향이 표시되어 있는 지도에서 3 -> 5로 가는 최단 거리를 구해보겠습니다. 각 지점 간의 관계는 다음과 같이 표시하기로 합시다. [시작 지점, 거리, 도착 지점] 3 번 지점의 경우 [3, 2, 1], [3, 5, 4] 4 번 지점의 경우 [4, 1, 5] ​ 지점은 총 5 개가 있고, 출발 지점은 3 번입니다. 도착 지점은 5 번입니다. 맵은 다음과 같이 있습니다. 일단 모든 노드들의 관계를 저장할 리스트를 하나 만듭니다. 저는 adjacent_cities로 만들었습니다. 5 번째 줄에서 node + 1을 하는 이유는 리스트는 0부터 시작하지만 여기서 node는 1부터 시작하기 때문입니다. 맵에서 각 노드들의 정보를 가져온 다음, 해당 노드 위치에 시간과 목적지 노드를 추가합니다. 3 번 노드의 경우 두 개의 리스트를 원소로 가지게 됩니다. 그다음 전체 소요 시간을 관리할 리스트 하나 만듭니다. 아직 미지의 지역이기 때문에 큰 값을 넣어줍니다. 그리고 현재 시작 노드인 3은 소요 시간을 0으로 만들어줍니...

사용 버전: Python 3.7.9 ​ 파이썬 math.lcm()을 알아보겠습니다. ​ lcm은 최소공배수를 구할 때 사용합니다. 보시다 싶이 Python 3.9 버전에 추가된 것이라서 현재 제가 사용하는 3.7.9에서는 사용할 수 없습니다. 괄호 안에는 여러 정수들을 넣습니다. 3.9가 아니라서 그냥 직접 만들어서 사용합니다. 최소공배수와 최대공약수의 관계를 이용해서 만듭니다. https://shwoghk14.blogspot.com/2022/12/blog-post.html 끝. 카테고리: Python, python_math

사용 버전: Python 3.7.9 파이썬 math.gcd()를 알아보겠습니다. ​ gcd는 최대공약수를 구할 때 사용합니다. 괄호 안에는 최대공약수를 구하고 싶은 두 수를 집어넣습니다. ​ 4와 5의 최대공약수는 1입니다. 50과 70의 최대공약수는 10입니다. ​ ​ 끝. 카테고리: Python, python_math

수학 최소공배수, 최대공약수를 알아보겠습니다. ​ 두 수가 있을 때의 경우를 보겠습니다. 최소공배수(Least Common Multiple, LCM)는 각 수의 곱한 것이 서로 만나는 가장 작은 수를 말합니다. 예를 들어 4와 5가 있다고 치면, 4, 8, 12, 16, 20 5, 10, 20 이렇게 두 수는 20에서 만납니다. 4와 5의 최소공배수는 20입니다. ​ 최대공약수(Greatest Common Divisor, GCD)는 두 수가 가진 약수 중에 가장 큰 수를 말합니다. 4의 약수는 1, 2, 4 5의 약수는 1, 5 두 수가 공통으로 가지는 약수 중에 가장 큰 수는 1입니다. 4와 5의 최대공약수는 1입니다. ​ ​ 하나 더 해봅시다. 12와 6이 있습니다. 12 6, 12 12와 6의 최소공배수는 12입니다. ​ 1, 2, 3, 4, 6, 12 1, 2, 3, 6 12와 6의 최대공약수는 6입니다. ​ 이렇게 일일이 하나씩 대조해 보는 게 아니라 계산하는 방법이 존재합니다. 앞에 나와있는 숫자를 곱하면 최대공약수입니다. 2 x 3 = 6 ​ 그리고 앞에 있는 숫자와 밑에 있는 숫자를 모두 곱한 것이 최소공배수입니다. 2 x 3 x 2 x 1 = 12 그런데, 자세히 보면 최대공약수는 최소공배수를 구할 때 들어갑니다. A x B x a x b = 최소 공배수 최대공약수 x 2 x 1 = 최소공배수 ​ 그리고 신기한 것은 12 * 6을 최대공약수와 최소공배수로 표현할 수 있습니다. 12 = A x B x a 6 = A x B x b 12 x 6 = A x B x A x B x a x b 최대공약수 = A x B 최소공배수 = A x B x a x b 12 x 6 = 최대...

수학 순열(Permutation)을 알아보겠습니다. ​ 순열은 순서대로 무엇인가를 뽑는 경우의 수를 나타냅니다. 기호로는 이렇게 표현하는데요. ​ 총 n 개가 있고, 여기서 r 개를 고르는 걸 의미합니다. 이것을 수식으로 쓰면 이렇게 됩니다. 예를 들어 1, 2, 3, 4, 5가 적힌 공 5 개가 있고, 여기서 3 개를 뽑는 것이라고 한다면 다음과 같이 표현됩니다. 이 경우, 나올 수 있는 경우의 수는 무엇일까요? 5 x 4 x 3으로 답은 60입니다. 위의 수식을 사용해서 표현하면 이렇게 되는데요. 결론은 5 x 4 x 3으로 동일합니다. 기억하기에는 이게 더 편한 것 같네요. ​ ​ 만약 똑같은 것이 들어있는 순열이라면 어떻게 구해야 할까요? 5, 5, 3, 3, 2가 적힌 공이 있습니다. 5 개를 꺼낼 때 경우의 수는 어떻게 구할까요? 같은 것이 있는 경우에는 다음과 같은 수식을 사용합니다. 같은 것끼리는 자리를 앞뒤로 변경해도 같기 때문에 나누기합니다. 같은 개수를 분모로 나눕니다. 현재는 5가 2 개, 3이 2 개라서 2!2!로 나눕니다. 답은 30 가지 경우의 수가 있군요. ​ 끝. ​ 카테고리: Math

알고리듬 Sum adjacent values in matrix를 알아보겠습니다. ​ 행렬이 주어지고 해당 행렬의 동서남북으로 인접한 값의 합을 구하는 방법을 알아봅시다. [[1, 2, 3],  [4, 5, 6],  [7, 8, 9]] 이런 행렬이 있을 때, 좌표가 주어지면 주변 값들을 더하는 코딩을 합니다. 예를 들어 (1,1)이 선택되면, 2 + 6 + 8 + 4를 수행해서 20이 나오면 됩니다. ​ 파이썬으로 해봅시다. 우리가 생각할 것은, 그냥 상하좌우 다 더해주면 됩니다. 단지 이게 영역 밖인지만 확인하면 됩니다. 그 역할을 하는 게 is_area 함수입니다. 끝. 카테고리: Algorithm

운영 체제: macOS Ventura 13.0.1 사용 버전: Xcode 14.2, Swift, SwiftUI ​ iOS Multi select list items를 알아보겠습니다. 리스트의 아이템을 여러 개 선택할 수 있게 만들어 보겠습니다. ​ ​ 아래 코드를 봅시다. List로 items의 내용들을 표현하고 있습니다. 클릭도 안되고 아무것도 안 됩니다. 클릭되게 만들어 봅시다. ​ 아래 공식 문서의 init 부분을 봅시다. https://developer.apple.com/documentation/swiftui/list 현재 코드는 init(data, id, rowContent)를 사용해서 click이 안 됩니다. 두 번째, selection: binding<SelectionValue?>?를 사용하면 하나 클릭이 가능합니다. 일단 하나 클릭이 가능한 것부터 해봅시다. ​ 13 번째 줄에 @State를 만듭니다. 형식은 String?이고 그 이유는 items가 [String]이기 때문입니다. 여러 개가 클릭되게 해봅시다. 13 번째 줄의 Type을 Set<String>으로 변경해 줍니다. 그리고 21 번째 줄은 ForEach로 변경해 줍니다. 여러 개가 선택될 거니까요. 실행해 보면, 하나 선택되는 것 밖에 안됩니다. 네, 여러 개 선택은 EditMode 일 때에만 가능합니다. ​ ​ ​ ​ 16 번 줄처럼 NavigationStack을 추가하고, 27 번째 줄처럼 toolbar를 추가해 ...