알고리즘 이야기15

• 

  투 포인터 이해하기, 리트코드 예제 투 포인터 알고리즘 개념 투 포인터 알고리즘은 주로 정렬된 배열이나 리스트를 다룰 때 사용되며, 문제를 해결하기 위해 두 개의 포인터를 사용하는 방법입니다. 이 알고리즘에서는 보통 한 포인터는 시작점에, 다른 하나는 끝점에 위치하고, 배열을 순회하면서 두 포인터가 가리키는 값을 비교하여 문제의 조건을 만족하는지 확인합니다. 조건에 따라 한 포인터만 이동시키거나 두 포인터를 동시에 이동시키기도 합니다. 이런 방식을 통해, 예를 들어 주어진 합을 만족하는 두 수를 찾거나, 최대 길이의 연속 부분 배열을 찾는 등의 문제를 효율적으로 해결할 수 있습니다. 투 포인터 알고리즘의 주요 장점은 불필요한 탐색을 줄여 시간 복잡도를 개선할 수 있다는 것이며, 대부분의 경우 O(n) 시간 안에 문제를 해결할 수 있습니다... 알고리즘 이야기/알고리즘 개념 2024. 3. 26.

• 

  자바스크립트 알고리즘 해시 개념, 리트코드 예제 안녕하세요. 오늘은 자바스크립트 알고리즘 중 해시(hash)에 대한 개념을 설명드리고 해당 개념을 응용해볼만한 쉬운 리트코드 예제를 보여드리도록 할게요. 해시의 개념 해시(Hash)는 키(Key)를 값(Value)에 매핑할 수 있는 데이터 구조입니다. 해시 테이블은 이러한 키와 값을 저장하는 데 사용되며, 복잡한 자료 구조보다 데이터를 더 빠르게 검색, 삽입, 삭제할 수 있게 해 줍니다. 키를 해시 함수를 통해 해시 코드로 변환하며, 이 해시 코드를 사용하여 값이 저장되는 위치, 즉 인덱스를 결정합니다. 자바스크립트 알고리즘에서 해시를 이용하기 위해선 Map 객체를 사용하여 해시 테이블을 구현합니다. Map 객체는 키-값 쌍인 집합입니다. 한 Map에서의 키는 오직 단 하나만 존재합니다. 이는 Map 집.. 알고리즘 이야기/알고리즘 개념 2024. 3. 25.

• 

  자바스크립트 알고리즘 재귀(recursion) 개념과 예제 안녕하세요. 오늘은 자바스크립트 알고리즘 중 초반에 감 잡기 가장 힘든 개념 중 하나인 재귀에 대해 포스팅 해보려고 합니다. 재귀란 무엇일까? 재귀는 어떤 함수가 자기 자신을 호출하는 기법입니다. 모든 재귀 함수는 종료 조건을 갖는데, 재귀 호출이 무한히 반복되지 않도록 하기 위해서지요. 재귀는 정말 여러 방면에서 사용하는데, DOM, JSON.parse 등과 같은 기본적인 자바스크립트 실행 코드들에도 재귀가 들어있습니다. 재귀를 사용하면 복잡한 알고리즘이 좀 더 간결하고 자연스럽게 풀리는 경우가 많습니다. 예시 1 - countDown 아래는 countDown을 하는 함수입니다. 기본적인 반복문으로 사용하면 아래처럼 쓰일 수 있는데요. // Iterative Version function countDo.. 알고리즘 이야기/알고리즘 개념 2024. 3. 25.

• 

  투 포인터 알고리즘 개념, 쉬운 예시 문제, 리트코드 문제 투 포인터 알고리즘 개념 설명 투 포인터(Two-pointers) 알고리즘은 주로 배열이나 리스트와 같은 선형 구조에서 특정 조건을 만족하는 요소들을 찾거나, 작업을 수행할 때 사용되는 기법입니다. 이 기법은 주로 두 개의 다른 위치를 가리키는 포인터를 활용하여, 중첩된 루프의 사용 없이 문제를 효율적으로 해결할 수 있게 도와줍니다. 이를 통해 시간 복잡도를 줄일 수 있으며, 주로 정렬된 배열이나 리스트에서 두 요소의 합이나 차이와 같은 특정 조건을 만족하는 쌍을 찾을 때 유용합니다. 예를 들어, 정렬된 두 배열의 모든 요소를 합치거나, 주어진 합을 이루는 두 요소를 찾는 문제에 투 포인터 알고리즘을 적용할 수 있습니다. 이 알고리즘의 기본 아이디어는 시작점과 끝점이라는 두 포인터를 배열의 시작과 끝에 .. 알고리즘 이야기/알고리즘 개념 2024. 3. 11.

