알고리즘 · 26
그대로 따라 하기와 모두 해 보기
이야기가 시키는 대로 한 걸음씩 따라 하고, 후보를 하나도 빼놓지 않고 넣어 봐요.
알고리즘의 첫걸음은 꾀를 내지 않는 거예요.
아래 예제의 로봇은 1번부터 n번 칸까지 있는 복도에서 L(왼쪽)·R(오른쪽) 명령대로 한 칸씩 움직이고, 벽에 막히면 제자리에 있어요.
명령이 끝났을 때 goal번 칸에 서게 되는 출발 칸을 모두 찍고, 마지막에 그 개수를 찍어요.
n, goal = map(int, input().split())moves = input().strip()count = 0for start in range(1, n + 1): # 모두 해 보기: 출발 칸 후보 n개 pos = start # 후보마다 처음부터 다시 for m in moves: # 그대로 따라 하기: 명령 하나에 한 걸음 if m == "L" and pos > 1: pos -= 1 elif m == "R" and pos < n: pos += 1 if pos == goal: print(start) count += 1print(count)const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, goal] = lines[0].split(" ").map(Number);const moves = lines[1].trim();let count = 0;for (let start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 let pos = start; // 후보마다 처음부터 다시 for (const m of moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m === "L" && pos > 1) pos--; else if (m === "R" && pos < n) pos++; } if (pos === goal) { console.log(start); count++; }}console.log(count);import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, goal] = lines[0].split(" ").map(Number);const moves: string = lines[1].trim();let count: number = 0;for (let start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 let pos: number = start; // 후보마다 처음부터 다시 for (const m of moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m === "L" && pos > 1) pos--; else if (m === "R" && pos < n) pos++; } if (pos === goal) { console.log(start); count++; }}console.log(count);import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), goal = sc.nextInt(); String moves = sc.next(); int count = 0; for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (char m : moves.toCharArray()) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { System.out.println(start); count++; } } System.out.println(count); }}using System; class Program{ static void Main() { string[] first = Console.ReadLine().Split(' '); int n = int.Parse(first[0]), goal = int.Parse(first[1]); string moves = Console.ReadLine().Trim(); int count = 0; for (int start = 1; start <= n; start++) // 모두 해 보기: 출발 칸 후보 n개 { int pos = start; // 후보마다 처음부터 다시 foreach (char m in moves) // 그대로 따라 하기: 명령 하나에 한 걸음 { if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { Console.WriteLine(start); count++; } } Console.WriteLine(count); }}#include <iostream>#include <string> int main() { int n, goal, count = 0; std::string moves; std::cin >> n >> goal >> moves; for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (char m : moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { std::cout << start << '\n'; count++; } } std::cout << count << '\n';}#include <stdio.h> int main(void) { int n, goal, count = 0; char moves[1001]; scanf("%d %d %1000s", &n, &goal, moves); for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (int i = 0; moves[i] != '\0'; i++) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (moves[i] == 'L' && pos > 1) pos--; else if (moves[i] == 'R' && pos < n) pos++; } if (pos == goal) { printf("%d\n", start); count++; } } printf("%d\n", count); return 0;}first = 콘솔.수들읽기();n = first[0];goal = first[1];moves = 콘솔.줄읽기().공백제거();count = 0;반복 (start = 1; start <= n; start++){ pos = start; // 후보마다 처음부터 다시 각각 (m 에서 moves) { 만약 (m == "L" && pos > 1) { pos -= 1; } 아니면 만약 (m == "R" && pos < n) { pos += 1; } } 만약 (pos == goal) { 콘솔.쓰기(start); count += 1; }}콘솔.쓰기(count);6 3 LLLRR
1 2 3 4 4
핵심
- 그대로 따라 하기(시뮬레이션)는 문제의 이야기를 순서 그대로 코드로 옮겨요.
지금 상태를 변수에 담고(여기서는 로봇의 자리pos), 한 걸음마다 규칙대로 고쳐요.
벽 때문에 "오른쪽 수 − 왼쪽 수" 같은 식으로는 답이 안 나오니, 직접 걸어 보는 게 가장 확실해요. - 모두 해 보기(완전 탐색)는 답이 될 수 있는 후보를 하나도 빼놓지 않고 넣어 보고, 조건에 맞는 것만 골라요.
여기서 후보는 출발 칸 1번부터 n번까지예요.
빠뜨린 후보가 없으면 놓치는 답도 없어요. - 후보마다 상태를 처음으로 되돌려요.
예제에서pos = start가 바깥 반복 안에 있는 까닭이에요. - 쓰기 전에 몇 걸음인지 세어 봐요: 후보 수 × 후보 하나에 드는 걸음 수.
이 예제는 n × 명령 수예요.
n개에서 둘을 고르면 n × (n − 1) ÷ 2쌍(n이 200이면 19,900쌍), 넣을지 뺄지를 n번 정하면 2ⁿ가지(n이 20이면 약 100만), 한 줄로 세우는 차례는 n!가지(n이 10이면 약 360만)예요. - 여기서 한 걸음은 명령 하나를 한 번 따라 하는 것(안쪽 반복 한 바퀴)이에요.
이 예제를 우리 채점기에서 재 보니, 1천만 걸음(칸 1만 개 × 명령 1천 개)은 여덟 언어 모두 1초 안에 끝났어요.
1억 걸음(칸 1만 개 × 명령 1만 개)은 C·C++·Java·C#은 1초 안에, JavaScript·TypeScript는 1초쯤에 끝났지만, Python은 시간 제한 4초를 넘겼어요.
크레이콘은 4천만 걸음까지는 끝났고, 5천만 걸음에서는 "너무 오래 걸려서"라며 멈췄어요. - 걸음 수가 넉넉하면 모두 해 보기로 충분해요.
너무 많을 때 비로소 더 빠른 방법을 찾고, 그때도 느린 풀이는 작은 입력에서 빠른 풀이의 답을 맞춰 보는 데 써요.
언어별로 쓰는 법
| Python | for start in range(1, n + 1): 안에서 pos = start로 되돌리고, 명령은 for m in moves:로 한 글자씩.두 개 고르기는 itertools.combinations(nums, 2), 모든 차례는 itertools.permutations(nums)가 만들어 줘요 |
|---|---|
| JavaScript | for (let start = 1; start <= n; start++) 안에서 let pos = start;, 명령은 for (const m of moves).두 개 고르기는 안쪽 반복을 let j = i + 1부터 |
| TypeScript | JavaScript와 같아요 |
| Java | int pos = start;를 바깥 반복 안에 두고, 명령은 for (char m : moves.toCharArray()).글자는 작은따옴표로 비교해요( m == 'L') |
| C# | int pos = start;를 바깥 반복 안에 두고, 명령은 foreach (char m in moves).글자는 'L' |
| C++ | 명령은 for (char m : moves), 글자는 'L'.모든 차례는 정렬해 둔 vector에 std::next_permutation(v.begin(), v.end())을 거짓이 나올 때까지 되풀이해요 |
| C | 명령은 for (int i = 0; moves[i] != '\0'; i++) — 문자열 끝 표시 '\0'까지 번호로 돌아요.글자는 'L' |
| Craykon | 반복 (start = 1; start <= n; start++) 안에서 pos = start;, 명령은 각각 (m 에서 moves).한 번 실행에 돌 수 있는 걸음 수에 한도가 있어서, 넘으면 "너무 오래 걸려서 (끝나지 않는 반복?)"라며 멈춰요 |
자주 하는 실수
후보마다 되돌리지 않았어요
let sum = 0;
for (let x = 10; x <= 12; x++) {
for (const d of String(x)) sum += Number(d);
console.log(x, sum);
}→ 10 1, 11 3, 12 6 — 자릿수 합은 1, 2, 3이어야 하는데, 앞 후보의 합이 남아서 계속 쌓여요
let sum = 0;을 바깥 반복 안으로 옮겨서 후보마다 0에서 시작해요.
두 개 고르기에서 같은 쌍을 두 번 셌어요
int nums[] = {1, 2, 3, 4}, count = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (nums[i] + nums[j] == 4) count++;
printf("%d\n", count);→ 3 — 합이 4인 쌍은 (1, 3) 하나뿐인데, 뒤집은 (3, 1)과 자기 자신과 짝지은 (2, 2)까지 셌어요
안쪽 반복을 j = i + 1부터 시작해요.
쌍마다 한 번만 보고 자기 자신과는 짝짓지 않아서 1이 나와요.
칸을 고치면서 이웃을 읽었어요
cells = list("O..")
for i in range(3):
left = i > 0 and cells[i - 1] == "O"
right = i < 2 and cells[i + 1] == "O"
cells[i] = "O" if cells[i] == "." and left != right else "."
print("".join(cells))→ ... — 답은 .O.예요. 규칙은 "켜진 칸은 꺼지고, 꺼진 칸은 켜진 이웃이 딱 하나일 때 켜진다"이고(left != right가 "딱 하나"라는 뜻이에요), 모든 칸이 한꺼번에 바뀌어야 해요. 그런데 0번 칸을 먼저 꺼 버려서, 1번 칸이 이웃을 볼 때는 이미 꺼져 있었어요
다음 상태는 새 목록에 적고, 다 적은 뒤에 바꿔 끼워요.after = []를 만들어 after.append(...)로 모으고, 반복이 끝나면 cells = after.
그러면 .O.이 나와요.
언어마다 다른 점
문제에 적힌 입력 크기로 걸음 수부터 세어 보는 버릇을 들여요.
그 수가 넉넉하면 가장 단순한 풀이가 가장 좋은 풀이예요.
따라 하기에서 답이 틀리면, 작은 입력을 손으로 한 걸음씩 따라가며 변수 값과 견줘 봐요.
벽 같은 경계에서 한 칸 어긋나지 않았는지부터 봐요.
문제에 적힌 입력 크기로 걸음 수부터 세어 보는 버릇을 들여요.
그 수가 넉넉하면 가장 단순한 풀이가 가장 좋은 풀이예요.
따라 하기에서 답이 틀리면, 작은 입력을 손으로 한 걸음씩 따라가며 변수 값과 견줘 봐요.
벽 같은 경계에서 한 칸 어긋나지 않았는지부터 봐요.