* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 앞선 포스팅에서 살펴 본 이진 탐색 트리를 통한 searching은 일반적으로 시간 복잡도가 O(logN)이다. 그러나, 트리가 불균형할 경우, 시간 복잡도가 O(N)까지 상승할 수 있다.https://cascade.tistory.com/97 [열혈자료구조] 11강. 탐색(Search) 1* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 11강에서 다루는 이전에 다루었던 단순 탐색, 이진 탐색을 다루는 것이 아니라, 트리 구조를cascade.tistory.com 예를 들어, 아래와 같은 트리가 "불균형한 트리"이다.이러한 트리의 모양은 5, 4, 3..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 11강에서 다루는 이전에 다루었던 단순 탐색, 이진 탐색을 다루는 것이 아니라, 트리 구조를 기반으로 하는 탐색을 다룬다. 즉, 데이터를 어떻게 저장하는지가 탐색의 효율에 큰 영향을 미칠 수 있다. 단순 탐색과 이진 탐색은 이전 포스팅을 참고!! https://cascade.tistory.com/62 탐색 알고리즘 (백준 1920번)무작위로 N개의 수가 들어있는 리스트가 있다고 하자. 이 안에 특정 수 x가 들어있는지 찾는 최적의 알고리즘은 무엇일까? 이런 류의 문제를 탐색(searching)문제라고 한다. 탐색 문제에는 크게 세cascade.tistory.com 보간 탐색(Interpolation S..

해시폰켓몬당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 5. 병합 정렬(Merge Sort) 병합 정렬은 divide and conquer라는 알고리즘에 의해 근거하였다. 16개의 데이터를 정렬한다고 하면, 8개짜리 2개로 나눠서 정렬하고 합치는 것이 더 효율적이라는 것이다. 즉, 8개를 다시 4개로, 4개를 다시 2개로 ... 재귀적으로 가장 작은 단위까지 정렬할 데이터를 쪼개면, if문만으로 정렬이 가능한 것이다. 그리고 이를 합쳐 가며 하나로 만들면 된다. 병합 정렬은 구현이 조금 까다롭다. 먼저, MergeSort 함수는 정렬 대상이 되는 데이터의 개수 정보가 아닌 정렬 대상의 범위 정보를 전달해야 한다. 정렬 대상을 계속 쪼개 가면서 진행할 것이기..

OpenCV는 오픈소스 컴퓨터비전 라이브러리로, python에서 이미지 혹은 영상처리를 할 때 유용하게 사용할 수 있다. OpenCV 패키지 설치 먼저, OpenCV 패키지는 아래 명령어로 설치할 수 있다. pip install opencv-python OpenCV로 이미지 읽어오기 OpenCV의 cv2.imread() 함수를 이용해 이미지를 읽어올 수 있다. 이미지는 NumPy의 다차원 배열(numpy.ndarray) 객체로 저장되며, 이 배열은 이미지의 픽셀 값을 저장한다. 이미지 배열은 아래 요소를 갖는다. 색상: 이미지의 색상은 B, G, R 순으로 저장되며, 색상 채널은 0~255 사이의 값을 가진다. 형태: 이미지 배열은 (높이, 너비, 채널 수)로 표현되고, 흑백 이미지는 채널 수 없이 (높..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 1부터 N까지의 수가 한 줄로 무작위 순서로 서 있다. 이들을 크기 순서로 세우는 최적의 알고리즘은 무엇일까? 본 포스팅에서는 각종 정렬 알고리즘을 교재를 바탕으로 정리해보고자 한다. 정렬 알고리즘의 성능은 비교의 횟수와 이동의 횟수가 결정한다. 그리고 이를 기준으로 Big-O notation을 정한다. 1. 버블 정렬(Bubble Sorting) 버블 정렬은 연속한 두 개의 항을 비교하여, 앞의 것이 크기가 크면 순서를 바꾸고, 뒤의 것이 크면 순서를 유지하는 방법이다. 앞에서부터 뒤로 훑는 이 과정을 모든 수가 정렬될 때까지 반복한다. 버블 정렬의 코드는 아래와 같다. #include void Bu..