python125 [Python] 백준 3079번 : 입국심사 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 💡 문제 풀이 이분탐색 문제이다. 이번 이분탐색 문제에서 중심이 되는 값은 주어진 시간에 얼마나 많은 사람들이 통과할 수 있을까이다. 최대 범위(모든 사람이 가장 오래걸리는 심사대)에서 최소 범위(0)부터 이분탐색을 진행한다. 모든 입국 심사대를 확인하는데, 주어진 시간으로 얼마나 많은 사람들이 통과할 수 있는지만 보면 된다. ✔️ 느낀 점 이분 탐색은 항상 헷갈리는 문제이지만 어떤.. 2023. 4. 27. [Python] 백준 17140번 : 이차원 배열과 연산 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 💡 문제 풀이 구현 문제이다. R 연산과 C 연산은 대상만 다를 뿐 똑같은 로직을 가진다. 따라서, 배열의 열과 행을 바꿔줌으로 추가적인 로직 구현을 할 필요가 없다. 연산을 하다 보면 처음 크기보다 작아져서 오류가 뜨는 경우가 있다. 예외처리를 통해서 그런 경우는 넘어가도록 하게 해야 한다. ✔️ 느낀 점 zip() 함수를 사용하면 정말 2차원 배열을 쉽게 뒤집을 수 있다. 이번 문.. 2023. 3. 8. [Python] 백준 16234번 : 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡 문제 풀이 BFS를 기반으로 한 구현 문제이다. 문제에서 요구하는 답은 인구 이동이 몇 번 일어났는지가 아니라 인구 이동이 일어난 날짜이다. 따라서, 단순하게 몇번 실행되었는지 보다 날짜를 기준으로 카운트하는 게 중요하다 ✔️ 느낀 점 중요한 점을 놓쳐서 코드를 깨작깨작 계속 수정햇던 문제이다. 시간 복잡도는 생각한대로 해결되었다! 💻 코드 import sys ; input = .. 2023. 3. 6. [Python] 소프티어 : 플레이페어 암호 https://softeer.ai/practice/info.do?idx=1&eid=804&sw_prbl_sbms_sn=162388 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 전형적인 구현 문제이다. key에 맞춰서 5x5 짜리 판을 초기화해 주고, 특정 알파벳의 위치를 저장한 테이블을 초기화한다. 이후 2자리로 잘라준다음 요구사항에 맞춰서 구현하면 된다. 주의할 점은 X가 단 하나 남았을 경우 XX가 만들어진다는 점과 J를 사용하지 않는다는 점이다. ✔️ 느낀 점 크게 어려울 것 없는 문제였다. 💻 코드 import sys ; input = sys.stdin.readline from collections import deque ALPHABET = ".. 2023. 3. 5. [Python] 소프티어 : 징검다리 https://softeer.ai/practice/info.do?idx=1&eid=390 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 기본적인 DP 문제이다. 이번 DP 리스트에서는 i번째 징검다리까지의 최댓값을 넣어주면 된다. 따라서, 이번 징검다리를 건널 때 현재 값과 이전 값에서 1 추가한 값과 비교해 주면 된다. ✔️ 느낀 점 기본적인 DP 문제이다! 문제 설명이 딱히 친절하지 않아서 어떻게 할까 고민하다가 쓱 풀었는데 맞았다. 💻 코드 import sys ; input = sys.stdin.readline n = int(input()) stones = list(map(int, input().split())) DP = [1] * n for i .. 2023. 3. 5. [Python] 백준 1005번 : ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 💡 문제 풀이 동적 프로그래밍과 위상정렬을 합친 문제이다. 위상정렬을 통해서 해당 노드까지 가는 길을 파악하고 DP로 최적화한다. 이해를 위해서 문제에서 제공된 첫 예제로 이해해 보자. 1부터 4까지 가기 위해서는 1 → 2, 3 → 4로 가야 한다. DP[i]에서 저장되는 값은 정점 i까지 도달했을 때의 최댓값이다. 4로 가는 길은 2가지이지만, 각 경로에 대한 비용을 따져서 최댓값으로만 .. 2023. 3. 3. 이전 1 2 3 4 ··· 21 다음