알고리즘 스터디 1주차. 스택/큐
stack
선입 후출 (LIFO)
마지막에 들어온 데이터가 먼저 나가는 자료구조
js에서의 stack 메서드
데이터 추가: push
데이터 삭제: pop
연결리스트로 stack 구현
class Node {
constructor(data) {
this.data = data;
this.prev = null;
}
}
class Stack {
constructor() {
this.top = null;
this.length = 0;
}
push(data) {
const newNode = new Node(data);
if (this.length === 0) {
this.top = newNode;
} else {
const preNode = this.top;
this.top = newNode;
this.top.prev = preNode;
}
this.length++;
}
peek() {
this.length && console.log(this.top.data);
}
pop() {
if (this.length === 0) {
console.error("stack is empty");
} else {
this.top = this.top.prev;
}
this.length--;
}
}
const stack = new Stack();
stack.push(1);
stack.peek();
stack.push(2);
stack.peek();
stack.push(3);
stack.peek();
stack.pop();
stack.pop();
stack.pop();
stack.peek();
stack 활용 예시
- 웹페이지 상에서 뒤로가기
- 실행 취소
- array.reverse()
- 괄호 검사
- 후위 표기법 계산
프로세스와 스택
프로세스
실행중인 프로그램
스레드
프로세스의 실행 단위
프로세스의 메모리 영역은 4부분으로 나뉜다.
- 텍스트: 프로그램 코드가 저장되어있음
- 데이터: 전역 변수, static 변수 등 저장되어있음
- 스택: 지역변수, 매개변수, 반환값, 함수 복귀주소 등 저장됨(임시 데이터들) / 가변적
- 힙: 런타임에 할당되는 영역 / 가변적
프로세스 내부의 스레드는 code, data, heap 영역을 공유하고 stack 영역을 독립적으로 갖는다.
stack을 통해 각 스레드가 독립적인 실행 흐름을 가능하게 한다.
스레드간의 텍스트 영역 공유를 통해 함수 호출을 가능하게 한다.
스레드간의 데이터, 힙 영역 공유를 통해 메로리 공간을 공유하며 스레드간 통신을 가능하게 만든다.
queue
선입 후출 (FIFO)
처음으로 들어온 데이터가 먼저 나가는 자료구조
js에서의 queue 메서드
데이터 추가: push
데이터 삭제: shift
연결리스트로 queue 구현
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Queue {
constructor() {
this.top = null;
this.bottom = null;
this.length = 0;
}
push(data) {
const newNode = new Node(data);
if (this.length === 0) {
this.top = newNode;
this.bottom = newNode;
} else {
const preNode = this.top;
this.top = newNode;
preNode.next = newNode;
}
this.length++;
}
peek() {
this.length > 0 && console.log(this.top.data);
}
shift() {
if (this.length === 0) {
console.error("stack is empty");
} else {
this.bottom = this.bottom.next;
}
this.length--;
}
}
const queue = new Queue();
queue.push(1);
queue.peek();
queue.push(2);
queue.peek();
queue.push(3);
queue.peek();
queue.shift();
queue.shift();
queue.shift();
queue.shift();
queue.peek();
queue 활용 예시
- 프린터 인쇄 대겨얼
- 프로세스 관리
- 캐시 구현
- BFS(너비 우선 탐색)
queue와 프로세스
CPU는 프로세스를 관리하며, CPU를 각 프로세스에게 적절히 할당하는 임무를 가지고 있다.
한정된 메모리를 여러 프로세스가 효울적으로 사용할 수 있도록 다음 실행 시간에 실행할 수 있는 프로세스를 선택할 필요가 있는데 이는 스케줄링 기법을 통해 선택한다.
- Job Queue: 하드디스크에 있는 프로그램이 실행되기 위해 메인 메모리의 할당 순서를 기다리는 공간
- Ready Queue: CPU 점유 순서를 기다리는 공간
- Device Queue: I/O와 관련된 장치들을 기다리는 공간
문제
https://programmers.co.kr/learn/courses/30/lessons/77485
접근
직사각형 테두리에 있는 숫자들을 따로 저장시킨 뒤, 맨 앞의 수를 뒤로 보낸 후, 다시 배열에 넣어주면 될 것 같다.
문제풀이
1. rows, columns에 맞는 배열 생성
const arr = Array.from(Array(rows), (_,i) => Array.from(Array(columns),(_,j)=>i*columns+j+1))
2. query에 맞춰 직사각형 테두리 값들을 순차적으로 stack에 저장
const stack = [];
for(let i=y1;i<y2;i++) stack.push(arr[x1][i]);
for(let i=x1;i<x2;i++) stack.push(arr[i][y2]);
for(let i=y2;i>y1;i--) stack.push(arr[x2][i]);
for(let i=x2;i>x1;i--) stack.push(arr[i][y1]);
3. 저장된 stack에서 가장 작은 값을 result에 push
answer.push(Math.min(...stack))
4. stack의 맨 앞 값을 맨 뒤로 보냄
stack.unshift(stack.pop())
5. 배열 내부의 직사각형 테두리에 stack 값을 순차적으로 저장
for(let i=y1;i<y2;i++) arr[x1][i] = stack.shift();
for(let i=x1;i<x2;i++) arr[i][y2] = stack.shift();
for(let i=y2;i>y1;i--) arr[x2][i] = stack.shift();
for(let i=x2;i>x1;i--) arr[i][y1] = stack.shift();
전체 코드
function solution(rows, columns, queries) {
const answer = []
const arr = Array.from(Array(rows), (_,i) => Array.from(Array(columns),(_,j)=>i*columns+j+1))
console.log(arr)
queries.map(query=>{
const [x1,y1,x2,y2] = [query[0]-1,query[1]-1,query[2]-1,query[3]-1]
const stack = [];
for(let i=y1;i<y2;i++) stack.push(arr[x1][i]);
for(let i=x1;i<x2;i++) stack.push(arr[i][y2]);
for(let i=y2;i>y1;i--) stack.push(arr[x2][i]);
for(let i=x2;i>x1;i--) stack.push(arr[i][y1]);
answer.push(Math.min(...stack))
stack.unshift(stack.pop())
for(let i=y1;i<y2;i++) arr[x1][i] = stack.shift();
for(let i=x1;i<x2;i++) arr[i][y2] = stack.shift();
for(let i=y2;i>y1;i--) arr[x2][i] = stack.shift();
for(let i=x2;i>x1;i--) arr[i][y1] = stack.shift();
})
return answer;
}
Author And Source
이 문제에 관하여(알고리즘 스터디 1주차. 스택/큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wkahd01/알고리즘-스터디-1주차.-스택큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)