B_log

기본 정렬 구현하기 오랜만에 알고리즘을 보며 기본 정렬(버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬)을 구현해봤어요. 알고리즘 풀이를 위해 제가 사용하는 언어인 Python과 iOS 개발을 위해 사용하는 언어인 Swift로 각각 구현했어요. 각 정렬의 시간복잡도나 자세한 정렬 알고리즘을 위한 글이 아니라, 단순히 기본 정렬 알고리즘들을 구현하고 싶은 분들을 위해 코드를 공유해요 :) 제가 구현할 때 했던 생각 정도만 설명으로 추가할게요. 입력되는 배열이 빈 배열인 상황 등은 고려하지 않은 코드예요. 혹시 빈 배열의 입력이 가능한 상황이라면 추가적인 처리가 필요해요 :) 혹시 코드에 미흡한 점이 있거나 더 좋은 코드로 개선 가능한 방향이 있다면 피드백 부탁드려요! 버블 정렬(Bubble So..

📎 간단한 소수 판별법 소수 판별에는 여러가지 방법이 있습니다. 사실 가장 간단한 방법은 Brute Force로 2보다 크고 소수 판별의 대상인 수보다 1 작은 모든 수를 탐색하며 나누어 떨어지는지 확인하는 것입니다. 예시를 통해 설명하면 아래와 같습니다. func isPrime(checkNumber: Int) -> Bool { let criterion = checkNumber - 1 for i in 2...criterion { if checkNumber % i == 0 { return false } } return true } 여기서 한단계 더 나아간다면 모든 수를 체크하는 것이 아니라 제곱근까지만 탐색해도 됩니다. 왜냐하면 소수가 아닌 수는 인수가 존재하고, 인수는 곱의 쌍으로 존재하기 때문에 제곱근..

연결리스트에 새로운 데이터 추가하기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Node: def __init__(self, data, next=None): self.data = data self.next = next class NodeMgmt: def __init__(self, data): self.head = Node(data) def add(self, data): if self.head == '': self.head = Node(data) else: node = self.head while node.next: nod..

문자 클래스 [ ] - [] 사이의 문자와 매칭한다. - [abc]의 경우 매칭되는 문자가 a,b,c중 하나라도 가지고 있으면 매칭된다. - [a-c]처럼 할 경우 구간으로 인식하여 from 'a' to 'c'구간을 체크한다. Dot(.) - 줄바꿈(\n)을 제외한 모든 문자와 매칭 - a.b와 매칭되는 문자열은 aab, a0b처럼 a와 b 사이에 어떠한 종류의 문자가 와도 매칭이 된다. 하지만 abc처럼 a와 b사이에 아무 글자도 존재하지 않으면 매칭이 되지 않는다. 반복(*) - ca*t의 경우 a가 1번 이상 반복될 경우 매칭이 된다. 예를 들어, cat, caat, caaat 같은 문자열의 경우 매칭된다. - ct는 a가 0번 반복되어 마찬가지로 매칭된다. 반복(+) - 반복 * 와 차이가 거의 ..

최적 부분 구조 - 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 최적 부분 구조 조건을 성립한다고 한다. (예시) - 서울에서 부산을 가는 최단 경로의 경우 이 최단 경로가 대전을 지난다고 가정한다. 이 때, 최단 경로는 (서울, 대전)의 최단경로, (대전, 부산)의 최단 경로를 찾아서 이으면 구할 수 있다. 즉 부분문제를 통해 전체의 최적해를 구할 수 있으므로 이는 최적 부분 구조라고 할 수 있다. 최적 부분 구조가 존재하지 않을 경우 - 서울에서 부산으로 향하는데 고속도로의 통행료 합이 3만원을 초과하지 않는 최단경로를 찾을 때, 대전에서 부산으로 가는 경로가 2가지 있다. 통행 시간 통행료 경로 A 2 시간 1만원 경로 B 1 시간 2만원 - 이 두 경로 중 어느..

👨‍💻 특징 - pivot을 기준으로 그룹을 나눠 정렬하는 방식 - pivot 선택 방식에 따라 속도가 크게 차이난다. - 최악의 경우 n^2의 속도가 날 수 있으므로 pivot을 잘 선택해야 한다. - 정렬이 되지 않은 리스트의 경우 중앙값이 가운데 값이 아니므로 시작값, 중간값, 마지막 값 중 가운데 값을 피봇으로 설정한다. 💾 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 def quick_sort(lst): # 기저조건 만들기 if len(lst) pivot: right.append(n) elif n

👨‍💻 특징 - binary search (이진 탐색) - 주어진 리스트를 절반씩 줄여가며 탐색 - O(logN)의 속도 - 이미 정렬되어 있는 리스트에서만 사용 가능 🚦 필요한 경우 - 선형 순차 탐색보다 빠른 탐색이 필요하고 리스트가 정렬되어 있는 경우 사용한다. 💾 코드 123456789101112131415161718192021222324252627282930313233343536 # iteration 사용 def b_search_e(lst, target): start_idx = 0 end_idx = len(lst)-1 # idx의 역전이 일어날 때까지 순회 while start_idx target: end_idx = target_idx - 1 elif lst[target_idx] end_idx ..

- 문제 상황 : 주어진 리스트를 O(N)으로 순회하며 그 안에서 target - nums[i]의 꼴로 검색할 경우 O(N^2)의 순회가 되어 시간이 초과된다. - 해결책 : 먼저 O(NlogN)의 sort 함수를 사용해 nums를 정렬한 후, 인덱스의 시작점과 끝점을 주어 찾는 값이 target보다 작으면 앞쪽 인덱스를 증가시키고 더 크면 뒷쪽 인덱스를 감소시키는 방향으로 찾는다. - Check Point : 문제에서 주어진 상황이 답이 항상 존재하기 때문에 가능한 방식이다.