백준 algorithm
-
백준 1149 - RGB거리백준 algorithm 2020. 7. 4. 02:01
=> DP문제입니다. => 오랜만에 푸는 문제인지라 이해하는데 오래 걸렸습니다. => 빨간색을 칠하기 위해서는 이전에 초록색 혹은 파란색이 칠해져 있어야 합니다. =>이 경우, 둘 중에 최소값을 골라 해당하는 집에 빨간색을 칠하는 금액에 더해주어야 합니다. 파랑 or 초록 (1번째 집) 빨강 (2번째집) => 위의 방식처럼 이루어져야 합니다. =>2번째 집에 빨강을 칠하고 싶을 경우, 이전의 집의 색이 파랑 혹은 초록이어야 합니다. **주의할 점 : row가 0인 지점부터 값을 넣어줄 경우 (0-1) 지점을 참조할 수 있으니 실수하지 않도록 합니다. 점화식은 아래와 같습니다. dp[i][0] += min(dp[i-1][1] , dp[i-1][2]); dp[i][1] += min(dp[i-1][0] , d..
-
백준 1026 - 보물백준 algorithm 2020. 7. 4. 01:15
=> 간단한 정렬 문제입니다. => 문제에서 B는 그대로 두라고 하지만, 실제로는 정렬을 해야 계산이 쉬워집니다. A를 정렬한다. B를 정렬한다. A[0] * B [N-1] + A [1] * B [N-2]... 를 취한다. => 위와 같은 방법으로 문제를 해결하면 됩니다. #include #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; int A[51]; int B[51]; for(int i=0; i> tmp; A[i] =tmp; } for(int i=0; i> tmp; B..
-
백준 11724 - 연결 요소의 개수백준 algorithm 2020. 7. 3. 16:27
=> graph의 연결 요소의 개수를 묻는 문제입니다. => 기존의 DFS와 BFS를 이해하신 분이라면 쉽게 풀 수 있는 문제입니다. 기존 방식대로기존 방식대로 입력을 받으며, 인접 행렬, 인접 리스트, 간선 리스트, check 행렬을 생성합니다. 연결 요소의 개수를 확인해야하므로 DFS나 BFS를 통해 Path를 찾으며 해당 check 행렬을 최신화합니다. 정점의 개수에 해당하는 check행렬이 모두 true가 될 때까지 진행합니다. 해당 프로세스를 진행하며 연결요소의 개수를 구합니다. *저는 DFS를 통해 연결요소의 개수를 셌습니다. 하지만 code에는 BFS함수까지 구현했으므로 BFS로 해도 무방합니다. *둘 중 어느 방법을 골라서 할지는 코드 작성자의 취향에 따라 갈립니다. #include #in..
-
백준 1260 -DFS와 BFS백준 algorithm 2020. 7. 3. 13:14
=> DFS와 BFS를 사용할 줄 아는지 묻는 문제였습니다. => 기본적으로 입력을 받을때 인접 행렬, 인접 리스트, 간선 리스트를 만들어두면 편합니다. => DFS와 BFS code 역시 형식이 정해져있으므로, 이해와 함께 암기해두시면 편리합니다. => DFS와 BFS에 대한 설명은 생략하겠습니다. => DFS : 깊이를 끝까지 따라가며 탐색하는 방법 ( stack을 사용하지만, 코드에서는 재귀를 통해 구현 가능) => BFS : 너비를 우선시하면 탐색하는 방법 ( queue를 사용하여 코드로 구현 가능) void dfs(int x, int n) //x는 탐색 시작점, n은 정점의 갯수 { check[x]=true; cout
-
백준 13023 - ABCDE백준 algorithm 2020. 7. 3. 11:42
=> 그래프와 브루트 포스가 섞여 있는 문제입니다. => 자료구조 시간에 배운 그래프를 기억해내야 합니다.. => 인접행렬, 인접 리스트, 간선 리스트 이 세 가지를 미리 만들어놓고 문제를 해결할 때 사용하면 좋습니다. => DFS, BFS 문제가 아니기 때문에 브루트포스 방식으로 문제를 풀어도 무방합니다. => 본인은 아래의 세가지 행렬과 리스트를 사용해서 문제 해결하였습니다. bool arr[MAX][MAX]; //인접행렬 vector list[MAX]; //인접리스트 vectoredges; //간선리스트 A -> B -> C -> D -> E 인 경로를 찾아야 한다. A->B , B->C는 그냥 간선이기 때문에 간선 리스트로 찾는다. ( 이 경우, 브루트 포스를 사용하기 때문에 각 값들이 다른 값을..
-
백준 1759 - 암호만들기백준 algorithm 2020. 6. 17. 15:44
=> 입력값의 범위가 작기 때문에 브루트 포스로 해결할 수 있습니다. ** 본인이 작성한 코드에는 정렬의 과정이 표현되어있지 않기 때문에, 함수 진입 전에 alpha vector의 sort과정이 필요합니다. #include #include #include #include using namespace std; bool check(string &password) { int conso=0; int vowel=0; for(char x : password) { if(x == 'a' || x=='e' ||x=='i' || x == 'o' || x== 'u') { vowel ++; } else{ conso++; } } return conso >= 2 && vowel >=1; } void go(int n, vector..
-
백준 2839 - 설탕 배달백준 algorithm 2020. 6. 5. 23:02
=> 브루트 포스 문제는 아니지만, 브루트 포스 문제로 해결하였습니다. 5를 3보다 더 많이 써야 효율적인 알고리즘입니다. 5를 더 많이 쓰기 위해 이중for문의 안쪽에 5를 위치하였습니다. 그후 3를 바깥쪽 for문에 위치하였습니다. 입력 받은 값과 i j와 3 5 를 곱한 값이 같은지 확인합니다. 이중for문이 끝나도 원하는 값이 없을 경우 -1을 출력합니다. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; int FiveLimit = (N / 5); int ThreeL..
-
백준 10973 - 이전 순열백준 algorithm 2020. 6. 5. 22:23
=> 이전에 풀었던 다음 순열과 같은 문제입니다. => prev_permutation() 함수를 사용할 줄 안다면 쉽게 풀 수 있는 문제입니다. https://codingham.tistory.com/145 백준 10972 - 다음 순열 => STL의 Algorithm 헤더에는 next_permutation과 prev_permutation 함수가 있습니다. (Library) => 해당 함수를 통해 구현할 수 있는 간단한 문제입니다. => 시간이 될 때 직접 구현해보는 방향으로 다시 풀어보.. codingham.tistory.com => 위의 포스팅을 확인하시면 쉽게 알 수 있습니다. #include #include #include #include using namespace std; int main() {..