10000COW

기수 정렬 : 주어진 수 들간의 비교를 하지 않고 버킷을 사용해 정렬하는 방법으로, 낮은 자리(1의 자리)에서 높은 자리(10^n 자리) 순으로 버킷에 넣는 방법으로 정렬한다. 실제로 숫자들 간의 비교를 통해 정렬을 하는 것이 아닌, 0~9까지의 버킷이 있고 이 버킷에 숫자를 넣어가며 분류한다고 생각하면 된다. 시간복잡도 O(r*n) : r은 숫자의 자릿수, n은 정렬될 수의 갯수 특징 1. 시간 복잡도에서 엄청난 이점을 갖는다. 무려 O(N).. 2. 하지만 그만큼 추가적인 메모리가 많이 필요하다. [153, 262, 37, 598, 433, 855]를 기수 정렬을 이용해 정렬해보자. 가장 낮은 1번째 자리부터(1의 자리) 가장 높은 3번째 자리(100의 자리) 순으로 정렬한다. 다음과 같이 0~9 까..

삽입 정렬 - 이미 정렬된 부분은 항상 정렬되어 있다. - 처음에는 정렬된 부분에 원소가 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..

문제: 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"], ["..

BFS는 큐를 이용한 반복 구조로 구현한다. 먼저 큐를 이용한 BFS Pseudo code를 보면서 어떻게 구현해야할지 생각해보자. 1) 큐를 이용한 BFS Pseudo code BFS(G, start_v) let Q be a queue label start_v as discovered Q.enqueue(start_v) while Q is not empty do v := Q.dequeue() if v is the goal then return v for all edges from v to w in G.adjacentEdges(v) do if w is not labeled as discovered then label w as discovered w.parent := v Q.enqueue(w) 2) 큐를 이..

1) 재귀를 이용한 DFS 구현 Pseudo code G는 그래프, v는 정점(vertex)일 때, DFS(G,v) lable v as discovered for all directed edges from v to w that are in G.adjacentEdges(v) do if vertex w is not labeled as discovered then recursively call DFS(G,w) 재귀를 이용한 DFS 구현 Python code def recursive_dfs(v, discovered=[]): discovered.append(v) for w in graph[v]: if w not in discovered: discovered = recusrive_dfs(w, discovered) ..