백준34 [BOJ]11657번: 타임머신 www.acmicpc.net/problem/11657 음의 가중치가 있는 최단 경로 문제입니다. 벨만 포드 알고리즘을 통해 해결할 수 있습니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ11657.cc 2020. 9. 6. [BOJ]7562번: 나이트의 이동 https://www.acmicpc.net/problem/7562 기본적인 BFS 문제입니다. 나이트가 이동할 수 있는 8칸을 다음 칸 후보로 두고 탐색하면 됩니다. https://github.com/cottory/algorithm/blob/master/BOJ/BOJ7562.cc 2020. 8. 18. [BOJ]4195번: 친구 네트워크 문제: https://www.acmicpc.net/problem/4195 단순 DFS로 탐색하면 시간초과로 터지는 문제입니다. Union & Find를 통해 해결했습니다. 풀이는 jason님 (https://jason9319.tistory.com/41) 링크를 참고했는데요. 일반 Union & Find 보다 한 단계 더 나아가 자식의 숫자를 저장하고 있어야 합니다. 그러므로 문제가 생기는 부분이 있습니다. 바로 friend1, friend2 로 들어오는 관계가 이미 부모 - 자식 관계인 경우 입니다. BEFORE의 경우 무조건 부모쪽에 더하도록 만들어주었고, AFTER는 부모 - 자식 관계인 경우 부모를 리턴, 부모 - 자식 관계가 아닌 경우 더하도록 만들었습니다. BEFORE 코드가 문제가 되는 이유는.. 2020. 8. 11. [BOJ]2096번: 내려가기 문제: https://www.acmicpc.net/problem/2096 슬라이딩 윈도우 문제입니다. 메모리 제한이 심상치 않습니다. 발판은 board[N][3]의 형태를 가지고 있지만, i번째 칸을 계산함에 있어서 필요한 발판정보는 i-1번째 칸의 정보만 필요합니다. 그러므로 메모이제이션을 위한 dp[][] 배열이나 input값을 저장하는 board[][] 배열 모두 [2][3] 크기면 됩니다. dp배열을 다음과 같이 정의내리겠습니다. max_dp[N][M]: 맨 윗칸에서부터 board[N][M] 칸까지 내려왔을 때 얻을 수 있는 최댓값 min_dp[N][M]: 맨 윗칸에서부터 board[N][M] 칸까지 내려왔을 때 얻을 수 있는 최솟값 끝으로 dp[i][], dp[i+1][] 이렇게 두 칸만 사용하.. 2020. 7. 22. 이전 1 2 3 4 5 6 7 ··· 9 다음
