SWEA
-
[SWEA] 3135. 홍준이의 사전놀이Problem_Solving/Graph 2020. 1. 5. 23:49
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6pTXqsXUDFAWS 시간 복잡도를 어림잡아 계산해보니 특별한 알고리즘을 사용하지 않아도 시간 안에 실행될것 같았지만, 문제의 힌트에 Trie라는 개념을 사용하면 된다는 말에, 구글링을 해서 Trie를 익히고 적용하여 풀게 되었습니다. https://twpower.github.io/187-trie-concept-and-basic-problem [Algorithm] 트라이(Trie) 개념과 기본 문제 Practice makes perfect! twpower.github.io 이 분 글..
-
[SWEA] 2891. 분수 스도쿠 - DFS & 가지치기Problem_Solving/Graph 2019. 2. 11. 21:34
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do 이 문제를 보고 먼저 든 생각은, 임의의 빈칸에 대해 넣을 수 있는 숫자의 목록을 반환하는 함수를 만들어야겠다 였습니다. 그러기 위해서 그 칸이 포함된 행, 열, 3x2 격자칸을 확인해보고, 분수 칸이라면 다른 쪽(분모라면 분자, 분자라면 분모)에 있는 숫자를 확인해서 1~9 중의 수에서 넣을 수 있는 수를 반환합니다. 그래서 각 빈칸마다 넣을 수 있는 수의 목록을 반환 받아서 하나씩 넣어보면서 막힌다면 다시 되돌아와서 다른 수를 넣어보는 식으로 하면 되겠죠. 그런데 이 문제의 제한 시간은 1초입니다. 만약 이 문제..