본문 바로가기
반응형

공부/데이터사이언스48

Sorting algorithm(정렬 알고리즘) - 4탄 Bubble sort(버블 정렬) 4. Bubble sort (거품 정렬, 버블 정렬) ▪ 바로 옆의 수와 비교해서 큰 수를 뒤로 정렬하는 방법 ▪ 시간 복잡도: O(n²) (예) # Bubble sort (거품정렬, 버블정렬) from typing import List def bubble(L: List) -> List: for i in range(len(L)): for j in range(len(L)-1): if L[j] > L[j+1]: L[j], L[j+1] = L[j+1], L[j] return L bubble([3, 91, 1, 5, 7, 2]) #답: [1, 2, 3, 5, 7, 91] 참고: https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC 2022. 7. 13.
[백준] 11단계 - 2751번 (파이썬) check! 2751번 https://www.acmicpc.net/problem/2751 정렬문제인데, merge sort를 써도 시간초과가 계속 떠서 알아보니... sorting의 문제가 아니라 input의 문제였다. input()을 반복적으로 이용하면 시간이 초과가 뜬다. 모듈 sys의 stdin.readline()를 이용해서 시간을 줄여야 한다. 주의해야 할 점은 readline()을 쓰면 개행문자(?) (\n, \t 등)가 포함된 채 입력된다는 점인데... 실제로 풀어본 결과 음...strip()을 쓰지 않아도 정답이 떴다. 왜 그런지 잘 모르겠다. 조금 더 조사해봐야 겠다. 여하튼, 일단은 정답이라고 뜬 코드는 아래와 같다. (두 버전 다 그냥 sort 내장함수를 이용했다.) # 버전1 (개행문자 없애는 작.. 2022. 7. 10.
Sorting algorithm(정렬 알고리즘) 3탄 - Merge Sort(합병 정렬) 3. Merge Sort (합병 정렬) ▪ 정렬된 두 리스트가 있을 때 (리스트1, 리스트2), 각각의 첫번째 수를 비교해서 작은 수를 정렬. → (리스트1의 첫번째 수가 정렬됐다고 가정하면,) 리스트1의 두번째 수와 남은 수 즉, 리스트2의 첫번째 수를 비교해서 정렬. → 동일한 방식으로 계속 진행해서 정렬된 하나의 리스트를 만듦. (그래서 병합이라고 하나 봄!!!ㅋㅋㅋ) ▪ 주의: 병합하기 전 두 리스트는 이미 정렬되어 있어야 함. 즉, Recursion을 이용해서 해당 두 리스트도 Merge sort 방식으로 정렬해야 함! ▪ 특징 : Memory Complexity는 Time Complexity는 (예) 정렬된 두 리스트 첫번째 수: 30 vs 2 → 2가 작으므로 2는 병합리스트 맨 앞에 위치... 2022. 7. 10.
[백준] 9단계 - 11729번 (파이썬) check! 11729번 https://www.acmicpc.net/problem/11729 하노이의 탑은 대표적인 재귀 문제이다. 하지만...매번 잊어버리고...매번 어려워한다. 이번에도 혼자 풀다가 엄청 이상하게 풀어버렸다. 내가 돌리면 잘 돌아가고 답도 맞는데 백준에서 돌리면 계속 런타임에러가 떴다. 메모리초과가 뜨기도 하고...ㅎㅎㅎ 망했어요... 결국 위키백과의 도움을 받았다. 매번 볼 때마다 신기한 풀이다. 언제쯤 익숙하게 이런 코드를 생각해낼 수 있을까? # 참고: 위키백과 # https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91 # n: 이동시킬 원판 개수 # from_ : 시작 원판, to_ : 도착 원판, via_ .. 2022. 7. 5.
반응형

티스토리툴바