Python/백준 문제풀이

파이썬(python) 백준 1966 : 프린터 큐

collections 라이브러리에서 deque 를 큐로 사용하였습니다. 첫번째 요소를 추가/제거 하는 appendLeft(), popLeft() 메소드 지원 마지막 요소를 추가/제거 하는 append(), pop() 메소드 지원 모든 요소를 왼쪽/오른쪽 으로 회전시키는 rotate() 메소드 지원 Target(인쇄되는 순번이 궁금한 문서)의 index를 기억하기 위하여 튜플(우선순위, 0또는1) 형태로 변환해주었습니다. Target 만 1입니다. zip() 함수를 이용하여 [1,2,3] [0,0,0] => [(1,0), (2,0), (3,0)] 형태로 묶을 수 있습니다. 이렇게 안하고 enumerate() 로 index 를 집어넣고 index가 m 인 요소인지로 판별해도 됩니다. 우선순위 오름차순 정렬 ..

파이썬(python) 백준 1987 : 알파벳

1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 내용 시간 제한 : 2 초 메모리 : 256 MB 공간 RxC 크기의 공간 (각 좌표마다 알파벳 쓰여있음) 등장인물 말 : (1,1) 위치에 놓여있음 동작 말을 상하좌우로 이동한다. 아래의 제약 조건 있음. 각 알파벳을 2번 이상 밟고 지나갈 수 없음. 입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다. 출력 첫째 줄에 말..

파이썬(python) 백준 16236 : 아기 상어

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 내용 시간 제한 : 2 초 메모리 : 512 MB 공간 NxN 크기의 공간 등장인물 물고기 M마리, 각 크기는 1~6으로 입력 주어짐 아기상어 1마리, 최초 크기 2 동작 아기상어가 1초에 상하좌우로 이동한다. 아래의 제약 조건 있음. 자기보다 크기가 큰 물고기 : 못먹음, 지나가기 가능 크기 같은 물고기 : 못먹음, 지나가기 가능 크기 작은 물고기 : 먹음. 지나가기 가능 아기상어 현재 크기만큼 물고기 (개수) 먹으면 아기상어 크기+1 종료 조건 더..

파이썬(python) 백준 14496 : 그대, 그머가 되어

14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1

파이썬(python) 백준 2206 : 벽 부수고 이동하기

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 내용 시간 제한 : 2 초 메모리 : 192 MB N×M의 행렬로 표현되는 맵에서 (1, 1)에서 (N, M)로 이동할때 최단 경로로 이동 이동은 4방향이다. 시작, 끝점 카운트해서 최단경로 길이 구하라. 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동해도 됨 0은 이동할 수 있는 곳 1은 이동할 수 없는 벽이 있는 곳 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(..

파이썬(python) 백준 7576 : 토마토

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 내용 시간 제한 : 1 초 메모리 : 256 MB 세로 n 가로 m의 창고에 토마토가 있다. 익은 토마토는 하루 지날때마다 4방향의 안익은 토마토를 익은 토마토로 바꿈 창고의 모든 토마토 익으려면 최소 며칠 걸리는지 구하라 익은 토마토 : 1 안익은 토마토 : 0 토마토 없음 : -1. 입력 가로 m 세로 n nxm 크기의 창고 정보 출력 처음부터 모든 토마토가 익은 상태면 0 출력 토마토가 모두 익지 못하는 상황이면 -1 출력 토마토가 모..

파이썬(python) 백준 2580 : 스도쿠

백준 2580 : 스도쿠 문제 내용 시간 제한 : 1 초 메모리 : 256 MB baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다. C++14: 80ms Java: 292ms PyPy3: 1172ms 문제 아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다. 입력 모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다. 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다. 출력 첫째 줄에 정답을 출력한다. 예제 입..

파이썬 (python) 백준 13305 : 주유소

백준 13305 : 주유소 문제 내용 시간 제한 : 2 초 메모리 : 512 MB 문제 일직선 상의 n개 도시 순서대로 이동 (n: 2~10만) - 노드 : 도시를 뜻하며, 숫자는 해당 도시에서의 기름값 - 간선 : 도시간의 도로길이 (1km이동 당 1리터 기름 사용) 입력 도시 개수 n 도로길이 순서대로 n-1개 주유소 리터당 가격 순서대로 n개 출력 모든 도시 이동하는 최소 비용 예제 입력 1 4 2 3 1 5 2 4 1 예제 출력 1 18 예제 입력 2 4 3 3 4 1 1 1 1 예제 출력 2 10 유형 그리디 알고리즘 풀이 이 문제는 그리디 알고리즘 문제이다. 기름값이 싼 도시에서 기름을 최대한 많이 구입하는게 이득이다. 이동을 위해 1번 도시에서는 무조건 기름 구매할 수 밖에 없다. 더 싼 가..

파이썬(python) 백준 1541 : 잃어버린 괄호

백준 1541 : 잃어버린 괄호 문제 내용 시간 제한 : 2 초 메모리 : 128 MB 문제 양수와 +, -, 로 이루어진 식에 괄호를 적절히 쳐서 이 식의 값을 최소로 만들어라 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 예제 입력 1 55-50+40 예제 출력 1 -35 유형 수학 그리디 알고리즘 문자열 파싱 풀이 이 문제는 그리디 알고리즘 문제이다. 괄호를 쳐서 식을 최소로 만들기 위해서는 최대한 -를 탐욕..