Algorithms/Stack & Queue 검색 결과

해당 글 3건

[BOJ 3190] 뱀(C++)

뱀 (Gold5) 문제 전체 문제 보기 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 접근법 이번 문제는 Snake game 이라는 유명한 고전 게임의 일부를 구현하는 문제입니다. 문제에서 제시한 기능들을 하나씩 구현하여 문제를 해결할 수 있습니다. 뱀의 이동과 사과 가장 중요한 뱀을 구현하기 위해서는 큐를 사용할 수 있습니다. 뱀이 이동 메커니즘은 다음과 같습니다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 ..
Algorithms/Stack & Queue 2021. 9. 28. 10:11

[BOJ 1918] 후위 표기식 (C++)

후위 표기식 (Gold 3) 문제 전체 문제 보기 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 접근법 후위 표기식 문제는 스택의 대표적인 문제 중 하나이다. 중위 순위식으로 들어온 연산자들을 특정 규칙에 맞게 stack에 push 및 pop을 하여서 풀 수 있다. stack을 우선 순위가 낮은 연산자가 가장 아래에 가도록 유지한다면 우선순위가 가장 낮은 연산자가 가장 늦게 pop 될 수 있기 때문이다. 그래서 아래와 같은 방법으로 중위 표기식을 후위 표기식으로 바꿀 수 있다. 모든 문자에 대해서 ..
Algorithms/Stack & Queue 2021. 9. 7. 16:13

[프로그래머스](Queue) 다리를 지나는 트럭 (C++)

다리를 지나는 트럭(Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr 접근법 다리를 지나가는 트럭은 First-In First-Out(FIFO)의 성질을 지닌다. 항상 먼저 다리에 들어간 트럭이 먼저 빠져나온다. 그래서 다리를 하나의 Queue로 생각해볼 수 있다. Queue의 (FIFO)성질 만으로는 문제에서 언급한 다음의 조건을 만족시키기 부족하다. 트럭은 1초에 1만큼 움직인다. 다리는 무게 weight까지 견딘다. 우리는 다리를 하나의 Queue로 정..
Algorithms/Stack & Queue 2021. 4. 24. 14:11