알고리즘 이론

Prefix Sum 기법 배워보기

Prefix sum Prefix sum 기법은 배열의 부분 합을 미리 구해놓고 계산의 횟수를 줄이는 기법이다. ex) [1, 2, 3, 4, 5] 이라는 배열이 있다면, 각 부분합인 [1, 3, 6, 10, 15] 를 저장해둔다. Prefix sum 을 미리 구해둔 상태에서 아래와 같은 계산을 쉽게 할 수 있다. 1~5 까지의 합 - 1~3 까지의 합 을 구하라고 한다면, 각각을 다시 반복문으로 반복할 필요 없이 15 - 6 을 구하면 된다. (15가 15까지의 합, 6이 13까지의 합이기 때문) 원본 배열에서 인덱스 2번부터 4번까지의 합(sum(array[2], array[3], array[4]))을 구하라고 한다면, prefixSum[4] - prefixSum[2] 로 쉽게 구할 수 있다. 하나의 ..

Sliding Window, max-consecutive-ones-iii 풀이

문제 https://leetcode.com/problems/max-consecutive-ones-iii/ 조건 이진수 배열 nums 가 주어진다. 정수 k가 주어진다. nums 를 정수 k 번만큼 뒤집을 수 있다. 제약 1

Sliding Window, Maximum Average Subarray 문제 (leet code)

문제 링크 https://leetcode.com/problems/maximum-average-subarray-i 해결 방법 subarray 라는 용어를 보고 sliding window 알고리즘으로 접근해본다. 길이 k 가 고정되어 있으므로, 초기에 윈도우 사이즈만큼 더하며 초기화를 해준다. 초기화 후에 sliding window 를 우측으로 한칸씩 옮기며 모든 window 를 점검하면 끝난다. 소스코드 /** * @param {number[]} nums * @param {number} k * @return {number} */ var findMaxAverage = function (nums, k) { // subarray -> sliding window // init variables to solve s..

Sliding Window 기법 배워보기

Sliding Window 알고리즘이란? 배열 문제를 풀 때, 자주 이용되는 접근법이다. 보통 배열의 부분 배열(subarray)을 구하는 문제로 나온다. 부분 배열이란, [1, 2, 3, 4, 5] 와 같은 배열이 있을 때 [2, 3, 4] 와 같은 배열을 의미한다. [2, 4, 5] 처럼 연속되지 않으면 부분 배열이 아니다. sliding window 풀이 방식을 이용하면, Two pointers 전략과 비슷하게 2개의 포인터를 이용한다. 보통 첫번째 포인터가 시작점 (left bound)이 되고 두번째 포인터가 끝점 (right bound)이 된다. 마치 창문을 옆으로 밀어 이동시키는 것과 비슷하여, sliding window 라고 부른다. 특정 조건을 만족하는 부분 배열 (subarray) 을 구..

Two Pointers, 정렬된 제곱의 배열 구하기 (squares of a sorted array)

