본문 바로가기

시뮬레이션

 (13)
[Python] 19778번 Игра https://www.acmicpc.net/problem/19778 24/05/20  그룹 연습 문제로 풀었던 문제다. 간단한 게임 이론 + 구현 문제다. 최적의 전략을 생각하는 것이 그다지 어렵지는 않지만, 이를 실제로 구현하는 것이 전략을 생각하는 난이도에 비해서 조금 까다로운 편이다. 골드 5에 비해 난이도가 낮다고 생각이 되어서 낮게 측정했다. 문제 접근 방식:  러시아어로 되어 있는 문제이기 때문에 번역을 하면 다음과 같이 번역할 수 있다. 문제 번역:체육 수업 시간에 1학년 페티야와 바샤가 흥미로운 게임을 하고 있습니다. 남학생들 앞에 높이가 다른 $n$개의 기둥이 일렬로 서 있습니다. 남학생들은 $m$개의 반지를 가지고 번갈아 가며 기둥에 던지는데, 기둥에 이미 반지가 있으면 이 기둥에 반지..
[Python] 31218번 자료 구조의 왕 https://www.acmicpc.net/problem/31218 31218번: 자료 구조의 왕 흐즈로는 어느 날 집 주변 잔디밭에 무성히 자란 잔디를 보고, 새로 산 잔디깎이 로봇의 성능을 시험해 보기로 했습니다. 잔디밭은 $n$개의 행과 $m$개의 열을 가진 2차원 격자로 구성되어 있으며, www.acmicpc.net 24/01/10 실수할 수도 있는 구현 문제로, 생각 없이 구현하다가는 시간 초과를 받을 수도 있는 문제이다. 약간의 세심함이 필요한 문제다. 문제 접근 방식: 초반 접근 방식은 문제에서 요구하는 것 처럼 쿼리 1, 쿼리 2, 쿼리 3에 대한 함수를 각각 구현하여, 각 요청을 받을 때마다 해당 함수를 불러오는 방식으로 구현했다. 나이브하게 구현했더니 시간초과가 났다. 문제는 쿼리 3에..
[Python] 14503번 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 24/01/07 구현/시뮬레이션 문제로, 문제에서 요구하는 바를 그대로 구현하면 맞았습니다를 받을 수 있는 정직한 문제다. 문제 접근 방식: 이 문제를 접근할 때에 기존에 이렇게 $N \times M$형태의 map이 주어지고 이 위에서 BFS나 DFS를 진행하는 문제를 풀어봤다면 어떻게 접근할지 조금은 감이 잡힐 수 있을 것이다. 북, 동, 남, ..
[Python] 16891번 탄성 충돌 / 22295번 twOBoOgEr https://www.acmicpc.net/problem/16891 16891번: 탄성 충돌 탄성 충돌은 운동 에너지가 보존되는 충돌이다. 일차원 상에서 질량이 m1, m2인 두 물체가 각각 속도(여기서 속도는 방향을 포함하는 양이다) u1, u2로 운동하다가 탄성 충돌하면 충돌 후 두 물체 www.acmicpc.net https://www.acmicpc.net/problem/22295 22295번: twOBoOgEr 채점 및 기타 정보 예제는 채점하지 않는다. www.acmicpc.net 23/09/01 두 문제는 코드가 완벽하게 같은 것은 아니지만, 거의 비슷한 코드로 해결할 수 있는 문제로, 해결 방법을 올려보고자 한다. 첫 번째 접근 방식: 첫 번째 접근 방식은 다음 영상을 참조했다. https:..
[Python] 23747번 와드 https://www.acmicpc.net/problem/23747 23747번: 와드 와드를 설치하지는 않았지만, 한별이의 최종 위치의 위, 아래, 왼쪽, 오른쪽 칸은 시야로 확보하고 있다. 지나온 경로를 모두 시야로 확보하지는 않는다. www.acmicpc.net 22/11/21 BFS문제에 시뮬레이션을 곁들인 문제로, 문제에서 주어지는 상황을 그대로 시뮬레이션하여 쉽게 해결할 수 있는 문제이다. 다만, 파이썬으로 해결하려고 한다면 시간초과에 유의해서 접근해야 풀 수 있는 문제이다. 문제 접근 방식: 먼저, 문제에서 주어진 정보대로 그래프의 크기, 그래프, 한별이의 현재 위치, 여행 기록을 모두 입력으로 받았다. 이후, 한별이의 여행기록을 for문으로 하나하나 돌리며 시뮬레이션을 해보는데, 와드를 놓..
[Python] 2661번 좋은수열 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 22/10/06 전형적인 백트래킹 문제로, 좋은 수열이 되는 조건을 잘 따라가며 시뮬레이션하면 되는 문제이다. 문제 접근 방식: 문제를 해설하기에 앞서, 먼저 N = 8일 때의 찾는 과정을 도식화한 그림을 보자. 우리는 좋은 수열 중 가장 작은 수열을 찾는 것이 목적이다. 이 그림은 이를 찾기 위해 3가지 조건을 지키면서 탐색을 진행하는 과정을 나타낸 것으로, 3가지 조건은 다음과 같다. 1. 가장 작은 수열..
[Python] 14382번 숫자세는 양 (Large) https://www.acmicpc.net/problem/14382 14382번: 숫자세는 양 (Large) 예제 입출력 1번에 대해서, 2 × 0 = 0, 3 × 0 = 0 등등으로 이어지므로, 블리트릭스는 0외에는 다른 숫자를 기록할 수 없을 것이며, 따라서 영원히 잠에 들 수 없다. 예제 입출력 2번의 경우, 1, 2, 3, 4, www.acmicpc.net 22/09/25 단순한 시뮬레이션 문제로, 엄밀한 증명은 하지 않았으나 누구나 쉽게 떠올릴 법한 풀이로 해결한 문제이다. 문제 접근 방식: 먼저 문제에서 주어진 것처럼 계속 숫자를 키워나가며 수를 기록해갔다. 근데, INSOMNIA를 어떻게 판단하느냐가 관건이였다. 영원히 잠에 들지 못하면 INSOMNIA를 출력한다고 했는데, 반복문으로는 영원..
[Python] 1455번 뒤집기 II https://www.acmicpc.net/problem/1455 1455번: 뒤집기 II 세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고 www.acmicpc.net 22/09/23 전형적인 그리디 문제로, 문제 상황을 잘 시뮬레이션하면 되는 문제이다. 문제 접근 방식: 먼저, 문제 상황을 보자. 문제는 모든 동전을 뒤집어서 앞면으로 만들고자 하는 것이 목표이고, 그때의 뒤집는 횟수를 최소화하고 싶은 것이 최종적인 목표이다. 한 동전을 선택하면, 맨 위의 좌측 동전부터 선택한 동전까지, 그 직사각형에 해당하는 영역만큼의 동전이 모두 뒤집힌다는 사실을 보고,..

티스토리툴바