Intro 알고리즘 문제를 풀 때 매우 많은 상황에서 주어진 데이터를 정렬해야 할 경우가 생깁니다. 기본적으로 길이 N의 배열에서 특정 수를 찾는다면, 일반적인 탐색으로는 N번의 비교가 필요하지만, 정렬이 된 데이터라면 log(N) 번의 비교만에 찾아 낼 수 있는 강력한 binary Search를 사용 할 수 있습니다. 프로그래밍을 처음 공부하거나 자료구조를 공부 할 때 기본적인 정렬 알고리즘을 여러가지 배우게 되는데요. 흔히 기본적으로 접하게 되는 정렬 알고리즘을 살펴 보면.. O(n²)인 정렬 알고리즘 버블 정렬 선택 정렬 삽입 정렬 O(n log n)인 정렬 알고리즘 병합 정렬 힙 정렬 퀵 정렬 정도가 있습니다. 자바에서 정렬의 경우에는 기본적으로 DualPivotQuicksort로 구현이 되어 있..

Intro LeetCode 의 코딩 문제들을 풀다보면 자주 나오는 Node 계열 클래스들이 있습니다. 대표적으로 TreeNode와 ListNode 등이 있는데요. 처음 이런 문제를 접할 때에는 너무 당황해서 어떻게 풀어야 할지도 모르고 테스트 코드를 작성하기도 참 막막 한데요, 지금은 어느정도 익숙 해 졌다 보니 묵묵히 inner class로 복사해 집어 넣은 후에 코드를 작성 하기 시작합니다. TreeNode 예제 문제 https://leetcode.com/problems/range-sum-of-bst/ ListNode 예제 문제 https://leetcode.com/problems/merge-nodes-in-between-zeros/ 하지만 매번 같은 코드를 복사해서 이너클래스로 넣어서 만드는 것도 ..

Intro 개발공부를 시작 한 이후로 오랜 취미중 하나였던 온라인 게임을 그만 두었습니다. 사실 온라인 게임을 오래동안 해 왔던 이유는, 그 자체가 재밌다는 이유도 조금은 있었지만 그보다는 주로 무료한 시간을 달래기 위함이었습니다. 그러면서 게임이라는 가상 공간에서 모르는 사람들과 만나 협력하고 경쟁하여 승리를 따냈을 때의 그 달콤한 성취감에 중독되어서 시간이 남는다. 무료하다. 이 두가지 조건이 만족될때면 어김없이 게임을 하곤 했었습니다. 그러다 한국에 돌아와 2020년 11월. 개발 공부를 시작 한 이후로 게임을 하는 첫번째 조건이었던 시간이 남는다 로 로직을 타는 경우가 전혀 없게 되었습니다. 우선순위큐에 꾸준히 다음 학습 해야 할 것 이라는 항목으로 꾸준히 다음 할 일이 쌓이고 있으며 취업을 한 ..

Intro 프로그래머스 3단계에 해당하는 가장 긴 팬린드롬 문제를 풀어보았습니다. 팰린드롬은 앞으로 읽어도, 반대로 읽어도 똑같은 단어를 말하는데요, 기러기, 스위스등이 있습니다. 2020년에 개봉한 크리스토퍼 놀란 감독의 영화 TENET에서도 영화 전반에 걸쳐 palindrome의 의미가 녹아들었으며, 그 제목 자체도 팬린드롬 이였습니다. 문제가 워낙에 간단하기 때문에 금방 풀 거라고 생각 했는데, 몇가지 간과했던 점들이 있기 때문에 총 4번의 시도 끝에 풀이 하였습니다. 특별한 알고리즘이 필요한 문제는 아니지만 효율성 체크가 기다리고 있는 문제이기 때문에 제법 고민이 필요합니다. 문제 문제의 조건 자체는 굉장히 간단합니다. leetcode.com 에서는 공개된 2107개의 테스트 중 무려 5번째에 위..

Heap Heap은 최소값 및 최대값을 최대한 빠르게 찾아내기 위해 특별히 고안된 자료 구조 입니다. 완전 이진트리(마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리의 형태)를 기본으로 하고 있으며, 그 목적에 걸맞게 두개의 타입으로 나뉩니다. Max-Heap Max-Heap 에서 root 노드의 key는 무조건 해당 노드의 자식 노드들의 key보다 크거나 같습니다. 또한 같은 속성이 모든 sub-tree 들에게도 재귀적으로 적용됩니다. 간단히 말해 Max-Heap 트리에서 자식 노드에 딸린 트리 하나 하나가 모두 Max-Heap의 조건을 만족합니다. Min-heap Min-Heap 에서는 반대로 root 노드의 키값이 모든 자식들의 키 보다 작거나 같습니다. 또한 재귀적으로 자식 트리들 하나..