본문 바로가기

⭐ Problem_Solving/백준30

[백준] 2146 다리 만들기 (Python/파이썬) https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 기본 접근은 각각의 섬에 다른 번호를 부여하고 각각의 섬에 대해서 bfs를 통해서 다리의 최소 길이를 구하는 것이다. 2. 다만 메모리초과가 나기 쉬워서 visited배열을 잘 활용해야 한다. 나 같은 경우는 다리 건설하는 bfs 함수 안에 visited배열을 하나 만들고, 섬의 번호에 대한 visited배열을 하나 더 만들어서 한 번 탐색한 섬에 대해서 다시 탐색하지 않도록 했다. 3. 다리를 .. 2022. 10. 1.

[백준] 20055 컨베이어 벨트 위의 로봇 (Python/파이썬) https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 1. 주어진 조건대로 구현하면 되는 구현 문제이다. 2. 크게 복잡한 알고리즘이나 구현은 필요 없고 문제 읽고 단계별로 각 동작을 꼼꼼히 구현하면 무난하게 통과 된다. 3. 벨트 회전은 deque의 rotate() 메서드를 이용하면 편하고 로봇의 배열 같은 경우는 데크보다 그냥 리스트가 편하고 빠르다. from collections import deque import sys,.. 2022. 9. 30.

[백준] 2212 센서 (Python/파이썬) https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 그리디 알고리즘으로 분류되는 문제인데 대부분의 그리디 문제가 그렇듯이 그리디인 걸 알고 나면 쉽다. 그리디인 걸 알고 확신하기까지가 어려워서 그렇지... 센서와 집중국 간의 거리를 최소화 해야되기 때문에 센서 간 거리가 가장 큰 지역이 집중국 수신 영역 내에 포함되지 않도록 해야된다. 따라서 센서 간 거리를 구해서 가장 거리가 큰 지역 K - 1개를 총 지역에서 빼주면 된.. 2022. 9. 29.

[백준] 3190 뱀 (Python/파이썬) https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 큐의 선입선출 구조를 활용한 구현 문제이다. 구현해야할 사항들은 간략하게 나눠보면 다음과 같다. 뱀의 이동 게임 종료 조건 벽에 부딪혔을 때(= 범위를 벗어났을 때) 뱀의 몸통에 부딪혔을 때 사과가 있을 때 뱀의 크기를 사과가 있는 영역 한 칸만큼 늘려준다. 사과가 없을 때 뱀의 크기를 유지한 채 사과가 있는 영역으로 한 칸 이동 시켜준다.(꼬리 -1) 뱀의 몸통은 뱀이 이동하는 경로를 표시해주는 방식으.. 2022. 9. 28.

[백준] 2206 벽 부수고 이동하기 (Python/파이썬) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 벽을 부수는 걸 구현하는 게 핵심이다. 일반적인 2차원 배열에 벽 부수는 걸 나타내주는 변수를 추가적으로 넣어서 bfs를 돌리면 에러가 난다. 특정 지점 (r, c)에 벽을 부수고 도달하는 방법(a)랑 벽을 부수지 않고 도달하는 방법(b)가 있는데, a가 b보다 거리가 짧을 때(a < b)일 때 2차원 배열에서는 a만 표시 된다. 그러다 나중에 벽을 부수지 않고는 통과하지.. 2022. 9. 27.

[백준] 14503 로봇청소기(Python/파이썬) https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 구현 문제라 특별한 알고리즘은 필요 없고 문제에 주어진 내용을 정직하게 구현하면 된다. 방향 처리가 좀 복잡해서 신경 써야된다.(바라보는 방향이 주어지고 그 상태에서 왼쪽으로 회전 및 이동, 뒤로 이동) 청소한 영역을 벽이랑 똑같은 1로 표시하면 안된다.(-1 같이 0, 1 혹은 다른 숫자로 처리) # 220827 14503 로봇 청소기 # 정답코드 import sys input = sys.. 2022. 9. 26.

이전 1 2 3 4 5 다음

티스토리툴바