백트래킹
-
BOJ) 가르침 (1062 번)알고리즘/백준 2021. 2. 18. 11:40
가르침 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다. 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 구하는 문제다. 단어는 모두 소문자로 주어지고, 1
-
BOJ) 스도쿠 (2580 번)알고리즘/백준 2021. 2. 14. 23:13
스도쿠 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠의 조건에 따라 로직을 짜주었고, 백트래킹을 이용했다. (백트래킹을 사용하지 않으면 시간초과가 난다) 우선, 재귀 함수를 사용할 예정이어서 모든 스도쿠 맵을 돌면서 빈칸인 곳을 찾는 것이 비효율적이라고 생각했다. 그래서, 스도쿠 맵을 저장할 때, 비어있는 칸의 위치를 List에 저장해서 빈 칸들만 순회하도록 만들었다. 그리고, 빈 칸들에 들어갈 수 있는 모든 수를 넣어보면서, 적합한 수를 넣어주었다. 모든 수를 검사할 때는 빈칸의 가로와 세로에 어떤..
-
BOJ) 신기한 소수알고리즘/백준 2020. 7. 21. 15:15
신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수� www.acmicpc.net 풀이 처음에는 모든 숫자에 대해 DFS를 진행하면서 답을 구하려고 시도했다. 하지만 문제의 최대 조건인 n=8인 경우에 엄청난 시간이 소요되면서, 가지치기가 더 필요한 것을 느꼈다. 문제의 조건을 자세히 봤다. n=4 인 경우에 나오는 수를 살펴보면, 첫번째 자리에는 {2,3,5,7} 만 오고 나머지 자리에는 {1,3,7,9}만 나와있음을 확인했다. 이 말은, n=3인 경우, n=2인 경우에도 앞의 자리가 위의 네가지 숫자 말고는 올 수..