GOLD23 [백준/C++] #16933 벽 부수고 이동하기 2, 3 (BFS) 문제https://www.acmicpc.net/problem/16933 구상백준 14442번 벽 부수고 이동하기 문제에다가 낮/밤 조건이 추가된 문제였다. 이런 문제는 깊이 우선 탐색(DFS)로 풀기가 어렵다. 이유는 다음과 같다. 최단 경로 보장: DFS는 특정 경로를 완전히 탐색한 후에야 다른 경로를 탐색하기 때문에, 탐색 초기에 찾은 경로가 반드시 최단 경로라고 보장할 수 없다. 반면 BFS(Breadth-First Search)는 모든 경로를 동시에 탐색하며, 처음으로 목표에 도달하는 경로가 최단 경로임을 보장한다.낮과 밤의 전환: 이 문제에서는 낮과 밤이 번갈아가면서 바뀌는 조건이 있다. BFS는 단계별로 탐색하기 때문에 이 조건을 자연스럽게 처리할 수 있는데, DFS에서는 상태를 추적하며 .. 2024. 7. 31. [백준/C++] #1509 팰린드롬 분할 (DP) 문제https://www.acmicpc.net/problem/1509 구상확실히 골드 1이 느껴지는 문제였다. 그래도 차근차근 접근하니 옳은 풀이까지 도달할 수 있었다. 역시나 DP말고 특별한 접근 방식이 떠오르지 않아서 DP로 접근을 했다. 작은 길이의 팰린드롬 분할의 개수의 최솟값을 통해 더 큰(긴) 팰린드롬 분할의 개수의 최솟값을 구할 수 있었다. 그래서 처음에는 흔한 다른 DP문제들과 유사하게 접근을 했다. 흔한 DP 문제들은 DP배열의 특정 값이 답이 되는데, 그래서 나도 DP[i][j]가 str[i]~str[j]문자열에서 팰린드롬 분할의 개수의 최솟값이라고 잡고 문제를 접근했다. 그런데, 특정 크기의 문자열이 팰린드롬인지 확인하는 로직이 필요했다. 팰린드롬 여부를 어떻게 확인할까? 생각하다가.. 2024. 7. 24. [백준/C++] #11049 행렬 곱셈 순서 (DP) 문제https://www.acmicpc.net/problem/11049 구상행렬 곱셈 연산의 수의 최솟값을 구하는 문제였다. 해당 문제가 11066번(https://persi0815.tistory.com/47)과 같이 작은 부분을 통해 큰 부분의 값을 알아낼 수 있었다. 처음에 착각했던게, a b c d라는 배열이 있으면, abc * d와 a* bcd의 연산만 가능하다고 생각했었다. 사실 ab*cd도 되는데.. 그래서 해당 부분 수정해서 로직을 짰더니 성공 !!알고리즘이전에 구한 값으로 다음 값을 구하니 dp 유형이다. 풀이 + 코드dp[i][j]는 행렬 i부터 행렬 j까지의 최소 행렬 곱셈 연산 수이다. 최악의 연산수도 범위가 2^31-1보다 작다고 해서 int를 사용했다. #include#incl.. 2024. 7. 23. [백준/C++] #11066 파일 합치기 (DP) 문제https://www.acmicpc.net/problem/11066 구상문제 풀이가 생각이 안나면 나는 일단 DP로 접근을 해본다. 이 문제도 그러했는데, DP로 접근해보니 풀이가 보였다. 이전 합치는 비용을 이용해서 다음 합치는 비용을 구했다. DP를 사용할 때는 획일화된 기준이 중요해서 첫 기준을 파일 길이로 잡고 다음 기준을 파일 시작 위치로 정했다. 그랬더니 파일 끝 위치는 저절로 설정할 수 있었고, 다음 기준을 분할 위치로 잡았다. 그렇게 마지막 식을 보면 알 수 있듯이 이전 값들을 이용해서 보다 큰 다음 비용을 구할 수 있었다. 알고리즘이전 합치는 비용 이용해서 다음 합치는 비용을 구하니까 DP를 이용했다. 풀이 + 코드dp[i][j]: 파일 i부터 j까지 합치는 데 필요한 최소 비용. .. 2024. 7. 23. 이전 1 2 3 4 5 6 다음