• 

  [프로그래머스] JS알고리즘 - n^2 배열 자르기 오늘은 'n^2 배열 자르기' 알고리즘 문제를 자바스크립트로 해결하는 과정을 다뤄보겠습니다. 까다로워보이지만 2차원 배열의 규칙만 잘 찾아내면 오히려 쉽게 접근할 수 있는 문제입니다. 문제 설명 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지.. 알고리즘 이야기/알고리즘 문제풀이 2024. 1. 28.

• 

  [프로그래머스] JS알고리즘 - 피로도 오늘은 프로그래머스 2단계 를 완전탐색으로 푸는 방법에 대한 내용을 포스팅해보려 합니다. 문제 설명 XX게임의 피로도 시스템과 던전 탐험 메커니즘을 이해하는 것이 이번 문제의 핵심입니다. 각 던전은 '최소 필요 피로도'와 '소모 피로도'를 가지고 있으며, 이를 통해 유저가 탐험할 수 있는 최대 던전 수를 계산해야 합니다. 문제 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하.. 알고리즘 이야기/알고리즘 문제풀이 2024. 1. 23.

• 

  [프로그래머스] JS 알고리즘 - 귤 고르기 오늘은 프로그래머스에서 귤 고르기 문제를 풀었습니다. 다른 블로그를 보니 2단계치고는 쉬운 문제라고 하지만 그래도 나름 까다로운 편에 속하지 않았나 생각해요. 시간 복잡도를 줄이기 위해 많은 시도를 해보았던 것 같습니다. 문제 설명 [문제] 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크.. 알고리즘 이야기/알고리즘 문제풀이 2024. 1. 14.

• 

  [알고리즘 강의]JS 알고리즘 - DFS 팩토리얼 최근 회사에서 메신저 프로그램을 열심히 개발하고 난 후, 다시 코딩 강의를 복습하기로 결정했습니다. 하지만 오랜만에 알고리즘 문제를 풀어보니, 생각보다 잘 풀리지 않는 것 같더군요. 처음엔 혼자서 문제를 풀지 못하고, 시작조차 못하는 문제들이 많아져서 자존심이 상했었습니다. 하지만, 그러한 자괴감을 느끼기보다는 여러 번 복습을 통해 익숙해지는 것도 좋은 학습 방법이라는 조언을 들었습니다. 그래서 안심하고 이 방식을 따르기로 했습니다. 공부에 정답은 없으니까요. 천재도 아니고, 안 풀리는 문제가 갑자기 풀리지 않습니다. 무엇이든 시도해보는 것이 중요하죠. 이 방법으로 알고리즘을 공부하는 것이 얼마나 효과적인지에 대한 후기는 나중에 한 번 포스팅해보고 싶습니다. 그래서 다시 기본을 다질 겸 풀어본 문제는 기.. 알고리즘 이야기/알고리즘 문제풀이 2024. 1. 13.

• 

  JS 알고리즘 - DFS로 부분집합 구하기 DFS 이해하기 오늘의 자바스크립트 알고리즘을 풀던 중 잘 이해가 안가는 DFS를 결국 이해해서 블로그에 올려본다. 문제는 자연수 N이 주어지면 해당 자연수의 부분집합을 DFS로 구현하는 것이었고, 해답은 아래와 같다. DFS 해답 function solution(n) { let answer = []; let ch = Array.from({ length: n + 1 }, () => 0); console.log(ch) function DFS(L) { console.log(`n: ${n}, L: ${L}`) if (L === n + 1) { console.log(`if ${L} === ${n + 1}`) let tmp = ""; for (let i = 1; i 0) answer.push(tmp.trim()).. 알고리즘 이야기/알고리즘 문제풀이 2023. 11. 25.

• JS 알고리즘 - sort(), Math.max() 문제 오늘 푼 자바스크립트 알고리즘 문제는 어제 푼 것보다 더 어려운 것이었다. 문제는 아래와 같다. 졸업 선물 선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다. 학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라 고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다. 현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요. 선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는 할인에 포함되지 않습니다. ▣ 입력설명 첫 번째 줄에 반 학생수 N(1 알고리즘 이야기/알고리즘 문제풀이 2023. 10. 9.