알고리즘
[Algorithm] 데이터 추가, 삭제, 정렬로 보는 BFS / DFS 탐색 알고리즘
[Algorithm] 데이터 추가, 삭제, 정렬로 보는 BFS / DFS 탐색 알고리즘
2024.05.21예시 데이터단어 혹은 문장부호(' 아포스트로피 제외)를 기준으로 분리한 토큰 인덱스 정보가 담기는 Part 객체가 있다. 이 Part 객체는 child 배열을 가지며, child 배열의 각 요소인 Part는 부모 Part의 토큰 인덱스 범위 내의 인덱스를 가진다. 예를들어 부모 Part의 토큰 인덱스 범위가 2~13이라면 자식 Part의 토큰 인덱스는 3~13(3~13, 4~13, ...) 혹은 2~12(2~12, 2~11, ...) 범위를 가진다.[ // parts 배열 { id: 0, // part begin: 2, end: 13, kc: [{ id: 'kc-1', /* ... */ }], child: [ // parts 배열 { id: 1, // ..
[Algorithm] 퀵 정렬(Quick Sort) 알고리즘 톺아보기
[Algorithm] 퀵 정렬(Quick Sort) 알고리즘 톺아보기
2024.05.07퀵 정렬 알고리즘 개념퀵 정렬은 분할 정복 알고리즘(문제를 더 작은 2개의 문제로 분리해서 해결한 후 결과를 모아서 원래 문제를 해결하는 방법)의 하나로 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)기사가 개발했다. 가장 자주 사용하는 정렬 알고리즘으로 빠른 수행 속도가 특징이다. 기본적인 퀵 정렬은 아래 3단계를 반복하며 정렬한다. 기준(Pivot; 피벗) 요소 선택 — 주로 배열의 중간 요소를 기준으로함기준 요소보다 작은 요소는 왼쪽으로 이동, 기준 요소보다 큰 요소는 오른쪽으로 이동이동시킨 왼쪽 / 오른쪽 요소들에 대해 1~2번 작업 반복 구현Basic Quick Sort💡 구현하기 쉽지만 항상 새로운 left / right 배열을 생성해 비교한 요소를 추가하므로 ..
[Algorithm] 분할 정복 / 병합 정렬 알고리즘
[Algorithm] 분할 정복 / 병합 정렬 알고리즘
2024.05.07분할 정복 (Devide & Conquer)개념분할 정복은 “큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식"이다. 미국 수학자 폰노이만이 1945년에 개발한 알고리즘이다. 퀵소트, 병합 정렬이 분할 정복 방법을 통해 구현한다.예전엔 테이프를 이용해 데이터를 저장했다. 테이프 드라이브에 저장된 데이터는 항상 처음부터 순차적으로 읽어야 하기 때문에 데이터를 정렬하기 어려웠다. 이런 테이프 드라이브의 문제점을 극복하기 위해 병합 정렬 알고리즘이 탄생했다. 분할 : 문제를 더 이상 분할할 수 없을 때까지 동일 유형의 여러 하위 문제로 나눈다정복 : 가장 작은 단위의 하위 문제를 해결하며 정복한다조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다 예시분할 정복은 구조는 동일하지만 더 작은..
[Algorithm] 정렬 알고리즘 기본 (버블/선택/삽입)
[Algorithm] 정렬 알고리즘 기본 (버블/선택/삽입)
2024.05.06💡 예시의 모든 input은 [10, 7, 9, 5, 1]로 통일. 버블 / 선택 / 삽입 정렬 모두 최악의 경우 O(n²) 시간복잡도를 갖는다. 알고리즘 성능이 좋지 않아 거의 쓰진 않지만, 적은 데이터를 정렬할 땐 유용. 버블 정렬 | Bubble Sort거품이 일어난 것처럼 배열의 각 요소들이 순차적으로 정렬돼서 버블 정렬이라고 부른다. 두 요소를 묶어서 비교한 후 큰 숫자를 오른쪽으로 밀어낸다. i번째 정렬을 마칠때마다 “뒤에서 i번째” 자리의 순서가 확정된다. 시간 복잡도 (삽입 정렬과 동일)Worst Case(정렬이 전혀 안됐을 때) : O(n²) — 중첩 반복문을 사용하므로Best Case(이미 정렬됐을 때) : O(n) 장단점 (삽입 정렬과 동일)Stable 정렬 : 중복 데이터는 순서를..
[Algorithm] 자바스크립트 쌍(pairs)을 포함하는 배열에서 유니크 넘버 찾기
[Algorithm] 자바스크립트 쌍(pairs)을 포함하는 배열에서 유니크 넘버 찾기
2024.05.02아래 배열에서 단 한번만 나열되는 유니크 숫자는 17이다. 1과 3은 쌍을 이루고 있기 때문에 두번씩 나열되고 있다. 이런 배열에서 유니크 넘버(17)만 찾아내려면 어떻게 해야할까?[1, 3, 17, 3, 1] Naive Solution — O(n*n)2중 for문을 사용한 예시. 모든 숫자를 한번씩 돌아가면서 검사해야 되기 때문에 O(n*n)의 시간복잡도를 갖는다. 배열 길이가 5라면 정답을 찾을 때까지 최대 25번의 순회가 이뤄질 수도 있다.function singleNumber(nums) { for (let i = 0; i Linear Solution — O(n)💡 O(n)은 알고리즘 실행 시간이 선형이 되는 것을 뜻한다. 선형 시간(Linear time; 线性时间)이란 배열 길이(n)와 비례..
[Algorithm] 프로그래머스 비밀지도 문제 풀이
[Algorithm] 프로그래머스 비밀지도 문제 풀이
2024.04.30글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요 2018년 카카오 블라인드 테스트 1차 비밀지도 문제(문제 번호 17681). 파라미터는 arr1 arr2 n 이렇게 3개를 받으며, n은 한 변의 길이를 나타낸다(배열 각 요소를 이진수로 변환한 후의 length). ❶ 2개의 배열을 받아[9, 20, 28, 18, 11]; // arr1[30, 1, 21, 17, 28]; // arr2 ❷ 배열의 각 요소를 2진수로 변환한 뒤 (10진수 → 2진수 변환은 노트 참고)['01001', '10100', '11100', '10010', '01011']; // arr1['11110', '00001', '10101', '10001', '11100']; // arr2 ❸ 0 → ' ' 공..
[Algorithm] 특정 수 까지의 합 구하기 / 등차수열 (가우스 공식)
[Algorithm] 특정 수 까지의 합 구하기 / 등차수열 (가우스 공식)
2024.04.28프로그래머스 문제프로그래머스의 "부족한 금액 계산하기" 문제다. 아래 3개 파라미터를 받는다. price : 놀이기구의 이용료money : 고객이 가지고 있는 금액count : 고객이 해당 놀이기구를 이용한 횟수 놀이기구를 이용한 횟수가 늘어날 때마다 횟수 만큼의 이용료를 더 받는다. 놀이기구의 이용료 price 가 100원이라면 1번 이용할 땐 100원, 2번 이용할 땐 200원, 3번 이용할 땐 300원이 된다. 놀이기구를 count 번 탔을 때 money 금액에서 얼마나 모자라는지를 반환해야 된다. 금액이 모자라지 않으면 0을 반환한다. 반복문을 이용하면 아래처럼 쉽게 풀 수 있다.function solution(price, money, count) { let sum = 0; for (let i..