전체 글

[백준 2169] 로봇 조종하기 C++

www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 이 문제는 1,1에서 시작한 로봇이 N, M까지 도달하는 경로 누적 합 중 최대값을 구하는 문제 입니다. DFS로, 각 공간마다 방향 왼쪽, 아래, 오른쪽으로 나누어서 풀면 되지만, 문제 조건 중에 N, M 제한이 1,000이기 때문에, 매번 갔던 길을 또 계산한다면 시간 복잡도가 어마하게 나올 것으로 생각되었습니다. 다이나믹프로그래밍을 사용해서, 각 지점에서 출발해서 N,M에 도달할 때의 최댓값을 저..

[백준 9252] LCS 2 C++

www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS 2는 LCS 1를 응용한 문제입니다. LCS 2를 풀기위해서, LCS 1의 과정을 이해해야합니다. rolypolytoy.tistory.com/43?category=365766 [백준 9251] LCS C++ www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)..

[백준 9251] LCS C++

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최대공통부분 수열의 문제입니다. 처음에 용어가 헷갈렸는데, LCS는 2가지의 용어가 있습니다. 1. LCS (Longest Common Substring) 최대공통부분문자열 2. LCS (Longest Common Subseqeunce) 최대공통부분수열 입니다. 둘의 큰 차이는 연속하냐 안하냐의 차이인데, 문자열의 경우 연속하는 문자열중 최대의 공통 부분 문자열이고,..

[백준 2096] 내려가기 C++

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 이번 문제는 다이나믹 프로그래밍 문제로, 기존의 다이나믹 문제 유형과 비슷하지만, 메모리를 효율적으로 구성해야하는 문제입니다. 메모리를 효율적으로 사용하기 전에, 기존의 간단한 방법으로 문제를 풀면 배열을 arr[n][3] 배열에서 이전의 위치에서 arr[n][0~3]에 더 해질 수 있는 칸들(arr[n-1][0~3] 중에서 최댓값을 구해서 arr[n][0~3]에 더해주면 됩니다. 문제에서는 별 가능 가능 불가능 이렇게 나와..

[백준 1707] 이분 그래프 C++

www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net  이 문제는 두 개의 정점이 주어졌을 때, 두개의 정점은 인접하지 못하도록 표시 후, 이분 그래프가 맞는지 판별하는 문제입니다. BFS, DFS 둘 중 아무거나 사용하면 됩니다. 이분 그래프 알고리즘의 핵심은, 두 개의 정점이 인접하지 못하도록, 2 가지 색깔로 칠해주는 것입니다. 처음 노드를 선택했을 때 1, 1로 칠해진 노드안에 있는 다음 노드를 선택 했을 때 2, 그리고 2노드안에 있는 다음..

[백준 11660] 구간 합 구하기 5 C++

www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 다이나믹 프로그래밍 알고리즘을 사용해서 푸는 문제입니다. map의 전체 사이즈는 최대 1024x1024이고, 연산을 최대 100,000번 해야하기 때문에, 브루트포스로 풀게되면 당연히 시간초과가 나올 수 밖에 없습니다. 시간초과가 나오지 않으려면, DP를 사용해서 각 인덱스별로 누적합을 저장하면 되겠습니다. dp[i][j]는 i, j까지 누적합을 말합니다. 입력을 받을..