Algorithm/문제 풀이62 [알고리즘] 줄 세우기 (백준 2252번) 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net N, M의 크기만 봐도 알 수 있지만 그래프 완전탐색 문제이며 N은 정점, M은 간선의 수를 나타낸다. 정확히는 위상 정렬 문제다. 각 노드보다 앞서 있는 노드들이 먼저 출력되어야 하는 형태를 가진다. Solution import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStre.. 2020. 9. 28. [알고리즘] 집합 (백준 11723번) 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 가장 기본적인 비트마스크 문제다. 총 M의 크기가 최대 3백만이고 메모리 허용량이 4MB 밖에 되지 않기에 비트마스크를 필히 활용해야 한다. Solution 비트마스크 연산 방법대로 분기해서 처리했는데도 시간초과가 나서 당황했는데 자바의 bufferedReader와 bufferedWriter를 써주지 않아서 그랬다. 참고로 all 연산은 1~20까지의 수를 추가하는 것인데 이는 (0~20) = SET의 21 추가후 - 1 (1~20) = SET에서 - 1 이기에 최종적으로는 SET에 21을 추가후 .. 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. [알고리즘] 영화감독 숌 (백준 1436번) 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 브루트 포스 문제다. 시간복잡도를 생각해봤을 때, 정말 최대로 가정해봐도 1천만번 정도기에 단순히 1씩 증가시키는 연산으로도 충분히 풀만하다. Solution 666, 1666, 2666 이런식으로 1000단위로 증가하다가 6660, 6661과 같은 구간이 생길 것이다. 처음에는 이걸 일일이 구할까 하다가 브루트 포스 문제이니 좀 더 단순하게 생각해보자 해서 그냥 1씩 증가시켜서 나오는 수마다 세상의 종말 수인지를 검사해서 count를 증가시키는 방식으로 구했.. 2020. 9. 27. 이전 1 ··· 4 5 6 7 8 9 10 ··· 16 다음
