본문 바로가기

Python45

[Python] 백준 22965 k개의 부분 배열 문제 링크 : https://www.acmicpc.net/problem/22965 22965번: k개의 부분 배열 4 5 6 / 1 2 3으로 나눈 뒤, 1 2 3 / 4 5 6으로 재배열하면 된다. www.acmicpc.net 1. 접근 방법 간단한 정렬 구조를 묻는 문제라 생각했다. 만약 횟수 제한 또는 한 번에 하려면 몇 조각으로 나누어야 하냐는 문제라면 조금 더 까다로울 수도 있었지만, 제한 없이 반복할 수 있어서 3조각으로 나눌 수 있으면 무조건 가능하다. 3조각으로 나누면 한 개씩 잘라내서 원하는 자리에 넣는 작업만 반복해도 된다. 또한 정렬되어 있으면 1이 되는것은 주어진 예제에서도 알 수 있다. 문제는 언제 2번만 가능한지를 구현하는 것이다. 2. 풀이 코드 🖥python 코드 링크 : h.. 2021. 11. 7.
[Python] 백준 16884 나이트 게임 문제 링크 : https://www.acmicpc.net/problem/16884 1. 접근 방법 모든 경우의 수를 탐색하기에는 너무 경우의 수가 많았다. 최대 10,000이지만, n일 때 결과가 n + 1일 때 결과 및 과정에 직접적인 인과 과정을 찾을 수 없었기 때문에, DP 식의 풀이 과정은 옳지 않다고 생각했다. 만약 각각 과정을 백트레킹으로 계산할 수도 있지만, 최대 100개의 테스트 케이스가 주어지면 불가능할 것이라 생각했다. 2. 풀이 코드 🖥python 코드 : https://github.com/mintropy/baekjoon_py/blob/master/16000/16884.py GitHub - mintropy/baekjoon_py Contribute to mintropy/baekjoon_.. 2021. 11. 6.
[Python] 백준 20166 문자열 지옥에 빠진 호석 문제 링크 : https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 1. 접근 방법 범위가 작고, 전체 탐색이 아니라면 딱히 방법이 없을 것 같아, 브루트 포스로 시행했다. 8방향으로, 양 끝이 연결되어 있어 모듈러 연산으로 이동 위치를 구했고, 각 위치에서 신이 좋아하는 문자열에 있는지 확인하는 작업을 했다. 2. 풀이 코드 🖥python 코드 import sys input = sys.stdin.readline def search(string_now: str, x: int, y: int): global n, m, grid, dx, .. 2021. 11. 1.
[Python] 백준 1186 직사각형 색칠하기 문제 링크 : https://www.acmicpc.net/problem/1186 1186번: 직사각형 색칠하기 2차원 좌표 평면에 변이 축에 평행한 직사각형 N개가 있다. 직사각형은 1부터 N까지 번호가 매겨져 있다. i번 직사각형의 왼쪽 아래 꼭짓점의 좌표는 (xi,1, yi,1)이고, 오른쪽 위 꼭짓점의 좌표는 (xi www.acmicpc.net 1. 접근 방법 어떻게든 그리디 한 방법이나, 스위핑 같은 방법을 고민했는데, 여러 직 사각형이 겹치는 경우의 해결 방법이 떠오르지 않아, 전체 탐색을 고민했다. 최대 50개 직사각형을 탐색해서 50 * 50으로 각 직사각형마다 겹치는지 확인할 수 있고, 각 직사각형이 최대로 많이 탐색해도 50 * 8 정도라 생각하여 최대 1,000,000번의 탐색으로 가능.. 2021. 11. 1.
[Python] 백준 23259 Celebrity 문제 링크 : https://www.acmicpc.net/problem/23259 23259번: Celebrity 첫째 줄에 아름다운 별의 수를 출력한다. www.acmicpc.net 1. 접근 방법 그래프의 동형 확인은 매우 어려운 작업이다. 그나마 그래프의 동형을 판별하는 몇 가지 방법을 기준으로 하나하나 분류하려 시도했는데, 너무 많은 조건을 고려해야 할 것 같아서 그래프의 조건을 기준으로 동형을 판별하는 것은 포기하고, 브루트 포스로 탐색했다. 점이 5개로 고정이므로, 각 간선 번호를 0~9번으로 하여 각 별의 상태를 비트연산으로 계산한 숫자로 처리했다. 2. 풀이 코드 🖥python 코드 from itertools import permutations import sys input = sys.st.. 2021. 10. 31.
[Python] 백준 23257 비트코인은 신이고 나는 무적이다 문제 링크 : https://www.acmicpc.net/problem/23257 23257번: 비트코인은 신이고 나는 무적이다 코인 경력 4년차, 차트에 통달한 찬호는 이전 $N$개의 월봉을 통해 다음 월봉의 절댓값을 예측할 수 있는 아래의 공식을 만들어냈다. (다음 월봉의 절댓값) = 이전 $N$개의 월봉 중 중복을 허용해 www.acmicpc.net 1. 접근 방법 처음에는 XOR 연산에 대해 고민했는데, XOR 연산 처리는 비교적 쉽게 방법을 찾았다. https://stackoverflow.com/questions/52108901/xor-operation-on-three-values XOR operation on three values I have three boolean values. I nee.. 2021. 10. 30.
[Python] 백준 22234 가희와 은행 문제 링크 : https://www.acmicpc.net/problem/22234 22234번: 가희와 은행 가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다. [그림 1] 카운터 직원과 N명의 손님 x번 손님에 대한 정보는 x번 손님의 www.acmicpc.net 1. 접근 방법 간단한 구현 문제인데, 출력을 어떻게 조정할지 많이 고민했다. 구현 과정은 각 손님의 남은 시간을 확인하고, 업무처리를 각각 상황에 맞게 시간을 사용하고, 사용한 시간만큼 출력할 리스트에 저장하면서 진행했다. 2. 풀이 코드 🖥python 코드 from collections import deque import sys input = sys.stdin.readli.. 2021. 10. 28.
[Python] 백준 16888 루트 게임 문제 링크 : https://www.acmicpc.net/problem/16888 16888번: 루트 게임 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 105)가 주어진다. 둘째 줄부터 T개의 줄에 테스트 케이스가 한 줄에 하나씩 주어지며, N(1 ≤ N ≤ 106)이 주어진다. www.acmicpc.net 1. 접근 방법 소수 판정 에라토스테네스 체와 비슷한 방식으로 해결될 것이라 생각이 들었다. 처음에는 각 조건마다 다음 턴을 거꾸로 탐색하는 과정을 반복했는데, 시간이 생각보다 많이 걸려서, 에라토스테네스 체에서도 사용하는 아이디어인, 소수를 발견하면 배수를 모두 소수가 아님을 표시하는 방법을 채용하여 해결했다. 2. 풀이 코드 🖥python코드 import sys input = sys.stdi.. 2021. 10. 28.
[Python] 백준 3109 빵집 문제 링크 : https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 1. 접근 방법 좋지 않은 습관이지만, 문제 카테고리를 먼저 확인하고 접근했고, 그리디라는 카테고리만 생각하여 처음에는 잘못 접근했었다. 결론적으로, 파이프가 생성될 수 있는 시작점, 끝점을 이어가면서 해결했는데, 시작점부터 위에서, 아래로 확인을 하면 기존 파이프 때문에 새로 생성하지 못하는 경우는 없고, 이 방법으로 해결했다. 서로 겹치지 않고, 세 방향 탐색이라는 부분에서 그리디를 카테고리로 .. 2021. 10. 28.

티스토리툴바