2206번 벽 부수고 이동하기와 매우 유사한 0-1bfs, 데이크스트라 문제이다.

두가지 해결법이 있는데,

0-1bfs로 접근한다면

dist배열에는 2차원 배열에서 해당 좌표까지 도착했을 때 벽을 부순 횟수를 기록하고

벽을 부순 횟수가 더 적을 때 deque에 삽입한다

우리는 최대한 벽을 부수지 않으면서 멀리 갈 수 있어야 한다.

때문에 벽을 부수지 않고 전진하는 경우 deque의 front에 삽입하고

벽을 부수는 경우 deque의 back에 삽입한다.

하지만 이건 내가 데이크스트라를 통해 문제를 해결한 이후에 본 풀이법이다.

데이크스트라로 접근하는 것이 더 이해가 쉬울 수 있다.

기존 데이크스트라는 탐색 시점 최단 거리의 노드를 queue에 넣고, 

방문한 노드 기준으로 다시 연결된 노드의 최단거리를 갱신시켜 주는데

이 문제에서는 기준을 최단거리가 아닌 벽을 부순 횟수로 바꾸면 된다.

const readline = require('readline');
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout
})

const input = [];
rl.on('line', (line)=>{
	input.push(line);
}).on('close', ()=>{

	const [m,n] = input[0].split(' ').map(Number);

	const map = Array.from(Array(n), () => Array(m).fill(0));

	for(let i = 0; i < n; i++){
		const arr = input[i+1].split('').map(Number);
		for(let j = 0; j < m; j++)
			map[i][j] = arr[j];
	}

	const dist = Array.from(Array(n), () => Array(m).fill(Infinity));
	const bfs = () => {
		const q = [];
		q.push([0,0,0]);

		while(q.length > 0){
			const [y_,x_,v] = q.shift();

			const a = [1,-1,0,0];
			const b = [0,0,-1,1];

			for(let i = 0; i < 4; i++){
				const y = y_ + a[i];
				const x = x_ + b[i];
				if(x >= 0 && x < m && y >= 0 && y < n){
					if(map[y][x] === 0 && dist[y][x] > v){
						dist[y][x] = v;
						q.push([y,x,v]);
					}
					else if (map[y][x] === 1 && dist[y][x] > v + 1){
						dist[y][x] = v + 1;
						q.push([y,x,v+1]);
					}
				}
			}
		}
	}

	bfs();
	if(dist[n-1][m-1] === Infinity)
		console.log(0)
	else
		console.log(dist[n-1][m-1]);

})

이 문제는 사실 정석으로 접근했다면 풀지 못했을 것이다. 운영체제 내용과 관련이 있는 흥미로운 문제이다.

스케쥴링은 필요한 자원을 적절히 할당하여 효율적으로 리소스를 활용하는 것이다.

페이징 기법

프로세스가 사용하는 메모리 공간을 잘게 나누어 비연속적으로 사용하는 기법이다.

프로세스 적재를 위해 연속된 메모리를 요구하지 않기 때문에 한정된 메모리 공간을 효율적으로 사용할 수 있다.

가상 메모리 공간의 단위를 page, 물리 메모리 공간을 frame 이라고 하고 둘의 크기는 같다.

하지만 물리 메모리는 한정적이기 때문에, 운영체제는 물리 메모리와 보조 저장공간의 swap 공간을 함께 활용하게 되는데,

이 때 참조한 페이지가 물리 메모리에 올라가 있지 않을 때(invalid) 참조하는 페이지를 교체해서 새롭게 물리 메모리에 적재해야 한다.

여기서 사용하는 것이 페이지 교체 알고리즘이다

페이지 교체 알고리즘 (Page Replacement Algorithm)

페이지 교체 알고리즘에는 여러가지가 있다.

FIFO - 가장 먼저 메모리에 올라온 페이지를 교체한다

LRU - 가장 오랫동안 사용되지 않은 페이지를 교체한다

그 중에서 OPT(Optimal) 알고리즘이 있다.

이름부터가 Optimal..

OPT(Optimal) 알고리즘

페이지를 교체 하려는 시점에서, 이후에 페이지가 참조될 시점이 가장 늦은 페이지를 교체한다.

즉 가장 오랫동안 사용되지 않을 페이지를 교체하는 것이다

그림으로 봤을 때, 첫번째 교체 시점에서 1이 가장 나중에 참조되기 때문에 1을 3으로 교체하고

4를 교체해야 하는 시점에서 뒤에 바로 나오는 2,3을 고려해 0을 교체한다.

