SW

0. 제목 백준 1912 연속합 BOJ 1912 연속합 C++ 1912 연속합 1. 문제 https://www.acmicpc.net/problem/1912 2. 풀이 DP 방식을 이용하였다. 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 것이 목적이다. 예를 들어, 배열의 값들이 10, 20, -100, -500, 700, 30 이라고 할 때, dp[1] = 10, dp[2] = 30, dp[3] = -70, dp[4] = -500, dp[5] = 700, dp[6] = 730 이다. 이 배열 dp 의 원소 값들을 구하는 규칙은 다음과 같다. 만약 dp[i]를 구하려고 할 때 dp[i-1] 가 음수라면 dp[i] = arr[i] 로 업데이트 해주고 양수라면 dp[i] = dp[..

0. 제목 백준 1707 이분 그래프 BOJ 1707 이분 그래프 C++ 1707 이분 그래프 1. 문제 https://www.acmicpc.net/problem/1707 2. 풀이 DFS, BFS 두가지 방법으로 풀 수 있다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다고 문제에 정의되어 있다. 각 단계마다 색을 칠하는데 color 가 0이면 아직 방문하지 않은 것이고 1과 2로 색을 표현하였다. 이분 그래프 여부를 판단하는 함수에서는 다음 단계로 갈때 같은 색깔을 가지고 있으면 false를 반환하고 그것이 아니면 true를 반환하도록 하였다. 3. 코드 1 2..

0. 제목 백준 11724 연결 요소의 개수 BOJ 11724 연결 요소의 개수 C++ 11724 연결 요소의 개수 1. 문제 https://www.acmicpc.net/problem/11724 2. 풀이 DFS, BFS 두가지 방법으로 풀 수 있다. checked 배열을 N번째 index까지 검사하여 true가 아니면 탐색을 실시하고 실시할때마다 count값을 1씩 증가시켜준다. 그 count값이 연결 요소의 개수이다. 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 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 5..

0. 제목 백준 2750 수 정렬하기 BOJ 2750 수 정렬하기 C++ 2750 수 정렬하기 1. 문제 https://www.acmicpc.net/problem/2750 2. 풀이 가장 작은 것을 앞으로 보내는 것이 핵심 아이디어인 선택 정렬을 사용하였다. 가장 작은 원소를 맨 앞으로 보내고 다음 Loop에서는 두번째 작은 원소를 두번째로 보내고 이런식으로 원소 개수만큼 Loop를 돈다. 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 25 26 27 28 29 30 31 32 #include using namespace std; int main(int argc, const char * argv[]) { int N; int ar..

0. 핵심 아이디어 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내면 어떨까? 1. 예시 1 10 5 8 7 6 4 3 2 9 1 5 10 8 7 6 4 3 2 9 1 5 8 10 7 6 4 3 2 9 1 5 8 7 10 6 4 3 2 9 1 5 8 7 6 10 4 3 2 9 1 5 8 7 6 4 10 3 2 9 1 5 8 7 6 4 3 10 2 9 1 5 8 7 6 4 3 2 10 9 1 5 8 7 6 4 3 2 9 10 //결국 가장 큰 값이 뒤로 오게 됨. 첫번째 Loop 끝. 1 5 7 8 6 4 3 2 9 10 1 5 7 6 8 4 3 2 9 10 .... 2. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using n..

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까지)을 만족해야한다. 작은 수로 갱신이 되면 안되기..