초기 아이디어 조합이 가장 먼저 떠올랐다. 알파벳 스물여섯개 중 주어진 숫자만큼 조합으로 이용해서 뽑고, 단어마다 해당 단어가 뽑은 단어에 포함되어 있는지를 셈해보는 것이다. 최악의 경우 21C10 의 경우의 수에 각각 50개의 단어를 판별해야 한다. (acnti 다섯글자는 반드시 있어야 하므로) 대충 보면 시간 초과가 날 것 같진 않은데 ... 비슷한 문제를 재귀를 이용한 조합으로 단순히 풀었다가 시간 초과가 난 기억이 있어서 그냥 비트마스킹 연습도 할겸 비트마스킹으로 풀어보기로 한다. 비트마스킹은 사실 근본적인 알고리즘이라기 스킬의 일종이다. 이진법으로 나타낸 수의 각 자리를 하나의 불리언이라고 생각하고 특정 조합을 하나의 숫자로 나타내는 것이다. 예컨대 13을 이진수로 표현하면 1101 인데 '첫번..
전체 글
초기 아이디어 부분적으로 최단거리를 구하는 문제이므로 DFS, BFS 가 쓰일 것 같다는 생각은 바로 들었는데, 다소 복잡하다. 처음엔 "가장 먼 두 지점" 이라는 말에서 DFS 를 생각했는데 돌아서 가면 안된다는 조건 때문에 결국 가장 먼 지점이라고 해도 BFS 로 풀어내야 한다는 것을 깨달았다. 모든 육지에 대해서 BFS 를 수행하고 가장 멀리까지 갈 수 있는 지점을 계산 해보기로 했다. 문제풀이 1. 모든 두 지점을 순회하면서 BFS #include using namespace std; int n, m; char a[51][51]; int visited[51][51]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int bfs(int sX, int..
초기 아이디어 최단 거리를 묻는 문제는 우선 직관적으로 DFS, BFS 를 생각할 수 있다. 더 코드가 짧은 DFS 를 하기로 해보고 연습겸 BFS 로도 구현해보기로 한다. 문제 풀이 1. DFS #include using namespace std; int a[101][101]; int visited[101][101]; int n, m, ret=987654321; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; void dfs(int x, int y, int dept){ if(x==n-1 && y==m-1) { ret = ret>dept?dept:ret; return; } for(int i=0;i> n >> m; for(int i=0;i> m; for(in..