기기

이진 탐색 정렬되어 있는 데이터를 두 부분으로 나누며 값을 탐색하는 알고리즘 비슷하게 분할하는 알고리즘으로 분할정복이 있다. 하지만 분할정복은 문제를 부분적으로 해결하는 알고리즘으로 탐색이 목적이 아니다. 이진탐색은 '수가 존재하는지' 빠르게 알아낼 수 있다. 단 중복원소가 있을 때 가장 왼쪽의 원소의 위치를 반환하는 방법과, 가장 오른쪽 원소의 위치를 반환하는 방법이 있다. 기본적인 메커니즘 탐색 범위 내[low ~ high]의 배열의 중간 인덱스[(low + high)/2]를 구한다. 중간 인덱스 값과 key 값을 비교한다. (key는 탐색하고자 하는 값) key 값이 중간 값보다 작다면 왼쪽 부분을, key 값이 중간 보다 크다면 오른쪽 부분을 탐색한다. 이 과정을 반복하며 key 값이 있을 수 있..

투 포인터 배열에서 이중 for 문으로 O(N^2) 에 처리되는 작업을 2개 포인터의 움직임으로 O(N) 으로 해결하는 알고리즘 리스트에 순차적으로 접근해야 할 때 2개 점의 위치를 기록하며 처리 이 포인터는 c의 포인터가 아닌 가리키는 역할 머지소트에서 정렬되어 있는 두 리스트의 병합의 기초가 되기도 함. 정렬된 2개 리스트를 포인터를 이용해서 하나의 정렬된 리스트 완성 투 포인터는 블로그 설명들을 보면 구현이 조금씩 다양한 것을 알 수 있는데, 이는 포인터와 구간에 대한 문제정의를 맞게 했으면 구현을 어떻게 했던지 간에 풀 수 있는 것을 알 수 있다. 초기 단계 2개 포인터는 리스트에서 시작 s, 끝 e 를 의미 s와 e는 첫 번째 원소를 가리킴 초기에 s와 e가 동일 원소를 가리키기 때문에 문제에 ..

백준에서 Maaaaaaaaaze 문제를 풀고 다른 사람 풀이를 봤었다. 그런데, 배열 회전에서 차이가 있었다 처음 배열 회전 시킬 때, 그냥 한 칸씩 이동하는 과정을 여러 번 반복했었다. 하지만, 회전의 특징? 을 고려하면 더 빠르고 깔끔하게 코드를 짤 수 있었다. 말로 설명하는 것보단 그림을 보는 것이 바로 이해하기 좋기 때문에 그림으로 대체.. 이 그림대로 모든 좌표 ( y, x) 를 ( x, height - y - 1 )로 바꾸면 간단하게 90 회전한 배열을 구할 수 있다. 사실 이걸 몰라도 어떻게든 회전할 수 있지만, 이 방법을 알아두는게 좋을 것 같아 따로 정리했다. 구현 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 ..

binary tree에서 검색 효율이 좋은 자료구조다. 장점 이진 탐색과 링크드 리스트 자료구조를 결합한 형태로 각 장단점을 보완한 것이 BST 이진탐색 : O(logn) 으로 탐색한다. 매번 원소를 비교 시, 비교 대상이 절반으로 줄어든다. 링크드 리스트 : 추가 삭제 시 O(1) 시간 복잡도 트리 높이에 비례한다. 따라서, balanced/unbalanced인지에 영향을 받는다. balanced경우, 탐색이 O(logn)이지만, unbalanced 되면 O(n)이 된다. 이 경우, 다시 rebalancing이 필요하다. 이 기법을 갖는 자료구조가 AVL, red black tree 특징 1 모든 key값은 unique. 그렇지 않으면 조건 2,3 번에 위배된다. 그래서 중복된 key입력이 보이면 co..

tree 자료구조 tree는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조다. 큐, 스택, 리스트와 같은 서형 자료구조와 다르다. parent, child로 노드간의 상위/하위 노드를 표현한다. root노드를 제외한 나머지 노드는 단 하나의 부모노드만 갖는다. 1 tree에는 사이클이 없다. 2 모든 노드는 모두 연결되어 있다. 3 임의의 노드에서 다른 노드로 가는 경로가 유일하다. 쓰임 1 현실 세계 개념을 추상화 2 탐색형 자료구조 구성 Node(노드) : tree를 구성 요소 Edge(간선) : Node간에 연결하는 선 Root Node : 트리에서 최상위 노드 Leaf Node : 트리에서 최하위 노드들로 다른 하위 노드가 없다. Internal Node : Le..

선택 정렬 - 어떤 정해진 위치에 들어갈 원소를 선택하는 정렬 - in-place 정렬 중 하나다. in-place정렬이란 입력 배열 외에 추가적인 메모리가 필요없는 정렬을 의미한다. 공간 복잡도 O(1) - 시간복잡도 항상 O(N^2) 왜냐하면 원소를 선택하기 위해 모든 원소를 검사하기 때문이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 static void swap(int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } static void selectionSort() { // 최소 원소가 들어갈 위치 for(int place = 0 ; place 공간 복잡도 O(1) - 단점 ..

자료구조 구현 1. 자료구조 특징 정리 2. 자료구조 특징에 사용될 변수를 정의한다. 3. 자료구조 특징에 따라 구현한다. 구현 시, 변수를 어떻게 활용할지 고려 4. 자료구조 '최대 입력', '비었을때 제거'와 같이 경계영역? 예외 처리 해준다. ex) 배열 크기, 포인터 역할의 변수 ( 경계 영역에서 어디를 가리켜야 하는지 ) 스택 1. Last In First Out 2. top 이용 마지막 원소의 인덱스 3. 구현 시 주의할 점 pop() 스택이 빈 경우 push() 스택이 다 찬 경우 배열을 이용한 스택 구현 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 static class mySta..

일렬로 늘어선 자료를 저장하기 위한 자료구조. 종류 정적 배열 동적 배열 연결 리스트 정적 배열 - 데이터가 메모리에 연속적으로 저장된다. - 크기가 고정이다. - 시간 복잡도 인덱스를 알면 O(1)로 접근 가능 ( Random Access ) 동적 배열 - 데이터가 메모리에 연속적으로 저장된다. - 크기(capacity)가 동적으로 증가한다. 자바에서 대표적으로 ArrrayList가 동적배열이다. - 시간 복잡도 인덱스 통한 접근 O(1) ( Random Access ) capacity 증가 시, 배열을 복사 후 더 큰 배열로 옮기기 때문에 O(N) 삽입/삭제 시, 기존 원소들의 shift 연산이 필요해서 최악으로 O(N) ex) 첫 번째에 삽입/삭제는 기존의 모든 원소들을 밀어야 하기 때문에 O(N)..