0. 들어가며 프로그래머스 순위 탐색 문제를 풀다가 이진 탐색을 실제로 사용해야 하는 상황이 발생해서 정리를 해보았다. 이진 탐색 자체에 대한 내용은 깊게 다루지 않고 어느 정도 이해한 상태라고 가정하고 작성한다. 1. 사용 방식 [10, 30, 50, 60, 100, 200] 이란 배열이 있을 때, 기준 값으로 70이 주어지면 배열에서 70 이상의 값의 개수가 몇 개인지 확인할 때 사용하였다. 2. 코드 구현 for (const item of query) { // item은 query의 값 const key = item.split("and ").join("").split(" "); const score = parseInt(key.pop()); const joinKey = key.join(" "); co..

0. 들어가며 프로그래머스 순위 탐색 문제를 풀다가 배열을 참조해서 순차적으로 배열을 변경하는 경우가 의외로 많이 있는 것 같아서 정리하였다. 1. 사용 방식 예를 들어 [a, b, c, b, e]라는 배열이 있는데, 이것을 [-, b, c, d, e], [-, -, c, d, e], ... [a, b, c, d, -] 순으로 모든 경우의 수를 다 만들어야 하는 상황이 있을 것이다. 그럴 경우에 반복문을 통해서 만들어도 되지만 그렇게 만들려면 배열의 길이는 고정되야하고 배열의 속성 개수에 따라 반복문 개수도 변경되기 때문에 일반적으로 재귀함수를 사용한다. 2. 코드 구현 const info = [ "java backend junior pizza 150", "python frontend senior chi..

1. 배열 연관된 데이터를 연속적인 형태로 구성된 구조를 가진다. 배열에 포함된 원소는 순서대로 번호(index)가 붙는다. 특징 고정된 크기를 가지며 일반적으론 동적으로 크기를 늘릴 수 없다. - 자바스크립트처럼 스크립트 언어의 경우 동적으로 크기가 증감되어진다. 원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있다. 원소를 삭제하면 해당 index에 빈자리가 생긴다. 2. 배열의 요소 삭제 [1, 1, 2, 3, 5, 7, 10, 13, 34] 인 배열이 있다. 여기서 7을 제거할 경우 진행되는 방법을 보자면 1. 7이 삭제된다. => [1, 1, 2, 3, 5, ` `, 10, 13, 34] 2. 10이 앞으로 한칸 이동한다. => [1, 1, 2, 3, 5, 10, ` `, 13..

1. 구조 분해 할당을 이용한 변수 swap ES6의 구조 분해 할당 문법을 사용하여 두 변수를 swap 할 수 있다. let a = 5; let b= 10; [a,b] = [b,a]; console.log(a, b); // 10 5 2. 배열 생성으로 루프 제거 let sum = 0; for (let i = 5; i k + 5) .reduce((acc, cur) => acc + cur, 0); 만약 범위 루프를 함수형 프로그래밍 방식으로 사용하고 싶다면 배열을 생성해서 사용할 수 있다. Array .from(new Arr..

Big-O notation 프로그램의 성능을 알기 위해선 입력 크기, 하드웨어 성능, 운영체제 성능 .... 등 고려해야할 것이 많다. 따라서 프로그램의 성능을 정확하게 파악하는 것은 불가능하다. 그래서 대략적인 성능을 비교하기 위한 상대적인 표기법(Big-O notation)을 사용한다. O(1)에서 O(log n) .... O(n!)로 갈수록 점점 시간이 오래 걸린다. O(log n)과 O(n)이 눈으로 봤을 때는 크게 차이가 없는 것 같지만 n이 1024일 경우 O(n)은 1024번 반복하지만 O(log n)은 10번만 반복하게된다. O(3n - 30)이나 O(3 log n)같은 시간 복잡도는 본적이 없을 것이다. 그 이유는 Big-O notation이 점근적 표기법을 따르기 때문이다. 점근적 표기..

1. 자료구조? 메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다. 특정 상황에서는 빠르게 작동하지만 반대로 특정 상황에서 느리게 작동할 수 있기 때문에 상황에 맞는 자료구조를 고를 수 있는 능력이 필요하다. 자료구조의 종류는 다음과 같이 있다. 선형 구조 한 원소 뒤에 하나의 원소 만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가진다. 선형 구조에 해당되는 자료구조는 배열, 연결 리스트, 스택, 큐 등이 있다. 비선형 구조 원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절하다. 비선형 구조에 해당되는 자료구조는 트리와 그래프 등이 있다. 2. 알고리즘? 특정 ..

우리가 문제 해결 시에 사용하는 동적 계획법(DP) 또는 분할 정복과 같은 완전 탐색에 기초한 디자인 패러다임은 실생활에서 사용하기 매우 한정적이다. 예를들어, 인공지능 체스 프로그램을 브루트 포스 방식으로 짠다면 이동 가능한 모든 말의 움직임을 다 확인한다. 하지만 이 방법으로 개발한다면 말과 이동할 수 있는 칸이 너무 많기 때문에, 게임이 끝나지 않는다고 한다. (경우의 수가 10^120 가지) 결국 모든 경우의 수를 확인하지 않고도 답을 찾아낼 수 있는 방식을 사용해야 한다. 휴리스틱 알고리즘이란? 불충분한 시간이나 정보로 인해 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않을 경우 보다 빠르게 사용할 수 있는 추론의 방법이다. 기본적으로 가능성이 없는 답들을 탐색하는..

크루스칼 알고리즘 : 가장 적은 비용으로 모든 노드를 연결하기 위해 사용되는 알고리즘 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘입니다. ​ ※ 신장 트리 : 그래프 내의 모든 노드를 포함하는 트리 노드 = 정점 = 도시 : 그래프에서 동그라미에 해당하는 부분 간선 = 거리 = 비용 : 그래프에서 선에 해당하는 부분 ​ 위 그래프를 살펴보았을 때 6개의 노드와 8개의 간선이 있습니다. 해당 그래프를 크루스 칼 알고리즘을 적용시켜 본다면 아래와 같습니다. ​ 잠시 그래프에서 모든 노드를 연결하기 위해 최소한으로 필요한 간선의 수는 N( 노드) - 1개입니다. 즉 위 그래프는 노드가 6개 있으므로 최소 비용 신장 트리를 만들기 위해 필요한 간선의 수는 5개입니다. ​ 일단 모든 노드를 최대한 적은 ..