백준
-
백준 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
-
백준 2941 - 크로아티아 알파벳카테고리 없음 2020. 6. 17. 16:36
=> 문자열을 다룰 줄 아는지 물어보는 문제입니다. => string 헤더를 제대로 이해하고 내장되어있는 함수들을 통해 풀 수 있습니다. => 저는 처음에 if문으로 구현할 수 있을 줄 알았는데, 해당 방식으로 하면 참조하지 말아야 할 위치를 참조하는 등의 잘못이 생깁니다. => string의 find() 함수와 replace 함수를 적절히 사용하여야 합니다. 크로아티아 알파벳을 담을 배열을 생성하고 초기화한다. 해당 크로아티아알파벳을 찾을 경우 해당 구간을 *로 바꿔준다 위의 과정은 같은 단어가 여러 번 들어가 있을 경우를 위해 다시 검색되지 않도록 하기 위해서 하는 과정이다. 해당 과정을 진행하며, 크로아티아 알파벳의 개수와 해당 알파벳의 길이를 점진적으로 구한다. 문자열의 길이 - 크로아티아 알파벳..
-
백준 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() {..
-
백준 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) 백트래..