Algorithm (10) 썸네일형 리스트형 [알고리즘 공부] 최근접 점의 쌍 찾기 알고리즘(Closest Pair of Points) - python 파이썬 ▶ 최근점 점의 쌍을 찾는 문제? 최근접 점의 쌍(Closest Pair)을 찾는 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제입니다. 바로 그 문제를 해결하기 위한 방법은 효율적인 분할 정복을 이용하는 것입니다.n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 쌍을 찾고, 2개의 부분 해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾습니다. 여기서 주의할 점!취합할 때 중간 영역을 고려해야합니다. 이게 무슨 말이냐면, 분할된 왼쪽 점 중에 하나, 오른쪽 점 중에 하나가 최근접점 쌍이 될 수 있습니다. 그래서 중간 영역도 왼쪽 부분과 오른쪽 부분의 최단 거리인 10과 15중에 더 짧은 거리 10이내에 있는 각각 왼쪽과 오른쪽 점들만 거.. [ 알고리즘 공부 ] 선택 문제 알고리즘(Selection) (feat.python 파이썬) ▶ 선택문제(Selection)란? ※ 선택 정렬(Selection Sort)과는 다른 알고리즘입니다.선택(Selection) 문제는 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제입니다. 이 문제를 해결하기 위한 단순한 방법은 다음과 같습니다. 1) 최소 숫자를 k번 찾는다.→ 숫자 n개가 들어있는 배열 중에서 최소 숫자를 찾고, 찾을 때마다 입력에서 그 숫자를 제거합니다.시간복잡도는 O(kn), k번째 숫자를 찾을 때까지 반복하는 과정마다 항상 n, n-1, n-2....(최소 숫자는 제거되므로) 개의 숫자들을 탐색하기 때문입니다. 2) 숫자들을 정렬한 후, k번째 숫자를 찾는다.→ 시간복잡도는 O(nlogn), 즉 정렬하는 과정에서 걸리는 시간에 따라 다를 것입니다. (k번째 숫자를 찾.. [ 알고리즘 공부 ] 퀵정렬 퀵소트(Quick Sort) - 분할 정복 알고리즘(feat. python 파이썬) 퀵 정렬이란? 퀵 정렬도 분할 정복 알고리즘입니다. 2개의 문제로 분할합니다. 합병 정렬(Merge Sort) 같은 경우에는 2개의 문제로 분할할 때, 문제의 크기가 항상 같았지만, 퀵 정렬은 일정하지 않은 형태로 분할합니다. 퀵 정렬은 피봇(pivot)이라 부르는 배열의 원소를 기준으로 피봇보다 작은 값은 왼쪽으로, 피봇보다 큰 값은 오른쪽으로 위치하도록 분할합니다. 이 과정을 통해 분할된 왼쪽 배열과 오른쪽 배열에도 동일한 과정을 수행합니다. 이렇게 반복을 하다 보면 배열은 어느새 정렬이 되어 있을 겁니다. 여기서 주의할 점은 피봇(pivot)은 분할된 왼편이나 오른편 부분에 포함되지 않습니다.그 이유는 피봇을 기준으로 왼편과 오른편의 분할 과정을 수행했다면, 피봇의 위치는 확정되었기 .. [ 알고리즘 공부 ] 합병 정렬(Merge Sort) 알고리즘 - 분할 정복 알고리즘(python, 파이썬) 합병 정렬(Merge Sort)이란? 입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘입니다.즉, n개의 숫자들을 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분 문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)합니다. 즉, 합병 과정이 정복하는 것입니다. → 합병이란?2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자들로 합치는 것입니다. 합병 정렬이 어떻게 정렬하는지 감이 안 잡히실 수도 있는데, 이 그림 한 장이면 어떤 알고리즘이신지 알 수 있습니다.(화살표 옆 숫자는 실행 순서를 의미합니다.) 합병 정렬 수행 과정을 설명해 보도록 하겠습니다. 맨 위에 원소의 개수가 8인 배열이 정렬되지 않은 채 있습니다... [ 알고리즘 공부 ] 시간 복잡도(빅오Big-Oh, 빅오메가Big-Omega, 세타Theta) 시간 복잡도란? 알고리즘의 효율성은 알고리즘의 수행 시간 또는 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기로 나타낼 수 있습니다. 이들을 각각 시간복잡도, 공간복잡도로 나타낼 수 있습니다. 시간복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 비례한 함수로 표현합니다.예를 들어, 숫자 카드가 10장이 있고 이 중에서 최대 숫자를 찾는데, 순차 탐색으로 찾는 경우에 숫자 비교가 기본적인 연산이고, 숫자 비교가 9번입니다.숫자 카드가 만약에 n장이 있다면, 숫자 비교는 n -1 번을 하므로 n -1이 시간복잡도가 됩니다. ▶ 복잡도를 표현하는 방법 - 최악 경우 분석'어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다'라는 상한(Upper Bound)의 의미보통 .. [C/C++ 공부] 깊은 복사와 얕은 복사 차이? (feat.복사 생성자) 객체를 생성하고 초기화시킬 때 멤버 변수를 어떻게 초기화하느냐에 따라 깊은 복사가 될 수 있고, 얕은 복사가 될 수 있습니다. *디폴트 생성자가 아닌 일반 생성자는 생성자의 인수를 전달 받아 멤버 변수를 초기화시킵니다.복사 생성자는 별도 생성자를 선언하지 않는다면, 암시적 생성자로 인수로 제공된 객체의 멤버 변수를 복사하여 새롭게 생성하는 객체의 멤버 변수를 생성합니다. ※디폴트 생성자란?명시적인 초기화 값을 제공하지 않았을 때 객체를 생성하는 데 사용하는 생성자. 사용자가 어떠한 생성자도 정의하지 않을 경우에만 컴파일러가 디폴트 생성자를 제공 ▶ 복사 생성자 밑에 보이는 프로그램은 아마 오류가 날 것입니다.왜 그럴까요? #include #include #include class MyString .. [C/C++ 공부] 수정이 불가능하도록 만들어주는 const 상수(또는 const 변수) const란? ↳ 변수에 저장된 데이터는 언제 어느때라도 수정이 가능합니다. 그러나 특정 변수나 포인터는 경우에 따라 수정이 불가하도록 만들어 줄 필요가 있는데, 이러한 성격을 가진 변수를 바로 const 변수 또는 const 상수 라고 합니다. const 상수 사용법 ↳ 아래 코드와 같이 변수 선언 시에 const 키워드를 앞에 사용하면 됩니다. 만약에 const 상수를 수정하고자 한다면 에러가 발생합니다. const double pi = 3.14159;pi = 3.1415926535 //pi에서 에러가 발생합니다. #define 또는 리터럴과의 차이점? ↳ 리터럴과 #define 지시문은 컴파일 시점에 값이 결정되는 반면에 const 상수는 프로그램이 실행되는 시점에 값이 결정됩니다. const .. [알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(2) 앞서 Boyer-Moore 알고리즘에 사용되는 두 원리 중 Bad Character 원리를 살펴 보았다.이번에는 그 나머지 원리인 Good Suffix 원리를 배워보려고 한다. 2021.07.26 - [Algorithm/Pattern Searching] - [알고리즘 공부] Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) [알고리즘 공부] Boyer-Moore Algorithm(문자열 검색 알고리즘)(1)Boyer-Moore 알고리즘 또한 앞서 봤던 KMP 알고리즘과 같이 문자열을 검색할 때, 패턴을 둘 이상 이동할 수 있도록 패턴에 대한 사전 처리를 진행합니다. ↓그 전 KMP 알고리즘 관련 글 2021.07.23 - [Algoribblackscene21.tistory.com Go.. 이전 1 2 다음
