Just Do IT

Selection Sort Selection Sort은 가장 기본적인 정렬 알고리즘 중 하나이다. 알고리즘의 진행 순서는 다음과 같다. 주어진 리스트에서 최소값을 찾는다. 그 값을 맨 앞의 값과 교체한다. 맨 처음위치를 뺀 나머지 리스트에 대하여 반복한다. 그림으로 보는게 가장 이해가 잘 될 것같다. 테이블로 보면 다음과 같다. Round Array Min Value 0 [9,1,6,8,4,3,2,0] 0 1 [0,1,6,8,4,3,2,9] 1 2 [0,1,6,8,4,3,2,9] 2 3 [0,1,2,8,4,3,6,9] 3 4 [0,1,2,3,4,8,6,9] 4 5 [0,1,2,3,4,8,6,9] 6 6 [0,1,2,3,4,6,8,9] 8 시간복잡도 위의 테이블 예시를 보면 n = 8인 array에서 in..

Binary Search Binary Search는 가장 기본적인 탐색 알고리즘 중 하나다. Sorting되어있는 배열의 중간값을 기준으로 크기를 비교하는 과정을 반복하여 search를 진행한다. 만약 77을 찾는다고 하면 가장 먼저 1부터 100 사이의 중간인 middle인 50을 찍는다. 50 77이 되면 87 이후로는 볼 필요가 없기 때문에 버릴 수 있다. 따라서 다음 search에서는 75부터 86 사이의 반을 찍으면 된다. 반복적으로 반을 나눠 (n/2) 들어가기 때문에 $ O(logn) $ 시간에 search가 진..

Matrix의 0을 없애는 방법 Matrix에서 쓸데없는 0들을 없애고 필요한 값만 넣으면 시간을 O(n)으로 줄 일 수 있습니다. 그러면 Marker에서 O(n) Stack에서 O(n) Matrix(이 경우 Linked List or list)에서 O(n)으로 총 O(n)시간으로 줄게됩니다. Linked List 먼저 링크드리스트를 이용하려고 합니다. 동치관계를 위해서는 Insert기능만 필요하므로 Insert만 구현하고 링크드리스트의 자세한 내용은 다음에 포스팅 하겠습니다. Linked List를 사용 할 때는 Matrix를 기억하는 변수 대신 Node를 기억하는 변수를 사용하면 됩니다. List 학교에서 수업을 들을 때는 C++의 벡터를 이용했지만 Python에서는 기본 자료형인 list를 이용하면..

동치관계란? 동치관계란 모든 원소 사이에서 동치율이 성립하는 것을 말한다. 동치관계가 성립하기 위해서는 반사, 대칭, 추이를 만족해야한다. 동치관계를 코딩으로 알기 위해서는? 위의 동치관계가 Minimul Form으로 주어진다고 하자. Minimul Form이란 유추가 가능한 쌍들은 주어지지 않는 것을 말한다. ex) 10 7 -> 총 10개의 node 7개의 input 1 3 3 9 6 2 5 10 7 3 4 9 8 10 동치관계를 위해서는 Marker와 Matrix가 필요하다. 추가로 Stack도 필요하다. Marker은 방문한 Node를 체크하는 역할을 하고 Matrix는 Node간의 연결 관계를 담고있다. 1. 가장 먼저 1번 Node에서 시작한다.(어떤 Node에서 시작하느냐는 상관 없다.) 2..

Queue Queue는Tail에서는 Insert, Head에서는 Delete가 이루어지는 구조이다. 흔히 매표소를 비유한다. First in, First out이다. 성능 Insert: O(1) Delete: O(1) 간단한 구현 Queue를 이용한 미로찾기 1. 현재 위치에서 갈 수 있는 모든 위치를 Queue에 넣는다. 2. Queue에서 위치를 꺼내서 전진한다. 3. Queue가 비었으면 실패한다. 4. 오른쪽 맨 아래에 도착하면 성공한다. BFS 미로찾기의 정확성 DFS 미로찾기와 비슷하다. 갈수 있는 모든 곳은 Queue에 넣으므로 도착지점까지의 좌표 sequence가 있으면 항상 방문한다.

Stack Stack은 Last in, First out구조로 가장 늦게 들어간 데이터가 가장 먼저 나오는 구조이다. Insert/Delete만 제공하고 각각 Push/Pop이라고 부른다. 성능 Push: O(1) Pop: O(1) 간단한 구현 Stack을 이용한 미로찾기 1. 현재 위치에서 주변에 갈 수 있는 위치 중 하나로 이동하면서 이전에 있던 위치를 Stack에 Push한다. 2. 현재 위치에서 주변에 갈 수 있는 위치가 없으면 Stack에서 Pop해서 이전 위치로 돌아간다. 3. 현재 갈 수 있는 곳이 없으며 Stack이 비어있으면 미로찾기에 실패한다. 4. 오른쪽 맨 아래에 도착하면 성공한다. DFS 미로찾기의 정확성 (0, 0)에서 어떤 위치 (s,t)로 가는 길이 있다고 가정한다. (0,0..

수학적 귀납법 단계 수학적 귀납법은 3단계로 구성된다. $$1+2+3+4\cdots+n = \frac{n(n+1)}{2}$$ 를 증명하는 걸로 한다면 1. 기본 n은 1일 때 $$n=1, 1= \frac{1(2)}{2}$$ 이므로 성립한다. 2. 가정 n이 k일 때 $$1+2+3+4\cdots+k = \frac{k(k+1)}{2}$$ 가 참이라고 가정한다. 3. 증명 n이 k+1이면 $$1+2+3+4\cdots+k+k+1 = \frac{k(k+1)}{2}+k+1$$ $$\frac{k(k+1)}{2}+k+1 = \frac{(k+1)(k+2)}{2}$$ 이므로 귀납적 추론에 의해 $$1+2+3+4\cdots+n = \frac{n(n+1)}{2}$$ 가 성립하게된다. 왜 참이라고 가정할까? 수학적 귀납법을 보..

Array란? 동일한 Type을 가진 element가 연속된 주소에 저장되는 자료구조를 말한다. 장점: n개의 데이터중 k번째 데이터 access가 상수시간에 가능하다. 즉, Search가 빠르다. 단점: 크기 변화 비용이 크기 때문에 Insert, Delete가 느릴 수 있다. 변화가 없거나 드문 자료의 경우 사용이 적합하다. Pack Pack은 element를 왼쪽으로 밀어 놓는 것을 말한다. Pack Index 1 2 3 4 Data 1 5 2 X UnPack Index 1 2 3 4 Data 1 X 5 2 Packed, UnSorted 가장 간단한 방법이다. 앞에서 부터 Insert하면 되고 Delete를 할 때는 배열의 마지막 element값을 Delete되는 Index에 넣으면 된다. C++로..