jyoon dev log

순열과 조합 순열(順列, permutation)은 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것이다. 조합과 마찬가지로 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다. 순열은 조합과 달리 순서를 따져서 부분집합을 만든다. 과일 3개 집합에서 부분 집합 만들 수 있는 경우는 6가지 된다. 순열 공식 순열은 일반화 과정을 거쳐, Permutation의 약자 P로 표현한다. N: 원소의 총 개수를 의미 R: 그중 뽑는 개수를 의미 중복을 허용하지 않기 때문에 반드시 R

공간 복잡도는 알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미한다. 프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미한다. 프로그램이 요구하는 공간은 고정적인 공간과 함께 가변적인 공간을 함께 요구한다. 가변적인 공간은 처리할 데이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향을 준다. 공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오(Big-O) 표기법으로 표현한다. 공간 복잡도 예시 function factorial(n) { if(n === 1) { return n; } return n*factorial(n-1); } 함수 factorial은 재귀함수로 구현되었습니다. 변수 n에 따라 변수 n이 n개가 만들어지게 되며, factorial 함수를 재귀함수로 1까지..

그래프 탐색 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 깊이 우선 탐색(DFS, Depth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 미로를 탐색할 때 한 방향으로 갈 수 있을 때 까지 계속 다가다 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 넓게 탐색하기 전에 깊에 탐색하는 것이다. 사용하는 경우 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다 깊이 우선 탐색(DFS)이 너비 우선..

Memoization으로 중복 연산을 방지하며, 작은 부분 문제로 큰 문제를 해결 하며 해를 도출하는 알고리즘 설계 기법. 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 동적 계획법 특징 부분 문제는 중복되며, 상뮈 문제 해결 시 재사용한다. Memoization 기법을 사용한다( 동일한 계산을 반복할 때, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 따라서 이전에 계산한 값을 메모리에 저장하여 중복 연산 방지함) 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다. 1. 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 (O..

매 순간 최적 해를 선택하면서 최종적으로 최적해에 도달하는 알고리즘 설계 기법 탐욕 알고리즘 특징 최적 부분 구조나 탐욕 선택 속성 문제를 해결하는데 적합하다. 매 순간 최적 해를 찾으면서 구하는 방법이 항상 최적임을 보장하지 않아서 유의가 필요하다. 탐욕 알고리즘으로 문제 해결하는 방법 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다. 탐욕 알고리즘 조건 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 ..

DFS (Depth First Search) 트리나 그래프 등에서 하나의 노드를 최대한 깊게 들어가면서 해를 찾는 탐색 기법 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. (재귀 or 스택) 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다. 검사하지 않을 경우 무한루프에 빠질 수 있다. ex) vistit[index] = true; 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 모든 노드를 방문하고자 할 때, 이 방법을 선택한다. 너비우선탐색(BFS)보다 더 간단하다...

🌼 시간복잡도 알고리즘의 로직을 코드로 구현할 때, 시간복잡도를 고려한다는 것은 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?'라는 말이다. 효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성하는 것이다. 시간 복잡도는 Big-o 표기법을 사용해 나타낸다. 🌼 Big-o 표기법 시간복잡도를 표기하는 방법 Big-O(빅-오) ⇒ 상한 점근 (최악의 경우) Big-Ω(빅-오메가) ⇒ 하한 점근 (최선의 경우) Big-θ(빅-세타) ⇒ 그 둘의 평균 (평균의 경우) 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다. 이 중에서 Big-O 표기법이 가장 자주 사용되며..

정렬(sorting) 배열 내 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘. 1. 거품정렬(bubble sort): 서로 인접한 두 원소를 비교하면서 정렬하는 알고리즘 평균 시간 복잡도: O(n^2) 1.인접한 값 비교 => 큰값 교환 2. index N번 3. N 차례 N-i //swap함수는 arr를 받고 매개변수 두개를 받아 각각의 인덱스를 받는다. let swap = function (arr, idx_1, idx_2){ //원소의 값 교환 let tmp = arr[idx_1]; arr[idx_1] = arr[idx_2]; arr[idx_2] = tmp; }; let bubbleSort_1 = function (arr){ for (let i = 0; i < arr.leng..

힙 정렬 (Heap Sort) 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬 방식 힙 정렬은 병합 정렬과 퀵 정렬만큼 빠른 정렬 알고리즘이다. 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리다. 힙에는 최대 힙과 최소 힙이 존재하는데 최대 힙은 부모 노드가 자식 노드보다 큰 힙이라고 할 수 있다. 힙정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야 한다. 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘 (Heapify Algorithm)을 사용한다. 힙 생성 알고리즘은 특정한 하나의 노드에 대해서 수행하는 것이다. 힙 생성 알고리즘은 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 힙 정렬은 병합 정렬과 다..

데큐(Double-ended Queue) 특징 큐와 스택의 장점을 합쳐놓은 자료구조 양쪽 끝에서 삽입과 삭제가 모두 가능 Scroll(입력제한데크) : 입력이 한쪽 끝으로만 가능하도록 설정한 데크 Shelf(출력제한데크) : 출력이 한쪽 끝으로만 가능하도록 설정한 데크