개발/알고리즘

그리디(Greedy) 알고리즘

그리디 알고리즘은 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘이다. 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. --> 그냥 이래저래 결과를 도출하자? 이렇게 느껴지긴 한다. 그리디 알고리즘은 탐욕적, 갈망법 기법 등으로 다양하게 불리기도 한다. 내가 동빈나 유투브를 보며 알고리즘을 공부하는데, 거의 이 내용은 동빈나에서 더욱 자세히 설명과 함께 들을 수 있다. https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw/featured 동빈나 안경잡이개발자 나동빈입니다. www.youtube.com 그리디 알고리즘은 최적의 해를 보장하지 못하는 경우가 더 많다. #include usi..

라빈 카프(Rabin-Karp)알고리즘

일반적인 경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘이다. 라빈 카프알고리즘의 특징 중 해시를 사용한다는 것이다. 여기서 해시를 알고가야하는데, 해시는 일반적으로 긴 데이터를 짧은 데이터로 바꿔주는 특징을 가지고 있다. 참고로 단순 해시 알고리즘의 경우는 연산 속도는 O(1) 달하고 있다. 라빈 카프 알고리즘은 문자열의 해시 값을 비교하여 그 일치 여부를 검사하는 알고리즘. 0. 각 문자의 아스키코드 값에 2의 제곱 수를 차례대로 곱하여 더해준다. --> 이러한 경우에는 강한 충돌성을 보여준다. 충돌이 발생하면? 포인터를 이용해 연결 자료구조를 이용해 해결한다고 한다. 문자열을 시작 인덱스에서 한칸 한칸 옆으로 옮겨가며 해시값을 구하고, 패턴의 해시값을 비교한다. --> 한칸 한칸 옆으로 옮..

KMP(Knuth-Morris-Pratt)알고리즘

문자열 비교 알고리즘 중 단순 비교 알고리즘보다 효울적인 알고리즘이다. 먼저 단순 비교 알고리즘은 패턴을 옆으로 하나하나 옮겨가며 비교하는 알고리즘인데, 생각해보면 문자열의 길이 n, 패턴의 길이 m 이라고하면 O(nm)이라는 시간복잡도가 나올 수 있다. 즉, 문자열과 패턴의 길이가 길면 길수록 시간복잡도는 커진다. 그래서 KMP 알고리즘은 모든 경우를 다 비교하지 않아도부분 문자열을 찾을 수 있는 알고리즘이다. Idea. 일치하지 않는 부분 이전까지 한 번에 위치를 옮기면 어떨까? KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 반복되는 연산을 얼마나 줄일 수 있는지를 판별하여 매칭할 문자열을 빠르게 점프하는 기법이다. --> 참고로, 나는 접두사 접미사 개념을 겨우겨우 진짜 이해했다. 여기서 실패..

계수 정렬(Counting Sort)

먼저, 계수 정렬은 '범우 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘 얼마나 빠르냐면 시간 복잡도가 O(N) 계수 정렬은 크기를 기준으로 세는 알고리즘 Ex) {1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1}; 예를 들어 이런 배열을 정열한다고 생각합시다. 보이는 배열의 데이터들은 5이하이다. 그래서 1의 개수를 세고, 2의 개수를 세고, ,,, 5의 개수까지 세서 새롭게 출력해주는 것이다. #include int main(void) { int temp; int count[5]; int array[30] = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5..

힙 정렬(Heap Sort)