다시 0을 교체해야 할 때는 이후 4는 참조되지 않기 때문에 4와 0 을 교체한다.

이는 가장 적은 page fault를 보장하는 최적화 알고리즘이다.

하지만 실제로는 운영체제 입장에서 앞으로 사용할 페이지를 알아야 하기 때문에 구현하기 어렵다. 

그러나,

이 문제에서는 용품의 사용 순서가 주어지기 때문에 우리는 미래를 알고있다.

가장 적은 교체, 가장 적은 페이지 부재를 보장하는 Optimal을 적용해서

교체가 필요한 시점을 기준으로 가장 늦게 사용하는 용품을 교체해주면 되겠다.

그래서 이 관련없어 보이는 얘기를 한 것이다.

운영체제 내용으로 조금 야매로 풀었지만 그래서 오히려 재밌는 문제다.

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];

rl.on('line', function (line) {
  input.push(line);
}).on('close', function () {

	const [n,k] = input[0].split(' ').map(Number);

	const con = Array(n).fill(0);
	const arr = Array(k);

	const tmp = input[1].split(' ').map(Number);
	for(let i = 0; i < k; i++)
		arr[i] = tmp[i];

	const find_least = (idx) => {

		let tmp = -Infinity;
		let index;

		for(let i = 0; i < con.length; i++){
			let num = 0;
			for(let j = idx; j < arr.length; j++){
				if(arr[j] !== con[i])
					num++;
				else
					break;
			}
			if (tmp < num) {
					tmp = num;
					index = i;
				}
			}
			return index;
		}

	let answer = 0;
	for(let i = 0; i < k; i++){

		if(con.indexOf(arr[i]) !== -1)
			continue;

		const idx = con.indexOf(0);

		if(idx !== -1)
			con[idx] = arr[i];
		else{
			const index = find_least(i);
			con[index] = arr[i];
			answer += 1;
		}
	}

	console.log(answer);
})

입력 크기에서 힌트를 얻는 편이다.

n이 1000000까지 들어온다는 것은 시간복잡도 O(n)으로 해결해야 1초로 끊을 수 있다는 뜻이다.

그러므로 배열을 선형으로 한번만 순회하면서 해결할 수 있는 방법을 생각해 보는 것이 좋겠다.

배열이 계속 내림차순 이라면 오큰수는 나올 수 없다. 반대로 배열이 오름차순이라면 맨 마지막 수를 제외한 모든 수는 자신의 앞에 수를 오큰수로 가질 것이다.

이를 토대로 생각해보면, 현재 내가 순회하는 숫자를 기준으로 내림 차순이 이어지면 오큰수는 알 수 없고,

나보다 큰 수가 나왔다면, 그 수는 여태 오큰수를 알 수 없던 모든 수의 오큰수 '후보'가 되는 것이다.

이제 해결법을 떠올릴 수 있다. 내림차순이라면 현재 순회하는 수의 정보를(값, 인덱스) 잠시 저장해두고, 오름차순일 때는 저장된 값들 중에서 오큰수의 조건을 만족하는 값들을 갱신해주면 되는 것이다.

여기서 쉽게 떠올릴 수 있는 구조가 바로 스택 이다. 근데 난 문제를 풀 때는 생각이 안났고 최소힙이 생각났다.

최소힙에서 조건에 맞을때마다 요소룰 빼면서 오큰수를 갱신해주면 된다.

스택도 이와 동일하게 생각하면 된다.

const readline = require('readline');
const rl = readline.createInterface({
	input:process.stdin,
	output:process.stdout
})

const input = [];
rl.on('line', (line)=>{
	input.push(line);
}).on('close', () =>{

	const n = Number(input[0]);
	const arr = input[1].split(' ').map(Number);
	const ans = Array(n).fill(0);
	const q = [];


	for(let i = 0; i < n; i++){
		const j = i+1;
		if(j === n)
			break;
		if(arr[j] <= arr[i]){
			q.push([i, arr[i]]);
		}
		else{
			ans[i] = arr[j];
			q.sort((a,b) => a[1] - b[1])
			while(q.length > 0){
				if(q[0][1] < arr[j]){
					ans[q[0][0]] = arr[j];
					q.shift();
				}
				else
					break;
			}

		}
	}

	for(let i = 0; i < ans.length; i++){
		if(ans[i] === 0)
			ans[i] = -1;
	}


	console.log(ans.join(' '));

})

이 코드는 sort연산에서 O(nlogn)이 나오기 때문에 시간초과가 뜬다.

