C++
-
백준 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..
-
백준 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..
-
백준 2309 - 일곱난쟁이백준 algorithm 2020. 5. 16. 00:56
=> Brute Force 문제이다. => 모든 경우의 수를 탐색해보면 알 수 있다. 알고리즘은 아래와 같다. 배열을 입력받으며, 전체 난쟁이(9명)들 키의 합을 구한다.(sum) 배열을 sort 시킨다. STL을 써도 무방한다. ( 이 경우, 배열의 크기 또한 정해져 있다.) 해당 배열을 i가 index 0부터 9까지 탐색한다, j는 i+1부터 9까지 탐색한다. i, j index 값을 sum에서 뺏을 때, 100이 되는 i와 j를 구한다. => 위의 방법을 통해 제외되는 두 명의 난쟁이를 구할 수 있다. *** 본인은 원하는 난쟁이를 구한 경우, 프로그램을 끝내지 않고, 모든 경우의 수를 탐색하도록 하여 여러 번 틀렸었다. *** 원하는 i와 j를 찾았을 경우, 프로그램을 중지시켜주는 것이 정답을 맞..
-
백준 11053 - 가장 긴 증가하는 부분 수열백준 algorithm 2020. 5. 9. 12:42
=> DP 문제이다. => 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. => 수열 A =[10, 20, 10, 30, 20 ,50] => 가장 긴 증가하는 부분 수열 A = [10, 20, 30, 50] => D[N] : A[i] 를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 => D[i]는 A[i]를 반드시 포함하여야 한다. => 위의 그림을 보면 어떤 방식으로 이루어지는지 알 수 있다. **가장 긴 증가하는 부분 수열 구하는 알고리즘 for(int i=0; i N; for(int i=0; i> A[i]; } int D[N]; for(int i=0; i
-
백준 2193 - 이친수백준 algorithm 2020. 4. 23. 17:39
=> DP 문제이다. => DP [i][j] => i : 몇 자릿수인지 나타냄 => j : 어떤 숫자로 끝나는지 나타냄 DP[i][0] = DP[i-1][0] + DP[i-1][1] => 0으로 끝나는 수의 경수, 앞의 수가 1이어도 되고 0이어도 된다. DP[i][1] = DP[i-1][0] => 1으로 끝나는 수의 경수, 앞의 수가 0이어야 된다. 위의 식대로 풀어도 된다. 본인은 하나씩 손으로 풀어보며 식을 세우게 되었다. DP[i] = DP[i-1] + DP[i-2] => 위의 식을 통해 원하는 값을 얻을 수 있다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr)..