본문 바로가기

구현

 (72)
[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] 14502번 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 24/01/06 BFS와 브루트포스 연습 문제로, 구현하는 중간에 조금 꼬여서 살짝 해멨던 문제이다. 문제 접근 방식: 문제 자체는 단순하다. 벽을 $3$개 세워야만 하고, 그렇게 벽을 세운 뒤에는 BFS를 돌리면 된다. 즉, $64\times 64\times 64 \approx 260,000$번 정도의 BFS를 수행하면 된다. BFS를 진행할 때에는 바이러스가 있는 부분을 큐에 넣고 BFS를 진행하면 된다...
[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] 1092번 배 https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 23/09/03 그리디적으로 접근하면 풀리는 문제로, 구현이 살짝 까다로웠다. 문제 접근 방식: 생각한 방법은 다음과 같았다. 1. 크레인과 박스가 있으면 두 리스트를 모두 내림차순 정렬한다. 2. 만약 가장 무거운 박스와 가장 무거운 무게를 들 수 있는 크레인의 무게제한을 비교했을 때, 가장 무거운 박스가 더 무겁다면 어떻게 하더라도 그 박스는 옮길 수 없으므로, $-1$을 출력..
[Python] 15703번 주사위 쌓기 https://www.acmicpc.net/problem/15703 15703번: 주사위 쌓기 아래 설명에서 k개의 주사위가 쌓여져 있고, 위에서부터 적혀있는 정수가 s1, s2, ..., sk인 주사위 탑을 (s1, s2, ..., sk)로 표현했다. 예제 1의 경우에는 주사위 탑 1개를 만들 수 있다. (1, 2, 4, 5) 또는 ( www.acmicpc.net 23/05/25 구현을 조금 요하는 그리디 문제이다. 문제 접근 방식: 문제 요약을 하면 다음과 같다. 주사위가 주어져 있고, 하나의 주사위의 모든 면에는 같은 눈금이 적혀있다. 이런 주사위들을 모아 주사위 탑을 쌓고자 하는데, 한 주사위에 적힌 눈금이 $5$라면, 그 주사위 위에는 $5$개를 넘어서 주사위를 쌓을 수 없다고 한다. 이럴 때,..
[Python] 26006번 K-Queen https://www.acmicpc.net/problem/26006 26006번: K-Queen 재헌이는 생일 선물로 크기가 $N \times N$인 체스판과 백색 킹 하나, 흑색 퀸 $100\ 000$개를 받았다. 킹은 8방향(상하좌우 및 대각선)으로 한 칸씩 이동할 수 있고, 퀸은 같은 행, 열, 대각선에 있는 상 www.acmicpc.net 22/12/01 그룹 연습 문제로 나왔던 문제를 풀었다. 실버 3치고는 개인적으로 어려웠던 편에 속해서, 실버 2로 충분히 올라가도 될 것 같다. 문제 접근 방식: 전형적인 구현 문제이지만, 구현을 잘 못한다면 어렵게 돌아갈 가능성이 존재한다. 먼저, 나는 흰색 킹이 8방향으로 움직일 수 있다는 점에 착안하여, BFS를 구현할 때처럼 dr, dc배열을 선언해주었..
[Python] 23747번 와드 https://www.acmicpc.net/problem/23747 23747번: 와드 와드를 설치하지는 않았지만, 한별이의 최종 위치의 위, 아래, 왼쪽, 오른쪽 칸은 시야로 확보하고 있다. 지나온 경로를 모두 시야로 확보하지는 않는다. www.acmicpc.net 22/11/21 BFS문제에 시뮬레이션을 곁들인 문제로, 문제에서 주어지는 상황을 그대로 시뮬레이션하여 쉽게 해결할 수 있는 문제이다. 다만, 파이썬으로 해결하려고 한다면 시간초과에 유의해서 접근해야 풀 수 있는 문제이다. 문제 접근 방식: 먼저, 문제에서 주어진 정보대로 그래프의 크기, 그래프, 한별이의 현재 위치, 여행 기록을 모두 입력으로 받았다. 이후, 한별이의 여행기록을 for문으로 하나하나 돌리며 시뮬레이션을 해보는데, 와드를 놓..

티스토리툴바