CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 이 문제는 BFS와 우선순위 큐를 이용해 해결할 수 있습니다. BFS를 이용해 경로를 찾되, 벽을 최소로 부수는 경우를 찾아야 하기 때문에 우선순위 큐를 통해 현 시점에서 가장 적게 벽을 부순 경로부터 체크를 해주면 됩니다. 그리고 이미 검사를 한 구역이더라도, 현재의 경로가 벽을 더 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 기본적으로 bfs를 이용하여 문제를 해결할 수 있습니다. 하지만 최대한 위험한 지역을 통과하지 않고 목적지에 도착하는 것이 목적이기 때문에 한 번 검사한 지역도 생명의 개수에 따라 중복해서 검사해야 하는 문제가 생깁니다. 다시 말해 이미 검사한 칸이라도 현재 도착한 경로가 원래 지나간 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/20159 20159번: 동작 그만. 밑장 빼기냐? 카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다. 둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다. www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 우선 밑장을 한 번 빼고 나면, 해당 카드로부터 앞으로 정훈이가 받았어야 할 카드와 상대방이 받았어야 할 카드가 뒤바뀌게 됩니다. 문제를 해결하기 위해 두 개의 배열을 이용합니다. 하나는 해당 카드까지 정훈이 또는 상대방이 받은 카드의 점..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081i..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 비교적 간단한 구현 문제입니다. 저는 재귀를 이용해 각 톱니바퀴에서 오른쪽부터 모두 검사하고, 그 뒤에 왼쪽을 모두 검사하여 회전시켜야 할 톱니바퀴들만 마지막에 일괄적으로 회전시켜주는 형식으로 문제를 해결했습니다. 1234567891011121314151617181920212223242526272829..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 특별한 자료구조를 사용하는 것이 아닌 구현 문제입니다. 주사위가 굴러갈 때마다 주사위의 각 면을 새롭게 배치해주는 방식으로 해결하였습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 전형적으로 BFS를 사용하여 풀 수 있는 문제이며, 단 한 가지 다른 점은 일반적인 BFS 문제는 2차원 배열에서 풀이를 한다면, 위의 문제는 3차원 배열에서 풀이를 한다는 점입니다. 따라서 이동할 수 있는 장소를 표현할 때 한 차원을 더 표현해주어야 하기 때문에 조금 헷갈리는 부분이 있을 수 있을 뿐, 어렵게 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 저는 이 문제를 Deque를 사용하여 해결했습니다. Deque는 스택과 큐를 합쳐놓은 형태로, 배열의 앞 뒤로 모두 입출력이 가능한 형태입니다. 폭발 문자열을 찾아낼 때는 스택이, 폭발 문자열이 아님을 확인하고 그대로 출력할 때는 큐가 필요하여 Deque를 사용했습니다. 또한 Deque를 사용..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 전형적으로 BFS를 이용하는 문제입니다. 단지 보통 BFS를 수행하는 문제와 다른 점은 지훈이와 불의 이동을 따로 체크해주어야 한다는 점입니다. 그래서 저는 BFS를 위한 큐와 BFS 함수를 2개씩 만들어 지훈이의 이동과 불의 이동을 따로 관리했습니다. 그 외에는 크게 고려해야 할 사항이 없는..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 저는 이 문제를 다이나믹 프로그래밍을 이용해 해결했습니다. dp 배열을 생성하고, 해당 위치까지 올 수 있는 가장 짧은 거리의 값을 배열에 저장하였습니다. 특정 위치까지 올 수 있는 가장 짧은 거리는 현재 dp에 저장된 값과 한 칸 전까지 올 수 있는 가장 짧은 거리 +1, 그리고 해당 지점에 도..