힙 정렬이란? 힙 트리 구조를 이용하는 정렬 방법 힙 정렬 선행 지식: 힙 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진트리 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 --> EX) 최대 힙(Max Heap), 최소 힙(Min Heap) 완전 이진트리를 표현하기 위해 배열을 사용해도 된다. 배열에서 데이터와 Index 관계가 매우 중요하다 먼저, 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘을 사용 힙 생성 알고리즘의 시간 복잡도는 O(log N) 트리를 힙 구조로 변환하는 시간 복잡도는 O(N..

퀵 정렬 (Quick Sort) - 정의

얼마나 빠르길래 이름 자체가 퀵 정렬일까? 지금까지 선택, 버블, 삽입 정렬들은 이름에서 어떻게 해결하는지 알 수 있었는데, 이건 유추가 불가능 퀵 정렬 - 피봇(Pivot)을 고르고, 피봇보다 작은 값은 피봇의 왼쪽, 큰 값을 피봇의 우측 이동해 정렬하는 알고리즘 - 분할 정복 방법 - 평균적으로 O(N*logN)을 보여주고 있으나, 최악의 경우 O(N^2)의 시간복잡도를 가짐. - 최악의 경우는 이미 정렬 되어 있는 경우를 의미. - 퀵 정렬 알고리즘은 코드를 따라가면서 직접 해보는게 좋다. - 추가로 코드를 올릴 예정

기본 정렬 비교 (1)- 선택 정렬, 버블 정렬, 삽입정렬

기본 정렬에 대해서 설명하려고 한다. 다른 부가 설명이 추가되면 좋겠지만, 직관적으로 설명하기 위해 특징만 쓴다. 소스 코드는 하나하나 다뤄보면서 업로드 할 예정이다. 1) 선택 정렬 ( Selection Sort ) - 가장 작은 값 또는 큰 값을 선택해서 차례로 앞에서부터 정렬하는 알고리즘 - O(N^2) 2) 버블 정렬 ( Bubble Sort ) - 바로 옆에 있는 데이터와 비교해서 정렬하는 알고리즘 - 그래서 계속 옆과 비교해서 거품같다해서 버블 정렬이라고 하는 것 같음. - O(N^2) --> Big-O 표기라서 선택 정렬과 다를 게 없어 보이지만, 진짜 코드를 보면 최악 그 자체 3) 삽입 정렬 ( Insertion Sort ) - 각 숫자를 적절한 위치에 삽입해 정렬하는 알고리즘 - 필요할..

이진 탐색과 이진 탐색 트리

처음엔 두 단어만 봤을 때, 그냥 같은 건데 사람들 차이인 줄.. 정확하게 말하면 이진 탐색 : '정렬된 데이터 집합'에서 사용할 수 있는 탐색 알고리즘, 탐색 범위를 1/2씩 줄여나가는 방식에 붙여진 이름 이진 탐색 트리 : '이진 탐색'을 위한 '이진트리' --> 말장난 같은데, 뭐 더 좋은 정의는 없는 것 같다 이진 트리에 대해서 알고 오면 좋다. 이진 탐색 트리에서 제일 큰 특징이 있는데, 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 크다. 그래서 이진 탐색 트리는 추가적으로 설명할 예정

알고리즘을 공부하면서 느낀 것

해당 내용은 C++개발자한테만? 필요한 내용일수 도 있음. 엄청나게 주관적이니, 댓글을 남긴다면 겸허히 받아들이겠음. 사실 C로 구현된 알고리즘, 자료구조책으로 공부하고 있는데, C++ STL에서 이미 손쉽게 함수하나로 쓸 수 있게 만들어놓은게 있다. STL 공부를 안해서 모르나, 공부하다가 자료를 찾아보면 있더라 그래서 STL도 공부 필수 리스트이지 않을까해서 여기다가 글을 남긴다 C++ STL 도 공부하기

정렬 - 버블정렬

왜 버블인가 했는데 그냥 바로 옆에 있는 애들끼리 계속 비교하고 바꾸고 해서 거품 같다해서 이름을 지어준 것 같다 --> 썰인지, 진짜인지는 모르겠지만? 버블 정렬의 핵심 생각 : 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행 버블 정렬은 효율은 거품처럼 좋지 않다. 그러나 내가 버블 정렬 알고리즘을 쓰기 위해 배운건 아니고, 다른 효율적인 정렬을 배우기 전에 그냥 다들 생각할 수 있는 일반적인 방법을 배워본 것이다. 사실 그림으로 설명해주고 싶은데, 아직 그정도의 실력을 가지고 있지 않다. Github에 코드 있다 그러나 보기 귀찮은 사람을 코드 스크린숏 정도는 올려준다 틀린 부분이나 있으면 댓글 남겨주세요 https://github.com/Park52/Bagic_Alg..