전체 글 (21) 썸네일형 리스트형 [알고리즘 문제] 백준 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차원이 되면서 영역을 빼고 더하는 부분이 생긴.. [알고리즘 문제] 백준 9019번 DSLR 9019번: DSLR (acmicpc.net) 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 한 수에서 여러 명령을 수행해 다른 값으로 만드는 문제다. 아이디어 만약 문제를 보고 수학 계산으로 해결할 수 있을 거라 생각했다면 함정에 빠진 것이다. 숫자 사이를 공식으로 구할 방법은 없으며, 각 숫자를 그래프의 노드로 보고 DSLR 명령을 노드 사이의 간선으로 생각한다면 BFS를 통해 둘 사이의 거리를 구할 수 있다. 1. 초기 값에서 시작하는 BFS 큐를 만든다. 2. 현재 위치에서 D, S.. 이전 1 2 3 4 5 6 7 다음
