백준 algorithm
-
백준 10972 - 다음 순열백준 algorithm 2020. 6. 5. 22:12
=> STL의 Algorithm 헤더에는 next_permutation과 prev_permutation 함수가 있습니다. (Library) => 해당 함수를 통해 구현할 수 있는 간단한 문제입니다. => 시간이 될 때 직접 구현해보는 방향으로 다시 풀어보겠습니다. => 해당 함수는 vector든, 일반 배열이든 해당 배열의 처음과 끝 부분을 매개변수로 주면 그다음 함수가 있을 경우, true를 return 하고, 아닐 경우 false를 return 합니다. => 또한 해당 배열을 다음 배열로 미리 바꾸어주는 동작을 합니다. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false)..
-
백준 1316 - 그룹 단어 체커백준 algorithm 2020. 6. 4. 01:37
=> 단순한 구현 문제입니다. => string을 사용하고 bool형 array를 사용하여 구현할 수 있습니다. 알파벳을 담을 bool형 array를 생성합니다. 현재의 단어의 글자를 탐색하며 처음 나온 알파벳인지, 나왔던 알파벳인지를 확인합니다. 처음 나온 알파벳일 경우, 해당 알파벳을 방문했다고 표시해줍니다. 처음 나온 알파벳이 아닐 경우, 이전 알파벳과 같은 알파벳인지, 같지 않은지 확인합니다. 같지 않을 경우 그룹 단어에 해당이 안됩니다. 해당하는 경우에 okay라는 bool형 변수를 true로 바꿔주고, 해당 변수를 통해 단어의 개수를개수를 세는 cnt의 개수를 올릴지 말지 정합니다. 모든 순서가 끝나면 방문하였던 알파벳 arr를 초기화시켜주고, okay 변수 또한 초기화 시켜줍니다. => 저는..
-
백준 15651 - N과 M(3)백준 algorithm 2020. 6. 3. 21:43
=> 브루트 포스 문제입니다. => 기존의 N과 M 문제와의 차이점이라고 하면, visited [] 배열이 필요가 없다는 것입니다. => 해당 문제는 중복을 허용하기 때문에 visited가 없이 바로 코드를 짜면 가능합니다. https://codingham.tistory.com/142 백준 15650 - N과 M(2) => 브루트 포스 문제입니다. => 기존의 N과 M문제에서 힌트를 받아 풀 수 있습니다. => 오름차순으로 해야되는 것만 염두에 두면 풀 수 있습니다. https://codingham.tistory.com/41 백준 15649 - N과 M(1) 백트.. codingham.tistory.com https://codingham.tistory.com/41 백준 15649 - N과 M(1) 백트래..
-
백준 15650 - N과 M(2)백준 algorithm 2020. 6. 3. 21:23
=> 브루트 포스 문제입니다. => 기존의 N과 M문제에서 힌트를 받아 풀 수 있습니다. => 오름차순으로 해야되는 것만 염두에 두면 풀 수 있습니다. https://codingham.tistory.com/41 백준 15649 - N과 M(1) 백트래킹과 관련된 기초 문제이다. 본인은 백트레킹의 개념은 알지만 코드로 구현함에 있어 어려움을 겪어, 다른 사람들의 코드를 보며 썼다. 길이가 M이므로, cnt가 M이 될때까지 해당 Backtracking codingham.tistory.com => 위의 문제를 참조하면 쉽게 풀 수 있습니다. #include #include #include bool visited[10]; //false로 초기화 int arr[10]; using namespace std; voi..
-
백준 1748 - 수 이어 쓰기 1백준 algorithm 2020. 6. 2. 23:15
=> 브루트 포스 문제입니다. => 모든 숫자를 탐색하며 길이를 재 더할 경우, 시간초과의 늪에 빠지게 됩니다. #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 ans=0; for(int i=1; i N; long long ans =0; for( int start=1, len=1; start N) { end = N; } ans += (long long)(end - start +1)*len; } cout
-
😭백준 6064 - 카잉 달력백준 algorithm 2020. 6. 2. 22:34
=> 브루트 포스 문제입니다. => 시뮬레이션 문제로 생각하여 모든 경우의 수를 확인할 경우 시간 초과의 덫에 걸리게 됩니다. => 우선 x를 맞춰두고 그 이후에 맞는 y가 있는지 확인하여야 합니다. => 찾은 값이 두 수의 최소공배수를 넘지 않도록 유의하여야 합니다. 최소공배수를 구하는 식은 최대공약수를 구하는 식의 도움을 받습니다. 저는 유클리드 호제법을 사용하였습니다. int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; } int lcm(int a, int b) { return a * b / gcd(a, b); } #include #include #include using namespace std; int..
-
백준 1107 - 리모컨백준 algorithm 2020. 6. 2. 14:19
=> 브루트 포스 문제입니다. 이동할 채널 C를 정합니다. C에 포함되어있는 숫자 중에 고장 난 버튼이 있는지 확인합니다. 고장 난 버튼이 포함되어 있지 않다면 |C-N|을 계산해 +나 -버튼을 몇 번 눌러야 하는지를 계산합니다. => 위의 방식에 따라 문제를 풀이합니다. => 고장난 버튼을 확인하기 위해 broken []이라는 bool형 array를 사용하였습니다. => 채널은 50만이지만, 숫자 버튼을 눌러서 이동하는 채널은 100만까지 허용하여야 합니다. (현재의 위치 100 때문) => 현재 위치에서 +or -를 눌러서 타겟하는 C로가는 방법 현재 위치에서 + or -를 눌러서 타깃 C로 이동하는 방법 채널 버튼을 눌러 타겟으로 이동한 다음 버튼을 눌러 이동하는 방법 => 위의 두가지 중에 최소의..
-
백준 1476 - 날짜 계산백준 algorithm 2020. 6. 1. 00:12
=> 브루트 포스를 활용해 우리가 알고 있는 연도 1년부터 올라가며 주어진 E S M과 같은 지 확인하면 됩니다. E S M과 비교하며 증감을 연속하는 변수 세 개를 설정합니다. (goingE, S, M) E S M 과 변수들이 같아질 때까지 while문을 통해 연속적으로 year의 값을 증가시킵니다. E S M 각 변수들이 지닐 수 있는 최대의 숫자까지 갈 경우 다시 1로 돌아가도록 합니다. E S M과 going 변수들이 모두 똑같아졌을 경우의 Year 변수를 출력합니다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr..