10000COW

선택 정렬: 총 n개의 원소가 있을 때, 0번째 원소부터 n-1 번째 원소까지 i 번째 원소부터 마지막 원소까지 최소값을 갖는 원소와 i 번째 원소를 swap해주는 정렬. 버블 정렬과 달리 한 Cycle 내에서 한 번만 swap(교환)이 일어난다. 시간복잡도: Θ(n^2) 선택 정렬 선택 정렬 Python 코드 def selectionSort(): nums = list(map(int, input().split(' '))) for i in range(0, len(nums)): min_num = nums[i] min_idx = i for j in range(i+1, len(nums)): if(nums[j] < min_num): min_num = nums[j] min_idx = j nums[min_idx] =..

들어가기 전에, 문제에서 주어진 '정렬할 대상의 갯수'가 커지면 정렬이 어렵다. 그것에 대한 해결책은? 분할 정복 기법(Divide-and-Conquer) STEP 1. 원래 문제를 독립적으로 풀 수 있는 작은 문제로 나눔(Divide) STEP 2. 각각의 문제를 풂(Delegate) STEP 3. 각각의 문제의 답을 이용해 원래 문제의 답을 만든다.(Combine) 정렬을 위한 분할 정복 기법은 대표적으로 두 가지가 있다. 1. 병합 정렬(Merge sort) 2. 퀵 정렬(Quick sort) 본격적으로 병합 정렬에 대해 알아보자. 알고리즘의 기본 아이디어 Divide - 정렬할 리스트를 앞 쪽 반, 뒤쪽 반으로 나눈다. Half Delegate(Front) - 앞 쪽 반을 정렬한다. Half De..

삽입 정렬 - 이미 정렬된 부분은 항상 정렬되어 있다. - 처음에는 정렬된 부분에 원소가 1개 - 매번, 정렬할 부분의 원소 1개를 이미 정렬된 부분으로 옮긴다. 시간 복잡도 Θ(n^2) - 가장 좋을 때: 이미 오름차순으로 정렬되어 있을 때 -> 총 n-1 번 = Θ(n) - 최악의 경우: 역순으로 정렬되어 있을 때 i번째 위치의 원소를 정렬된 부분에 추가할 때, i-1 개의 원소와 모두 비교해야한다. i = 2,3, ..., n일 때 각각 비교해야할 개수는 1+ 2+ ... + n-1 = n(n-1)/2 = Θ(n^2) 삽입 정렬 Python 코드 def insertionSort(): nums = list(map(int, input().split(' '))) for i in range(1, len(n..

버블 정렬: 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환함. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복. 시간복잡도: O(n^2) 버블정렬 Python 코드 def bubbleSort(): numbers = list(map(int, input().split(' '))) for i in range(0, len(numbers) - 1): for j in range(i+1, len(numbers)): if(numbers[i] > numbers[j]): tmp = numbers[j] numbers[j] = numbers[i] numbers[i] = tmp print(numbers) 입력 및 출력

문제: Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["..