본문 바로가기

전체 글312

[JAVA] 백준 1446 - 지름길 https://www.acmicpc.net/problem/1446다익스트라를 풀고 싶어서 Solved.ac에서 다익스트라 태그를 붙여서 찾은 문제이다.다익스트라 태그를 타고 들어갔기 때문에 문제를 보고 바로 그리디하게 정렬할 수 있는 기준을 열심히 찾았는데아무리 봐도 그 기준이 모호했다. 하나를 고치면 다른 곳에서 구멍이 났다.그래서 N도 작겠다 그냥 DFS로 풀었다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List.. 2025. 9. 21.
[JAVA] 백준 11444 - 피보나치 수 6 https://www.acmicpc.net/problem/11444N번째 피보나치수를 10억 7로 나눈 나머지를 출력하는 문제이다.N의 범위를 보면 알듯 일반적으로 사용하는 동적계획법이나 재귀를 이용해 풀면 반드시 시간초과가 난다.F(n+1) = F(n)+F(n-1)라는 점화식을 이런 식으로 나타낼 수 있으므로 (1 1 1 0) 행렬의 거듭제곱으로 N번째 피보나치수를 구할 수 있다고 한다.이런 걸 어떻게 알아내는거지..여튼 이걸 알았으니 일반적인 빠른 제곱 알고리즘을 이용해 풀었다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static long .. 2025. 9. 17.
[JAVA] 백준 1918 - 후위 표기식 https://www.acmicpc.net/problem/1918중위 표기식으로 주어진 식을 후위 표기식으로 바꾸는 문제이다.괄호나 연산자 우선순위를 결정하는 문제는 주로 스택을 많이 사용하는데, 나한텐 정말 어려웠다.스택을 어떻게 활용해야하지 한참 고민하다가 결국 GPT에게 아웃라인을 받아서 풀었다,,알파벳인 경우는 그냥 출력하고, 연산자나 여는 괄호의 경우 스택에 넣는다.+, - -> 스택이 비어 있으면 스택에 삽입, 스택이 차 있다면 스택이 빌 때까지, 또는 괄호를 만날 때까지 연산자를 꺼낸 후 만난 +, - 를 삽입한다. 지금까지 만난 연산자 중 우선순위가 가장 후순위이기 때문이다.*,/ -> 스택이 비어 있으면 스택에 삽입 스택이 차 있다면 하나 꺼내서 +나 -일 경우 다시 집어넣고 *,/를 만.. 2025. 9. 16.
[JAVA] 백준 1167 - 트리의 지름 https://www.acmicpc.net/problem/11671967번 트리의 지름 문제랑 동일한 개념을 다루는 문제로, 다익스트라 및 DFS를 이용해 푸는 문제이다.정점의 개수가 10배인 것만 제외하면 세부사항도 같다.먼저 첫번째 다익스트라로 임의의 정점에서 가장 먼 정점을 찾고, 가장 먼 정점을 기준으로 다익스트라를 돌려 나온 가장 먼 정점과의 거리를 구하면 되는 문제이다.일반적으로 Node 클래스 내에 ArrayList로 간선을 저장하는 걸 선호해왔는데, 이번엔 int 2차원 배열로 해보자~ 했다가 메모리초과가 나서 계산해보니 10만*10만칸의 int는 약 40GB를 차지한다. 쓰던 방식을 계속 써야겠다.1967번과 똑같이 골드 4문제 같다.import java.io.BufferedReader;.. 2025. 9. 10.
[JAVA] 백준 16236 - 아기 상어 https://www.acmicpc.net/problem/162362차원 배열에서 주어지는 아기상어의 위치에서 이동하며 주어진 규칙에 따라 물고기를 먹을 수 있을 만큼 먹었을 때 이동거리를 구하는 문제이다. 내가 생각한 로직은 BFS를 이용해서 아기상어 위치를 기준으로 먹을 수 있는 가장 좌측 상단의 물고기까지의 이동 거리를 구하고, 먹은 물고기의 위치를 기준으로 다시 BFS를 돌리는 과정을 반복해 이동이 불가능할때까지의 depth를 구하는 것이었다. 구현을 완료하고 예제를 돌려보니 틀린 점이 있어서 보니까 가장 좌측 상단의 물고기를 구하지 않고 먹을 수 있는 물고기를 찾으면 break하도록 구현해놨던 것이다. 그래서 각 DFS마다 최단거리로 이동한 먹을 수 있는 물고기 위치의 최소행, 행이 같을 경우 .. 2025. 9. 9.
[JAVA] 백준 11779 - 최소비용 구하기2 https://www.acmicpc.net/problem/11779다익스트라로 출발점에서 목적지까지의 최단 경로의 가중치를 구하되, 거쳐온 도시의 개수와 경로를 출력하는 문제이다.이렇게만 봤을 때 사실 만만하게 생각했는데 예상치 못한 부분에서 시간을 많이 소비했다.정점 리스트에 미리 N개의 정점을 만들어놓고 우선순위 큐에서 그 정점을 계속 뽑아서 썼는데 이게 같은 주소를 가진 객체가 중복으로 삽입되어서 가중치가 더 작은 쪽으로 변경되어 같은 정점을 두 번 반복해서 방문하는 형태가 나타났던 것이다.그래서 new로 객체를 새로 만들어서 값을 세팅해 준 뒤 Insert하고 poll 할때 미리 만들어놓은 정점에 값을 입혀주는 방식을 사용했는데 메모리초과가 났다.알고보니 visited 체크를 제대로 안하고 있어서.. 2025. 9. 8.

티스토리툴바