Algorithm

[자료구조][JS] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)이란? 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료와 비교해 삽입할 위치를 결정하는 알고리즘 즉, 두 번째 자료는 첫 번째 자료와, 세 번째 자료는 두 번째와 첫 번째 자료와 비교를 해 삽입될 위치를 찾는다. 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. 처음 Key값은 두 번째 자료부터 시작한다. 예시 배열에 3, 7, 2, 5, 1, 4가 있다고 가정하고 자료를 오름차순으로 정렬해보자. 1. key: 7(두 번째 자료). 첫 번째 값인 3과 비교한다. 2. key: 2(세 번째 자료). 두 번째 값인 7과 비교해 7을 한 칸 뒤로 이동한다. 첫 번째 값인 3과 비교하고 3을 한 칸 뒤로 이동한다. 2를 첫 번째 자리에 넣는다..

[JS] LeetCode - 2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/ Add Two Numbers - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single dig..

[JS] 봉우리

문제 지도 정보가 N*N 격자판에 주어진다. 각 격자에는 그 지역의 높이가 쓰여있고, 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역이다. 봉우리가 몇 개 있는지 알아내는 프로그램을 작성하시오. (1= 0 && ny = arr[i][j] ) { flag = 0; break; } } if (flag) answer++; } } return answer; } arr = [ [5, 3, 7, 2, 3], [3, 7, 1, 6, 1], [7, 2, 5, 3, 4], [4, 3, 6, 4, 1], [8, 7, 3, 5, 2], ]; arr[i][j]의 상하좌우를 확인하기 위해서 dx, dy 배열을 선언해주고 [i-1][j], [i][j+1], [i+1][j]..

[JS] 일곱 난쟁이

문제 아홉 난쟁이 모두가 자기가 일곱 난쟁이라고 주장한다. 일곱 난쟁이의 키의 합이 100이고 아홉 난쟁이의 키가 주어졌을 때, 그 중 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우 아무거나 출력) 입력 예제 20 7 23 19 10 15 25 8 13 출력 예제 20 7 23 19 10 8 13 정답 function solution(arr) { let answer = arr; let sum = answer.reduce((a, b) => a + b, 0); for (let i = 0; i < 8; i++) { for (let j = i + 1; j < 9; j++) { if (sum - (answer[i] + answer[j]) == 100..

[JS] LeetCode - 53. Maximum Subarray / 카데인 알고리즘(Kadane's Algorithm)

Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array. Input, Output 예시 Input: nums =..

[자료구조][JS] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort) 시간 복잡도 최선: O(n^2) 최악: O(n^2) 평균: O(n^2) 장점 실행 전에 자료의 이동 횟수를 알 수 있음 보조 메모리가 제한되는 경우 복잡한 알고리즘에 비해 성능적인 이점을 낼 수 있음 단점 보통의 경우 O(n^2)의 시간 복잡도로, 비효율적인 정렬 방식 배열 내에 동일한 값이 중복되어 있다면 상대적인 위치가 변경될 수 있음 - 코드 예시 function solution(arr) { let answer = arr; for (let i = 0; i = arr[j]) idx = j; } [arr..

[자료구조][JS] 스택, 큐 - push(), pop(), shift()

기본적인 자료구조인 스택, 큐에 대해서 JS로 정리해보려 한다. push() push() 메서드는 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환한다. arr.push(element1[, ...[, elementN]]) elementN: 배열의 끝에 추가할 요소. const animals = ['pigs', 'goats', 'sheep']; const count=animals.push('cows'); console.log(count); // expected output: 4 console.log(animals); // expected output: Array ["pigs", "goats", "sheep", "cows"] animals.push('cats', 'dogs'); conso..

[알고리즘][JS] 해쉬 알고리즘 - JS ES6 Map()

해쉬 알고리즘이란? 해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다. 이를 이용해 특정한 배열의 인덱스나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존의 자료 구조들을 탐색이나 삽입을 할 때 선형시간이 걸리기도 했던 것에 비해 해쉬를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더 빠른 속도로 처리할 수 있다. 1. 직접 주소 테이블(Direct Addressing Table) Direct Addressing Table은 key-value 쌍의 데이터를 배열에 저장할 때 key값을 직접적으로 배열의 인덱스로 사용하는 방법이다. 예를 들어 키 값이 400인 데이터가 있다면 이는 배열의 인덱스가 400인 위치에 키 값을 저장..

투포인터 알고리즘, 슬라이딩 윈도우

투포인터 알고리즘(Two Pointers Algorithm) 투포인터 알고리즘은 1차원 배열에서 각자 다른 원소를 가르키는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다. 알고리즘 문제를 풀다가 완전 탐색으로 해결하다가 시간 초과가 발생하는 경우에 사용할 수 있다. 문제는 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 이 문제에서 각 원소는 자연수이고 M 또한 자연수인데, 이 조건이 성립할 경우 사용할 수 있는 알고리즘은 다음과 같다. 포인터 2개를 준비. 이를 left, right라고 함. 처음에는 left = right = 0. 항상 left

[알고리즘] 완전탐색(Brute-Force)

완전탐색이란 가능한 모든 경우의 수를 일일히 나열하면서 계산하는 방법이다. 이는 100%의 확률로 문제의 답을 찾아낼 수 있는 방법이다. 하지만 완전 탐색은 답으로 가능한 경우의 수가 많은 경우에는 이용하기가 어려우므로 이를 활용할 수 있는 문제인지 잘 생각해보고 쓰는 것이 좋다. 아래는 완전 탐색을 이용할 수 있는 예제들 정리 (풀어볼 것!) https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net https://www.acmicpc.net/problem/22..