[TIL]Stack, Queue, Tree, Graph
Achievement Goals
- 자료구조가 무엇인지 설명할 수 있다.
- Stack, Queue, Tree, Graph 자료구조에 대해 이해할 수 있다.
- 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.
- 각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.
- 알고리즘 문제의 각 상황에 맞는 자료구조를 떠올릴 수 있다.
- 트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.
- Binary Search Tree를 이해할 수 있다.
- BFS와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있다.
- 자료구조를 활용하여 알고리즘 문제에 접근할 수 있다.
Stack
- 데이터를 순서대로 쌓는 자료구조
- 먼저 들어온 자료는 가장 나중에 나올 수 있다.
- ex)브라우저 뒤로가기,앞으로 가기
coplit 브라우저 뒤로 가기 앞으로 가기
function browserStack(actions, start) {
let prev=[] //이전 페이지 스택(뒤로가기)
let next=[] //다음 페이지 스택(앞으로가기)
let page=start //현재 페이지
for(let i of actions){
if(i===-1&&prev.length!==0){ //뒤로가기
next.push(page)
page=prev.pop()
}else if(i===1&&next.length!==0){ //앞으로가기
prev.push(page)
page=next.pop()
}else{ //새로운 페이지
prev.push(page)
next=[]
page=i
}
}return([prev,page,next])
}
Queue
- 데이터를 줄 세우는 자료구조
- 먼저 들어온 자료부터 처리
- ex)프린트 인쇄 작업 , Buffer
coplit 프린터
function queuePrinter(bufferSize, capacities, documents) {
let count=0
let queue=[] //인쇄 목록 공간
let total = 0 //인쇄 목록에 들어있는 문서의 총 용량
//목록 크기(칸)만큼 0을 queue에 넣어둔다.
for(let i=0;i<bufferSize;i++){
queue.push(0)
}
//첫번째문서를 인쇄 목록에 넣는 코드
let curDocument=documents.shift()//문서하나를 빼서 현재 문서로 넣는다.
queue.unshift(curDocument)//현재 문서를 인쇄 목록에 넣는다.
queue.pop()//인쇄 목록 끝을 출력 빼낸다.
total=curDocument
count++
//total에 아무것도 안남을때까지 반복
while(total>0){
total-=queue.pop()//인쇄 목록 끝 출력
curDocument=documents.shift()
//인쇄목록에 들어있는 문서의 총 용량이 최대용량보다 작으면 새문서를 인쇄목록에 넣는다.
if(total+curDocument<=capacities){
queue.unshift(curDocument)
total+=curDocument
//용량이 부족한 경우 0값을 인쇄목록에 넣는다.
}else{
documents.unshift(curDocument)//다시 문서에 현재문서를 넣는다.
queue.unshift(0)
}
count++
}
return count
}
Graph
- 여러개의 점들이 서로 복잡하게 연결되어 있는 자료구조
- ex)포털 사이트 검색 엔진, SNS사람관걔, 네비게이션
- 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.
- 각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.
- 알고리즘 문제의 각 상황에 맞는 자료구조를 떠올릴 수 있다.
- Binary Search Tree를 이해할 수 있다.
- BFS와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있다.
- 데이터를 순서대로 쌓는 자료구조
- 먼저 들어온 자료는 가장 나중에 나올 수 있다.
- ex)브라우저 뒤로가기,앞으로 가기
coplit 브라우저 뒤로 가기 앞으로 가기
function browserStack(actions, start) {
let prev=[] //이전 페이지 스택(뒤로가기)
let next=[] //다음 페이지 스택(앞으로가기)
let page=start //현재 페이지
for(let i of actions){
if(i===-1&&prev.length!==0){ //뒤로가기
next.push(page)
page=prev.pop()
}else if(i===1&&next.length!==0){ //앞으로가기
prev.push(page)
page=next.pop()
}else{ //새로운 페이지
prev.push(page)
next=[]
page=i
}
}return([prev,page,next])
}
Queue
- 데이터를 줄 세우는 자료구조
- 먼저 들어온 자료부터 처리
- ex)프린트 인쇄 작업 , Buffer
coplit 프린터
function queuePrinter(bufferSize, capacities, documents) {
let count=0
let queue=[] //인쇄 목록 공간
let total = 0 //인쇄 목록에 들어있는 문서의 총 용량
//목록 크기(칸)만큼 0을 queue에 넣어둔다.
for(let i=0;i<bufferSize;i++){
queue.push(0)
}
//첫번째문서를 인쇄 목록에 넣는 코드
let curDocument=documents.shift()//문서하나를 빼서 현재 문서로 넣는다.
queue.unshift(curDocument)//현재 문서를 인쇄 목록에 넣는다.
queue.pop()//인쇄 목록 끝을 출력 빼낸다.
total=curDocument
count++
//total에 아무것도 안남을때까지 반복
while(total>0){
total-=queue.pop()//인쇄 목록 끝 출력
curDocument=documents.shift()
//인쇄목록에 들어있는 문서의 총 용량이 최대용량보다 작으면 새문서를 인쇄목록에 넣는다.
if(total+curDocument<=capacities){
queue.unshift(curDocument)
total+=curDocument
//용량이 부족한 경우 0값을 인쇄목록에 넣는다.
}else{
documents.unshift(curDocument)//다시 문서에 현재문서를 넣는다.
queue.unshift(0)
}
count++
}
return count
}
Graph
- 여러개의 점들이 서로 복잡하게 연결되어 있는 자료구조
- ex)포털 사이트 검색 엔진, SNS사람관걔, 네비게이션
function queuePrinter(bufferSize, capacities, documents) {
let count=0
let queue=[] //인쇄 목록 공간
let total = 0 //인쇄 목록에 들어있는 문서의 총 용량
//목록 크기(칸)만큼 0을 queue에 넣어둔다.
for(let i=0;i<bufferSize;i++){
queue.push(0)
}
//첫번째문서를 인쇄 목록에 넣는 코드
let curDocument=documents.shift()//문서하나를 빼서 현재 문서로 넣는다.
queue.unshift(curDocument)//현재 문서를 인쇄 목록에 넣는다.
queue.pop()//인쇄 목록 끝을 출력 빼낸다.
total=curDocument
count++
//total에 아무것도 안남을때까지 반복
while(total>0){
total-=queue.pop()//인쇄 목록 끝 출력
curDocument=documents.shift()
//인쇄목록에 들어있는 문서의 총 용량이 최대용량보다 작으면 새문서를 인쇄목록에 넣는다.
if(total+curDocument<=capacities){
queue.unshift(curDocument)
total+=curDocument
//용량이 부족한 경우 0값을 인쇄목록에 넣는다.
}else{
documents.unshift(curDocument)//다시 문서에 현재문서를 넣는다.
queue.unshift(0)
}
count++
}
return count
}
- 여러개의 점들이 서로 복잡하게 연결되어 있는 자료구조
- ex)포털 사이트 검색 엔진, SNS사람관걔, 네비게이션
Tree
- 단방향 그래프 구조로 뿌리로부터 가지가 사방으로 뻗은 형태
- ex)월드컵 토너먼트 대진표, 가계도 조직도
Author And Source
이 문제에 관하여([TIL]Stack, Queue, Tree, Graph), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@yonggar/TILStack-Queue-Tree-Graph
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Author And Source
이 문제에 관하여([TIL]Stack, Queue, Tree, Graph), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yonggar/TILStack-Queue-Tree-Graph저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)