알고리즘

백준 1062번 가르침 (C++)

문제설명 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제해결 전체적인 코드 흐름은 다음과 같다. default_alpha에 항상 들어가는 5개의 알파벳을 넣어준다. 최적화를 하기 위해 백트래킹에서는 default_alpha에 해당하는 문자들은 탐색하지 않았다. 따라서 문장들을 탐색하면서 default_alpha에 해당하는지 검사한다. 만약 default_alpha에 속하면 이미 검사를 완료했다는 의미로 word_dup을 1로 바꿔주..

백준 1759번 (C++)

문제 설명 문제 해결 수의 크기가 크지 않으면서, 모든 경우의 수를 탐색해야 하므로 완전 탐색인 DFS 문제임을 알 수 있다. 크게 어려운 문제는 아닌데, 처음에 visit 배열을 만들고, for 문을 돌면서 DFS 함수에 들어가는 식으로 잘못 접근했다가 시간이 조금 걸렸다. 여기서는 그래프 탐색이 아니고 암호 선택의 문제이기 때문에, 해당 알파벳을 택한다 / 택하지 않는다의 두 가지 경우밖에 없다. 이 경우에 한해 재귀를 돌면 된다. 다시 방문할 일이 없으므로 visit 배열도 불필요하다. 나는 아직도 재귀의 개념이 직관적으로 와닿지가 않는다. 그게 다양한 dfs 문제를 풀었음에도 불구하고 잘 막히는 이유인 것 같다. 문제를 풀 때 먼저 손으로 들어가기 전에 DFS의 정의를 어떻게 해야하는지를 확실히 ..