Web Development/algorithm (11) 썸네일형 리스트형 [Algorithm][LeetCode 560] Subarray Sum Equals K 문제 풀이 - 누적합과 Hash Map 활용법 🟢 LeetCode 560. Subarray Sum Equals K 문제 풀이 (with 누적합 + 해시맵)최근 Leetcode 2845. Count of Interesting Subarrays 문제를 풀다가 막히는 부분이 있었는데, 유튜브에서 힌트를 찾아보다가 아래 영상을 발견했습니다.How to solve Count of Interesting Subarrays (Leetcode 2845)이 영상에서는 Leetcode 560번과 523번 문제를 먼저 풀어보면 이해가 잘 된다고 추천하더라고요.그래서 먼저 Leetcode 560. Subarray Sum Equals K 문제를 풀어보았습니다.🟢 문제 설명Given an array of integers nums and an integer k,return .. [algorithm] Sliding Window 패턴 (슬라이딩 윈도우 패턴) Sliding Window Pattern (슬라이딩 윈도우 패턴)슬라이딩 윈도우 패턴은 배열이나 문자열 같은 데이터 집합에서 연속적인 부분 집합을 효율적으로 추적할 때 사용하는 패턴이다.이 패턴을 사용해서, 특정 조건에 따라 윈도우(범위)를 조정하여 사용한다. 1. 윈도우 : 연속된 데이터의 부분 집합, 특정 구간을 나타낸다.2. 윈도우 이동 : 특정 조건에 따라서, 윈도우 위치를 이동 시킨다. 주로 윈도우를 왼쪽에서 오른쪽으로 이동시킨다.3. 효율성 : 매번 전체 배열을 탐색할 필요 없이 윈도우의 시작과 끝만을 조작하여 이전 값을 재사용하는 방식으로 문제를 처리할 수 있다. 1. 문제 Write a function called maxSubarraySum which accepts an array of .. [algorithm] Multiple Pointers Pattern (다중 포인터 패턴) Multiple Pointers Pattern (다중 포인터 패턴) 다중 포인터 패턴은 배열에서 여러 개의 포인터를 사용하여 포인터를 이동시키면서 문제를 해결하는 방법입니다. 이 패턴은 배열이나 문자열처럼 순서가 있는 데이터 집합에서 공간 복잡도를 낮추면서 효율적으로 문제를 해결할 수 있게 해줍니다. 특징 • 포인터 생성 및 이동: 인덱스나 위치에 대응하는 포인터를 생성하고, 조건에 따라 시작, 끝, 또는 중간을 향해 이동시킵니다. • 효율성: 최소한의 공간 복잡도로 문제를 해결할 수 있어 매우 효율적입니다. 예시 문제 예시 1: 두 요소의 합이 0이 되는 첫 번째 요소 쌍 찾기 문제정렬된 배열이 주어졌을 때, 두 요소의 합이 0이 되는 첫 번째 요소 쌍을 배열로 반환하는 함수를 작성하세요. 해당하는 .. [algorithm] Frequency Counter 패턴 (빈도수 카운터 패턴) Frequency Counter 패턴이란?Frequency Counter 패턴은 일반적인 알고리즘 패턴 중 하나로, 두 배열이나 문자열이 동일한 구성 요소를 가지고 있는지를 판단할 때 유용하다. 이 패턴은 객체나 집합(Set)을 사용하여 배열이나 문자열의 값을 수집하고, 그 값들의 빈도를 기록하여, 두 배열 또는 문자열이 동일한 구성 요소를 가지고 있는지 비교한다.이 패턴을 이용하면, 중첩 반복문이나 O(N^2) 시간 복잡도의 연산을 피할 수 있어 성능을 향상 시킬 수 있다. 이 패턴은 특히 배열이나 문자열이 같은 요소나 구조를 가지는지, 혹은 아나그램인지 등을 확인하는 문제에서 강력한 도구로 활용된다. Frequency Counter 패턴 예시 예시 1: 두 배열이 서로 제곱 관계인지 확인하는 함수 문.. [algorithm] 알고리즘을 잘 세우기 위한 전략 1. 문제를 이해하기 • 문제 예시: 0부터 주어진 숫자까지의 합을 구하는 함수를 구현하라. • 문제를 나만의 언어로 이해: 문제를 간단히 요약하고 필요 시 다시 설명합니다. • 입력값을 파악: 정수인지, 부동소수점인지, 입력 크기 제한이 있는지, 입력이 없거나 여러 개일 경우를 고려합니다. • 출력값을 파악: 정수, 소수 등 출력 형태를 결정하고, 부적절한 입력 시 어떻게 처리할지 정합니다. • 충분한 정보 여부: 필요한 정보가 모두 주어졌는지 확인하고, 예외 상황을 고려합니다. • 라벨링 계획: 변수와 함수 이름을 어떻게 명명할지 계획합니다 (예: add, sum 등). 2. 입력값과 출력값의 예시 찾기 • 예시 찾기 목적: 문제를 더 잘 이해하고 함수가 제대로 작동하는지 검증합니다. • 예시 단.. [algorithm] Big O 표기법 1. Big O 표기법이란? • 정의: Big O 표기법은 컴퓨터 과학에서 알고리즘의 실행 시간 복잡도 또는 최악의 경우 시나리오를 입력 크기에 따라 설명하는 수학적 표기법입니다. 2. Big O 표기법을 사용하는 이유 1. 알고리즘 효율성 비교: 동일한 문제를 해결하기 위해 여러 알고리즘의 효율성을 비교합니다. 2. 알고리즘 동작 예측: 입력 크기 증가에 따른 알고리즘의 성능 변화를 예측합니다. 3. 코드 최적화 지표: 성능을 최적화하는 데 참고할 수 있는 지표로 사용됩니다. 4. 자원 관리 지표: 메모리 사용, CPU 성능 등을 고려한 자원 관리에 유용합니다. 5. 효율적인 문제 접근법 제시: 효율적인 해결 방법을 찾는 데 도움을 줍니다. 3. 직접 시간을 측정해서 코드 성능 평가의 어려움 • .. [algorithm] 하노이탑 문제 하노이탑 문제는 재귀 알고리즘을 설명하는 데 자주 사용된다.하노이탑 문제의 규칙한 번에 하나의 디스크만 옮길 수 있다.각 이동은 디스크를 한 막대에서 다른 막대로 옮겨야 한다.어떤 막대 위에도 더 작은 디스크 위에 더 큰 디스크를 놓을 수 없다재귀적 해결 방법A에서 C로 3개의 원반을 옮겨야 한다고 생각하면, 가장 큰 문제는 A의 3번째 원반을 C로 옮기는 것이다. 이를 위해서는 1, 2번 원반을 B로 옮겨야 한다. 그 이후 A를 C로 옮겼다고 가정하자. 이후 B의 원반들을 C로 옮기기 위한, 생각할 수 있는 가장 큰 문제는 B의 2번째 원반을 C로 옮기는 것이다. 이를 위해서는 B의 첫번째 원반을 A로 옮겨야 한다. 그 이후 B를 C위로 옮긴다고 가정하자. 이 상황에서는 A의 원반을 C로 옮기기만 하면.. [algorithm] 재귀와 재귀함수에 대한 이해 재귀는 어떤 것을 정의할 때, 자기 자신을 참조하는 것을 의미합니다. 프로그래밍에서는 주로 함수가 자기 자신을 호출하는 방식으로 구현됩니다. 이를 재귀함수라고 합니다. 재귀는 문제를 더 작은 하위 문제로 나누어 해결하는 데 유용합니다.콜스택(Call Stack) 이해하기콜스택은 함수 호출이 이루어질 때마다 함수의 정보를 저장하는 메모리 영역입니다. 함수가 호출되면 콜스택에 등록되고, 함수가 종료되면 콜스택에서 제거됩니다. 이 과정을 통해 함수 호출 순서와 현재 실행 중인 함수를 관리합니다.예제: 콜스택 동작function a() { console.log('a'); b();}function b() { console.log('b'); c();}function c() { console.log('c');}a().. 이전 1 2 다음
