밤낮개발

import java.util.Scanner; public class Q1855 { public int fibonacci(int n) { /* Fibonacci sequence is a sequence f numbers where each number is a sum of two precedent numbers. * Thus, sequence looks as follows: 1 1 2 3 5 8 13 21 34 ... * For nth fibonacci number, the repetition occurs n times, each of which adds two numbers, starting from 0 and 1. * e.g. 3rd fibonacci number: requires computing ..

Introduction To backtrack means going back to a previous step. Backtracking algorithm is applied to problems finding the solution step-by-step. For instance, we use backtracking algorithm for searching the path to a destination in a maze. On every direction taken carefully, algorithm judges whether this choice would lead to an escape. If a step taken currently is confirmed to be a part of the po..

지난 시간, 리스트를 활용해서 퀵 정렬을 보다 직관적으로 구현해보았다. 이번에는 이론 (Array 1단계) 에서 설명한 구현에 이어서 재귀호출과 배열을 사용해 퀵 정렬을 구현해보자. 배열을 활용한 퀵 정렬 - 시간복잡도: O(logN) - 공간복잡도: O(N). 이론에서 설명한 대로 한 차례 루프를 돌고 나면, 이제 배열을 쪼갤 차례이다. 기준 값이 이동하는 것이다. 그 전에, 먼저 메서드의 매개 변수를 추가해주어야 한다. 추적하기 위함인데, 쪼개진 배열의 첫 번째와 마지막 인덱스로, 계속 어디를 기준으로 쪼갤지를 명시한다고 생각하면 된다. 이 매개 변수가 변하면서 재귀적으로 메서드를 호출하면 된다. 그래서 정수 startIdx, endIdx 를 새로운 메서드의 매개 변수로 넣어주고 구현한다. publi..

배열이 주어졌을 때, 임의로 기준값을 정하여 기준보다 작은 수와 큰 수들의 집합으로 쪼개는 과정을 각 집합이 더이상 쪼개질 수 없을 때까지 반복한 후, 나누어진 집합들을 각각 정렬한 후 병합하는 알고리즘 Pivot? noun. a fixed point supporting something that turns or balances 명사. 변하거나 균형을 맞추는 것들을 받쳐주는 고정된 지점 Quick Sort 적용 과정 1단계: 대소비교를 통해 세 개 내지는 두 개의 리스트로 분리, 각 리스트 내에는 기준값보다 크고 작은 수들이 모여 있도록 함. import java.util.ArrayList; import java.util.List; public class QuickSort { /* 1. 배열의 중간(크기..

QuickSort 는 어려운 부분이 포인터 총 세 개를 이용해서 하나는 기준값, 하나는 맨 왼쪽의 원소, 하나는 맨 오른쪽의 원소를 가리킨 채로 시작을 한다는 점이다. 기준값을 가지고 어떠한 액션을 취할 것 같은데, 사실 기준값은 말 그대로 기준의 역할 외에는 하는 것이 없다. 기준 값을 기준으로 현재의 두 원소들을 (포인터들로 가리키고 있다) swap할 것인지, 아니면 다른 원소를 찾을 것인지를 결정한다. 다른 원소를 찾기로 결정되면 포인터가 가리키는 위치를 증가 or 감소시킨다. 이후 다음 iteration phase 에서 이번 두 원소는 swap 할 조건을 충족시키는지 확인한다. (즉, 왼쪽 포인터는 pivot 보다 더 큰 원소를 가리키고, 오른쪽은 pivot 보다 더 작은 원소를 가리키는 상황) ..

Introduction Queue data structure follows First In First Out (FIFO) order. Not like Stack data structure, Queue allows the least recently added value to be freed the earliest. Thus, Queue data structure is more in accordance with common sense in reality familiar to us. Implementation Since Queue takes out the value pushed the earliest above all, two pointers are required for tracking the working..

Introduction One of the most famous data structures used in JAVA is Stack. Stack follows "LIFO (Last In First Out)" order, meaning a data value pushed on stack firstly is popped with priority. This rule Stack data structure follows may be unfamiliar to us, as we are more used to the concept of lining up. In the formation of lining up, the person who walked into a line earlier would enter into th..