전체 글 (22) 썸네일형 리스트형 [알고리즘 문제] 백준 1707번 이분 그래프 1707번: 이분 그래프 (acmicpc.net) 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 주어진 그래프에서 정점을 두 집합으로 분리하되, 두 집합 사이에 인접한 점이 없도록 하는 문제입니다. 아이디어 두 집합 사이에 인접한 점이 없다는 말은, 인접한 두 점은 다른 집합이라는 뜻입니다. 이를 통해 각 정점의 집합을 골라가며 그래프를 탐색하면 해결할 수 있습니다. 여기서는 BFS를 사용해보겠습니다. 1. 시작점을 임의의 집합으로 정하고 탐색을 시작합니다. 2. 자신과 인접한 점은 다른 집합으로 표시.. [알고리즘 문제] 백준 16953번 A → B 16953번: A → B (acmicpc.net) 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 주어진 숫자 A에서 다음의 연산을 몇 번 거쳐야 B에 도달하는지 구하는 문제입니다. 1. 2를 곱한다. 2. 1을 수의 가장 오른쪽에 추가한다. (n * 10 + 1) 아이디어 연산에 규칙성이 보이지 않으니 모든 경우를 해보는 수밖에 없습니다. 그래프를 탐색하듯 1번과 2번 규칙을 각각 적용해보며 진행해 봅시다. 1. 숫자 A에서 시작합니다. 2. A에 1번 규칙을 적용시킨 경우와 2번 규칙을 적용시킨 경우를 나누어 연산 수를 재귀적으로 구합니다. 3. A는 둘 중 더 적은 수의 규칙 + 1을 통해 도달 가능합니다. 둘 모두 도달할 .. [알고리즘 문제] 백준 11660번 구간 합 구하기 5 11660번: 구간 합 구하기 5 (acmicpc.net) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 2차원 배열에서 지정한 사각형 구역 내의 합을 구하는 문제입니다. 아이디어 구간합 방법의 2차원 예입니다. 1차원 배열에서의 구간 합의 경우, 0부터 i까지의 합을 캐시하면, 구간 합은 O(1) 시간에 구할 수 있습니다. 2차원의 경우도, 같은 아이디어를 적용해 O(1) 시간에 구간합을 구할 수 있습니다. 단, 2차원이 되면서 영역을 빼고 더하는 부분이 생긴.. 이전 1 2 3 4 5 6 ··· 8 다음
