Algorithm & 자료구조

[알고리즘 JS] 다트 게임 (프로그래머스 Lv.1)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정말 오랜만에 알고리즘 문제 풀이! 지금까지 나름 꾸준히 풀긴 했는데 기록으로 남기질 않은 것 같아서 다시 정리해본다. 본 문제는 다트게임이라는 문제로, 문제에서 제시되는 상황을 정리하면 아래와 같다. 총 3번의 게임 기회가 있다. 각 라운드당 획득 점수는 1 ~ 10점 이다. S, D, T 각각 1, 2, 3만큼 거듭제곱되는 영역이 있다. *, # 같은 옵션이 하나씩만 붙을 수 있다. * 기호의 경우 이전에 획득한 점수, 현재 획득한 점수 *2배, #의 경우 현재 점수를 음수로 바꾼다. 예를들어 1D#..

[알고리즘 JS] 퀵정렬 알고리즘 : Quick Sort Algorithm

퀵정렬 알고리즘이란? 하나의 기준점을 가지고 분할과 정복 방식으로 정렬하는 알고리즘이다. 최선의 경우 O(NlogN) 의 속도를 낼 수 있다. 아래 그림에서는 가장 오른쪽에 위치한 요소를 첫 번째 피봇 기준점으로 삼았지만, 전체 배열의 중간 요소를 초기 시작점으로 정하는 것이 일반적이다. 처음 정한 피봇을 기준으로 전체 배열 안에서 피봇의 위치를 확정할 수 있는데, 이 때 정렬은 피봇을 기준으로 좌측에 순서 상관 없이 피봇보다 작은 값, 우측으로 순서 상관 없이 피봇보다 큰 값이기 때문에 피봇에 대한 위치는 확정적이라고 할 수 있다. 한 번의 반복이 끝나면 피봇의 위치가 확정되고, 이 피봇의 위치를 기준으로 좌측, 우측이 분할되기 때문에 각 범위를 다시 재귀적으로 호출하여 최종적으로 정렬할 범위 안에 요..

[알고리즘] 마구간 정하기

문제 N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ... , xN의 좌표를 가지며, 마구간 간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요. 풀이 const arr = [1, 2, 8, 4, 9]; const C = 3; function count(positions, distance) { // 말은 최소 하나 이상 들어갈 것이기 때문에 cnt 는 최소 1..

[알고리즘 JS] 삽입 정렬 알고리즘 : Insertion Sort Algorithm

삽입 정렬 알고리즘이란? 요소가 들어있는 배열을 i 로 반복할 때, 현재 i 위치 좌측으로 이미 요소가 정렬된 상태이고, i 값과 좌측의 값들을 비교해 i의 적절한 위치를 찾아 삽입하는 정렬 알고리즘이다. 삽입 정렬 알고리즘 코드 적용 const nums = [11, 7, 5, 6, 10, 9]; function insertionSort(nums) { let N = nums.length; for (let i = 1; i < N; i++) { // i는 언제나 1번째부터 시작하고, temp 변수에 i의 현재 값을 보관한다. let temp = nums[i]; // j는 언제나 i - 1의 위치에서 시작한다. let j = i - 1; // 만약에 j 가 0 이상이고, i위치의 값보다 j위치의 값이 더 큰 ..

[알고리즘 JS] 쇠막대기 (Stack)

문제 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. • 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. • 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. • 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다. 1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 ..

[알고리즘 JS] 크레인 인형뽑기 게임 (프로그래머스 Lv.1)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 /* [풀이 해설] 1. N * N의 행렬이 존재할 때, moves로 받고있는 '크레인의 위치' 는 i번째 행의 인덱스가 된다. 2. 크레인의 위치에서 맨 위부터 시작해 인형이 존재할 때 까지 아래로 파고들기 때문에, ... 전체 board를 반복해서, board[i][move - 1] 로 접근해야한다. ... moves로 들어오는 각 값을 0번째부터 시작하는 배열의 인덱스로 접근하기 ..

[알고리즘] 모든 아나그램 찾기

문제 S문자열에서 T문자열과 아나그램이 되는 S의 부분 문자열의 개수를 구하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다. 부분 문자열은 연속된 문자열이어야 합니다. 입력 : 두 문자열 S 와 T, T 문자열의 길이는 S문자열보다 작거나 같습니다. 출력 : S 단어에 T문자열과 아나그램이 되는 부분 문자열의 개수를 출력합니다. 풀이 이 문제는 슬라이딩 윈도우 알고리즘과 맵 객체를 활용하여 풀 수 있는 문제이다. T 와 S의 0부터 T.length - 1 까지의 문자열에 대해서 각 문자를 키로, 포함하고 있는 갯수를 밸류로 하는 맵 객체를 만든다. 두 개의 포인터로 T의 길이만큼 범위를 잡아서 S 문자열을 이동하며 T와 S 문자열의 일부분을 비교한다. T 길이 만큼 범위를 잡는다는 것은,..

[알고리즘] 최대매출

문제 현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출 기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다. 만약 N = 10이고 10일 간의 매출 기록이 아래와 같습니다. 이 때 k = 3 이면, 12 15 11 20 25 10 20 19 13 15 연속된 3일간의 최대 매출액은 11 + 20 + 25 = 56만원 입니다. 여러분이 현수를 도와주세요. 풀이 1번 풀이 // 1번째 시도한 코드 // : lt와 rt를 선언해서, rt를 증가하면서 더하고, // rt - lt 가 k - 1 보다 클 경우(index가 0부터 시작하므로 -1을 해줌) // sum 에서 lt를 빼면서 증가 // sum에 rt를 더하고 max 값과 비교하여 max를 갱신하여 리턴 fu..

[알고리즘] 연속 부분수열 2 (투포인터 알고리즘)

문제 N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속 부분수열의 합이 특정 숫자 M 이하가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요. 풀이 const M = 5; const arr = [1, 3, 1, 2, 3]; function solution1(M, arr) { const N = arr.length; let lt = 0; let count = 0; let sum = 0; for (let rt = 0; rt M) sum -= arr[lt++]; // 이..

[알고리즘 JS] 버블 정렬 알고리즘 : Bubble Sort Algorithm

버블 정렬 알고리즘이란? 아래 그림의 주황색 부분 처럼, 인접한 두 개의 요소의 대소를 비교해 자리를 바꿔 정렬을 하는 알고리즘이다. 바깥쪽 반복과 안쪽 반복이 있을 때 바깥 반복을 배열의 길이만큼 반복하고, 안쪽 반복에서는 j로 0번째 인덱스부터 마지막요소를 제외한 범위만큼 반복하면서, 배열의 j번째 요소와 j + 1번째 요소의 대소를 비교한다. j + 1번째 요소와 비교되기 때문에 배열의 마지막 요소는 범위에 추가를 하지 않아도 저절로 반복이 된다. 위 그림처럼 정렬이 완료된 범위의 마지막 부분은 정렬 범위에서 제외시켜 주어도 되는데, 그렇게 하기 위해서 i 가 증가할 때마다 j의 범위에서 i만큼 감소시켜준다. 버블 정렬 알고리즘 코드 적용 const bubbleSort = function (arr)..