BaekJoon/Algorithm 10 [백준,Python]1932번 정수 삼각형(DP,dynamic programming) 백준 1932번 정수 삼각형(DP)문제 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 정수 삼각형에서 이어지는 경로로 탐색했을 때 모든 노드 수의 합의 최댓값을 구하는 문제를 리뷰하겠습니다. Dynamic Programming으로 푸는 문제이며, 하나씩 depth을 증가시키며 이어지는 경로로 내려가며 탐색을 진행해야 하므로 배열 arr이 있다고 하면, arr[i][j] = arr[i][j] +( arr[i.. 2020. 8. 17. [백준,Python]1697번 숨바꼭질(BFS) 백준 1697번: 숨바꼭질 문제를 리뷰하는 시간을 가져보겠습니다. 문제를 요약하면, -N과K 두 수를 입력 받아 N이 K에 도달하는 최단 시간을 구하는 문제이고, N은 1초에 +1,-1,*2방법을 통해 이동할 수 있습니다. (자세한 문제 설명은 https://www.acmicpc.net/problem/1697를 참고하시면 됩니다.) 먼저, 이 문제는 BFS로 푸는 문제이며, DFS와의 차이에 대해서 간략하게 설명드리겠습니다. DFS는 탐색하면서 depth가 증가할 때 마다, 기준점을 바꾸고 재귀를 써서 탐색을 진행하게 되는데, 이 문제를 그렇게 풀 경우 무한 루프에 빠지므로 BFS로 푸는 방식을 이용해 탐색을 진행하도록 구현하였습니다. DFS로 풀지 않고 BFS로 푼다의 가장 큰 특징은 for문 또는 w.. 2020. 8. 15. [백준,Python]1260번 DFS와 BFS(DFS&BFS) 오늘 리뷰하는 문제는 DFS와 BFS의 기초를 공부하기에 좋은 문제라고 생각되는 문제입니다. 백준 1260번 문제를 Python으로 구현해보았습니다. 먼저, 간략하게 문제를 소개하자면, Input으로 정점 개수 N, 간선 개수 M, 시작 정점 V를 입력받고, M만큼 간선 들을 또 입력받고 Output으로 DFS와 BFS의 결과를 출력하는 문제입니다. (자세한 문제 설명은 https://www.acmicpc.net/problem/1260로 확인하시면 됩니다.) 일단 간단하게 개념을 설명하자면, DFS는 깊이 우선 탐색으로 그래프가 있을 때 방문한 점에서 길이 있으면 길이 없을 때까지 계속 방문하고 없으면 처음 루트에서 다시 탐색을 진행하는 알고리즘이고, BFS는 너비 우선 탐색으로 시작 루트 기준으로 가능.. 2020. 8. 11. [백준,Python]1463번_1로 만들기(DP,Dynamic Programming) 백준 알고리즘(Dynamic Programming 문제)들 중 *1463번_1로 만들기 문제*는 풀어 보면서 느끼는 것도 많고, 굉장히 중요한 문제라고 생각이되어 따로 정리해보는 시간을 가져보려 합니다. (https://www.acmicpc.net/problem/1463) 문제를 쭉 보고 생각을 해보니 N이라는 정수를 입력받았을 때 3가지 연산식을 이용해 N을 나타내는 데 최소값을 구하는 것이니까 min(3i+1, 2i+1,i)로 나타낼 수 있을 것라 생각했다. 그리고 최솟값이 되려면 3으로 나누고 1을 빼주는 것이 무조건 최솟값이므로 (같은 수N을 나타내려면 3i+1과 2i+1 중 당연히 3i+1의 i 값이 더 작을 것이기 때문) while문으로 1이 아닐 때 3으로 나누고 못나눌 경우 1을 뺴주고 나.. 2020. 8. 1. 이전 1 2 다음
