목록대학교/Algorithm (105)
차근차근
0. 핵심 아이디어 가장 작은 것을 선택해서 제일 앞으로 보내면 어떨까? 1. 예시 1 10 5 8 7 6 4 3 2 9 1 2 5 8 7 6 4 3 10 9 1 2 3 8 7 6 4 5 10 9 1 2 3 4 7 6 8 5 10 9 1 2 3 4 5 6 8 7 10 9 1 2 3 4 5 6 7 8 10 9 1 2 3 4 5 6 7 8 9 10 2. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int main(int argc, const char * argv[]) { int i, j, min, index, temp; int array[10] = {1, 10, 5, 8, 7, 6,..
0. 제목 백준 1260 DFS와 BFS BOJ 1260 DFS와 BFS C++ 1260 DFS와 BFS 1. 문제 https://www.acmicpc.net/problem/1260 2. 풀이 먼저 탐색을 완료했는지 여부를 체크하는 checked 배열을 선언한다. 그래프를 생성해줄 때는 vector를 이용해서 선언해준다. 연결되어 있는 점들을 해당 vector에 push_back 해줌으로써 원소로 추가해준다. 그렇게 그래프를 생성한 후 오름차순으로 정렬해주어야 한다. 그 이유는 정점이 여러 개인 경우에 작은 번호부터 먼저 방문하기 때문이다. DFS의 경우에는 이미 탐색 완료를 하였으면 리턴하고 탐색하지 않았으면 탐색상태를 true로 바꿔준 후, 출력해준다. 그리고 그 점에 연결되어 있는 점들을 재귀적으로..
0. 제목 백준 11054 가장 긴 바이토닉 부분 수열 BOJ 11054 가장 긴 바이토닉 부분 수열 C++ 11054 가장 긴 바이토닉 부분 수열 1. 문제 https://www.acmicpc.net/problem/11054 2. 풀이 DP 방식을 이용하였다. 가장 긴 증가하는 부분 수열을 앞에서부터 한 번, 뒤에서부터 한 번 실시하면 된다. 먼저 모든 dp[i] 값을 나올수 있는 최소값인 1로 초기화 시킨다. dp[i]를 구하기 위해서는 다음과 같은 과정을 거쳐야 한다. 해당 인덱스의 배열 값(A[i])과 그 이전 값들을 비교한다. A[i]가 이전 값들보다 크면 1씩 증가해주면 된다고 생각할 수 있다. 그러나 그렇게 하면 오류가 발생한다. 각각의 전 dp값들과 비교하지만 dp[i] < dp[j] + ..
0. 제목 백준 11722 가장 긴 감소하는 부분 수열 BOJ 11722 가장 긴 감소하는 부분 수열 C++ 11722 가장 긴 감소하는 부분 수열 1. 문제 https://www.acmicpc.net/problem/11722 2. 풀이 DP 방식을 이용하였다. 먼저 모든 dp[i] 값을 나올수 있는 최소값인 1로 초기화 시킨다. dp[i]를 구하기 위해서는 다음과 같은 과정을 거쳐야 한다. 해당 인덱스의 배열 값(A[i])과 그 이전 값들을 비교한다. A[i]가 이전 값들보다 작으면 1씩 증가해주면 된다고 생각할 수 있다. 그러나 그렇게 하면 오류가 발생한다. 각각의 전 dp값들과 비교하지만 dp[i] < dp[j] + 1 (j는 1부터 i-1까지)을 만족해야한다. 작은 수로 갱신이 되면 안되기 때문이..
0. 제목 백준 11055 가장 큰 증가 부분 수열 BOJ 11055 가장 큰 증가 부분 수열 C++ 11055 가장 큰 증가 부분 수열 1. 문제 https://www.acmicpc.net/problem/11055 2. 풀이 DP 방식을 이용하였다. 먼저 모든 dp[i] 값을 나올수 있는 최소값인 A[i]로 초기화 시킨다. dp[i]를 구하기 위해서는 다음과 같은 과정을 거쳐야 한다. 해당 인덱스의 배열 값(A[i])과 그 이전 값들을 비교한다. A[i]가 이전 값들보다 크면 A[i] 만큼 증가해주면 된다고 생각할 수 있다. 그러나 그렇게 하면 오류가 발생한다. 각각의 전 dp값들과 비교하지만 dp[i] < dp[j] + A[i] (j는 1부터 i-1까지)을 만족해야한다. 작은 수로 갱신이 되면 안되기..
0. 제목 백준 11053 가장 긴 증가하는 부분 수열 BOJ 11053 가장 긴 증가하는 부분 수열 C++ 11053 가장 긴 증가하는 부분 수열 1. 문제 https://www.acmicpc.net/problem/11053 2. 풀이 DP 방식을 이용하였다. 먼저 모든 dp[i] 값을 나올수 있는 최소값인 1로 초기화 시킨다. dp[i]를 구하기 위해서는 다음과 같은 과정을 거쳐야 한다. 해당 인덱스의 배열 값(A[i])과 그 이전 값들을 비교한다. A[i]가 이전 값들보다 크면 1씩 증가해주면 된다고 생각할 수 있다. 그러나 그렇게 하면 오류가 발생한다. 각각의 전 dp값들과 비교하지만 dp[i] < dp[j] + 1 (j는 1부터 i-1까지)을 만족해야한다. 작은 수로 갱신이 되면 안되기 때문이다..
0. 제목 백준 2156 포도주 시식 BOJ 2156 포도주 시식 C++ 2156 포도주 시식 1. 문제 https://www.acmicpc.net/problem/2156 2. 풀이 DP 방식을 이용하였다. 연속하여 3잔을 마실 수 없다는 것이 핵심이다. 먼저 점화식에 사용될 초기값들 dp[1], dp[2], dp[3] 을 구한다. dp[i] 를 구할 때, 총 세가지 경우가 나올 수 있다. 먼저 마지막 포도주 잔을 선택했을 경우 두가지 경우가 나오는데, 전 포도주를 마신 경우(dp[i-3] + arr[i-1] + arr[i])와 전 포도주를 안마신 경우(dp[i-2] + arr[i])이다. 마지막 포도주 잔을 선택하지 않았을 경우는 그 전에 잔을 선택한 경우(dp[i-1])에 최대값이 된다. 따라서 이 ..
0. 제목 백준 9465 스티커 BOJ 9465 스티커 C++ 9465 스티커 1. 문제 https://www.acmicpc.net/problem/9465 2. 풀이 DP 방식을 이용하였다. 오른쪽으로 한칸씩 늘려가면서 규칙을 생각해보았다. 어떤 것들이 정답에 영향을 줄 수 있을지 살펴보니 한 단계 전 값들, 두 단계 전 값들이 영향을 줄 수 있었다. dp[i][j] 를 i 단계에서 j 일때 최댓값이라고 하였다. 두 단계 전까지 영향을 끼칠 수 있으니 처음 두 단계는 값을 직접 설정해주었다. dp[j][0] 은 arr[j][0]의 값과 dp[j-1][1], dp[j-2][0], dp[j-2][1] 세 개중 최대값의 합과 같다. dp[j][1] 은 arr[j][1]의 값과 dp[j-1][0], dp[j-2..
0. 제목 백준 2193 이친수 BOJ 2193 이친수 C++ 2193 이친수 1. 문제 https://www.acmicpc.net/problem/2193 2. 풀이 DP 방식을 이용하였다. dp[i][0]은 i 단계에서 0일때, dp[i][1]은 i 단계에서 1일때의 이친수 개수를 뜻한다. 이친수의 규칙에 의하면 1은 연속으로 나올수 없고, 0은 처음에 나올수 없다. 1단계에서의 dp[1][0], dp[1][1]은 각각 0, 1 로 초기화한다. i 단계에서 0일때, i-1 단계에서는 0, 1 둘다 올 수 있다. 따라서, dp[i-1][0] + dp[i-1][1]의 값과 같다. i 단계에서 1일때, i-1 단계에서는 0만 올 수 있다. 따라서, dp[i-1][0]의 값과 같다. N단계에서 이친수의 개수는..
0. 제목 백준 11057 오르막 수 BOJ 11057 오르막 수 C++ 11057 오르막 수 1. 문제 https://www.acmicpc.net/problem/11057 2. 풀이 DP 방식을 이용하였다. dp[i][j]는 i단계에서 값이 j일때 오르막 수의 개수를 의미한다. 먼저 처음에 1자리 수일 경우에 대한 초기화를 한다. 즉, 1단계일때 오르막 수는 1개씩(0~9) 뿐이다. 예를 들어, 5단계에서 값이 7일때 오르막 수의 개수를 구하고 싶다면 5단계의 6일때 오르막 수의 개수와 4단계의 7일때 오르막 수의 개수를 합하면 된다. 다음과 같이 써보니 규칙 찾기가 수월하였다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..