Algorithm

총 23개의 글

[Programmers, Lv.2] 땅따먹기 (feat. 동적계획법, 자바스크립트)

🚀 동적계획법을 이용하여 자바스크립트 언어로 땅따먹기 문제를 해결해 봅시다! 문제 설명 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하..

Algorithm 2023.06.22

[이론] 순열

🚀 자바스크립트로 순회 구현하기 순열이란 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산을 의미한다. 조금 더 쉽게 말하면 순서가 있는 정렬을 만드는 경우의 수를 의미 한다. 순열이 사용되는 문제 유형으로는 완전탐색이 있다. 주어진 값 안에서 가능한 모든 경우의 수를 탐색하기 위해 순열이 사용된다. 순열을 사용하여 풀이할 수 있는 문제로는 아래 문제가 있다. [프로그래머스] 소수 찾기 순열 의사코드 순열은 선별 배열과 잔여배열을 인자로 전달받으며, 진행 과정은 다음과 같다. 먼저, 전달받은 잔여 배열을 순회한다. 각 순회에서 선택한 값을 선별 배열에 반영한 후, 선택한 값을 제외한 잔여배열을 다음 순회의 잔여배열로 지정한다. 이후 새로운 선별 배열과 잔여배열을 재귀방식으로 순열 함수에 전달해준다. ..

Algorithm 2023.06.15

[프로그래머스] 소수 찾기 (Javascript)

문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 문제 풀이 이 문제를 풀기 위해선 완전 탐색(순열)과 소수 판별 방법 에 대해 이해해야 합니다. 순열 순열에 대한 기본적인 설명은 이 링크에서 확인할 수 있습니다. 가능한 모든 숫자 조합을 완전 탐색하기 위..

Algorithm 2023.06.15

[프로그래머스] 큰 수 만들기

목표 : 그리디에 대해 간단히 알아보고 이를 이용하여 문제를 풀이해보자 문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입..

Algorithm 2023.06.14

[프로그래머스] 전력망을 둘로 나누기

💡 DFS (혹은 BFS)를 이용하는 것이 포인트! Question 문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 2 이상 100 이하인 자연수입니다. wires는 길이가 n-1인 정수형 2차원 배열입니다. wires의 각 원..

Algorithm 2023.06.13

[이론] BFS와 DFS (javascript)

💡 대표적인 트리 순회 알고리즘인 DFS와 BFS에 대해 알아보고, 자바스크립트로 구현해 봅시다. BFS (넓이 우선 순회) BFS란? BFS는 Breadth-First-Search의 줄임말입니다. 트리를 순회할 때 같은 레벨의 노드(넓이)를 우선하여 순회하는 알고리즘을 의미합니다. 즉 현재 노드의 자식 노드보다 형제 노드를 우선하여 탐색합니다. 다음과 같은 트리 (그래프) 가 있을 때, BFS를 이용한 순회 순서는 해당 그림과 같습니다. BFS 구현 로직 BFS을 구현하기위한 로직은 다음과 같습니다. 방문한 노드들을 기억할 배열을 생성해 줍니다. 방문해야 하는 노드를 기억할 큐를 생성해 줍니다. 방문해야하는 노드(= 큐의 길이)가 존재하는 한 큐에서 다음 방문할 노드를 뽑아 줍니다. 뽑은 노드가 이미 ..

Algorithm 2023.06.13

롤케이크 자르기

문제 유형 출처 프로그래머스 레벨 Lv. 2 문제 설명 철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다. 예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다. 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다. 만약 세 번째..

Algorithm 2023.05.19

뒤에 있는 큰 수 찾기

문제 유형 출처 프로그래머스 레벨 Lv. 2 문제 설명 정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다. 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다. 제한 사항 4 ≤ numbers의 길이 ≤ 1,000,000 1 ≤ numbers[i] ≤ 1,000,000 문제 풀이 풀이 설명 이 문제는 제한 사항을 가장 먼저 봐야 합니다. numbers의 길이가 최대 100만이므로, 오직 단 한번의 순회(시간 복잡도 : O(n))만으로..

Algorithm 2023.05.17

[Algoithm] 짝수의 합

짝수의 합 출처 프로그래머스 풀이 언어 javascript 문제 설명 정수 n이 주어질 때, n이하의 짝수를 모두 더한 값을 return 하도록 solution 함수를 작성해주세요. 제한사항 0 { let i = 0; let answer = 0; while(i

Algorithm 2022.12.23

[Algorithm] 배열의 평균값

배열의 평균값 출처 프로그래머스 풀이 언어 javascript 문제 설명 정수 배열 numbers가 매개변수로 주어집니다. numbers의 원소의 평균값을 return하도록 solution 함수를 완성해주세요. 제한사항 0 ≤ numbers의 원소 ≤ 1,000 1 ≤ numbers의 길이 ≤ 100 정답의 소수 부분이 .0 또는 .5인 경우만 입력으로 주어집니다. 입출력 예 numbers result [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 5.5 [89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] 94.0 풀이 const solution = (numbers) => numbers.reduce((a, b) => a + b, 0) / numbers.length;..

Algorithm 2022.12.22
< [1] [2] [3] >

티스토리툴바