본문 바로가기

Python45

[Python] 백준 1461 도서관 문제 링크 : https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 1. 접근 방법 마지막 책을 옮긴 후 다시 원점으로 돌아올 필요가 없어서 가장 멀리 있는 위치를 마지막에 가는 것은 어렵기 않게 생각했는데, 세부적 구현에서 많이 고민했다. 최적의 위치를 잘 찾는것이 이 문제의 가장 중요한 부분이라 생각한다. 2. 풀이 코드 🖥python 코드 import sys input = sys.stdin.readline MIIS = lambda: map(int, .. 2021. 10. 27.
[Python] 백준 20056 마법사 상어와 파이어볼 문제 링크 : https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 1. 접근 방법 빡빡한 구현이 필요한 상어 문제를 처음 접했을 때는 많이 막막했었다. 코드를 구현하는 과정뿐만 아니라, 적절한 자료구조, 알고리즘을 잘 다루지 못해서 더욱 막막했었던 것 같다. 그러나 시간이 지나고, 문제를 코드로 구현하는 과정과, 자료구조, 알고리즘을 잘 다루기 시작하며 보다 수월하게 문제를 해결하는 것 같다. 2. 풀이 코드.. 2021. 10. 25.
[Python] 소가 길을 건나간 이유 7 문제 링크 : https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 7 30에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다. www.acmicpc.net 1. 접근 방법 최단거리 문제인데, 사이클과 방문한 위치를 여러 번 방문할 수 있는 문제여서 다익스트라로 접근했다. 여러 차례 시행착오를 거쳤는데, 완전 탐색이 되지 않도록 하는 것이 이 문제의 핵심인 것 같다. 2. 풀이 코드 🖥python 코드 import heapq import sys input = sys.stdin.readline MIIS = lambda: .. 2021. 10. 25.
[Python] 백준 21608 상어 초등학교 문제 링크 : https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 1. 접근 방법 구현의 난이도가 낮지는 않지만, 조건 분기가 많지 않아서 비교적 어렵지 않게 구현할 수 있을 것이라 생각한다. 구현 문제는 문제만 잘 읽는다면, 한 번에 해결할 수도 있는 문제 종류라고 생각한다. 2. 풀이 코드 🖥python 코드 import sys input = sys.stdin.readline def search_friends(student: int,.. 2021. 10. 22.
[Python] 백준 16926 / 16927 배열 돌리기 1, 2 문제 링크 배열 돌리기 1 : https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 배열 돌리기 2 : https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3.. 2021. 10. 12.
[Python] 백준 1398 동전 문제 문제 링크 : https://www.acmicpc.net/problem/1398 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 www.acmicpc.net 1. 접근 방법 기본적인 접근은 거스름돈 문제처럼, 해당 금액을 가장 큰 금액으로 채우는 것으로 시작했다. 그런데, 10과 25가 약수 / 배수 관계가 아니라서 일반적인 방법으로 해결하지 못한다. (30일 때, 10 + 10 + 10이 최소이지만, 큰 값 부터하면 25 + 1 + 1+ 1+ 1+ 1으로 최소가 아니게 됨) 그래서 전반적인 .. 2021. 10. 8.
[Python] 백준 9080 PC방 요금 문제 링크 : https://www.acmicpc.net/problem/9080 9080번: PC방 요금 현성이는 요즘 LINEAR 2라는 온라인 게임에 빠져있다. PC방에 가서 게임을 즐기는데, 자주 가는 PC방의 요금체계는 다음과 같다. 일반 요금으로 시간당 1000원 씩을 받으며, 야간 정액을 끊으면 5000원 www.acmicpc.net 1. 접근 방법 주간과 야간을 나누고, 야간에는 일반 요금과 야간 정액이 있어 적어도 3가지를 고려해야 할 것 같았다. 진행하며 보니 더욱 안정적으로 풀이하기 위해 더욱 많은 분기점이 생겼다. 하지만 큰 토대는 주간과 야간 그리고 하루가 넘어가는 것을 어떻게 잘 처리하는지인 것 같다. 그리고, 시간, 분을 각각 저장해도 되지만, 나는 00:00 기준으로 지난 시간.. 2021. 10. 7.
[Python] 백준 5052 전화번호 목록 문제 링크 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 1. 접근 방법 가장 쉬운 방법은 각 전화번호를 길이별 오름차순 정렬하여 해결하는 방법이다. 각 테스트 케이스 별 입력도 10000개 이고, 정렬, 탐색을 고려한다고 해도 더 빠르게 작동할 것이다. 하지만 이번 문제는 트라이 알고리즘으로 해결하고 싶었다. 처음에는 무슨 알고리즘인가 하여 찾아보고 고민도 했는데, 오히려 구현은 이러한 과정보다 더 쉽게 해결됐다... 2021. 9. 15.
[Python] 백준 9655 돌 게임 문제 링크 : https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. 접근 방법 작은 숫자부터 시작해서 규칙성을 찾는 것으로 시작했다. n = 1일 때, 상근이가 시작하므로, 무조건 상근이가 이기게 됨 n = 2일 때, 상근이는 하나만 가져갈 수 있고, 나머지 하나를 창영이가 가져가므로 창영이가 이기게 됨 n = 3일 때, 상근이가 3개를 가져가면 이길 수 있지만, 1개를 가져가면 창영이가 이는 결과가 나옴. '완벽하게' 게임을 했다는 가정이 있으므로 상근이가 3개를 가져가서 이기게 됨 n = 4일 때, 상근이가 1개, 3개를 가져가는 경우가 있음. 1개를 가져가서 .. 2021. 9. 12.

티스토리툴바