기록방

👉 문제링크 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 🔸 문제 분석 🔸 N이 3x2^k (0

👉 문제링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 🔸 문제 분석 🔸 N * M 행렬 맵에서 (1, 1)부터 (N, M) 까지 이동하는 최단거리를 구한다. 인접한 상하좌우로 1칸씩 이동할 수 있다. 이동할 수 있는 칸은 0, 벽은 1로 표시되는데, 1번 벽을 부수고 이동할 수 있다. 행렬에서 최단거리를 구하는 문제이므로 BFS를 사용한다. 벽을 부수고 먼저 도착했었던 칸을 벽을 부수지 않고 도착했다면, 이어서 탐색해보아야 한다. 벽을 부수지않고 먼저 도착했던 칸이면 더 탐색해..

👉 문제링크 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 🔸 문제 분석 🔸 N * 3 보드판을 내려가며 최대,최소값을 구하는 문제이다. 내려갈 수 있는 방법이 3가지가 있는데, 브루트포스로 그래프 탐색하면 시간초과가 난다. 내려가는 방법이 아닌, 역으로 이전 줄을 보고 최대/최소값을 고르는 DP 방식으로 풀이할 수 있다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io...

👉 문제링크 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 🔸 문제 분석 🔸 중위 표기식을 후위 표기식으로 변환해 출력한다. 입력되는 피 연산자는 알파벳 대문자, 연산자는 "+-*/()"의 6가지가 사용된다. 스택 자료구조를 사용해서 후위 표기식으로 변환할 수 있다. 🔸 코드 🔸 import java.io.*; public class Main { private static class MyStack { private int pointer; private char[] stack; public MyStack(..

👉 문제링크 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 🔸 문제 분석 🔸 가중치가 있는 방향 그래프에서 시작 노드부터 다른 모든 노드까지의 최단 거리를 구한다. 정점의 수 V, 간선의 수 E. 시작 노드 K와 연결 정보가 주어진다. 가중치는 10 이하의 자연수이다. 다익스트라의 반복이나 프림 알고리즘으로 풀이할 수 있다. 시작 노드에서 아직 방문하지 않은 인접 노드 중 최소 가중치 간선을 선택해 탐색한다. (갈 수 있는 간선 중 최소 값을 선택하면 최단거리가 보장된다..