본문 바로가기

Algorithm43

[백준]BOJ 17484 진우의 달 여행 (Small) [자바/DFS] 문제자체는 간단합니다. 갈 수 있는 방향에 대해 가보고 달에 도착한다면 멈추고 최솟값을 갱신해 주는 완전탐색으로 풀 수 있습니다. 다만, 삽질했던 점은 문제를 보면 시작 위치가 지구에서 출발한다는 것을 알 수 있습니다. 즉, 지구 위치에서도 3방향으로 가볼 수 있다는 소리이므로, DFS 탐색을 수행할때 3방향 개수만큼 반복문을 돌려주며 모든 방향에 대해 탐색해보아야 합니다. 구현 for(int i = 0; i < M; i++) { for(int j = 0; j < 3; j++) {//처음에 시작할때 3방향으로 갈 수 있음 DFS 탐색 수행 } } public class Main{ private static int[][] maps; private static int M, N; private static i.. 2023. 2. 22.
[백준]BOJ 18352 특정 거리의 도시 찾기(자바/다익스트라/메모리초과 해결) 한 정점에서 다른 정점으로 가는 최단 거리의 문제입니다. 다음과 같이 모든 도로의 거리는 1이라는 조건이 있습니다. 이를 통해 BFS나 다익스트라로 문제를 풀어볼 수 있음을 알 수 있었습니다. 어려웠던 점 처음에는 인접행렬로 이 문제를 풀이했습니다. 제출했더니 메모리 초과가 났습니다. 이후에, 인접 리스트로 다시 문제를 풀었고, 다행히 성공할 수 있었습니다. 인접리스트로 단방향에 대해 저장하였습니다. 구현 큐에는 정점들을 넣었고, 현재 정점에 대해 경유지로 삼는 인접한 정점들을 방문하고 갱신한 뒤 이 정점을 큐에 넣었습니다. public class Main_18352 { public static void main(String[] args) throws IOException { BufferedReader .. 2023. 2. 4.
[백준] BOJ 2504 괄호의 값(자바/스택) 문제 풀이 방법 분배 법칙을 통해 괄호에 대한 연산 처리를 해주어야 하는 문제였습니다. 다음과 같은 예시를 통해 설명드리겠습니다. 다음 조건과 같이 값 * ( XY )가 값 * X + 값 * Y로 계산됩니다. 이는 분배 법칙에서 a(b + c)가 a*b + a*c로 전개되었던 것과 같습니다. 다음과 같은 예시로 문제 설명을 드리겠습니다. 이 경우에는 분배법칙에 따라서 2 * ( 2 + 3 * 3) 가 4 + 2 * 9 = 22가 된다. 따라서, 여는 괄호 '(' , '['인 경우 스택에 넣고, temp = temp * 2 또는 temp = temp * 3을 진행한다. 분배 법칙에 따라 곱셈을 하기 위해서이다. 닫는 괄호 ')' , ']' 인 경우 먼저, 올바른 괄호인지 확인한다. 올바르지 못하면 brea.. 2023. 1. 26.
[백준]BOJ 10799 쇠막대기 문제 조건 어려웠던 점 문제를 풀면서 여는 괄호와 닫는 괄호가 인접한 레이저인 경우에는 stack의 size만큼 더해주는 것은 생각을 했었습니다. 그러나, 그다음에 대해 생각해주지 못했습니다. 문제 풀이 왼쪽 끝은 여는 괄호 ‘ ( ’는 스택에 넣어줍니다. 레이저인 경우에는 쇠막대기가 잘립니다. 즉, 오른쪽 닫는 괄호 ')'인 경우 스택의 Top을 pop하여 레이저인 경우에는 스택 사이즈만큼 더해주면 됩니다. 다음과 같이 레이저(빨갛게 칠해놓은 부분)를 만나는 경우 쇠막대기(노랗게 칠해놓은 부분)는 스택 사이즈만큼인 3개로 나뉘는 것을 확인할 수 있습니다. 닫힌 괄호가 레이저가 아닌 경우, 즉 쇠막대기인 경우 남은 잘린 부분을 더해주면 됩니다. 남은 잘린 부분은 +1 해주면 됩니다. 다음과 같이 쇠막대기.. 2023. 1. 19.

티스토리툴바