꿀팁
DFS
- 모든 경우의 수
- 백트래킹 사용
- 최적의 조합 이나 특정 조건을 만족하는 모든 경우 (순열, 조합)
-> 백트래킹을 통해 여러가지 방법을 다 해보는 방식
BFS
- 최단거리
- 모든 방향 동시에 탐색하며 점진적 확장 -> 가까운 곳부터
- 큐(queue)
- 최단거리,특정 조건을 만족하는 가장 빠른 경로탐색 (미로탈출, 네트워크 탐색)
-> 요약 : 한번 방문후 끝나는 방식
(Lv.3) 성적평균
여기에서 배운점
?? 연산자
num[0]-2 ?? 0;null이나 undefined에서만 된다고 함 충격. 바보다.
풀이
시도 1. 막무가내 평균 구하기 (DP 미사용)
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, k] = input[0].split(' ').map(Number);
const score = input[1].split(' ').map(Number);
let studentNum = [];
for(let i=2; i<input.length; i++) {
studentNum.push(input[i].split(' ').map(Number))
}
const ans = [];
for(let i=0; i<studentNum.length; i++) {
let startNum = studentNum[i][0]-1;
let endNum = studentNum[i][1];
let sliceArr = score.slice(startNum, endNum);
let scoreAvg = sliceArr.reduce( (acc, cur) => acc+=cur, 0) / sliceArr.length;
ans.push(scoreAvg.toFixed(2));
}
for(let ansScore of ans) {
console.log(ansScore)
}
}
solution();
시도 2. DP사용 (근데 아니긴함)
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, k] = input[0].split(' ').map(Number);
const score = input[1].split(' ').map(Number);
let studentNum = [];
for(let i=2; i<input.length; i++) {
studentNum.push(input[i].split(' ').map(Number))
}
let dp = new Array(n).fill(0);
for(let i=0; i<score.length; i++) {
let sliceArr = score.slice(0, i+1);
dp[i] = sliceArr.reduce( (acc, cur) => acc+=cur, 0 )
}
for(let num of studentNum) {
let startNum = num[0]-2;
let endNum = num[1]-1;
let divNum = startNum === -1 ? num[1] : num[1] - num[0] + 1;
let sum = startNum !== -1 ? dp[endNum] - dp[startNum] : dp[endNum];
console.log((sum/divNum).toFixed(2))
}
}
solution();
3. DP 사용 (점화식)
- dp[0] = score[0] 을 통해 점화식의 초기틀 마련
- 그 후 for문을 통해 dp[i] = dp[i-1] + score[i]
DP의 전 거와 현재 자신의 거를 더하면서 DP 배열을 완성
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, k] = input[0].split(' ').map(Number);
const score = input[1].split(' ').map(Number);
let studentNum = [];
for(let i=2; i<input.length; i++) {
studentNum.push(input[i].split(' ').map(Number))
}
let dp = new Array(n).fill(0);
dp[0] = score[0]
for(let i=1; i<score.length; i++) dp[i] = dp[i-1] + score[i];
for(let num of studentNum) {
let startNum = num[0]-2;
let endNum = num[1]-1;
let divNum = startNum === -1 ? num[1] : num[1] - num[0] + 1;
let sum = startNum !== -1 ? dp[endNum] - dp[startNum] : dp[endNum];
console.log((sum/divNum).toFixed(2))
}
}
solution();
최종 정리 코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, k] = input[0].split(' ').map(Number);
const score = input[1].split(' ').map(Number);
let studentNum = [];
for(let i=2; i<input.length; i++) {
studentNum.push(input[i].split(' ').map(Number))
}
let dp = new Array(n).fill(0);
dp[0] = score[0]
for(let i=1; i<score.length; i++) dp[i] = dp[i-1] + score[i];
for(let [start, end] of studentNum) {
let startNum = start-2;
let endNum = end-1;
let divNum = startNum === -1 ? end : end - start + 1;
let sum = startNum !== -1 ? dp[endNum] - dp[startNum] : dp[endNum];
console.log((sum/divNum).toFixed(2))
}
}
solution();
(Lv.3) 나무 조경
여기에서 배운점 (문법정리)
배열 평면화 flat
배열.flat()
const nestedArray = [1, 2, [3, 4, [5, 6]]];
const flatArray = nestedArray.flat(); // 깊이 1로 평면화
console.log(flatArray); // [1, 2, 3, 4, [5, 6]]
만약 3차원에서 1차원으로 2차원정도를 뺴고싶으면
const nestedArray = [1, 2, [3, 4, [5, 6]]];
const flatArray = nestedArray.flat(2); // 깊이 2로 평면화
console.log(flatArray); // [1, 2, 3, 4, 5, 6]
★ BFS 중 가장 큰 값으로 이동하는 방법
maxValue생성 후 상우하좌 4반복문과 같은 레벨에서 큰값을 찾아서 넣어주면 됨
while(queue.length) {
const [x, y] = queue.shift();
let maxValue = -1;
let nextPos = null;
// 상우하좌 중 가장 큰 값을 찾기
for(let k=0; k<4; k++) {
let nx = x + dx[k];
let ny = y + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
if (maps[nx][ny] > maxValue) {
maxValue = maps[nx][ny];
nextPos = [nx, ny];
}
}
}
// 가장 큰 값이 있는 방향으로 이동
if (nextPos) {
let [nx, ny] = nextPos;
visited[nx][ny] = true;
queue.push([nx, ny]);
ans += maps[nx][ny];
maps[nx][ny] = 0;
max = desNum.shift();
}
}
가능한 모든 조합을 확인해야할 떄
BFS -> 동시라서 X
DFS -> 백트래킹을 하며 최적의 값을 찾음 (모든경로)
풀이
얘는 모든 짝을 탐색하는 경우기 때문에 두 짝에 대한 visiteed의 변경이 필요함
dfs 시작시에 (2차원)
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (!visited[i][j]) { const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const n = parseInt(input[0]);
let maps = [];
for(let i = 1; i < input.length; i++) maps.push(input[i].split(' ').map(Number));
let visited = [];
for(let i=0; i<n; i++) visited.push(new Array(n).fill(false))
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
let maxBeauty = 0;
// BFS가 아니라 DFS (가능한 4쌍의 모든 조합을 찾는 것이라)
function dfs(pairCnt, beautySum) {
// 종료 조건
if (pairCnt === 4) {
maxBeauty = Math.max(maxBeauty, beautySum);
return;
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (!visited[i][j]) {
for (let k = 0; k < 4; k++) {
let nx = i + dx[k];
let ny = j + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
// 현재 위치 및 짝을 방문 처리
visited[i][j] = true;
visited[nx][ny] = true;
// 아름다움 갱신 후 DFS 진행
dfs(pairCnt + 1, beautySum + maps[i][j] + maps[nx][ny]);
// 백트래킹 (되돌리기)
visited[i][j] = false;
visited[nx][ny] = false;
}
}
}
}
}
// 모든 경우에서 maxBeauty 비교용 생성
maxBeauty = Math.max(maxBeauty, beautySum);
}
dfs(0, 0);
console.log(maxBeauty);
}
solution();
나중에 보니 가장 전형적인 dfs문제
pairCnt의 값이 특정 되어 있고 그게 4가 되면 종료하는 것뿐만 아니라
백트래킹을 통해 모든 경우를 따질 수 있기 떄문
무엇보다 beautySum을 통해 가장 최대값을 비교하면서
모든 경우 중에 큰 값을 return하게 됨
잊지 말아야할 점
flat, 경로이동이어도 특정 조건 + 모든 경우를 탐색해야할 땐 dfs가 활용됨
dx ,dy 쓴다고 무조건 bfs가 아니라 dfs는 stack이라는 장점 (백트래킹)을 통해 모든 경로를 다 탐색할 수 있음
(Lv.3) 순서대로 방문하기
이 문제는 경유지가 존재하는 dfs문제
출발점이 경유지의 첫번째가 되고 벽도 존재를 함
여기에서 배운점
-
DFS는 visited를 통해 백트래킹을 진행 함
-
처음부터 맵의 전부를 스캔하는 것이 아닌 특정 시작점이 존재하기 때문에 이중포문은 사용하지 않아도 됨
-
경유지에 도착 했을 때 다음 경유지를 목표로 한번 더 dfs
풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, m] = input[0].split(' ').map(Number);
let maps = [];
for(let i=1; i<n+1; i++) maps.push(input[i].split(' ').map(Number));
const pointPos = [];
for(let i = n+1; i < input.length; i++) {
const [x, y] = input[i].split(' ').map(Number);
pointPos.push([x-1,y-1])
}
let visited = [];
for(let i=0; i<n; i++) visited.push(new Array(n).fill(false))
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
let cnt = 0;
// dfs로 순회하는데 무조건 지정 포인트를 거쳐 마지막에 도달해야만함
function dfs(x, y, pointIndex) {
if (pointIndex === pointPos.length) {
cnt++;
return;
}
const [targetX, targetY] = pointPos[pointIndex];
// 들린 곳이 중간 경유지와 동일하다면 다음 경유지를 목표로 dfs 실행
// 얘가 더 아래 있기 때문에 길이가 되면 자동으로 종료
if(x === targetX && y === targetY) {
dfs(x, y, pointIndex+1)
return
}
for(let i=0; i<4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && maps[nx][ny] !== 1) {
visited[nx][ny] = true;
dfs(nx, ny, pointIndex);
visited[nx][ny] = false; // 백트래킹
}
}
}
const [startX, startY] = pointPos[0];
visited[startX][startY] = true;
dfs(startX, startY, 1)
console.log(cnt)
}
solution();(Lv.3) 루돌프 월드컵
승패를 따지며 모두 탐색하는 완전 탐색 (브루쓰 포쓰) 혹은 dfs문제
하지만 수학이 약한 나에겐 쉽지만은 않았던 것 같다
보다보면 이해가 되긴 하지만 승률을 곱해주고 하는 것이 이해가 잘되지않음
풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);
function solution() {
const forces = input; // 루돌프들의 힘
let winCount = 0; // 1번 루돌프가 2등 이상인 경우 카운트
const totalGames = 3 ** 6; // 6경기, 각 경기마다 3가지 경우의 수(승/무/패)
// 루돌프들 간의 모든 경기 조합 (순서 고려 X)
const matches = [];
for (let i = 0; i < 4; i++) {
for (let j = i + 1; j < 4; j++) {
matches.push([i, j]);
}
}
function dfs(curIndex, scores, probability) {
// 모든 경기 진행 후, 1번 루돌프가 2등 안에 들었는지 판별
if (curIndex === matches.length) {
// 점수 기준으로 정렬 (점수 내림차순, 동점 시 번호 작은 루돌프 우선)
const sorted = scores.map((score, index) => ({ index, score }))
.sort((a, b) => b.score - a.score || a.index - b.index);
// 1번 루돌프(인덱스 0)가 상위 2등 안에 있는 경우만 카운트
if (sorted[0].index === 0 || sorted[1].index === 0) {
winCount += probability;
}
return;
}
// 현재 경기 중인 루돌프
const [i, j] = matches[curIndex];
const Fi = forces[i];
const Fj = forces[j];
// 승리, 패배, 무승부 확률 계산
const P_i = (4 * Fi) / (5 * Fi + 5 * Fj);
const P_j = (4 * Fj) / (5 * Fi + 5 * Fj);
const P_draw = (Fi + Fj) / (5 * Fi + 5 * Fj);
// 승리 시
scores[i] += 3;
dfs(curIndex + 1, scores, probability * P_i);
scores[i] -= 3;
// 패배 시
scores[j] += 3;
dfs(curIndex + 1, scores, probability * P_j);
scores[j] -= 3;
// 무승부 시
scores[i] += 1;
scores[j] += 1;
dfs(curIndex + 1, scores, probability * P_draw);
scores[i] -= 1;
scores[j] -= 1;
}
// DFS 탐색 시작 (초기 확률 1)
dfs(0, new Array(4).fill(0), 1);
// 확률(%) 계산 후 출력
console.log((winCount * 100).toFixed(3));
}
solution();
(Lv.3) 스마트 물류
생각보다는 쉬웠던 문제인데 레벨에 걸맞게 따로 투포인터라는 그리디 접근 방식을 활용했어야만 했음
풀이
아래는 내코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
function solution() {
const [n, k] = input[0].split(' ').map(Number);
let lines = input[1].split('')
let cnt = 0;
// 이중 배열
for(let i=0; i<n; i++) {
for(let j=i-k; j<=i+k; j++) {
if (lines[i] === 'P' && lines[j] === 'H') {
lines[i] = 0;
lines[j] = 0;
cnt++
}
}
}
console.log(cnt)
}
solution()
진짜 풀이
위치를 리스트들에 저장한다음에 위치들의 차이가 k 이내라면
둘의 인덱스를 올려주고 cnt값을 증가시킴
여기에서 만약 위치가 맞지 않아 매칭이 불가하면
다음 로봇이나 다음 부품으로 이동
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
function solution() {
const [n, k] = input[0].split(' ').map(Number);
const lines = input[1].split('');
let robots = [];
let parts = [];
// 1. 로봇(P)과 부품(H)의 위치를 리스트에 저장
for (let i = 0; i < n; i++) {
if (lines[i] === 'P') robots.push(i);
else if (lines[i] === 'H') parts.push(i);
}
let r = 0, p = 0, cnt = 0;
// 2. 투 포인터 방식으로 매칭
while (r < robots.length && p < parts.length) {
if (Math.abs(robots[r] - parts[p]) <= k) {
cnt++;
r++; // 현재 로봇 사용
p++; // 현재 부품 사용
} else if (robots[r] < parts[p]) {
r++; // 로봇이 더 왼쪽이면 오른쪽으로 이동
} else {
p++; // 부품이 더 왼쪽이면 오른쪽으로 이동
}
}
console.log(cnt);
}
solution();(Lv.3) 우물 안 개구리
map을 통해 접근하면서 푸니까 풀만했었음
이 문제에서 배운점
Map 관계정리
for(let i=0; i<relation.length; i++) {
const key = relation[i][0];
const value = relation[i][1]
maps.get(key) ? maps.get(key).push(value) : maps.set(key, [value])
maps.get(value) ? maps.get(value).push(key) : maps.set(value, [key])
}
난 위와 같은 식으로 삼항연산자를 통해 map에 set을 해주었는데 그게 아니라
for(let i=0; i<relation.length; i++) {
const key = relation[i][0];
const value = relation[i][1];
if (!maps.has(key)) maps.set(key, []);
if (!maps.has(value)) maps.set(value, []);
maps.get(key).push(value);
maps.get(value).push(key);
}
위와 같은 식으로 갖고 있지 안흐면 빈배열 있으면 추가 해주면 됨풀이
// 두 관계에서 둘 중에 한 명이 아예 크면 최고
// 한사람이 여러 관계를 가지고 있으면 모든 관계에서 자기가 제일 최고여야함
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, m] = input[0].split(' ').map(Number);
const weight = input[1].split(' ').map(Number);
const relation = [];
for(let i=2; i < input.length; i++) {
relation.push(input[i].split(' ').map(Number))
}
const maps = new Map();
for(let i=0; i<relation.length; i++) {
const key = relation[i][0];
const value = relation[i][1]
maps.get(key) ? maps.get(key).push(value) : maps.set(key, [value])
maps.get(value) ? maps.get(value).push(key) : maps.set(value, [key])
}
let cnt = 0;
for(let i=0; i < maps.size; i++) {
if (!maps.has(i+1)) { // 관계가 없는 노드는 항상 최고로 간주
cnt++;
continue;
}
for (let j=0; j < maps.get(i+1).length; j++) {
const keyWeight = weight[i];
const valueWeight = weight[maps.get(i+1)[j]-1];
if (keyWeight > valueWeight) cnt++
}
}
console.log(cnt)
}
solution()위 코드는 아무래도 런타임 에러가 발생
GPT 수정 코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, m] = input[0].split(' ').map(Number);
const weight = input[1].split(' ').map(Number);
const relation = [];
for(let i=2; i < input.length; i++) {
relation.push(input[i].split(' ').map(Number))
}
const maps = new Map();
for(let i=0; i<relation.length; i++) {
const key = relation[i][0];
const value = relation[i][1];
if (!maps.has(key)) maps.set(key, []);
if (!maps.has(value)) maps.set(value, []);
maps.get(key).push(value);
maps.get(value).push(key);
}
let cnt = 0;
for (let i=0; i < n; i++) {
if (!maps.has(i+1)) { // 관계가 없는 노드는 항상 최고로 간주
cnt++;
continue;
}
let isHighest = true;
for (let j=0; j < maps.get(i+1).length; j++) {
const neighbor = maps.get(i+1)[j];
if (weight[i] <= weight[neighbor - 1]) {
isHighest = false;
break;
}
}
if (isHighest) cnt++;
}
console.log(cnt);
}
solution();
방법은 비슷하지만
- 관계를 정립할 때 if문을 사용해서 빈배열도 포함시켜 주는 것
- 내가 빠트렸던 관계가 없는 노드는 항상 최고로 간주하는 것
- isHighest를 통해 우선 i가 가장 큰 값으로 두고 i의 value들이 더 크다면 그떄 isHighest를 해주어서 그 친구는 선택하지 않음
- 나는 관계들을 양방향으로 정립 해주었기 떄문에 전체적인 for문을 돌아도 되는 것
(Lv.3) 강의실 배정
그리디의 대표격인 문제
소팅하고 나서 접근하는 방법은 굉장히 쉬웠음
풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
// 대표적인 그리디 문제
function solution() {
const n = parseInt(input[0]);
const times = [];
for(let i=1; i<input.length; i++) times.push(input[i].split(' ').map(Number));
times.sort( (a, b) => a[1] - b[1]);
let stack = [times[0][1]];
for(let i=1; i < times.length; i++) {
const lastIndex = stack.pop();
if(lastIndex <= times[i][0]) {
stack.push(lastIndex);
stack.push(times[i][1])
}
else stack.push(lastIndex);
}
console.log(stack.length)
}
solution()최적화 코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
function solution() {
const n = parseInt(input[0]);
const times = [];
for (let i = 1; i <= n; i++) {
times.push(input[i].split(' ').map(Number));
}
// 끝나는 시간을 기준으로 정렬
times.sort((a, b) => a[1] - b[1]);
let count = 0;
let lastEndTime = 0; // 마지막 회의 종료 시간
for (let i = 0; i < times.length; i++) {
// 현재 회의 시작 시간이 마지막 회의 종료 시간보다 크거나 같으면
if (times[i][0] >= lastEndTime) {
count++;
lastEndTime = times[i][1]; // 현재 회의의 종료 시간으로 업데이트
}
}
console.log(count);
}
solution();
굳이 stack에 넣고 빼고가 아니라 그냥 값을 담아 뒀다가 비교해주면 됨
(Lv.3) 동계 테스트 시점 예측
최근 중에 가장 어려웠던 문제 문제를 풀고 이해하는데도 많은 시간이 걸렸음
이 문제에서 배운점
접촉면 계산시 역순으로 접근
- 오히려 얼음에서 따지는 게 아니라 공기, 얼음을 나누어 얘네가 진짜 가장 밖인지 확인 해줘야함
모든 얼음이 사라질 때
모든 얼음이 사라진다라는 조건이 있으므로 무한루프를 통해 없어질 때까지 반복을 해줘야함
풀이
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
function solution() {
const [n, m] = input[0].split(" ").map(Number);
let maps = [];
for(let i=1; i<input.length; i++) maps.push(input[i].split(' ').map(Number));
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
let queue = [];
let cnt = 0;
/**
* 🔹 BFS를 사용해 외부 공기를 탐색하고, 녹을 얼음을 찾는 함수
*/
function bfs() {
// BFS 탐색을 위한 큐 (초기값: (0,0) 위치부터 탐색 시작)
queue.push([0, 0])
let visited = [];
for(let i=0; i<n; i++) visited.push(new Array(m).fill(0));
// (0,0)은 항상 외부 공기이므로 방문 처리
visited[0][0] = -1;
while (queue.length) {
const [x, y] = queue.shift();
for (let i = 0; i < 4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
// [얼음일 때]
if (maps[nx][ny] === 1) {
// 현재 탐색 중인 얼음이 공기와 맞닿은 횟수를 증가 (나중에 2면 지우게)
visited[nx][ny] += 1;
} else if (maps[nx][ny] === 0 && !visited[nx][ny]) {
// [공기일 때]
// 방문 표시 후 큐에 추가 (근처도 탐색 - BFS 확장)
visited[nx][ny] -= 1;
queue.push([nx, ny]);
}
}
}
}
// 🔹 2변 이상 외부 공기와 맞닿은 얼음들을 녹임
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
// 얼음이 2변 이상 공기와 닿으면 녹음
if (visited[i][j] >= 2) {
maps[i][j] = 0;
}
}
}
}
/**
* 모든 얼음이 녹을 때까지 반복
*/
function checkAllMelted() {
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (maps[i][j] === 1) return false; // 아직 녹지 않은 얼음이 있으면 false 반환
}
}
return true;
}
while (true) {
if (checkAllMelted()) break;
// if문 통과 못하면 (얼음 남아있으면 다시 한번 더)
cnt += 1;
bfs();
}
console.log(cnt);
}
solution();
- 평소와 같이 bfs로 접근을 함
- 한 가지 특이한 것은 "모든 얼음이 사라질 때"까지이므로 visited를 bfs 안에서 수행을 해줘야함
- 물론 함수가 아니라
while(true)안에 넣어줘도 됨 - 여기에서 visited를 false로 하는 것이 아닌
숫자 (-1)로 해주어서 2가 됐을 때 걔네를 지워줄 수 있도록 함 - 그 후 동작을 하는데 여기에서 2가지로 나뉨 1. 얼음일 때, 2. 공기일 때
- while문의 마지막에 두 변이상이 공기와 맞닿았을 떄 얼음들을 녹임
- chieckAllMelted란 함수를 사용해서 무한루프 속에 cnt값을 증가시킴
기록, 꺼내 쓸 수 있는 즐거움