ALGORITHM

Sliding Window - minSubArrayLen

Q. 배열의 연속된 요소들로 이루어진 합 중에서 주어진 수의 이상의 값을 가지는 배열 중 가장 작은 길이를 구하시오 const minSubArrayLen = (arr, n) => { let sum = 0; let len = Infinity; let p1 = 0; let p2 = 0; while(p1 = n) { // 기존의 len과 현재의 len중에 최솟값 구하기 len = Math.min(len, p2-p1..

Priority Queue (우선순위 큐) / JS

// PriorityQueue에 삽입 될 자료구조 class QElement { constructor(element, priority) { this.element = element; this.priority = priority; } } class PriorityQueue { constructor() { this.queue = []; } // element, priority 삽입 enqueue(element, priority) { const qElement = new QElement(element, priority); let isContain = false; for(let i=0; i qElement.priority) { // i번째에 삽입 this.queue.splice(i, 0, qElement); i..

Floyd-Warshall Algorithm (최단경로)

이 알고리즘은 플로이드 알고리즘, 로이-워셜 알고리즘, 로이-플로이드 알고리즘, 또는 WFI 알고리즘으로 알려져 있다. 알고리즘 Floyd-Warshall 알고리즘은 그래프에서 지날 수 있는 모든 경로를 비교한다. 시간 복잡도는 O(n^3)으로, 코드로 짜면 3중의 중첩 반복문을 가진다. 노드i에서 노드j까지 가는 방법은 2가지 중 하나일 것이다. (중간에 k란 노드가 있다고 하자) i에서 바로 j로 가는 경우 i에서 k를 거쳐 j로 가는 경우 위 2가지의 경우의 수 중에서 최단경로가 결국 우리가 구하고자 하는 값이 된다. 따라서 아래와 같이 나타낼 수 있다. floyd(i,j,k) = min(i에서 j로 가는 최단거리, i에서 k로 가는 최단거리 + k에서 j로 가는 최단거리) 코드로 나타내면 아래와같..

에라토스테네스의 체

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수 구하기 알고리즘이다. 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. (위는 120까지가 예시) 짝수 중 유일하게 2는 소수이므로 2는 소수로 체크해준다. (빨간색) 2를 제외한 2의 배수를 모두 지워준다. 3은 소수이므로 3은 소수로 체크해준다.(초록색) 3을 제외한 3의 배수를 모두 지워준다. 5는 소수이므로 5는 소수로 체크해준다.(파란색) 5를 제외한 5의 배수를 모두 지워준다. ... 3~4단계의 과정을 소수를 만날때마다 해주면된다. 간단하게 말해서, 본인이 설정한 범위의 최댓값을 x라고 한다면, 2부터 시작해서 x까지 소수의 배수를 다 지워버리면 된다. 코드(C++)로는 아래와 같이 나타낼 수 있다. voi..

비트연산

마지막 수정 : 2022/01/09 참고 : http://www.tcpschool.com/c/c_refer_bitCalculation 코딩교육 티씨피스쿨 4차산업혁명, 코딩교육, 소프트웨어교육, 코딩기초, SW코딩, 기초코딩부터 자바 파이썬 등 tcpschool.com 비트 단위 연산(bitwise operation) 컴퓨터는 모든 데이터를 비트(bit) 단위로 표현하고 처리합니다. 비트 단위 연산을 통해 사용되는 메모리 공간을 줄이거나, 성능의 향상을 기대할 수 있기 때문이다. 비트 연산자 비트 연산자설명 ~ 비트를 1이면 0으로, 0이면 1로 반전시킴. (비트 NOT 연산) & 대응되는 비트가 모두 1이면 1을 반환함. (비트 AND 연산) | 대응되는 비트 중에서 하나라도 1이면 1을 반환함. (비..