Remind
🍑 Stack 브라우저 뒤로가기, 앞으로가기
🍑 Graph 인접행렬 생성하기
자료구조 문제를 복기해보도록 하겠다.
🍑 Stack
문제
현재 브라우저를 기준으로 뒤로가기 버튼을 누를때마다
뒤로가기 스택에 순차적으로 현재의 값들이 쌓인다.
🍎 보면서 이해하기
현재 브라우저 : 네이버
뒤로가기에 쌓인 stacks : [ "chrome://newtab" , "Google" ]
앞으로가기 버튼에 쌓인 stacks : [ 없음 ]
이상태에서 뒤로가기 버튼을 누른다면?
현재 브라우저 : 구글
뒤로가기에 쌓인 stack : ["chrome://newtab" ]
앞으로가기 버튼에 쌓인 stacks : [ "NAVER" ]
이상태에서 뒤로가기 버튼을 한번 더 누르면?
현재 브라우저 : "chrome://newtab"
뒤로가기에 쌓인 stack : [ 없음 ]
앞으로가기 버튼에 쌓인 stacks : [ "Google", "NAVER" ]
이상태에서 새로운창, 핀터레스트에 들어가면
현재 브라우저 : 핀터레스트
뒤로가기에 쌓인 stack : ["chrome://newtab"]
앞으로가기 버튼에 쌓인 stack : [ 없음 ]
이렇듯, 우리가 실생활에서 브라우저를 다룰때 이뤄지는 일들은 모두
stack 구조를 따르고 있었다.
🍎 코드로 작성하기
function browserStack(actions, start) {
// let actions = ["B", "C", -1, "D", "A", -1, 1, -1, -1];
// let start = "A";
let prev = [];
let cur = start;
let next = [];
for(let el of actions){
//새로운 페이지일때 : actions 의 el 번째요소가 알파벳일때 현재페이지가된다.
if(typeof el === 'string'){
prev.push(cur);
cur = el;
next = next.slice(next.length);
}
//prev 버튼 누를때 : actions의 el 번째가 -1일때
//prev의 값이 0이면(<-버튼이 invalid) 더이상 뒤로 갈 수 없다.
else if(el === -1 && prev.length !== 0){
next.push(cur)
cur = prev.pop();
}
//next 버튼 누를때 : actions의 el 번째 요소가 1일때
//next 값이 0이면(->버튼이 invalid) 더이상 앞으로 갈 수 없다.
else if(el === 1 && next.length !== 0){
prev.push(cur);
cur = next.pop();
}
}
return [prev,cur,next]
}🍑 Graph
문제
그래프 인접행렬 생성하기.
방향이 있는 간선과 방향이 없는 간선들의 목록들을 받아 2차원 배열의 인접행렬을 반환하는 함수를 작성하세요.
인자 : edges
Number 타입의 방향/무향인 간선들의 목록이 담긴 배열
edges = [
[0, 3, "directed"],
[0, 2, "directed"],
[1, 3, "directed"],
[2, 1, "directed"]
] 또는
[
[0, 2, "directed"],
[2, 4, "undirected"],
[1, 3, "undirected"],
[2, 1, "directed"]
]
의 형태.
인접행렬에는 direct(방향), undirect(무향) 두가지 방향이 존재한다고 이전 블로그에 작성한 적 있다.
간단히 말하자면 각각 편도, 왕복의 개념이다.
각 정점을 이어주는 이 선들을 간선이라고 하며, 간선이 있을때는 1표시, 없을땐 0 표시를 하며 인접행렬을 생성해보겠다.
🍎 보면서 이해하기
주어진 값 :
[0, 3, "directed"],
[0, 2, "directed"],
[1, 3, "directed"],
[2, 1, "directed"],
// 각 정점에 따른 인접행렬 결과
[
[0, 0, 1, 1],
[0, 0, 0, 1],
[0, 1, 0, 0],
[0, 0, 0, 0]
]처음엔 이게뭐지 .. 하고 이해가 가지 않았지만 찬찬히 뜯어보면 이런뜻이다.
[0, 3, "directed"] => 0과 3을 편도로 이어준곳에 간선추가
[0, 2, "directed"] => 0과 2를 편도로 이어준곳에 간선추가
[1, 3, "directed"] => 1과 3을 편도로 이어준곳에 간선추가
[2, 1, "directed"] => 2와 1을 편도로 이어준곳에 간선추가
여기서의 간선추가라 함은, 온통 0천지인 배열에 1을 더해준다는 뜻이다.
( 문제에 따라서 true/false 로 지정할수도 있지만 여기서는 0,1로 나눴다.)
즉, 우리가 해야할 것은
1. 주어진 값에서 가장 큰 수 고르기
=> 인접행렬은 주어진값에서 제일 큰 숫자만큼 행/열 로 이루어지기 때문에
그 가장 큰 수를 기준으로 2차원 배열을 생성해야 한다.
2. 빈 매트릭스 배열에 가장 큰 수만큼 배열을 생성을 하고 모두 0으로 채운다.
=> 0으로 전부 채워진 매트릭스에 간선이 있는곳만 1로 바꾸기 위함.
3. directed 와 undirected 에 따라 매트릭스배열 1로 변경하기
🍎 코드로 작성하기
function createMatrix(edges) {
// 방향이 있는 간선, 방향이 없는 간선들의 목록 : edges
// 2차원 배열의 인접행렬 반환함수 : matrix [[],[],[]]
// 1. edges 에서 가장 큰 숫자를 찾는다.
let flatArr = edges.flat().filter((el)=>typeof el === 'number')
let bigNum = Math.max(...flatArr);
// 2. bigNum 만큼 반복해서 만든 매트릭스에 0을 채운다.
let matrix = []
for(let i=0; i<=bigNum; i++){
matrix.push(new Array(bigNum+1).fill(0))
}
// 각 0으로 채워진 매트릭스를 edges 의 기준에 맞게 1로 바꾼다.
for(let el of edges){
if(el[2] === 'directed'){
matrix[el[0]][el[1]] = 1
}else if(el[2] === 'undirected'){
matrix[el[0]][el[1]]=1
matrix[el[1]][el[0]] =1
}
}
return matrix
}
