tose33

https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net dfs로 돌 두개를 놓는 모든 경우를 만들어낸다. bfs로 상대돌(2) 그룹이 빈틈없이 애워싸였는지 판단한다. 상대돌(2)에서 시작해서 다음칸이 상대돌(2)면 계속 이동한다. 만약 다음칸이 0인 경우가 있다면 해당 그룹은 애워싸이지 않았다는 의미다. 이때 바로 bfs를 탈출하지 않고 일단 bfs를 계속 진행한다. ( 해당 상대돌 그룹을 모두 방문처리하기 ..

https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net dfs 를 칭찬의 횟수만큼 돌리면 시간초과다. dfs 를 루트에서부터 딱 한번만 돌릴수 있는 방법이 있는데, 칭찬받은 직원과 수치를 저장해놓고 루트에서부터 내려오면서 수치가 누적되게 하는 방법이다.

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 처음에 단순하게 생각해보면 그냥 A 의 모든 문자열을 돌면서 S 에서 빼주면 되는게 아닌가 싶지만 아래와 같은 예외가 있다. S="abbb" A = {"b", "ab"} 일 경우 만약에 b 부터 S 에서 모두 빼버리면 a 가 남기 때문에 모두 없앨수가 없다. 하지만 ab 부터 지우면 bb 가 남고 그 후 b 를 모두 지워주면 모두 없앨수 있다. 따라서 단순하게 S 에서 A 에..

https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 이 문제는 next_permutation 을 돌리면 해결된다. next_permutation 은 중복된 결과를 제외하기 때문이다. 그냥 dfs 를 이용해서 풀려고하면 보통 순열을 만드는 것과는 조금 로직이 추가된다. https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러..