[BOJ] 백준 3101 토끼의 이동 자바(Java)/C++(Cpp)
2024. 11. 13. 00:45
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/3101문제를 풀며 고민했던 점배열을 직접 만들어서 해결하면 시간초과가 예상된다.배열의 수학적 규칙을 이용해서 해결해야겠다.밟았던 단계대각선으로 전개되는 배열이므로 대각선의 숫자를 이용해서 규칙을 만들자1번째 : (0, 0)2번째 : (0, 1), (1, 0)3번째 : (0, 2), (1, 1), (2, 0)n번째 : (0, n-1), (1, n-2), (2, n-3), ... , (n-3, 2), (n-2, 1), (n-1, 0)규칙 : (r, c)일때 r+c+1이 대각선의 번호가 된다 / n번째 대각선은 n개의 숫자를 갖게 된다.대각선 번호가 n을 넘어가게 되면 그 번호에 포함되는 숫자의 개수가 1씩 줄어드는 규칙을 가지고 있다n+1번..
[BOJ] 백준 23352 방탈출 자바 (Java)
2024. 11. 4. 23:20
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/23352문제를 풀며 고민했던 점조건이 생각보다 까다로운데 일반적인 BFS로 해결이 될까?더이상 갈 수 없을때를 어떻게 구할까?모든 조건에 대한 비교를 어떻게 진행해야할까?밟았던 단계모든 0이 아닌 값을 갖고 있는 부분을 시작점으로 잡고 BFS를 수행BFS에서 상하좌우 네 방향에서 들어갈 수 있는 방이 없다는 걸 isBlock으로 체크isBlock에 걸리는 노드는 더이상 갈 수 없는 곳이므로 답을 체크하는 ans 우선순위 큐에 집어넣음ans 큐의 최상단 Password 값을 출력 >> 해결package b23352;import java.io.BufferedReader;import java.io.IOException;import java.i..
[BOJ] 백준 1865 웜홀 자바 (Java)
2024. 11. 3. 19:59
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/1865문제를 풀며 고민했던 점벨만-포드 알고리즘에서 변형해야 하는 부분이 뭐가 있을까?https://devstackingdocs.tistory.com/25 이 문제와 다른 점이 무엇일까?밟았던 단계벨만-포드 알고리즘에 대한 전형적인 문제로 알고리즘 구현 >> 틀렸습니다.모든 노드가 연결이 되어있다는 보장이 없다는 점을 발견해결방안은 2가지로 생각모든 노드를 시작점으로 적용해서 벨만-포드 알고리즘을 돌린다 >> 시간 초과 예상임의의 시작점에서 벨만-포드 알고리즘을 한번 돌려 음수 사이클을 확인하는 방법 >> DIST배열이 INF인 경우를 제하지 않으면 해결할 수 있다! >> But, 틀렸습니다.최단거리를 구하는 것이 아닌 음수 사이클을 확..
[BOJ] 백준 11657 타임머신 자바 (Java)
2024. 11. 2. 17:25
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/11657문제를 풀며 고민했던 점벨만-포드 알고리즘에서 어떻게 음수 싸이클을 판별할 것인가?벨만-포드 알고리즘의 구현은 어떻게 할 것인가?밟았던 단계벨만-포드 알고리즘에 대한 전형적인 문제로 알고리즘 구현 >> 출력초과출력 초과에 대한 결과로 당황.. 무슨 문제일까 고민N = 500, M = 500, 모든 간선의 가중치가 -10,000인 경우, Integer 배열에 최소 값인 -21억보다 작은 결과값이 만들어짐그 결과 D배열에 간선 합 값이 매우 큰 양의 정수로 변경findCycle 함수에서 저장되어있는 가중치 합이 이미 커서 변경하지 않는 벨만-포드 사이클로 인식 >> true값 리턴결과적으로 -1만 출력하는 것이 아닌 가중치 합들을 출..
[BOJ] 백준 24230 트리 색칠하기 자바 (Java)
2024. 11. 1. 00:10
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/24230문제를 풀며 고민했던 점트리 구현을 클래스를 사용해서 부모노드 정보와 자식 노드 정보를 저장해야하나?부모노드 정보를 어떻게 구해야하지?부모노드 정보를 dfs를 사용해서 조사를 한번 진행해야하나? >> 시간복잡도 n이라는 시간을 잡아먹는데?밟았던 단계클래스로 부모노드와 자식노드를 가지고 있는 정보를 만들고 이를 배열로 만들어 트리 구현 >> 시간초과클래스를 사용하지 않고 각각 일반 int배열로 만들어서 부모와 자식노드를 찾아놓자 >> 시간초과부모노드를 따로 찾을 필요 없이 ROOT가 1번부터니까 dfs로 부모노드 정보를 따로 전달해서 구현하면 되겠다색 배열과 다르면 자식노드 색칠하기 >> 시간초과자식 노드와 부모노드가 색이 다르면 ..
[BOJ] 백준 30470 호반우가 학교에 지각한 이유 3 자바 (Java)
2024. 10. 28. 23:29
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/30470문제를 풀며 고민했던 점통나무 길이를 저장하기 위해서 PriorityQueue를 써야할까, 일반 Stack을 써야할까?시간복잡도 상으로 PQ가 더 시간이 필요한데 시간초과가 나지 않을까?Stack을 써야 한다면 직접 구현해야하나 아님 Stack 라이브러리를 써도 괜찮을까?밟았던 단계PriorityQueue를 활용해서 구현 >> 시간초과Stack을 구현해서 사용, 적절한 커스텀이 필요하다고 생각 >> 시간초과Stack에 같은 통나무 길이가 반복적으로 저장됨Stack을 길이와 개수로 저장하는 방식으로 수정 >> 틀렸습니다.Java는 int 곱셈을 통해서 long에 담을때 오토캐스팅을 해주지 않아 범위 초과로 인해 부적절한 값이 들어감..
[BOJ] 백준 1922 네트워크 연결 자바 (Java)
2024. 8. 20. 23:36
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/1922문제를 풀며 고민했던 점가중치가 있으니 다익스트라 알고리즘을 쓰면 되지 않을까?그래프 내에 사이클 판별은 유니온 파인드 알고리즘을 써야할 것 같다최소 스패닝 트리 문제인데 다익스트라 알고리즘과 유니온 파인드를 함께 쓰는게 맞을까?밟았던 단계다익스트라 구현 중 사이클 판별에 대한 의문이 생김유니온 파인드를 사용해야 한다는 점 발견최소 스패닝 트리에 대한 생각완전 탐색으로는 문제를 해결할 수 없다는 생각그리디한 알고리즘을 모색함크루스칼 알고리즘을 떠올림크루스칼로 구현package b1922;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStrea..
[BOJ] 백준 9205 맥주 마시면서 걸어가기 자바 (Java)
2024. 8. 19. 23:53
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/9205문제를 풀면서 고민했던 점1미터씩 움직이는 그래프를 구현해서 풀어야할까?편의점과 목적지의 정보로만 그래프를 구성해서 풀어야할까?밟았던 단계편의점과 목적지의 정보로만 그래프를 구성하면 ㅍisit 배열을 확인하는게 중복을 체크해버리면 문제가 생기지 않을까?1미터씩 움직이는 그래프를 구현해서 풀어야겠다문제점 : 가로, 세로 약 6만개 > 메모리 초과 발생편의점과 목적지의 정보로만 그래프를 구성해야한다.집에서부터 목적지까지 가까운 곳을 밟아가므로 visit배열 중복, 돌아가는 경우를 생각하지 않아도 된다구현하여 PASSimport java.io.BufferedReader;import java.io.BufferedWriter;import j..