그래서 우선순위 큐를 직접 구현하면 통과가 된다. (코드가 길어서 올리진 않았다) 물론 오래 걸린다. 거의 꼴지 수준이다. 요소를 뺄 때 log(n)이 걸려서 그럴 것이다. 아마 몇없는 우선순위 큐로 통과한 사람중 하나인 것 같다. 그러니까 O(1)의 스택을 사용하도록 하자.

접근법을 알면 쉽게 풀 수 있지만, 당연히도 접근법 생각하는 게 쉽지 않았던 문제이다.

입력으로 주어지는 배열은 트리를 중위순회한 값이라는 걸 알 수 있다. 이것이 매우 중요하다.

중위순회임임을 통해서 적절한 부분 배열로 나누었을 때 (자식 노드) - (부모 노드) - (자식 노드) 의  패턴이 유지된다는 것을 유추해야 한다. 여기가 어렵다.

입력의 인덱스 중앙값은 항상 트리의 루트 노드이다 즉 전체 배열 기준으로 양 부분 배열 사이의 노드가 부모 노드라는 뜻이다.

그리고 부모 노드 기준으로 양쪽 부분배열로 나누었을 때, 그 부분 배열 또한 부모 노드와 자식 노드를 포함하는 서브 트리임을 알 수 있다.

큰 문제를 같은 패턴의 작은 문제로 나눌 수 있고, 서로 독립적이다. 그러므로 재귀를 이용한 풀이를 생각해낼 수 있다.

부모 노드는 항상 부분 배열의 중앙으로 확정이기 때문에, 부모 노드를 해당 높이의 트리(배열)에 넣은 후 이후 부모 노드 기준으로 다시 양쪽 배열로 분할한 후 재귀 함수를 호출한다.

let readline = require("readline");

let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

let input = [];

rl.on("line", (line)=> {
	input.push(line);
}).on("close", () => {

	const k = Number(input[0]);
	const arr = input[1].split(' ').map(Number);

	const ans = Array(k+1);
	for(let i = 0; i <= k; i++)
		ans[i] = '';


	const make = (arr, depth) => {

		if(depth > k || arr.length === 0)
			return;

		const mid = Math.floor(arr.length / 2);
		if(ans[depth].length === 0)
			ans[depth] += arr[mid].toString();
		else
		ans[depth] += ' ' + arr[mid].toString();
		const leftarr = arr.slice(0, mid);
		const rightarr = arr.slice(mid+1, arr.length);

		make(leftarr, depth + 1);
		make(rightarr, depth + 1);
	}

	make(arr, 1);

	console.log(ans.slice(1,ans.length).join('\n'))
})

어렵게 접근해서 조금 헤맸다.

일반적인 dfs 경로 탐색과 유사하지만 '알파벳 순이 빠른 경로' 라는 조건때문에 어렵게 생각했다.

프로그래머스 문제는 명쾌하게 풀리는 편이라고 생각한다. 그러므로 너무 복잡하게 접근하지 않는 편이 좋을 것 같다.

중복 경로(같은 티켓이 또 들어오는 경우)인 케이스와 첫번째 정렬 경로로 모두 방문할 수 없는 경우

이 2가지를 고려하는 게 핵심이다.

function solution(tickets) {
    
    var answer = [];
    
    const map = [];
    const visited = [];
    
    for(let i = 0; i < tickets.length; i++){
        if(map[tickets[i][0]] === undefined){
            map[tickets[i][0]] = [];
            visited[tickets[i][0]] = [];
        }
        map[tickets[i][0]].push(tickets[i][1]);
        visited[tickets[i][0]].push(0);
    }
    
    const dfs = (air, br, k) => {
        
        
        if(k === tickets.length + 1 && answer.length === 0) {
            answer = [...br];
            return;
        }
        
        if(answer.length > 0)
            return;

        const arr = map[air];
        if(arr === undefined)
            return;
        
        arr.sort();
        for(let i = 0; i < arr.length; i++){
            if(visited[air][i] === 0){
                visited[air][i] = 1;
                br[k] = arr[i];
                dfs(arr[i], br, k+1);
                visited[air][i] = 0;
            }
        }
    }

같은 티켓이 또 들어오는 경우가 있기 때문에,

방문때마다 visited를 일반적인 공항이름을 넣거나 하면 같은 티켓을 탐색할 수 없다.

때문에 visited를 map과 동일한 배열을 만들어서 방문 체크를 진행했다.

한 경로에 탐색이 끝나고 해당 경로로 모든 경로를 방문할 수 없을 때를 위해

탐색이 끝나면 visited를 다시 방문하지 않은 것으로 되돌린다.