[BOJ] 12849. 본대 산책(경로 DP)py,cpp
#. Problemhttps://www.acmicpc.net/problem/12849* The copyright in this matter is in BOJ #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to improve it #. Solve경로 DP문제는DP문제에서도 전형적..
[BOJ] 1915. 가장 큰 정사각형(DP).py.cpp
#. Problemhttps://www.acmicpc.net/problem/1915* The copyright in this matter is in BOJ #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to improve it #. Solve유형만 잘 파악하면 되는 문제라고 하..
[BOJ] 2167. 2차원 배열의 합(DP, 누적합).py.cpp
#. Problemhttps://www.acmicpc.net/problem/2167* The copyright in this matter is in BOJ #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to improve it #. Solve최대 배열의 크기는 300x300 =..
#. Problemhttps://www.acmicpc.net/problem/11055* The copyright in this matter is in BOJ #. Solve전형적인 DP, LIS 문제이다.자세한 동작 설명은 문제를 참고해보자. #. Python Code12345678910import copyN, A = int(input()), list(map(int, input().split()))dp = copy.deepcopy(A) for i in range(1, N): for j in range(i): if A[i] > A[j]: dp[i] = max(dp[i], dp[j] + A[i]) print(max(dp))Colored by Color Scriptercs line 3) 자기 자신이 가장 긴 ..
[BOJ] 1932.정수삼각형.py.cpp (DP 기초)
#. Problemhttps://www.acmicpc.net/problem/1932* The copyright in this matter is in BOJ #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to improve it #. Solve입력이 아래와 같을 때, 7 3 8 ..
[Algorithm] 위상정렬(그래프 정렬)
#. Problemhttps://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98* The copyright in this matter is in Inflearn #. Solveㅇ위상정렬- 어떤 일을 하는 순서를 찾는 알고리즘- 각각의 일의 선후관계가 복잡하게 얽허있을 때 각각 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘 (그래프를 이용하여 일의 순서를 정할 때 주로 사용)- 순서가 지켜져야하므로 인접행렬 방향 그래프 사용 입력이 다음과 같을 때,6 61 4 (1번 작업 수행 후 4번 작업 진행)5 4 4 3 2 5 2 3 6 2아래와 같은 그래프가 그려진다.위상정렬에서는 진입차수, 들어오는 간선이 중요한데(차수 : 연결된 간선의 ..
[Inflearn] 회장뽑기(DP, 플로이드-워셜, Floyd-Warshall Algorithm)
#. Problemhttps://www.acmicpc.net/problem/2660* The copyright in this matter is in BOJ #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract- 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램- 회원 수는 50명을 넘지 않음- 회원번호는 1부터 회원의 수만큼- 마지막 줄에는 -1이 두 개 들어있음 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry o..
[Algorithm] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
#. Problemhttps://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98* The copyright in this matter is in Inflearn N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값을 구하는 프로그램을 작성하 세요. #. Solve 다익스트라, 벨만-포트 알고리즘은 그래프의 한 정점에서 다른 정점으로 가는 최단 거리를 구하는 알고리즘이라면,플로이드-워셜은 그래프의 모든 정점에서 모든 정점으로 가는 최단거리, 그 최소 비용을 구하는 알고리즘이다.모든 정점에서 모든 정점을 방문해야하므로 그래프는 2차원 배열로 구성 입력..