알고리즘
[Algorithm] 슬라이딩 윈도우 Sliding Window 알고리즘 톺아보기
[Algorithm] 슬라이딩 윈도우 Sliding Window 알고리즘 톺아보기
2024.11.11슬라이딩 윈도우 알고리즘 개념슬라이딩 윈도우 알고리즘(Sliding Window Algorithm)은 배열과 같은 선형 자료구조에서 연속된 구간 내의 데이터를 효율적으로 처리하기 위해 사용하는 기법이다. 특히 배열 내 연속된 요소의 합, 최댓값, 최솟값 등을 계산할 때 유용하다. 슬라이딩 윈도우는 이름 그대로 고정/가변 크기의 범위(윈도우)를 이동(슬라이드) 시키면서 필요한 계산을 반복하는 방식이다. 이때 전체 배열을 한 번만 순회하면 되기 때문에 중복 연산을 피하고 시간 복잡도를 개선할 수 있다. 일반적으로 슬라이딩 윈도우 기법을 사용하면 O(n)의 시간 복잡도로 문제를 해결할 수 있다.// 주어진 배열에서 연속된 k개 요소의 최대 합을 찾는 함수function maxSumSubarray(arr, k)..
[Algorithm] 프로그래머스 - 피로도 / 백트래킹으로 모든 부분집합 찾기
[Algorithm] 프로그래머스 - 피로도 / 백트래킹으로 모든 부분집합 찾기
2024.07.29프로그래머스 레벨 2 피로도 문제는 던전 목록과 HP가 주어졌을 때 방문할 수 있는 최대 던전의 수를 반환해야 한다. 각 던전은 최소 피로도와 소모 피로도를 가진다. 최소 피로도는 해당 던전을 방문하기 위해 필요한 최소 HP를 의미하고, 소모 피로도는 말 그대로 해당 던전을 방문했을 때 소모되는 HP를 나타낸다. 문제에서 주어지는 매개변수는 아래와 같다. k : 시작 HP. e.g., 80dungeons : [최소 피로도, 소모 피로도]로 이루어진 던전 목록. e.g., [[80,20],[50,40],[30,10]] 최소 피로도와 소모 피로도가 각각 다르기 때문에 방문 순서에 따라 방문할 수 있는 던전의 수가 달라진다. 예를 들어 [[80,20],[50,40],[30,10]] 던전 목록에서 2~3번(i1..
[Algorithm] 이진 탐색 및 변형 알고리즘 Binary Search Algorithm
[Algorithm] 이진 탐색 및 변형 알고리즘 Binary Search Algorithm
2024.06.02이진 탐색 알고리즘은 정렬된 배열에서 특정 값을 효율적으로 찾기 위한 알고리즘이다. 이진 탐색은 값의 크기에 따라 탐색 범위를 절반으로 줄여가며 원하는 값을 찾아내는 방식으로 작동하기 때문에 시간 복잡도는 $O(\log n)$으로 효율적이다. 예를 들어 1024개 요소를 가진 배열에서 원하는 값을 찾을 때 최대 10번의 비교만 필요하다. 하지만 데이터가 자주 변경된다면 매번 정렬을 해줘야 하기 때문에 효율성이 떨어질 수 있다. 데이터 삽입/삭제가 빈번한 경우엔 해시 테이블 같은 자료구조를 사용하는게 더 나을 수 있다. 💡 이진 탐색은 이분 탐색이라고도 불린다. 이진 탐색 기본중앙값 계산배열의 중간 인덱스를 계산한다 mid = Math.floor((left + right) / 2)중앙값과 찾고자 하는 ..
[Algorithm] 미니맥스 / 알파-베타 가지치기 알고리즘 톺아보기
[Algorithm] 미니맥스 / 알파-베타 가지치기 알고리즘 톺아보기
2024.06.01미니맥스 알고리즘개념💡 제로섬 게임은 한 플레이어가 이득을 얻으면 다른 플레이어는 그만큼 손해를 보는 게임을 가리킨다. 미니맥스 알고리즘은 틱택토, 체스처럼 2명이 참여하는 제로섬 게임에서 가장 널리 사용하는 알고리즘으로, 모든 플레이어가 최선의 수를 둔다고 가정하고 가능한 모든 수를 고려하여 승리할 수 있는 전략을 도출할 때 사용한다. X 플레이어는 승리하기 위해 최대 점수를 얻으려 하고, O 플레이어는 패배하지 않기 위해 최소 점수를 얻으려 하는 상황에서 최적의 해를 찾는 방법이다. 현재 X 플레이어 차례이고, X 플레이어가 선택할 수 있는 곳은 1, 4, 5번 인덱스(Zero-Based)라고 가정해 본다. X가 이기면 +100점, O가 이기면 -100점을 획득한다. 보드의 모든 수를 뒀지만 무승..
[React] 틱택토(Tic-Tac-Toe) 게임 주요 로직 톺아보기
[React] 틱택토(Tic-Tac-Toe) 게임 주요 로직 톺아보기
2024.05.30틱택토 소개틱택토는 2명의 플레이어가 자신의 기호(X, O) 3개를 가로, 세로, 대각선으로 연속해서 놓이도록 하는 보드 게임이다. 게임은 주로 3x3 격자 보드에서 진행된다. 플레이어는 번갈아가면서 자신의 기호를 놓고, 한 칸엔 한 개의 기호만 놓을 수 있다. 모든 칸에 기호를 놓았지만 어느 한쪽도 연속적인 세 개의 기호를 배열하지 못하면 게임은 무승부로 끝난다(무승부가 많은 게임). 승리 조건 체크틱택토는 행렬로 이뤄진 2차원 보드에서 진행하지만, 1차원 배열로 관리하면 각 칸을 단일 인덱스로 접근할 수 있기 때문에 데이터를 더 수월하게 관리할 수 있다. 게임 로직을 구현할 때도 인덱스 계산을 단순화시켜 코드의 복잡성을 줄이는 데 도움이 된다. 또한, 1차원 배열은 그리드 스타일을 이용해 2차원 보..
[Algorithm] 순열 / 조합 개념과 알고리즘 구현
[Algorithm] 순열 / 조합 개념과 알고리즘 구현
2024.05.28순열 Permutation개념순열은 서로 다른 n개 요소 중에서 r개를 선택하여 순서대로 나열하는 방법을 의미한다. 순열에선 순서가 결과에 영향을 미치기 때문에 순서가 중요하다. 동일한 요소를 서로 다른 순서로 나열하면, 각각을 별개의 순열로 간주한다. 예를 들어 A, B, C에서 A, B 두 요소를 선택하는 경우 AB와 BA는 서로 다른 순열이다. A 선택, 남은 글자 B, CB 선택, 남은 글자 C (2자리 순열이므로 무시) → ABC 선택, 남은 글자 B (2자리 순열이므로 무시) → ACB 선택, 남은 글자 A, CA 선택, 남은 글자 C (2자리 순열이므로 무시) → BAC 선택, 남은 글자 A (2자리 순열이므로 무시) → BCC 선택, 남은 글자 A, BA 선택, 남은 글자 B (2자리 순열..
[Algorithm] 자바스크립트 Map으로 구현하는 LRU Cache 알고리즘
[Algorithm] 자바스크립트 Map으로 구현하는 LRU Cache 알고리즘
2024.05.28LRU 캐시 특징캐시(Cache)는 데이터나 연산 결과를 일시적으로 저장하는 것을 가리킨다. 자주 사용하는 데이터나 연산 결과를 메모리 영역에 보관해서 동일한 정보를 요청받았을 때 더 빠른 속도로 제공할 수 있다. LRU 캐시는 대표적인 캐시 알고리즘 중 하나로 제한된 저장 공간을 관리하기 위해 가장 오래전에 사용한 데이터를 제거하는 알고리즘이다. LRU는 Least Recently Used의 약자로 사용한지 가장 오래된 정도로 해석할 수 있다. LRU 캐시에선 조회/쓰기시 해당 값을 가장 최근에 사용한 것으로 처리하는게 핵심이다. 자바스크립트 Map 등을 이용해서 구현할 땐 값이 뒤에 위치할 수록 가장 최근에 사용한 것으로 표시한다. 조회 : 캐시에 값이 존재하면 해당 값을 캐시 마지막(최신)으로 이동..
[Algorithm] 최소 힙(Heap)으로 우선순위 큐 구현하기
[Algorithm] 최소 힙(Heap)으로 우선순위 큐 구현하기
2024.05.28힙의 특징최단 경로를 찾을 때 널리 사용하는 다익스트라 알고리즘은, 탐색 큐의 자료구조가 전체 성능에 결정적인 영향을 미친다. 때문에 추가/삭제를 빠르게 수행할 수 있는 우선순위 큐를 주로 사용한다. 우선순위 큐는 일반 큐와 비슷하지만, 각 요소가 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 출력된다는 점이 다르다. 우선순위 큐는 크게 배열, 연결리스트, 힙 이렇게 세 가지 방법으로 구현할 수 있다. 그중 완전 이진 트리 구조를 갖는 힙으로 구현하면 추가/제거의 효율성이 크게 향상된다. 구현 방법삽입삭제순서 없는 배열O(1)O(n)순서 없는 연결리스트O(1)O(n)정렬된 배열O(n)O(1)정렬된 연결리스트O(n)O(1)힙O(log n)O(log n) 이진 트리는 각 부모 노드가 왼쪽/오른쪽 최..
[Algorithm] 다익스트라 알고리즘 — 최단 경로 찾기
[Algorithm] 다익스트라 알고리즘 — 최단 경로 찾기
2024.05.28문제 분석프로그래머스 레벨 2의 배달 문제(12978)는 마을 개수 N, 두 마을 사이의 거리 정보 road, 배달 가능한 시간(거리) K를 인자로 받아, 1번 마을에 있는 음식점이 K이하 시간에 배달할 수 있는 마을의 개수를 반환해야 한다. 마을 개수 N : 1 ≤ N ≤ 50거리 정보 : [[a, b, c], [...]]a b : 두 마을의 번호c : 두 마을의 거리(시간)배달 가능한 시간 K : 1 ≤ K ≤ 500,000 위 마을 이미지를 기준으로 1번부터 5번 마을까지 최소 배달 시간을 [번호, 시간] 배열 형태로 나타내면 아래와 같다. 만약 배달 가능한 시간 K가 3이라면 1, 2, 4, 5번 마을이 모두 3시간 이하여서 정답은 4가 된다. 이처럼 1번 마을에서 다른 모든 마을까지 소요되는 ..
[Algorithm] 유클리드 알고리즘 / 소인수분해로 최소공배수 최대공약수 계산하기
[Algorithm] 유클리드 알고리즘 / 소인수분해로 최소공배수 최대공약수 계산하기
2024.05.26N개의 최소공배수프로그래머스 레벨 2의 12953번 문제는 N개의 최소공배수를 구하는 문제다. 최소공배수는 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미한다. 예를들어 2와 7의 최소공배수는 14가 된다. 주어진 배열(arr)에서 가장 큰 수의 배수를 나머지 요소와 나눴을 때 모두 0이 되는 수를 찾는 방법으로 풀었지만, 매번 큰 수를 제외한 배열의 모든 숫자를 하나씩 나눠봐야 하기 때문에 효율적이지 않다. 배열 정렬을 제외하고 배열 길이가 n, while문의 반복 횟수가 x이라고 했을 때 시간복잡도는 $O(n \cdot x)$가 된다.function solution(arr) { const sortedArray = arr.sort((a, b) => b - a); const [bigges..
[Algorithm] 땅따먹기 알고리즘 / 동적 계획법
[Algorithm] 땅따먹기 알고리즘 / 동적 계획법
2024.05.25동적 계획법동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 분할하고, 그 결과를 저장하면서 큰 문제를 해결하는 방법이다. 이를 통해 문제의 연산 시간을 효과적으로 줄일 수 있다. 동적 계획법을 적용하기 위해선 다음 두 가지 조건을 만족해야 한다. 피보나치 수열이 아래 두 조건을 만족하는 대표적인 예. 최적 하위 구조 Optimal Substructure작은 하위 문제의 최적 해를 조합하여 전체 문제의 최적 해를 얻을 수 있다.하위 문제 중첩 Overlapping Subproblem동일한 하위 문제가 반복적으로 발생한다. 동적 계획법은 중복 계산 방지를 위해 메모이제이션 혹은 타뷸레이션 기법을 사용한다. 메모이제이션은 재귀 호출을 사용하여 필요한 문제만 계산하..
[Algorithm] 복잡한 DOM 예제로 보는 DFS 탐색 알고리즘
[Algorithm] 복잡한 DOM 예제로 보는 DFS 탐색 알고리즘
2024.05.22목표아래 DOM 구조에서 가장 안쪽 요소부터 시작해 부모 요소로 갈 수록 중첩 레벨이 1씩 늘어나고, class에 대응하는 dataset에 중첩 레벨 값을 할당해야 한다. 예를들어 class가 "clause" 이고, 해당 요소의 중첩 레벨이 2라면 data-clause-lv="2" 속성을 할당한다. Hello ; 만약 자식 요소가 2개 이상일 땐 자식 요소들중 중첩 레벨이 가장 높은 값 + 1이 부모 요소의 중첩 레벨이 된다. 아래 예시를 기준으로 1번째 자식의 중첩 레벨(data-word-lv="1") 보다, 2번째 자식의 중첩 레벨(data-phrase-lv="2")이 더 높으므로, 부모 요소의 중첩레벨은 3이 된다(data-clause-lv="3"). ..