문제 오름차순으로 정렬된 음수가 포함된 숫자 배열이 있다. 이 배열의 제곱 결과를 오름차순으로 정렬된 배열 형태로 만들어 보아라. ex) [-4,-1,0,3,10]가 입력으로 들어온다면, [16,1,0,9,100] 가 제곱한 결과가 되고 결과는 [0,1,9,16,100] 이 된다. 입력: [-4,-1,0,3,10] 출력: [0,1,9,16,100] 해법 1: 모두 제곱하고 정렬하기 말 그대로 제곱부터 먼저 구한 뒤에 모두 정렬하는 방법이다. 제곱할 때 N 의 복잡도가 들고, 정렬할 때 정렬 알고리즘에 의해 log N 의 복잡도가 나온다. class Solution { public int[] sortedSquares(int[] A) { int N = A.length; int[] ans = new int[N..

Two Pointers, O(n) 의 복잡도로 문자열 뒤집는 방법 (reverse string)

reverse string 배열 참조를 받아서 해당 배열을 reverse 된 배열로 변환하기 /** * @param {character[]} s * @return {void} Do not return anything, modify s in-place instead. */ var reverseString = function (s) { let l = 0; let r = s.length - 1; while (l < r) { const tmp = s[l]; s[l] = s[r]; s[r] = tmp; l += 1; r -= 1; } }; 순서를 뒤바꾸는 규칙 생각해보기 맨 첫번째 문자를 맨 마지막으로 옮긴다. 두번째 문자는 맨 마지막에서 두번째로 옮긴다. 세번째 문자는 맨 마지막에서 세번째로 옮긴다. n 번째 ..

알고리즘, Two Pointers 기법

Two Pointers 기법이란? 배열과 문자열을 다루는 문제에서 자주 사용되는 기법이다. 배열이 한 개일 때 사용 예시 abcdefg 라는 문자열이 있을 때 하나의 포인터는 문자열의 맨 앞인 a 를 가리키고 다른 하나의 포인터는 문자열의 맨 뒤인 g 를 가리킨다. 두 포인터를 움직이며, 로직을 수행하고 정답을 찾아낸다. 배열이 두 개일 때 사용 예시 abcdefg hijklmnop 라는 문자열 2개가 있을 때 하나의 포인터는 첫번째 배열의 맨 앞인 a 를 가리키고 다른 하나의 포인터는 두번째 배열의 맨 앞인 h 를 가리킨다. 두 포인터를 움직이며, 로직을 수행하고 정답을 찾아낸다. 이 방법의 장점 시간 복잡도가 O(n) 을 넘어가지 않는다. Two Pointer 기법으로 해결할 수 있는 문제 예시 팰린..

알고리즘에서 문자열과 배열

알고리즘에서 문자열과 배열 알고리즘의 입력 값은 문자열 혹은 배열로 들어오는 경우가 많다. 1차원 배열과 문자열은 보통 거의 동일한 구조를 가지고 있다. 언어마다 배열을 다루는 법은 매우 다르다. 자바스크립트의 경우, 배열이 매우 관대해서 크기도 늘었다 줄었다 하고 배열 내부 데이터 타입 제약도 없다. C 언어의 경우엔 크기가 고정이며, 동적으로 할당하고 싶다면 메모리 할당을 받아야 한다. 언어마다 문자열을 다루는 방법도 매우 다르다. C 는 가변이다. Python, Java 는 불변이다. 알고리즘에서 불변과 가변의 중요성 가변인 경우에는 일부만 문자를 변경할 수 있으므로 성능상 유리하다. 불변인 경우에는 일부의 문자를 변경하기 위해 새로운 문자열을 다시 만들어야 한다. 알고리즘 문제를 풀 때, 성능상의..

알고리즘에서 재귀 함수를 사용하는 이유는?

재귀함수란? 자기 자신을 호출하는 함수이다. 반복문으로도 구현될 수 있다. 재귀 함수 예제 코드 (자바스크립트) function recursive(num) { // base case, stopping condition, 종료 조건 if (num > 3) { return; } console.log(`before call itself, num: ${num}`); recursive(num + 1); console.log(`after call itself, num: ${num}`); return; } 위는 아주 간단한 재귀 함수의 예이다. 위의 주석에서 base case 라고 표기된 부분은 재귀 함수를 그만 생성하며 재귀 종료가 일어나는 시나리오를 말한다. stopping condition, 종료 조건 이라고 ..

알고리즘의 시간복잡도, 공간복잡도란? (feat. Big O Notation)

Big O 표기법 (Notation) 이란? Big O 표기법이란 알고리즘의 컴퓨터적인 복잡도를 기술하는 방식이다. 시간 복잡도 와 공간 복잡도 로 나뉘게 된다. 시간 복잡도: 입력값이 늘어남에 따라 얼마나 실행 시간이 늘어나냐를 의미한다. 공간 복잡도: 입력값이 늘어남에 따라 얼마나 메모리 공간을 많이 차지하냐를 의미한다. 일반적으로 알고리즘 문제는 더 나은 공간 복잡도보단 더 나은 시간 복잡도를 요구한다. 실제 표기 예제 O(n) O(n2) O(2n) O(log n) O(n * m) 여기서 n 은 보통 입력으로 들어온 배열의 길이거나 문자열의 길이이다. Big O 표기법에서 상수는 무시된다 ex) O(2n) 이 있다면, O(n) 으로 표기하는 것과 같다. 위에서 시간 복잡도와 공간 복잡도 모두 '입력..