브루트포스12 [알고리즘] 외판원 순회 2 (백준 10971번) 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원 순회, 일명 TSP라고 불리는 문제다. 외판원은 모든 도시를 최소 비용으로, 단 한 번 방문한 도시는 다시 방문할 수 없다는 조건 하에 순회하게 된다. (마지막 도시에서 출발 도시로 돌아오는 경우 제외) 도시를 방문하는 순서 케이스들을 찾아야 하기에 순열을 구하는 문제다. 이 경우는 N의 크기가 10 이하이기 때문에 백트랙킹으로 모든 경우를 찾을 수 있다. Solution 백트랙킹으로 순열을 구할 때와 조합을 구.. 2020. 10. 4. [알고리즘] 가르침 (백준 1062번) 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 백트랙킹을 통한 완전탐색을 하는 문제다. 비트마스크와 배열 둘 중 하나를 이용해서 풀 수 있다. 2개의 메모리, 시간 효율 차이는 거의 없다. 그냥 똑같은 수준이다. Solution 공통적으로 행해야 할 것은 우선 가르칠 수 있는 단어가 5개 미만이면 어떤 글자도 읽을 수 없다. 만약 5개 이상이라면 남극언어의 기본 시작단어, 끝단어를 이루고 있는 알파벳들 'a c t n i' 5가지부터 추가시키고 시작한다. 1. boolean 배열로 가르침 여부 체크 .. 2020. 10. 3. [알고리즘] 비트마스크 (BitMask) 비트마스크 (BitMask) 정수로 집합을 나타낼 수 있는 기법 비트마스크를 사용하는 이유 완전 탐색 시 재귀호출 없이 모든 경우를 살펴볼 수 있다. (브루트 포스) 집합을 배열의 인덱스로 표현 가능하다. → 메모리 절약 가능 상태가 다이나믹한 경우에 자주 사용한다. 연산 1. 포함 검사 '&' 사용 집합 S에 i가 포함되었는지 검사 : S & (1 2020. 9. 28. [알고리즘] 캐슬 디펜스 (백준 17135번) 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 브루트 포스 + 시뮬레이션 문제이다. 문제의 조건을 좀 헷갈리게 해놔서 조건을 잘 파악해서 어떻게 모듈화할지 생각해야 한다. Solution 1. dfs (백트랙킹 함수) public static void dfs(int index, ArrayList archers) { if(archers.size() == 3) { //시뮬레이션 int sim_map[][] = new int[N][M]; for(int i = 0;i < N;i++) sim_map[i] = map[i].clon.. 2020. 9. 28. 이전 1 2 3 다음
