태식 Devlog

오늘 알아볼 알고리즘은 DFS이다. 오늘 백신을 맞아서 백신공가로 쉬고있는데, 사실 좀 피곤한거같다. 이거만 후딱 쓰고 좀 쉬어야겠다. DFS란? 깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89 깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전 ..

한동안은 공채시즌이라서 알고리즘 공부를 좀 해야할 것 같아 코딩테스트용 알고리즘의 간단한 이론과 함께 연습을 해야겠다. 이번에 알아볼 알고리즘은 Dynamic Programming(줄여서 DP)이다. Dynamic Programming이란?? 수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 출처 : 위키백과 동적 계획법은 문제를 여러개의 하위 문제로 나누어 푼 다음, 그것을 다시 결합하여 최종적 목표에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤..

오늘 알아볼 알고리즘은 브루트 포스(Brute Force)라는 알고리즘이다. 사실, 학교 알고리즘 시간에 이 단어를 들어본 적은 없다. 하지만, 최근 모 기업에서 코딩테스트를 보고 관련된 문제가 나와서 한번 정리해봐야겠다는 생각을 했다. 브루트 포스의 사전적 의미 - 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법. 브루트 포스 공격(brute force attack) 또는 키 전수조사(exhaustive key search), 무차별 대입 공격(無差別代入攻擊) 등으로도 부른다. 흔히 수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 버전이다. 주로 암호학에서 연구되는 방법이나, 다른 알고리즘 분야에서도 사용되고 있다. 쉽게 말하면, 그냥 가능한 모든 경우의 수..

오늘 알아볼 내용은 Quick Sort이다. 왜 많고 많은 정렬 알고리즘(버블정렬, 삽입정렬, 힙정렬, 합병정렬, 등등....) 중에 하필 Quick Sort?? - 가장 많이 쓰는 정렬 알고리즘 중의 하나이기도 하고, 그만큼 꼭 알아야 하는 정렬 알고리즘 중에 하나이기 때문이다. Quick Sort의 동작 원리 - 기준 값(Pivot)을 정한 후에, 기준 값의 앞에는 기준 값보다 작은 모든 원소가 가고, 피벗 뒤에는 기준 값보다 큰 모든 원소들이 가게 된다. 이렇게 리스트를 둘로 나누고 나면, 분할된 두개의 리스트에서 같은 작업을 반복한다. 이 두개의 리스트가 0 또는 1이 될 때까지 진행한다. 즉, 운빨 알고리즘(?) 이라고 할 수 있다. 왜냐하면, 기준 값을 어떻게 고르는가에 따라서 알고리즘이 굉장..

오늘 알아볼 것은 레드블랙트리의 간단한 개념이다. 레드블랙트리는 STL map 자료구조에 사용되는 자료구조이고, 자동으로 균형을 잡아주는 트리이다. 균형을 잡는 것이 왜 중요할까? 라는 질문에 대해 그림을 하나 그려보겠다. 다음과 같은 이진트리가 있다고 가정해보자. 내가 찾고자 하는 값은 5이다. 위의 트리는 균형이 잡혀있지 않은 트리이기 때문에, 5까지 접근하기 위해서는 3번의 이동이 필요하다. 하지만, 균형잡힌 트리의 경우 어떻게 되는지 살펴보자. 다음과 같은 트리의 경우 어떤 경우에도 3번의 이동까지 하지 않고 모든 원소에 접근할 수 있다. 이처럼, 균형 잡힌 트리는 알고리즘의 성능에 큰 도움을 준다. 위의 설명을 좀 더 깔끔하게 하자면, 이진탐색트리의 경우 저장 또는 탐색에 평균적으로 O(logN..

오늘 포스팅 주제는 A Star 알고리즘이다. // 11.21 추가 내용 정보과학 분야에 있어서, A* 알고리즘(A* algorithm 에이 스타 알고리즘[*])은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프 탐색 알고리즘 중 하나이다. 이 알고리즘은 다익스트라 알고리즘과 유사하나 차이점은 각 꼭짓점에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값 "을 매기는 방법을 이용한다는 것이다. 이 알고리즘은 이 휴리스틱 추정값의 순서로 꼭짓점을 방문한다. 그러므로 A* 알고리즘을 너비 우선 탐색의 한 예로 분류할 수 있다. 이 알고리즘은 1968년 피터 하트, ..