기록방

💡 0-1 BFS는 특정 상황의 그래프에서 최단 경로를 찾을 때 사용된다. 가중치가 0과 1로 이루어진 그래프에서 최단 경로를 찾을 때 사용한다.최단 경로를 구할 때 많이 사용하는 우선순위 큐 다익스트라(Dikjstra) 알고리즘은 시간 복잡도가 O(E log V)인 반면에, 0-1 BFS는 일반적인 BFS 시간 복잡도와 같이 O(V + E)의 선형 시간 복잡도를 갖는다.일반 BFS 에서 큐를 사용하는 것과 달리 덱(Deque)을 사용한다. 🚀 0-1 BFS의 동작 과정덱의 front에서 현재 방문한 노드를 꺼낸다.연결된 인접 노드를 살펴본다.(현재 비용+ 다음 노드 가중치) 다음 노드에 기록된 비용을 갱신해 준다.노드가 갱신될 때, 가중치가 0이라면 덱의 front, 가중치가 1이라면 덱의 back..

👉 문제링크 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 🔸 문제 분석 🔸 NxN 게임판에서 뱀이 이동하는 게임이 몇초간 진행 되는지 반환한다. 게임 판에는 K개의 사과가 있고, 사과를 먹으면 몸 길이가 1 늘어나며 기존의 꼬리 위치가 변경되지 않는다. 몸 혹은 게임판 벽에 부딪히면 게임이 종료된다. 🔸 문제 풀이 🔸 특별한 알고리즘이 없는 시뮬레이션 문제이다. 뱀의 방향 전환 정보와 뱀의 꼬리 좌표를 기억하기 위해 큐 자료구조를 사용한다. 🔸 코드 🔸 import java.io.*; import java.uti..

👉 문제링크 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 🔸 문제 분석 🔸 T번의 테스트 케이스에서 다음 계산을 반복한다. 연산 p를 입력받는다. n 크기의 배열을 입력받는다. 연산을 수행한다. R : 뒤집기 D : 첫 번째 수 버리기 n과 p의 길이의 최대값이 10만이므로 R연산마다 배열을 직접 뒤집으면 시간초과가 난다. 배열의 시작과 끝 인덱스에 각각 포인터를 두고, 뒤집힌 상태를 보며 D연산을 수행한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.Input..

👉 문제링크 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 🔸 문제 분석 🔸 데크를 구현하는 문제이다. 🔸 코드 🔸 from collections import deque import sys input = sys.stdin.readline print = sys.stdout.write deq = deque() for i in range(int(input())): order = input().rstrip() if order[:10] == "push_front": deq.appendleft(order..