알고리즘 썸네일형 리스트형 백준 26156: 나락도 락이다 아이디어 & 코드 아이디어 뒤에서부터 보면서 'K', 'C', 'O'를 찾으면서 각 인덱스에서 "OCK"를 만들 수 있는 경우의 수를 구한다 그리고 값이 'R'인 모든 인덱스에서, 그 인덱스에서 1. "OCK"를 만들 수 있는 경우의 수와 그 인덱스의 2. 앞에 있는 문자의 개수만큼 2의 거듭제곱을 한 값을 구한다. 그리고 1과 2를 곱해 나온 값을 모두 더하면 답이 나온다 쉽게 이해하려면 R인 인덱스 기준으로 보면 된다 1. R인 인덱스 뒤에서 "OCK"를 만들 수 있는 경우의 수 -> 그 R을 가지고 ROCK을 만들 수 있는 경우의 수 2. 앞에 있는 문자의 개수만큼 2의 거듭제곱을 한 값 -> R 앞에 있는 문자 모두를 넣거나 넣지 않거나 하는 경우의 수 1과 2를 곱하면 그 R을 기준으로 가능한 ROCK으로 끝나는.. 더보기 백준 20955 아이디어 문제에서 말하는 사이클이 없는 그래프인 트리를 위한 edge의 삭제, 추가 횟수를 구하려면 다음과 같은 순서를 거쳐야 한다 1. 주어진 edge 중에서 사이클을 생성하는 edge를 다 쳐낸다 2. 주어진 edge로 만들어지는 그룹의 개수를 구한다 3. 쳐낸 edge 수 + 그룹 개수 - 1이 답이 된다 1번은 MST의 Kruskal 알고리즘에서 나오는 union find 알고리즘을 통해서, 2번은 DFS로 구하면 된다 union find 알고리즘을 처음 구현해봐서 포스팅하게 되었다. 코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int N, M; vector E; bool visited[100000]; int .. 더보기 이전 1 2 다음
