전체 글 (168) 썸네일형 리스트형 백준 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 문제 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 www.acmicpc.net 이분탐색과 BFS(혹은 DFS)를 활용한 문제. 이분탐색은 '가능한 최대'라거나 '가능한 최소' 등의 키워드에 맞춰 사용하면 될 것 같다. /* 배열에서 이동 */ #include #include #include #include using namespace std; int n, small, large; int map[100 + 1][100 + 1]; bool is_visit.. 백준 2629 양팔 저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 백 트랙킹과 DP를 활용하는 문제다. 적은 N과 상대적으로 널럴한 시간 제한을 보자마자 백트랙킹 감이 오긴했으나... 아직 recursion 알고리즘을 짜는 게 미흡한 것 같다. 이렇게 ''완전탐색''을 하면 반드시 풀 수 있는 문제를 백트랙킹과 DP로 구현할때는 각 케이스에서 발생 가능한 모든 사례를 Recursion으로 처리하는 연습을 해야겠다. ㅠㅠ /* 양팔 저울 */ #include #in.. 백준 1613 역사 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. �� www.acmicpc.net 플로이드 워셜 알고리즘을 활용하는 문제다. N이 400밖에 안되므로 O(N^3)을 해도 6400만이라서 시간초과에 걸리지 않는다. /* 역사 */ #include #define MAX_N 400 + 1 #define MAX_EDGE 50000 + 1 using namespace std; int n, k, s; int order[MAX_N][MAX_N]; int main(void) { .. 이전 1 ··· 37 38 39 40 41 42 43 ··· 56 다음