기록방

💡 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..

👉 문제링크 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 🔸 문제 분석 🔸 일정 범위 안에서 최소값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용해야 한다. 윈도우의 크기는 최소값을 구하는 범위가 i-L+1 ~ i 이므로 L로 생각한다. 일반적으로 정렬은 O(nlogn)인데 N,L 의 범위가 5,000,000까지 이므로 정렬은 사용하지 못한다. O(n)의 시간 복잡도로 해결해야되므로 윈도우를 덱(deque)로 구현하여 정렬 효과를 낸다. 덱은 (인덱스, 숫자) 형태의 노드..