본문 바로가기

Bootcamp/Algorithm40

[algorithm] 순열 문제 1부터 N까지 자연수 중에 M(M [1, 2] const output2 = permutation(3, 2); console.log(output2); // --> [12, 13, 21, 23, 31, 32] const output3 = permutation(3, 3); console.log(output3); // --> [123, 132, 213, 231, 312, 32] 코드(JavaScript) function permutation(n, m) { const r.. 2022. 1. 11.
[algorithm] GCD 최대공통약수 두 수의 최대공통약수를 구하는 유클리드 호제법 알고리즘 JavaScript 코드 const GCD = (a, b) => b ? GCD(b, a % b) : a; 2022. 1. 11.
[algorithm] Largest Rectangular Area in a Histogram 히스토그램에서 가장 큰 직사각형 문제 Geeksforgeeks 사이트의 페이지 백준 6549 히스토그램에서 가장 큰 직사각형 두 곳에서 문제를 확인할 수 있다. JavaScript로 구현 const largestRectangularArea = function (histogram) { // 주어진 구간 [left, right]에서 가장 작은 높이를 가진 곳을 찾아야 한다. // 높이는 histogram 배열의 값으로 나타난다. // 낮은 높이를 가진 인덱스를 구하는 함수 const minIdx = (arr, left, right) => { if (left === -1) return right; if (right === -1) return left; return (arr[left] { if (ss === se) return st[idx] .. 2022. 1. 11.
[algorithm] Segment Tree 세그먼트 트리, 최소값 문제 문제 Geeksforgeeks 사이트의 페이지에서도 찾아볼 수 있고, 백준 2357(최솟값과 최댓값)에서도 찾아볼 수 있다. 세그먼트 트리 알고리즘의 기본 유형 중 하나이다. 자세한 설명은 마지막에 링크로 걸어둔 두 개의 페이지를 통해 확인할 수 있다. 간략한 설명을 코드 주석으로 달았다. JavaScript로 구현 const rangeMinimum = function (arr, ranges) { // segment tree 만드는 함수 const makeST = (ss, se, si) => { // ss: 노드가 포함하는 범위의 시작 // se: 노드가 포함하는 범위의 끝 // si: 노드의 인덱스 if (ss === se) return st[si] = arr[ss]; let mid = Math.flo.. 2022. 1. 11.
[algorithm] 백준 4963, toy 41 섬의 개수 문제 백준 알고리즘 4963번 백준 알고리즘 1926번 두 문제가 사실 같은 문제이다. 표현만 다를 뿐 분석 BFS(너비 우선 탐색)의 초급레벨 문제이다. 알고리즘은 다음과 같다 0. 모든 점을 BFS로 탐색한다. 1. 이미 방문한 곳이 아닌(visited[row][col] = 0) 땅(grid[row][col] = 1)을 찾아 queue에 넣는다. 2. queue의 head에서 하나를 꺼낸다. 꺼낸 지점을 기준으로 상하좌우 네 지점으로 땅이 이어졌는지 확인한다. 이어졌다면 그 위치에 방문표시를 하고(visited[row][col] = 1) 그 위치를 queue에 푸시한다. queue가 빌 때까지 2를 반복한다. 3. 섬의 개수를 하나 증가시키고(count++) 1로 간다. JavaScript로 구현 c.. 2022. 1. 6.
[algorithm] Longest Palindrome 1. Brute Force 방식 문자열의 시작부터 끝까지 하나하나 스캔하면서 찾는 방식이다. 구현코드 Javascript const longestPalindrome = function (str) { let len = str.length; let maxLen = 1; let start = 0; for (let i = 0; i < len; i++) { for (let j = i; j < len; j++) { let flag = true; for (let k = 0; k < (j - (i - 1)); k++) { if (str[i + k] !== str[j - k]) flag = false; if (flag) maxLen = Math.max(maxLen, j - i + 1); } } } return maxLe.. 2022. 1. 5.
[algorithm] Coin change, 동전 환전 문제 들어가며 BOJ 2293번에 해당하는 문제이다. 동전의 종류를 담은 배열과 지불해야할 금액이 주어졌을 때 가능한 지불방법의 수를 구하는 문제이다. 이 문제를 DP 방식으로 풀기 위해 처음 사용했던 방식과, Geeksforgeeks의 글을 참고하여 더 짧게 구현했던 방식을 모두 설명하려고 한다. 풀이 1 접근방식 | 0 1 2 3 4 5 ---|------------- 0 | 0 0 0 0 0 0 1 | 1 2 | 1 5 | 1 ? i번 째 코인의 액면가는 coins[i] 이다. i번 째 코인까지 포함해 sum이라는 총액을 만드는 경우의 수를 ks(i, sum)라고 하자. (knapsack 문제라서 함수명을 ks로 했다) 코인 종류의 수를 n = coins.length, 최종금액을 total 이라고 할 때.. 2022. 1. 3.
[algorithm] 병합정렬 - Merge Sort 문제 병합정렬 알고리즘을 이용해 입력받은 배열을 오름차순 정렬해야 한다. 코드 Java Script const mergeSort = function (arr) { // 병합함수 const merge = (arr, l, m, r) => { let n1 = m - l + 1; // 왼쪽 배열의 길이 let n2 = r - m; // 오른쪽 배열의 길이 let L = arr.slice(l, m + 1); // 원본배열에서 왼쪽 배열을 복사 let R = arr.slice(m + 1, r + 1); // 원본배열에서 오른쪽 배열을 복사 // 투 포인터 알고리즘으로 두 배열의 원소를 작은 것부터 담는다. let i = 0; // 왼쪽 배열의 인덱스를 가리키는 포인터 let j = 0; // 오른쪽 배열의 인덱스를.. 2021. 12. 30.

티스토리툴바