[BOJ] 백준 2410 2의 멱수의 합 C++(Cpp)
2024. 11. 18. 21:01
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/2410문제를 풀며 고민했던 점DP를 어떻게 쪼개서 풀어야할까점화식은 어떻게 구해야할까와 같은 일반적인 접근법을 익히기 위해서 고민했다.밟았던 단계N이 홀수일 경우N - 1의 조합에서 +1을 하게 되면 그 조합이 만들어진다는 점을 착안해야한다고로 DP[N] = DP[N - 1]Ex. N = 3N = 2 조합 (1 + 1, 2) -> N = 3 조합 (1 + 1 + 1, 2 + 1)Ex. N = 5N = 4 조합 (1 + 1 + 1 + 1, 2 + 1 + 1, 2 + 2) -> N = 5 조합 (1 + 1 + 1 + 1 + 1, 2 + 1 + 1 + 1, 2 + 2 + 1)N이 짝수일 경우N - 1의 조합에서 + 1을 한 조합과 N / 2의..
[BOJ] 백준 2473 세 용액 C++(Cpp)
2024. 11. 13. 22:51
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/2473문제를 풀며 고민했던 점STL을 직접 구현해서 사용하기로 한 시점으로 sort를 어떻게 할것인가?시간복잡도 상 최선과 최악이 O(nlogn)인 병합(합병) 정렬을 사용하기로 선택!밟았던 단계병합 정렬을 구현하여 sort를 할 수 있게끔 함수를 만든다입력받은 nums를 merge_sort를 활용하여 정렬세 포인터를 구현하는 것보다 for문을 활용해 하나를 고정하고 두 포인터 알고리즘을 활용하여 0에 가까운 합을 구함세 개의 합이 30억이 넘어가는 숫자임으로 long long을 활용하여 풀어야한다!암묵적 형변환은 쓰레기 값이 들어갈 수 있으므로 명시적 형변환을 활용하여 쓰레기값을 방지하는 것이 중요!#include #define fas..
[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에 담을때 오토캐스팅을 해주지 않아 범위 초과로 인해 부적절한 값이 들어감..