0802 - 0808
0802
16일 차 재귀함수, DFS, BFS
재귀함수를 이용한 이진수 출력
10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용 해서 출력해야 합니다.
function solution(n) {
let answer = 0;
let tmp = [];
function DFS(n) {
if (n === 0) return;
else {
DFS(parseInt(n / 2));
tmp.push(n % 2);
}
}
DFS(n);
for (let i = 0; i < tmp.length; i++) {
answer = answer * 10 + tmp[i];
}
return answer;
}
console.log(solution(11));
- n이 0이 될 때까지 재귀함수로 호출하여 빈 배열 tmp에 n을 2로 나눈 나머지를 push했다.
- tmp에 있는 요소를 숫자형으로 변환했다.
이진트리 순회
이진트리를 전위순회와 후위순회를 연습해보세요.
function solution(n) {
let answer = "";
function DFS(v) {
if (v > 7) return;
else {
answer += v;
DFS(v * 2);
DFS(v * 2 + 1);
}
}
DFS(n);
return answer;
}
console.log(solution(1));
answer += v코드를 재귀함수 앞에 두면 전위, 가운데 두면 중위, 끝에 두면 후위순회이다.
부분집합 구하기(DFS)
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.
function solution(n) {
let answer = [];
let tmp = [];
function DFS(L) {
if (L === n + 1) {
if (tmp.length !== 0) answer.push(tmp.slice());
} else {
tmp.push(L);
DFS(L + 1);
tmp.pop(L);
DFS(L + 1);
}
}
DFS(1);
return answer;
}
console.log(solution(3));
- tmp에 요소를 push하고 재귀 함수 호출, pop하고 재귀 함수를 호출하여 부분집합을 구했다.
- 주의할 점은 answer에 배열인 tmp를 push할 때 slice()메소드를 사용해야지만 깊은 복사가 되어 제대로 복사된다.
- 트리로 그려보면, 각 요소를 넣었을 때와 안넣었을 때로 구분하는 상황이 나온다.
합이 같은 부분집합
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES”를 출력하고, 그렇지 않으면 ”NO”를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.
function solution(nums) {
let answer = "NO";
let total = nums.reduce((acc, current) => acc + current, 0);
let flag = false;
function DFS(L, sum) {
if (L === nums.length) {
if (flag) return;
if (total - sum === sum) {
answer = "YES";
flag = true;
}
} else {
DFS(L + 1, sum + nums[L]);
DFS(L + 1, sum);
}
}
DFS(0, 0);
return answer;
}
console.log(solution([1, 3, 5, 6, 7, 10]));
console.log(solution([5, 2, 6, 9, 10, 12]));
console.log(solution([3, 9, 11, 13]));
- 매개변수를 잘 활용해야 하는 문제
- L을 인덱스 번호처럼 사용해서 해결한다.
- 모든 수의 합을 구하고, 모든 수에서 일정 수까지 더한 값을 뺐을 때 그 값이 나오면 합이 같은 두 부분집합이 있다는 뜻으로, YES를 반환한다.
- 부분집합이 문제에 나온다면, DFS를 떠올려보자
바둑이 승차
철수는 그의 바둑이들을 데리고 시장에 가려고 한다.
그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.
function solution(nums, c) {
let answer = 0;
let total = nums.reduce((acc, current) => acc + current, 0);
function DFS(L, sum, tsum) {
if (sum > c) return;
if (total - tsum + sum < answer) return;
if (L === nums.length) {
answer = Math.max(answer, sum);
} else {
DFS(L + 1, sum + nums[L], tsum + nums[L]);
DFS(L + 1, sum, tsum + nums[L]);
}
}
DFS(0, 0, 0);
return answer;
}
console.log(solution([81, 58, 42, 33, 61], 259));
- 재귀적으로 L을 1씩 증가시켜가며 바둑이를 태웠을 때와 안태웠을 때로 나누어 sum을 계산한다.
- sum이 최대 무게를 넘어서면 더 이상 진행할 필요가 없으므로 return 한다.
- tsum은 현재까지 모든 강아지를 태웠을 때로 가정하고 무게를 모두 더한다.
- total은 모든 강아지의 무게인데, 여기서 tsum을 빼면 앞으로 남은 강아지를 모두 태웠을 때의 무게이다.
- 그 값에 현재 sum을 더해도 answer에 담긴 값보다 작을 때는 앞으로 남은 강아지를 모두 태워도 정답이 될 수 없기 때문에 return 한다.
최대점수 구하기
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.
각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.
제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
function solution(nums, m) {
let answer = 0;
function DFS(L, sum, time) {
if (time > m) return;
if (L === nums.length) {
answer = Math.max(answer, sum);
} else {
DFS(L + 1, sum + nums[L][0], time + nums[L][1]);
DFS(L + 1, sum, time);
}
}
DFS(0, 0, 0);
return answer;
}
console.log(
solution(
[
[10, 5],
[25, 12],
[15, 8],
[6, 3],
[7, 4],
],
20
)
);
console.log(
solution(
[
[15, 6],
[30, 11],
[23, 8],
[14, 4],
[10, 3],
[20, 7],
],
25
)
);
- 바둑이 승차 문제와 비슷한 방법으로 해결하면 된다.
- 입력이 많을 때 시간을 줄이고 싶다면, total을 구해서 최적의 해답이 아니라면 return하는 코드를 삽입해도 좋다.
중복 순열 구하기
1부터 N까지 번호가 적힌 구슬이 있습니다.
이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
function solution(n, m) {
let answer = [];
let tmp = [];
function DFS(L) {
if (L === m) {
answer.push(tmp.slice());
} else {
for (let i = 1; i <= n; i++) {
tmp.push(i);
DFS(L + 1);
tmp.pop();
}
}
}
DFS(0);
return answer;
}
console.log(solution(3, 2));
- L을 1씩 증가시키며 재귀호출을 해서 해결하는 문제이다.
- m은 깊이를 지정하고, for문은 n의 개수만큼 재귀를 하기 위해서 사용한다.
순열 구하기
10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
function solution(nums, m) {
let answer = [];
let tmp = [];
let ch = Array.from({ length: nums.length }, () => 0);
function DFS(L) {
if (L === m) {
answer.push(tmp.slice());
} else {
for (let i = 0; i <= nums.length; i++) {
if (ch[i] === 0) {
ch[i] = 1;
tmp.push(nums[i]);
DFS(L + 1);
tmp.pop();
ch[i] = 0;
}
}
}
}
DFS(0);
return answer;
}
console.log(solution([3, 6, 9], 2));
- 중복 순열구하기 문제에서 조금만 바꾸면 일반 순열 구하기가 된다.
- nums 길이만큼 ch 배열을 초기화 시켜두고, ch[i]가 0일 때만 코드를 동작시킨다.
- 그리고 내부에서 사용한 인덱스의 값을 1로 바꾸고, 다 사용한 뒤 0으로 바꾸면 중복해서 숫자가 조합되지 않는다.
조합의 경우수(메모이제이션)
아래 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.
nCr = n-1Cr-1 + n-1Cr
function solution(n, r) {
let answer;
let dy = Array.from(Array(35), () => Array(35).fill(0));
function DFS(n, r) {
if (dy[n][r] > 0) return dy[n][r];
if (n === r || r === 0) return 1;
else {
return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
}
}
answer = DFS(n, r);
return answer;
}
console.log(solution(33, 19));
- 조합의 경우수를 구해야 하는 경우 메모이제이션을 사용하면 코드가 동작하는 시간을 획기적으로 줄일 수 있다.
- 메모이제이션은 같은 값을 다른 곳에서 자주 사용하는 경우 사용하는 기법으로, 재귀에서 주로 사용한다.
Array.from()메소드는 첫 번째 매개변수로는 배열로 변환하고자 하는 배열 객체나 반복 가능한 객체가 들어가고, 두 번째 매개변수로는 map 콜백함수가 들어간다.- 위의 코드에서 첫 번째 매개변수에 Array(35)를 넣었으므로 길이 35의 배열이 들어가고, 두 번째 매개변수에서 Array(35)를 0으로 채워서 반환하므로 35 x 35의 2차원 배열이 생성된다.
- 첫 번째 매개변수에서
{length: 20}을 넣으면 배열이 생성되는 이유는 배열도 객체이기 때문이다. object에 Array 메소드들과 iterator, length 속성을 넣어준 것이 배열이기 때문에 첫 번째 인자로{length: 20}같은 것을 건내준다면 배열로 인식하여 코드가 동작한다.
- 이후 메모이제이션 기법을 사용해서 n, r에 값을 저장해놓고, DFS가 실행될 때마다 n, r로 조회하여 값이 있다면 더 이상 재귀 호출을 하지 않도록 한다.
수열 추측하기
가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.
예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
3 1 2 4
4 3 6
7 9
16
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.
단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
function solution(n, f) {
let answer;
let ch = Array.from({ length: n + 1 }, () => 0);
let p = [];
let b = [];
let flag = false;
b.push(1);
for (let i = 1; i < n; i++) {
b[i] = (b[i - 1] * (n - i)) / i;
}
function DFS(L, s) {
if (flag) return;
if (L === n) {
if (s === f) {
answer = p.slice();
flag = true;
}
} else {
for (let i = 1; i <= n; i++) {
if (ch[i] === 0) {
ch[i] = 1;
p.push(i);
DFS(L + 1, s + i * b[L]);
p.pop();
ch[i] = 0;
}
}
}
}
DFS(0, 0);
return answer;
}
console.log(solution(4, 16));
console.log(solution(5, 50));
- 상당히 어려웠고, 이해하는데에도 많은 시간이 걸린 문제
- 우선 파스칼의 삼각형이 이항계수와 관련되어 있다는 규칙을 먼저 알아채야만 했다.
- n개를 받았을 때, 이항계수 배열을 만드는 반복문을 실행했다.
- DFS 재귀함수를 호출해서 L이 n이 되기 전까지는 순열을 구하고, sum에는 위치한 값에 이항계수 값을 곱해서 더해주었다.
- L이 n이 되면 해당 순열이 가장 밑에 있는 줄의 값과 같은지 비교해서 같은 경우에만 answer에 추가하고 사전순으로 가장 앞에 오는 값을 구했으므로, flag를 바꿔서 더 이상 재귀호출이 되지 않도록 했다.
조합 구하기
1부터 N까지 번호가 적힌 구슬이 있습니다.
이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.
function solution(n, m) {
let answer = [];
let tmp = [];
function DFS(L, s) {
if (L === m) {
answer.push(tmp.slice());
} else {
for (let i = s; i <= n; i++) {
tmp.push(i);
DFS(L + 1, i + 1);
tmp.pop();
}
}
}
DFS(0, 1);
return answer;
}
- 이 코드는 외울 것
- for문이 꼭 처음에 뽑은 숫자 이후의 숫자부터 돌아야 한다.
- 순열은 (1, 2)와 (2, 1)이 다른 것이라면, 조합은 같은 것이다.
- 매개변수에 i 이후부터 시작하도록 저장하는 s를 넣어서 사용하여 해결
- 반복문을 i = s부터 시작하도록 설정하고, 재귀 호출을 할 때 s에 i + 1을 넣어서 호출하면, i는 i다음 인덱스부터 반복문이 돌아가기 때문에 조합을 제대로 출력한다.
0803
17일 차 DFS, BFS 응용, 그래프
수들의 조합
N개의 정수가 주어지면 그 숫자들 중 M개를 뽑는 조합의 합이 임의의 정수 K의 배수인 개수는 몇 개가 있는지 출력하는 프로그램을 작성하세요.
예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2+4+12로 2가지가 있습니다.
function solution(nums, m, k) {
let answer = 0;
function DFS(L, s, sum) {
if (L === m) {
if (sum % k === 0) answer++;
} else {
for (let i = s; i < nums.length; i++) {
DFS(L + 1, i + 1, sum + nums[i]);
}
}
}
DFS(0, 0, 0);
return answer;
}
console.log(solution([2, 4, 5, 8, 12], 3, 6));
console.log(solution([3, 5, 7, 8, 9, 12, 14], 4, 8));
- 조합 코딩 공식을 통해서 조합마다 합계를 구해서 k로 나눈 값이 나누어 떨어지면 정답을 1 증가시킨다.
이진트리 레벨탐색 (넓이우선탐색: BFS)
아래 그림과 같은 이진트리를 큐(Queue) 자료구조를 이용해 레벨탐색을 해보세요.
function solution() {
let answer = "";
function BFS() {
let queue = [];
queue.push(1);
while (queue.length) {
let v = queue.shift();
answer += v + " ";
for (let nv of [v * 2, v * 2 + 1]) {
if (nv > 7) continue;
queue.push(nv);
}
}
}
BFS();
return answer;
}
console.log(solution());
- BFS - 레벨 순으로 탐색
- 레벨 순으로 탐색한다는 말의 뜻은 0번 레벨에서 한 번만에 가는 요소들이 1번 레벨에 있다는 것이다.
- 최소 횟수, 최단 거리가 문제에 나오면 떠올리자
- queue를 생성하고 처음 값을 넣는다.
- queue를 while문으로 돌린다.
- queue에서 맨 앞의 요소를 꺼내어 자식 요소들을 호출하고, 자식 요소를 다시 queue안에 push한다.
- 이 행위를 queue가 빌 때까지 반복
- BFS의 기본 동작
송아지 찾기(BFS)
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.
현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.
최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.
function solution(s, e) {
let answer;
let ch = Array.from(Array(10001), () => 0);
function BFS() {
let queue = [];
queue.push(s);
ch[s] = 1;
let L = 0;
while (queue.length) {
let len = queue.length;
for (let i = 0; i < len; i++) {
let x = queue.shift();
for (let nx of [x + 1, x - 1, x + 5]) {
if (nx === e) return L + 1;
if (nx > 0 && nx <= 10000 && ch[nx] === 0) {
ch[nx] = 1;
queue.push(nx);
}
}
}
L++;
}
}
answer = BFS();
return answer;
}
console.log(solution(8, 3));
- 처음 현수의 위치는 5이므로, 가지를 4, 6, 10으로 뻗는다.
- 가지의 값 중 현재 송아지의 위치인 목표값이 없으므로, 레벨 1은 답이 아니다.
- 4, 6, 10에서 또 가지를 뻗어서 목표값을 찾은 레벨을 결과로 반환한다.
- 다만 이미 가지에서 제거된 값은 어차피 정답이 아니므로 가지를 뻗지 않는다.
- BFS함수를 시작하면 기본 세팅을 위해서 queue를 생성하고, 초깃값을 세팅하였다.
- 그리고 한 번 확인한 값은 다시 보지 않기 위해, ch를 생성하고 초깃값을 인덱스로 한 ch에는 1을 세팅하였다.
- queue.length로 while문으로 돌리고, 내부에서 queue의 길이만큼 반복문을 돌렸다.
- 반복문에서는 queue의 값을 하나 씩 꺼내어 그 값의 x-1, x+1, x+5에 방문하여 그 값이 목표값이라면, 아직 레벨을 올리지 않은 상태에서 추가적인 반복을 피하기 위해 살핀 것이니 L + 1을 리턴한다.
- 그렇지 않다면 계속해서 BFS로 탐색하기 위해 해당 값을 들른적이 없고, 값이 0보다 크면서 10000보다 작거나 같다면 ch[인덱스]를 1로 저장하고, 그 인덱스 값을 queue에 푸시한다.
- 이렇게 처음에 queue에 담겨 있던 만큼 반복을 마치고 나면, 레벨을 1 증가시키고 다시 queue.length를 조건으로 반복한다.
미로의 최단거리 통로(BFS)
7*7 격자판 미로를 탈출하는 최단경로의 길이를 출력하는 프로그램을 작성하세요.
경로의 길이는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다.
출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다.
격자판의 움직임은 상하좌우로만 움직인다.
function solution(board) {
let answer = 0;
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
let dist = Array.from(Array(7), () => Array(7).fill(0));
function BFS(x, y) {
let queue = [];
queue.push([x, y]);
board[x][y] = 1;
while (queue.length) {
let curr = queue.shift();
console.log(curr[0], curr[1]);
for (let j = 0; j < 4; j++) {
let nx = curr[0] + dx[j];
let ny = curr[1] + dy[j];
if (nx >= 0 && nx < 7 && ny >= 0 && ny < 7 && board[nx][ny] == 0) {
board[nx][ny] = 1;
dist[nx][ny] = dist[curr[0]][curr[1]] + 1;
queue.push([nx, ny]);
}
}
}
}
BFS(0, 0);
console.log(dist);
if (dist[6][6] === 0) return -1;
else answer = dist[6][6];
return answer;
}
- BFS로 돌리면 최단 거리가 5인 곳은 나중에 가도 이미 체크되어 있다.
- 간 지점은 1로 만들어 버린다.
- dx, dy는 인덱스를 상하좌우로 움직이기 위한 배열이다.
- dist에는 해당 인덱스까지의 거리를 저장한다.
- BFS로 인덱스를 변화시키며 뻗어나가면 dist[6][6]에 목표지점까지 최단거리가 들어가게 된다.
그래프와 인접행렬
인접 그래프
- 보통 코딩테스트에서는 입력 정보가 (1, 2)처럼 쌍으로 들어오는데 1과 2가 연결되어 있다는 뜻이다.
- 우선 2차원 배열을 생성한다.
- 인덱스 번호를 정점으로 사용하기 위해서
정점 + 1을 length로 생성한다.
- 인덱스 번호를 정점으로 사용하기 위해서
- 행에서 열로 이동한다고 생각하고 코드를 작성해야 한다.
- 무방향 그래프의 경우 (1, 2)가 들어오면 2차원 배열의 [1][2], [2][1]을 체크해준다.
- 방향 그래프의 경우 [1][2]만 체크하면 된다.
- 가중치 그래프에서는 [1][2]에 가중치 값을 넣어준다.
경로 탐색(인접행렬)
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요.
아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6 가지입니다.
매개변수 n에 정점의 수, 이차원 배열 edges에 간선의 정보가 주어진다.
function solution(n, edges) {
let answer = 0;
let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
let ch = Array.from(Array(n + 1), () => 0);
for (let [a, b] of edges) {
graph[a][b] = 1;
}
function DFS(v) {
if (v === n) {
answer++;
} else {
for (let i = 1; i <= n; i++) {
if (ch[i] === 0 && graph[v][i] === 1) {
ch[i] = 1;
DFS(i);
ch[i] = 0;
}
}
}
}
ch[1] = 1;
DFS(1);
return answer;
}
console.log(
solution(5, [
[1, 2],
[1, 3],
[1, 4],
[2, 1],
[2, 3],
[2, 5],
[3, 4],
[4, 2],
[4, 5],
])
);
- 모든 경로의 가지 수를 구해야 하는 문제이므로 DFS를 사용한다.
- graph 배열에는 인덱스 번호를 정점으로 해서 경로가 있다면 해당 인덱스에 1을 저장한다.
- ch 배열은 다시 갔던 경로로 되돌아가지 않도록 하기 위해서 생성하고, 기본 값을 0으로 초기화한다.
- DFS를 선언하기 전에 1은 출발 지점이므로 항상 ch[1]은 1로 되어있어야 한다.
- DFS에서 v가 n이 되면 경로를 찾은 것이므로 answer를 1 증가한다.
- 그렇지 않은 경우 1부터 n까지 반복문을 돌아서 방문한 적 없는 경로이고, 경로가 있다면 재귀호출하여 경로를 찾는다.
경로 탐색(인접리스트)
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요.
아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6 가지입니다.
function solution(n, edges) {
let answer = 0;
let graph = Array.from(Array(n + 1), () => Array());
let ch = Array.from(Array(n + 1), () => 0);
for (let [a, b] of edges) {
graph[a].push(b);
}
function DFS(v) {
if (v === n) {
answer++;
} else {
for (let nv of graph[v]) {
if (ch[nv] === 0) {
ch[nv] = 1;
DFS(nv);
ch[nv] = 0;
}
}
}
}
ch[1] = 1;
DFS(1);
return answer;
}
console.log(
solution(5, [
[1, 2],
[1, 3],
[1, 4],
[2, 1],
[2, 3],
[2, 5],
[3, 4],
[4, 2],
[4, 5],
])
);
- 정점의 개수가 100개가 넘어가면 인접행렬을 사용했을 때 효율이 너무 떨어진다.
- 인접리스트 사용해야 한다.
- 인접리스트 - 그래프의 행 크기 + 1만큼 배열을 생성한다.
- 1이 2를 가리키면, graph[1].push(2)를 한다. 무방향일 때는 반대로도 해줘야 한다.
- 가중치 그래프일 때는 2차원 배열로 graph[a].push([b, c]) 방식으로 한다.
- a번 인덱스가 b번 방향을 향하는데, 가중치가 c라는 뜻
- 인접행렬은 2차원 배열을 생성해서 모든 값을 0으로 초기화하고 필요한 인덱스에 값을 넣었다면, 인접리스트는 행 크기 + 1만큼만 생성해서 행 내에서 필요한 값만 push하여 사용한다.
동아리 개수
현수가 다니는 학교에는 동아리가 많이 있습니다. 현수가 다니는 학교의 동아리의 개수를 구하는 프로그램을 작성하세요.
현수가 다니는 학교의 학생은 1번부터 N번까지 번호가 부여된 N명의 학생들로 되어 입력됩니다.
만약 1번 학생과 2번 학생이 같은 동아리 이면 (1, 2) 순서쌍으로 입력되며, (2, 3)이 입력되면 1, 2, 3번 학생은 같은 동아리입니다.
모든 학생은 동아리를 가지고 있습니다.
// 인접 행렬 사용은 피해야 한다.
function solution(n, edges) {
let answer = 0;
let graph = Array.from(Array(n + 1), () => Array());
let ch = Array.from({ length: n + 1 }, () => 0);
for (let [a, b] of edges) {
graph[a].push(b);
graph[b].push(a);
}
function DFS(v) {
for (let nv of graph[v]) {
if (ch[nv] === 0) {
ch[nv] = 1;
DFS(nv);
}
}
}
for (let i = 1; i <= n; i++) {
if (ch[i] === 0) {
answer++;
ch[i] = 1;
DFS(i);
}
}
return answer;
}
console.log(
solution(7, [
[1, 2],
[2, 3],
[1, 4],
[1, 5],
])
);
- 문제에서 순서 쌍이 주어진 것을 보고 인접리스트와 DFS를 사용해서 문제를 해결할 수 있겠다고 생각했다.
- 무방향 그래프이므로 그에 맞게 인접리스트를 세팅했다.
- 기존에는 DFS내에서 if else문을 사용해서 해결했는데, 이번에는 바깥에서 for문을 돌려 조건을 검사해가며 필요할 때 DFS를 호출했다.
섬나라 아릴랜드(DFS)
N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.
각 섬은 1로 표시되어 상하좌 우와 대각선으로 연결되어 있으며, 0은 바다입니다.
섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.
function solution(board) {
let answer = 0;
let n = board.length;
let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
let dy = [0, 1, 1, 1, 0, -1, -1, -1];
function DFS(x, y) {
for (let k = 0; k < 8; k++) {
let nx = x + dx[k];
let ny = y + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 1) {
board[nx][ny] = 0;
DFS(nx, ny);
}
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] === 1) {
board[i][j] = 0;
answer++;
DFS(i, j);
}
}
}
return answer;
}
console.log(
solution([
[1, 1, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0],
[1, 0, 1, 0, 1, 0, 0],
])
);
- 1로 연결된 덩어리들의 개수 찾기 문제
- 8방향 탐색이니까 방향 배열 초기화를 잘 해줘야 한다.
- 반복문으로 board를 돌면서 값이 1이면 섬을 발견한 것이므로 answer를 증가시킨다.
- 발견한 곳이므로 값을 0으로 바꾸고, 해당 인덱스를 보내서 DFS를 실행시킨다.
- 해당 인덱스를 기준으로 인덱스를 상하좌우 대각선으로 바꿔가며 섬이 있는지 탐색한다.
- 있다면 해당 인덱스를 찾았으니 0으로 바꾸고, 다시 DFS를 호출한다.
최대 선호 음식(DFS)
엘리트 학원에서 선생님과 학생들이 소풍을 갔습니다. 선생님들은 학생들에게 요리를 해주기로 마음먹고, 학생들에게 각자의 취향에 대해서 물었다.
선생님들이 가지고 있는 양념재료의 종류는 D(1≤D≤15)종류입니다. 양념재료는 1부터 D까지 번호로 매겨져 있다.
각각의 학생들은 자기가 원하는 재료가 꼭 다 들어가야만 음식을 먹겠다고 합니다.
학생들은 총 N(1≤N≤30,000)명이 있고, 선생님이 사용할 수 있는 재료의 종류가 K(1≤K≤D)개 이하가 되도록 하려 한다. 위의 조건을 만족하면서 최대 몇 명의 학생에게 음식을 만들어 줄 수 있는지 구하는 프로그램을 작성하세요.
function solution(nums, d, k) {
let answer = Number.MIN_SAFE_INTEGER;
n = nums.length;
pow = Array.from({ length: d + 1 }, () => 0);
st = Array.from({ length: n }, () => 0);
pow[1] = 1;
for (let i = 2; i <= d; i++) {
pow[i] = pow[i - 1] * 2;
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < nums[i].length; j++) {
st[i] += pow[nums[i][j]];
}
}
function DFS(L, s, bit) {
if (L === k) {
let cnt = 0;
for (let j = 0; j < n; j++) {
if ((bit & st[j]) === st[j]) cnt++;
}
answer = Math.max(answer, cnt);
} else {
for (let i = s; i <= d; i++) {
DFS(L + 1, i + 1, bit + pow[i]);
}
}
}
DFS(0, 1, 0);
return answer;
}
- 비트 연산자를 활용해야 하는 문제이다.
- pow 배열에는 양념 번호와 매치 시켜 이진수로 표현해서 있으면 1, 없으면 0이라고 생각하고 가중치를 저장한다.
- st 배열은 pow 가중치를 적용한 학생들의 원하는 요리를 숫자화 시킨 것이다.
- 요리를 제한하는 개수만큼 뽑아서 조합하여, 학생들의 원하는 요리를 가장 많이 만족하는 개수를 반환한다.
- 원하는 요리를 만족하는지는 비트 연산자를 사용해서 해결한다.
토마토(BFS)
현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림 과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 합니다. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
function solution(board) {
let answer = 0;
let n = board.length;
let m = board[0].length;
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
let dist = Array.from(Array(n), () => Array(m).fill(0));
let queue = [];
function BFS() {
while (queue.length) {
let cur = queue.shift();
for (let j = 0; j < 4; j++) {
let nx = cur[0] + dx[j];
let ny = cur[1] + dy[j];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] === 0) {
board[nx][ny] = 1;
dist[nx][ny] = dist[cur[0]][cur[1]] + 1;
queue.push([nx, ny]);
answer = dist[nx][ny];
}
}
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (board[i][j] === 1) {
dist;
queue.push([i, j]);
}
}
}
BFS();
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (board[i][j] === 0) return -1;
}
}
return answer;
}
console.log(
solution([
[0, 0, -1, 0, 0, 0],
[0, 0, 1, 0, -1, 0],
[0, 0, -1, 0, 0, 0],
[0, 0, 0, 0, -1, 1],
])
);
- 방향 배열과, 익은 날짜를 저장하는 배열, BFS를 사용해서 해결한 문제
- 마지막에 for문에서 익지 않은 토마토가 있는지 확인하여 그렇다면 -1을 반환하고, 그렇지 않다면 토마토가 모두 익는데 걸린 날짜를 반환한다.
0804
18일 차 트리, 이분검색(결정알고리즘)
Union&Find
- 서로소 집합
- 여러개의 노드가 존재할 때 두 개의 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘
Find
- 한 노드(인덱스)가 해당 인덱스가 있는 집합과 같으면 해당 인덱스를 반환하고,
- 그렇지 않다면 해당 인덱스 집합으로 Find를 재귀호출하여 그 값을 인덱스 집합에 다시 저장한 뒤 반환하는 함수
function Find(v) {
if (v === unf[v]) return v;
else return (unf[v] = Find(unf[v]));
}
Union
- 두 노드가 속해있는 집합을 찾고, 집합이 서로 다르다면 같게 만들어주는 함수
function Union(a, b) {
let fa = Find(a);
let fb = Find(b);
if (fa !== fb) unf[fa] = fb;
}
친구인가? (Disjoint-Set : Union&Find)
오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다.
현수는 각 학생들의 친구관계를 알고 싶다.
모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구관계가 번호로 표현된 숫자쌍이 주어진다.
만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다.
그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다.
학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요.
두 학생이 친구이면 “YES”이고, 아니면 ”NO”를 출력한다.
function solution(n, nums, s1, s2) {
let answer = "YES";
let unf = Array.from({ length: n + 1 }, (v, i) => i);
function Find(v) {
if (v === unf[v]) return v;
else return (unf[v] = Find(unf[v]));
}
function Union(a, b) {
let fa = Find(a);
let fb = Find(b);
if (fa !== fb) unf[fa] = fb;
}
for (let [a, b] of nums) {
Union(a, b);
}
if (Find(s1) !== Find(s2)) return "NO";
return answer;
}
- nums로 넘겨받은 배열을 유니온 함수를 사용해서 같은 집합으로 묶는다.
- Find로 받은 매개변수 2개가 같은 함수 내에 위치했는지 확인한다.
MST(최소신장트리)
- 그래프 내의 모든 정점을 포함하는 트리를 스패닝 트리라고 한다.
- MST는 스패닝 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리이다.
- 각 간산의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다.
- 즉, 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것
특징
- 간선의 가중치의 합이 최소여야 한다.
- n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
- 사이클이 포함되어서는 안된다.
- 도로 건설, 전기 회로, 통신, 배관 등에서 사용
Kruskal MST 알고리즘
- 탐욕적인 방법을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
- MST가 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다.
- 간선 선택을 기반으로 하는 알고리즘
- 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법
원더랜드(최소스패닝트리: 크루스칼, Union&Find 활용)
원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.
모든 도시를 연결하면서 드는 최소비용을 반환하라.
function solution(n, edges) {
let answer = 0;
let unf = Array.from({ length: n + 1 }, (v, i) => i);
function Find(v) {
if (v === unf[v]) return v;
else return (unf[v] = Find(unf[v]));
}
function Union(a, b) {
let fa = Find(a);
let fb = Find(b);
if (fa !== fb) unf[fa] = fb;
}
edges.sort((a, b) => a[2] - b[2]);
for (let [a, b, c] of edges) {
let fa = Find(a);
let fb = Find(b);
if (fa !== fb) {
answer += c;
unf[fa] = fb;
}
}
return answer;
}
console.log(
solution(9, [
[1, 2, 12],
[1, 9, 25],
[2, 3, 10],
[2, 8, 17],
[2, 9, 8],
[3, 4, 18],
[3, 7, 55],
[4, 5, 44],
[5, 6, 60],
[5, 7, 38],
[7, 8, 35],
[8, 9, 15],
])
);
- 모든 도로 정보 배열을 비용으로 오름차순 정렬했다.
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택했다.
- 낮은 가중치를 먼저 선택
- 사이클 형성 간선 제외
- 해당 간선을 현재의 MST 집합에 추가한다.
이분검색
임의의 N개의 숫자가 입력으로 주어집니다.
N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요.
단 중복값은 존재하지 않습니다.
function solution(nums, m) {
let answer;
let lt = 0;
let rt = nums.length - 1;
nums.sort((a, b) => a - b);
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (m < nums[mid]) {
rt = mid - 1;
} else if (m > nums[mid]) {
lt = mid + 1;
} else {
answer = mid + 1;
break;
}
}
return answer;
}
console.log(solution([23, 87, 65, 12, 57, 32, 99, 81], 32));
- 이분 검색을 사용하려면 먼저 정렬을 해야 한다.
- lt와 rt를 설정하고, while문을 lt보다 rt가 크거나 같을 때까지 돌려서 mid를 조정해나가며 logN으로 구한다.
2차원 배열 이분검색
각 행과 각 열이 오름차순으로 되어 있는 2차원 배열이 주어지면 가장 효율적인 방법으로 특정 숫자는 찾는 프로그램을 작성해보세요.
function solution(matrix, target) {
let answer;
let row = 0;
let col = matrix[row].length - 1;
while (row < matrix.length && col >= 0) {
if (target > matrix[row][col]) {
row++;
} else if (target < matrix[row][col]) {
col--;
} else {
answer = [row, col];
break;
}
}
return answer;
}
console.log(
solution(
[
[1, 6, 9, 12],
[3, 7, 10, 14],
[5, 8, 13, 17],
[15, 18, 20, 23],
],
8
)
);
- row 번호는 0, col 번호는 len - 1에서 시작한다.
- target이 그 값보다 작으면 col을 앞으로 보낸다.
- target이 값보다 크면 row를 뒤로 보내서 값을 키워준다.
랜선자르기 (결정 알고리즘)
엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다.
선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다.
예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자.
그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
function solution(nums, n) {
let answer;
let lt = 1;
let rt = Math.max(...nums);
function count(len) {
let cnt = 0;
for (let x of nums) {
cnt += Math.floor(x / len);
}
return cnt;
}
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (count(mid) >= n) {
answer = mid;
lt = mid + 1;
} else {
rt = mid - 1;
}
}
return answer;
}
console.log(solution([802, 743, 457, 539], 11));
- 이분 검색으로 결정 알고리즘을 구현하려면, lt와 rt 사이에 답이 있는지 검증해야 한다.
- mid로 의도한 수를 반환하는 함수를 잘 작성하는 것이 실력
- 1과 매개변수로 받는 배열에서 가장 큰 값 사이에 답이 있을 것이라고 생각했다.
- while문으로 lt와 rt를 구하고, 함수로 그 중간값을 넘겨서 반환하는 값에 따라 lt와 rt를 조정해가며 원하는 값을 얻었다.
뮤직비디오(결정알고리즘)
지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.
순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다.
즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다.
또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다.
이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다.
그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.
function solution(nums, m) {
let answer;
let lt = Math.max(...nums);
let rt = nums.reduce((acc, curr) => acc + curr, 0);
function count(capacity) {
let cnt = 1;
let sum = 0;
for (let x of nums) {
if (sum + x > capacity) {
cnt++;
sum = x;
} else sum += x;
}
return cnt;
}
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (count(mid) <= m) {
answer = mid;
rt = mid - 1;
} else {
lt = mid + 1;
}
}
return answer;
}
- 결정 알고리즘을 적용하는 문제들은 우선 lt, rt를 지정한다.
- 그리고 while문으로
lt <= rt를 돌리고 내부에서 mid를 구한 뒤, mid를 목표 값과 비교하여 lt, rt를 조정한다. - mid를 매개변수로 하여 값을 계산하는 함수를 생성하여 구현한다.
마구간 정하기(결정알고리즘)
N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ……, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.
현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다.
각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.
function solution(nums, c) {
let answer;
nums.sort((a, b) => a - b);
let lt = 1;
let rt = nums[nums.length - 1] - 1;
function count(len) {
let cnt = 1;
let ep = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] - ep >= len) {
cnt++;
ep = nums[i];
}
}
return cnt;
}
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (count(mid) >= c) {
answer = mid;
lt = mid + 1;
} else {
rt = mid - 1;
}
}
return answer;
}
console.log(solution([1, 3, 6, 11, 18, 27, 38, 41, 56, 73, 92, 113], 8));
- count 함수는 거리를 매개변수로 받아서, nums의 배열 간의 거리 간격이 매개 변수로 받은 거리보다 길거나 같다면 해당 마구간에 말을 넣을 수 있는 것으로 판단하여 값을 계산했다.
- count 함수만 잘 작성하면 쉽게 해결할 수 있다.
제품 이동
섬이 많은 나라로 유명한 인도네시아는 N(1≤N≤10,000)개의 섬으로 이루어진 나라이다.
이 섬들은 다리로 연결되어 있는데, 각 다리는 통과하려면 무게제한이 있다.
이 무게제한을 넘어가는 무게가 다리를 이용하면 다리는 무너지게 된다.
엘리트 무역회사는 이들 섬 중 2개에 공장이 있는데 항상 두 공장에서 서로 제품을 이동하는 작업을 한다.
섬의 개수 N과 각 섬을 연결하는 다리 정보가 주어지면 한 번의 이동으로 옮길 수 있는 제품의 최대 무게를 구하세요.
단 다리를 건널 수 있는가의 무게제한은 제품의 무게로만 계산한다.
function solution(n, edges, s, e) {
let answer = 0;
let graph = Array.from(Array(n + 1), () => Array());
let lt = 1;
let rt = 0;
for ([a, b, c] of edges) {
graph[a].push([b, c]);
graph[b].push([a, b]);
rt = Math.max(rt, c);
}
function BFS(w) {
let ch = Array.from({ length: n + 1 }, () => 0);
let queue = [];
ch[s] = 1;
queue.push(s);
while (queue.length) {
let a = queue.shift();
for (let [b, c] of graph[a]) {
if (c >= w && ch[b] === 0) {
ch[b] = 1;
queue.push(b);
}
}
}
return ch[e];
}
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (BFS(mid)) {
answer = mid;
lt = mid + 1;
} else {
rt = mid - 1;
}
}
return answer;
}
console.log(
solution(
5,
[
[1, 2, 5],
[1, 3, 3],
[1, 4, 2],
[2, 4, 2],
[3, 4, 4],
[4, 5, 3],
],
1,
5
)
);
- 여러가지 생각해야 할 것이 많았던 문제였다.
- 우선 그래프를 생성하고 양방향 인접리스트에 맞게 매개변수로 받은 좌표를 입력했다.
- 그리고 물체의 무게를 기준으로 결정 알고리즘을 구현하였다.
- BFS를 통해서 물체의 무게를 정답으로 정할지 말지 정했는데, 물체의 무게가 허용하는 무게보다 작거나 같을 때만 다리를 통과하도록 했다.
- 그래서 목표했던 다리부터 다리까지 이동할 수 있다면 해당 무게로 한 번에 다리를 지날 수 있다고 판단하였다.
0805
19일 차 다이나믹 프로그래밍
계단 오르기
철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.
그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?
function solution(n) {
let answer = 0;
let dy = Array.from({ length: n + 1 }, () => 0);
dy[1] = 1;
dy[2] = 2;
for (let i = 3; i <= n; i++) {
dy[i] = dy[i - 1] + dy[i - 2];
}
answer = dy[n];
return answer;
}
- 다이나믹 프로그래밍의 기본은 dy[i]를 잘 정의하는 것
- 단계별로 조금씩 나눠서 구현하는데, 다음 단계를 구현할 때 바로 앞에 구한 값을 이용하여 구현
- dy[i]는 i 번째 계단까지 올라갈 수 있는 방법의 수다.
- i 번째 계단으로 가는 방법은, i - 1 번째 계단에서 한 칸 오르는 방법과 i - 2 번째 계단에서 두 칸 오르는 방법 두 가지밖에 없으므로, 그 둘을 더하면 값을 구할 수 있다.
돌다리 건너기
철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다.
철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다.
철수가 개울을 건너는 방법은 몇 가지일까요?
function solution(n) {
let answer;
let dy = Array.from({ length: n + 2 }, () => 0);
dy[1] = 1;
dy[2] = 2;
for (let i = 3; i <= n + 1; i++) {
dy[i] = dy[i - 2] + dy[i - 1];
}
answer = dy[n + 1];
return answer;
}
console.log(solution(7));
- 첫 번째 문제와 같은 문제. 돌다리를 모두 건너야 하니 n + 1만 해줘서 계산하면 쉽게 나온다.
최대 부분 증가수열
N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.
예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다.
function solution(nums) {
let answer = 0;
let dy = Array.from({ length: nums.length }, () => 0);
let pa = Array.from({ length: nums.length }, () => -1);
let pos = 0;
dy[0] = 1;
for (let i = 1; i < nums.length; i++) {
let max = 0;
for (let j = i - 1; j >= 0; j--) {
if (nums[i] > nums[j] && dy[j] > max) {
max = dy[j];
pa[i] = j;
}
dy[i] = max + 1;
if (dy[i] > answer) {
answer = dy[i];
pos = i;
}
}
}
let path = [];
function DFS(idx) {
if (idx === -1) return;
else {
DFS(pa[idx]);
path.push(nums[idx]);
}
}
DFS(pos);
console.log(path);
return answer;
}
console.log(solution([5, 3, 7, 8, 6, 2, 9, 4]));
- LIS(최장 증가 부분 수열) 알고리즘
- 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열
- 일반적으로 가장 쉽게 푸는 방법이 DP를 이용하는 것
- dy[i]는 i 번째 항이 마지막 항이 되는 최대 부분 증가수열 길이
- 최장 증가 부분 수열을 구하는 것은 요소를 전체적으로 탐색하면서 하나를 탐색할 때마다, 해당 요소부터 앞으로 검색해나가며 그보다 작은 수가 있고 그 중 dy가 제일 큰 수가 있으면 그 수의 dy + 1을 현재 요소의 dy에 저장
- 이러면 최장 증가수열의 길이를 저장
- 이것을 DFS와 응용하여 최장 증가수열의 path를 반환할 수도 있다.
- 증가 수열을 연결하게 만든 dy의 경로 인덱스를 저장해서 새로운 배열을 생성
- 최장 증가수열의 인덱스를 pos에 저장
- 위의 두 개를 사용해서 재귀 호출하여 path를 만든다.
효율적인 공부
철수는 과학적으로 공부하기 위해 전문 병원에서 철수의 신체 리듬에 따라 공부의 효율성을 표시한 표를 받았다.
표는 N(1<=N<=1,000,000)시간의 일정을 겹쳐지는 M(1<=M<=1,000)구간별로 공부의 효율성이 표시되어 있다.
각 구간은 시작시간(0<=st<N)과 끝나는 시간(st<et<=N) 그리고 해당 구간에서의 공부의 효율성이 주어진다.
철수는 한 구간을 공부하고 나면 꼭 휴식시간(1<=R<=N)을 가져야만 합니다.
철수가 N시간동안 공부를 할 때 각 구간을 잘 선택해서 공부를 열심히 한다면 가장 높은 효율성을 얼마인지 출력하는 프로그램을 작성하세요.
function solution(times, r) {
let answer;
let dy = Array.from({ length: times.length }, () => 0);
times.sort((a, b) => a[1] - b[1]);
dy[0] = times[0][2];
for (let i = 1; i < times.length; i++) {
let max = 0;
for (let j = i - 1; j >= 0; j--) {
if (times[j][1] + r <= times[i][0]) {
max = Math.max(max, dy[j]);
}
dy[i] = max + times[i][2];
}
}
answer = Math.max(...dy);
return answer;
}
- 우선 끝나는 시간을 기준으로 일정을 오름차순 정렬하였다.
- dy[i]는 i 번째 까지의 최대 공부 효율성
- 이전 문제와 비슷한 방법으로 구현하였고, if문에서 이전 스케줄들의 끝나는 시간 + 휴식시간이 현재 일정의 시작시간보다 작거나 같을 때만 dy에 삽입했다.
냅색 알고리즘
최고 11kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 5kg, 3kg, 6kg, 4kg의 무게를 가진 4종류의 보석이 있다.
이 보석들의 가치는 각각 12, 8, 14, 7이다.
이 보석을 가방에 담는데 11kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요?
각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있다는 뜻입니다.
function solution(nums, m) {
let answer;
let dy = Array.from({ length: m + 1 }, () => 0);
for (let i = 0; i < nums.length; i++) {
for (let j = nums[i][0]; j <= m; j++) {
dy[j] = Math.max(dy[j], dy[j - nums[i][0]] + nums[i][1]);
}
}
answer = dy[m];
return answer;
}
console.log(
solution(
[
[5, 12],
[3, 8],
[6, 14],
[4, 7],
],
11
)
);
- dy[i]는 i 번째까지 담을 수 있는 최대의 가치이다.
- 보석을 무한대로 쓸 수 있으므로, 기준을 보석의 무게로 잡고 무게만큼 떨어져 있는 가치에서 보석의 가치를 더한 값과 이전까지의 최대 가치를 비교하여 큰 값을 현재의 dy로 설정한다.
동전 교환(냅색 알고리즘)
다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?
각 단위의 동전은 무한정 쓸 수 있다.
function solution(nums, m) {
let answer;
let dy = Array.from({ length: m + 1 }, () => 1000);
dy[0] = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = nums[i]; j <= m; j++) {
dy[j] = Math.min(dy[j], dy[j - nums[i]] + 1);
}
}
answer = dy[m];
return answer;
}
console.log(solution([1, 2, 5], 15));
- dy[i]: i원까지 거스를 수 있는 최소 동전 개수
- 현재 dy[j]랑 비교하여 더 작은 값을 구해야 하기에 초기값을 설정하기 위해서 각 요소를 1000으로 크게 잡았다.
최대점수 구하기(냅색 알고리즘)
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.
각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.
제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.
(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
function solution(nums, m) {
let answer;
let dy = Array.from({ length: m + 1 }, () => 0);
for (let i = 0; i < nums.length; i++) {
let ps = nums[i][0];
let pt = nums[i][1];
for (let j = m; j >= pt; j--) {
dy[j] = Math.max(dy[j], dy[j - pt] + ps);
}
}
answer = dy[m];
return answer;
}
console.log(
solution(
[
[10, 5],
[25, 12],
[15, 8],
[6, 3],
[7, 4],
],
20
)
);
- 이전 두 문제와는 다르게 자원이 한 개로 한정되어 있다.
- dy[i]: i분을 사용해 얻을 수 있는 최대 점수
- 뒤에서부터 해당 자원을 얻을 수 있는 시간까지 앞으로 간다.
최대공통부분문자열(LCS)
최대 공통 부분 문자열이란 두 문자열 acbehf와, abefc의 공통의 부분 문자열 중에서 가장 긴 것을 의미한다.
여기서 최대 공통 부분 문자열은 abef 이다.
두 문자열이 주어지면 두 문자열의 최대공통부분문자열의 길이를 출력하는 프로그램을 작성하세요.
function solution(s1, s2) {
let answer;
let n = s1.length;
let m = s2.length;
let dy = Array.from(Array(n + 1), () => Array(m + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
if (s1[i - 1] === s2[j - 1]) {
dy[i][j] = dy[i - 1][j - 1] + 1;
} else {
dy[i][j] = Math.max(dy[i - 1][j], dy[i][j - 1]);
}
}
}
answer = dy[n][m];
let path = [];
function DFS(p1, p2) {
if (p1 === 0 || p2 === 0) return;
if (s1[p1 - 1] === s2[p2 - 1]) {
DFS(p1 - 1, p2 - 1);
path.push(s1[p1 - 1]);
} else {
if (dy[p1 - 1][p2] > dy[p1][p2 - 1]) DFS(p1 - 1, p2);
else DFS(p1, p2 - 1);
}
}
DFS(n, m);
console.log(path);
return answer;
}
console.log(solution("acbehf", "abefc"));
- LCS문제를 해결해야 할 때는 2차원 다이나믹 프로그래밍을 떠올려보자
- s1과 s2를 가지고 반복문을 돌면서 문자를 비교해 같다면 dy의 좌상 대각선에서 1을 더해 저장하고, 그렇지 않다면 위와 아래 값 중 큰 값을 dy[i][j]에 저장한다.
- 그렇게 하면 dy[i][j]에는 해당 문자열 길이까지의 최대 공통부분문자열의 길이가 들어간다.
- 2차 다이나믹 프로그래밍에서는 규칙을 직접 찾아내는 능력이 중요한 것으로 보인다.
- DFS를 사용해서 path를 구하는 코드도 작성해보았다.
0806
20일 차 최단거리, Trie
최소편집
문자열 A와 문자열 B가 주어져 있을 때, 문자열 A를 문자열 B로 편집(삽입, 삭제, 대체)하여 바꾸려 한다.
이때 편집하는 최소 횟수를 구하는 프로그램을 작성하세요.
만약 문자열 A가 aabab이고 문자열 B가 babb라면 2회의 편집으로 바꿀 수 있다.
문자열 aabab에서 제일 앞에 있는 a를 b로 대체하면 babab이고 네 번째 a를 삭제하면 된다.
function solution(s1, s2) {
let answer = 0;
let len1 = s1.length;
let len2 = s2.length;
let dy = Array.from(Array(1001), () => Array(1001).fill(0));
for (let i = 1; i <= len1; i++) dy[i][0] = i;
for (let i = 1; i <= len2; i++) dy[0][i] = i;
for (let i = 1; i <= len1; i++) {
for (let j = 1; j <= len2; j++) {
if (s1[i - 1] === s2[j - 1]) {
dy[i][j] = dy[i - 1][j - 1];
} else {
dy[i][j] = Math.min(dy[i - 1][j], dy[i][j - 1], dy[i - 1][j - 1]) + 1;
}
}
}
answer = dy[len1][len2];
return answer;
}
- 2차원 배열을 응용한 문제. dy[i][j]는 해당 위치까지의 최소 편집 횟수다
- 각 기능을 정의하였다. 삭제는 윗 값 + 1, 삽입은 왼쪽 값 + 1, 대체는 대각선 + 1
- 글자를 비교하여 둘이 같으면 대각선 값을 그대로 dy[i][j]에 저장하고, 그렇지 않으면 세 기능 중 하나를 실행해야 하므로 기능을 실행하기 전의 위치를 살펴 가장 작은 값 + 1을 해줘서 답을 구했다..
동전 바꿔주기(냅색알고리즘)
명보네 동네 가게의 현금 출납기에는 k가지 동전이 각각n1, n2, … , nk개 씩 들어있다.
가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고한다. 이때, 동전 교환 방법은 여러가지가 있을 수 있다.
예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은4가지 방법으로 교환할 수 있다.
20 = 10×2
20 = 10×1+5×2
20 = 10×1+5×1+1×5
20 = 5×3+1×5
입력으로 지폐의 금액 T, 동전의 가지수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1,2,…,k)
지폐를 동전으로 교환하는 방법의 가지 수를 계산하는프로그램을 작성하시오. 방법의 수는 2^31 을 초과하지않는 것으로 가정한다.
// dy[i]: i 원을 교환하는 방법의 수
function solution(t, coins) {
let answer;
let dy = Array.from(Array(t + 1), () => 0);
dy[0] = 1;
for (let [p, n] of coins) {
for (let j = t; j >= 1; j--) {
for (let k = 1; k <= n; k++) {
if (j - p * k < 0) break;
dy[j] += dy[j - p * k];
}
}
}
answer = dy[t];
return answer;
}
console.log(
solution(20, [
[5, 3],
[10, 2],
[1, 5],
])
);
- 냅색 알고리즘에서 자원의 개수가 한정되어 있다면 3중 포문을 사용해서 dp를 돌려야 한다.
- 우선 처음에는 주워진 자원 배열을 포문으로 돌린다.
- dy[j]는 j원을 교환하는 방법의 수로 정하고, t원까지의 방법의 수를 구하기 위해서 뒤에서부터 1씩 감소시키며 내려온다.
- 마지막으로 동전의 개수만큼 반복하여 금액에 동전의 개수를 곱한 값을 j에서 빼서, 해당 인덱스가 0보다 크다면 인덱스 위치에 있는 dy값 (이전의 동전들만 가지고 구한 방법의 수)을 dy[j]에 더한다.
- 처음에 dy의 0번째 요소를 1로 초기화 해줘야한다.
- 처음 초기값을 정해서 생각한대로 프로그래밍이 되도록 하는 코딩 기술
플로이드 와샬 알고리즘
N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값을 구하는 프로그램을 작성하세요.
function solution(n, edges) {
let answer = Array.from(Array(n), () => Array(n));
let dist = Array.from(Array(n + 1), () => Array(n + 1).fill(1000));
for (let [a, b, c] of edges) {
dist[a][b] = c;
}
for (let k = 1; k <= n; k++) {
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
if (i === j) dist[i][j] = 0;
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
if (dist[i][j] === 1000) {
answer[i - 1][j - 1] = "M";
} else {
answer[i - 1][j - 1] = dist[i][j];
}
}
}
return answer;
}
console.log(
solution(5, [
[1, 2, 6],
[1, 3, 3],
[3, 2, 2],
[2, 4, 1],
[2, 5, 13],
[3, 4, 5],
[4, 2, 3],
[4, 5, 7],
])
);
- 플로이드 와샬 알고리즘은 모든 최단 경로를 구하는 문제에 사용하기 적합한 알고리즘이다.
- 냅색과 비슷하다.
- dist[i][j]는 i번 정점에서 j번 정점으로 가는 최소 비용이다.
- 인접 행렬로 그래프를 생성해서 모든 경로의 방향에 거리(비용)을 할당한다.
- 그래프에 있는 요소들을 n번 반복해서 해당 요소로 이동하는 거리가 다른 요소를 거쳐서 가는 거리보다 짧은지 계산하여, 짧다면 그 거리를 dist[i][j]에 저장한다. 그 동작을 모두 반복하면 i에서 j로 가는 최단 거리가 저장된다.
회장뽑기(플로이드-와샬 응용)
월드컵축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이모임은 만들어진지 얼마 되지 않았기 때문에 회원사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 서로 모두 알 수 있다.
각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.
예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다.
어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나, 친구의 친구임을 말한다.
또한, 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친국의 친구의 친구임을 말한다.4점, 5점등은 같은 방법으로 정해진다.
각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구 사이이면서 동시에 친구의 친구 사이이면, 이 두 사람은 친구사이라고 본다. 회장은 회원들 중에서 점수가 가장 작은 사람이 된다.
회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.
function solution(n, edges) {
let answer = [];
let dist = Array.from(Array(n + 1), () => Array(n + 1).fill(1000));
let score = Array.from({ length: n + 1 }, () => 0);
for (let i = 1; i <= n; i++) dist[i][i] = 0;
for (let [a, b] of edges) {
dist[a][b] = 1;
dist[b][a] = 1;
}
for (let k = 1; k <= n; k++) {
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
let PS = 1000;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
if (i === j) continue;
score[i] = Math.max(score[i], dist[i][j]);
}
PS = Math.min(PS, score[i]);
}
answer.push(PS);
let cnt = 0;
for (let i = 1; i <= n; i++) {
if (score[i] === PS) cnt++;
}
answer.push(cnt);
return answer;
}
console.log(
solution(5, [
[1, 2],
[2, 3],
[3, 4],
[4, 5],
[2, 4],
[5, 3],
])
);
- 이전 문제와 비슷한 방식으로 해결하면 된다.
- 다만 중요한 것은, 이 문제를 보고 이런 방식으로 풀어야겠다고 도출해내는 것이다.
트라이 자료구조
// Trie 자료구조
class Node {
constructor() {
this.end = false;
this.child = {};
}
}
class Trie {
constructor() {
this.root = new Node();
}
insert(word) {
let cur = this.root;
for (let x of word) {
if (cur.child[x] === undefined) {
cur.child[x] = new Node();
}
cur = cur.child[x];
}
cur.end = true;
}
search(word) {
let cur = this.root;
for (let x of word) {
if (cur.child[x] === undefined) return false;
cur = cur.child[x];
}
return cur.end;
}
prefixS(str) {
let cur = this.root;
for (let x of str) {
if (cur.child[x] === undefined) return false;
cur = cur.child[x];
}
return true;
}
}
- 검색을 하는 데 사용하는 자료구조이다.
- Node에는 해당 단어가 끝났는지 알려주는 end와 Node를 잇기 위한 child가 있다.
- Trie는 생성될 때 기본적으로 root노드를 생성한다.
- insert는 단어를 삽입하는 메소드이다. 해당 문자를 이어서 단어를 Trie에 삽입하고, 마지막 문자는 단어가 끝났음을 알려주기 위해 end를 true로 한다.
- search는 단어가 Trie에 있는지 확인하는 메소드이다. 해당 단어는 마지막 문자가 end true이므로, cur.end를 반환함으로써 해당 단어가 있는지 확인한다.
- 비슷한 메소드로는 PrefixS가 있는데, 이 메소드는 해당 단어의 문자들만 제대로 이어진다면 true를 반환한다.
자동완성
포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어졌다.
예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다!
단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.
예를 들어, 학습된 단어들이 아래와 같을 때
go
gone
guild
go를 찾을 때 go를 모두 입력해야 한다.
gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신 할 수 없다.)
guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다. 이 경우 총 입력해야 할 문자의 수는 7이다.
라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서 대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.
class Node {
constructor() {
this.cnt = 0;
this.child = {};
}
}
class Trie {
constructor() {
this.root = new Node();
}
insert(word) {
let cur = this.root;
for (let x of word) {
if (cur.child[x] === undefined) {
cur.child[x] = new Node();
}
cur = cur.child[x];
cur.cnt++;
}
}
getCount(word) {
let cur = this.root;
let count = 0;
for (let x of word) {
cur = cur.child[x];
count++;
if (cur.cnt === 1) return count;
}
return count;
}
}
function solution(words) {
let answer = 0;
let trie = new Trie();
for (let x of words) {
trie.insert(x);
}
for (let x of words) {
answer += trie.getCount(x);
}
return answer;
}
console.log(solution(["go", "gone", "guild"]));
- Trie 자료구조를 필요한 부분을 살짝 변형하여 문제를 구현했다.
- insert 메소드는 트라이에 자료를 학습시키는 역할을 한다. 같은 문자가 중첩돼서 학습되면, cnt를 증가시킨다. 즉 cnt가 1인 문자부터 해당 단어를 독립적으로 구별할 수 있다.
- getCount 메소드는 단어를 독립적으로 구별할 수 있는 count 값을 반환한다.
0807
Weekly 알고리즘 4번 문제 풀이
올바른 괄호 만들기
올바르지 않은 괄호문자열이 주어지면, 최소횟수로 괄호를 제거하여 올바른 괄호문자열로 만드는 프로그램을 작성하세요.
괄호를 최소로 제거했을 때 나올 수 있는 모든 올바른 괄호의 경우수를 출력합니다.
function solution(s) {
let answer = 0;
let stack = [];
let cnt = 0;
for (let x of s) {
if (x === ")") {
if (stack.length === 0) {
cnt++;
} else {
stack.pop();
}
} else {
stack.push(x);
}
}
cnt += stack.length;
let tmp = [];
let path = [];
function DFS(L, t) {
if (L === s.length - cnt) {
tmp.push(path.slice());
} else {
for (let i = t; i < s.length; i++) {
path.push(s[i]);
DFS(L + 1, i + 1);
path.pop();
}
}
}
DFS(0, 0);
let sh = new Map();
for (let x of tmp) {
stack = [];
cnt = 0;
for (let y of x) {
if (y === ")") {
if (stack.length === 0) {
cnt++;
} else {
stack.pop();
}
} else {
stack.push(x);
}
}
cnt += stack.length;
if (cnt === 0) {
sh.set(x.join(""), 1);
}
}
for (let [k, v] of sh) {
if (k !== "") answer += v;
}
return answer;
}
console.log(solution("()(()()"));
- 우선 최소한으로 괄호를 제거하는 수를 구했다.
- DFS로 호출하여 해당 괄호의 수만큼 제거한 조합을 구했다.
- 해당 조합이 스택이 맞는지 확인하고, 맞다면 map에 중첩되지 않도록 저장했다.
- 키 값이 빈 스택일 때를 제외하고 수를 세서 반환했다.
- 한 편으로는 여러 개념을 사용해서 문제를 해결했다는 즐거움이 있었지만, 훨씬 간결하게 풀 수 있는 방법도 있을 것이라는 생각이 들었다.
0808
Weekly 알고리즘 5번 문제 풀이
최대길이 등차수열
길이가 N인 자연수 수열이 주어지면 이 수열에서 등차수열을 이루는 부분수열 중 최대길이를 갖는 부분수열을 구하는 프로그램을 작성하세요.
만약 주어지는 수열이 [1, 2, 3, 5, 7, 8, 9]가 주어지면 등차수열을 이루는 최대길이 부분수열은 [1, 3, 5, 7, 9]로 그 길이는 5입니다. 부분수열을 입력된 순서는 유지해야 합니다.
function solution(nums) {
let answer = 0;
let max = Math.max(...nums);
let min = Math.min(...nums);
let n = max - min;
let m = nums.length;
let dy1 = Array.from(Array(n + 1), () => Array(m + 1).fill(1));
let dy2 = Array.from(Array(n + 1), () => Array(m + 1).fill(1));
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
for (let k = j - 1; k >= 1; k--) {
if (nums[k - 1] === nums[j - 1] - i) {
dy1[i][j] = dy1[i][k] + 1;
break;
}
}
}
}
for (let i = 1; i <= n; i++) {
for (let j = nums[m - 1]; j >= 1; j--) {
for (let k = j + 1; k <= m; k++) {
if (nums[k - 1] === nums[j - 1] - i) {
dy2[i][j] = dy2[i][k] + 1;
break;
}
}
}
}
for (let i = 1; i <= n; i++) {
answer = Math.max(answer, ...dy1[i]);
answer = Math.max(answer, ...dy2[i]);
}
return answer;
}
console.log(solution([1, 2, 3, 5, 7, 8, 9]));
console.log(solution([25, 20, 15, 30, 10, 40, 5]));
- 배열 내에서 최솟값과 최댓값을 구해서 그 사이에 있는 공차를 모두 구했다.
- 공차가 +일 때와, -일 때를 구분해서 모두 계산해 가장 긴 값을 저장하여 결과로 출력했다.
- 다만 이렇게 풀면 공차의 크기가 커질수록 엄청 코드가 느려진다. 다른 방법도 한 번 생각해봐야겠다.