파이썬47 [BOJ] 7977번 크리스 마틴 [BOJ] 7977번 크리스 마틴 문제 굉장히 흥미로웠던 문제다. 이 문제를 알기 위해서는 최장 공통 부분 수열(LCS; Longest Common Subsequence)를 알아야한다. 몰라도 어찌어찌 풀 수는 있겠지만, 당연하게도 LCS 알고리즘을 알면 풀기 더 쉽다. LCS 알고리즘은 두 개의 길이가 다른 문자열이 있을 때, 공통적으로 존재하는 최대 부분 문자열을 구하는 알고리즘이다. 정확히는 다이나믹 프로그래밍(Dynamic Programming)의 일종이며, 그림을 보면서 이해하기가 쉽기 때문에 그렇게 막 어려운 알고리즘은 아니다. 관련 문제 - [BOJ] 9251번 LCS 문제 이 알고리즘의 핵심은 같은 문자일 때에는 모든 방향에서의 이전 DP 값에서 1을 더한 값을 저장하고, 아닌 경우에는 인.. 2022. 11. 10. [BOJ] 2448번 별 찍기 - 11 [BOJ] 2448번 별 찍기 - 11 문제 까다로운 재귀 문제다. 다만 푸는 방법을 파훼하면 급격히 쉬워지기에 그 방법을 알아보자. 우리의 목표는 피라미드 모양의 별을 보이는 패턴대로 찍는 것이다. 빈칸까지 붙어있으니 정말이지 어려워 보인다. 일단 출력 예시를 자세히 보면 빈칸이 앞에만 있는 것이 아니라 뒤에도 붙어있음을 생각해서 풀어야 한다. 이 때문에 PE(Print Error, 출력 형식 오류)가 생길 수 있으니 꼭 주의하자. 이 문제는 양 옆으로 붙은 빈칸이 있을 땐 굉장히 어려워 보이지만, 이 빈칸을 없애면 문제가 급격하게 쉬워진다. $ N \, $이 3 / 6 / 12 / 24일 때를 따로따로 보자. # N == 3: * * * ***** # N == 6: * * * ***** * * * *.. 2022. 10. 25. [BOJ] 15828번 Router [BOJ] 15828번 Router 문제 큐(Queue)를 배우기 매우 좋은 문제다. 큐는 FIFO(First In First Out)의 형태를 가진 자료구조로, 처음 들어온 데이터가 처음으로 나간다. 이를 쉽게 이해하고 싶다면 빨대를 생각하면 된다. 빨대의 원리를 생각해보자. 우리가 빨대를 쪽 빨아대면 음료가 올라온다. 즉, 빨대랑 가장 가까운 음료부터 올라올 것이다. 이것이 바로 큐의 원리다. 문제에서는 첫 숫자가 라우터 버퍼의 최대 개수를 뜻하고, -1이 들어올 때까지 이를 이용하여 연산한다. 0이 들어오면 패킷을 처리한 것으로 처리하고, 나머지가 들어오면 버퍼에 집어넣는데, 버퍼가 가득 차면 그 숫자를 못 넣는다. 또한 문제에서 라우터의 원리를 큐에 빗대어 설명했기 때문에 라우터 버퍼는 말 그대로.. 2022. 10. 23. [BOJ] 2981번 검문 [BOJ] 2981번 검문 문제 굉장히 까다로운 수학 문제다. 애초에 검문을 하는데 뭔 이상한 문제를 왜 푸는지 모르겠지만 그래야 문제가 되니까... 이 문제의 조건은 $ 2 \leq N \leq \: 100 $의 정수가 들어오고, 각 정수는 1보다 크거나 같고 1,000,000,000(10억) 보다 작다. 이 숫자들을 $ M $으로 나눌 때 나오는 나머지의 값이 같아야 한다. 그때 1보다 큰 $ M $을 전부 구해야 하는 것이 목표다. 일단 문제를 처음 보면 굉장히 정신이 아찔해지는데, 먼저 이 문제를 이해해보자. 문제에서는 $ M $이 존재하는 경우만 테스트 케이스로 주어지기 때문에 확실히 나뉘어지는 수가 있다고 가정할 수 있다. 그렇다면 예를 들어 입력으로 주어지는 수열 $ A[0], A[1], ... 2022. 10. 8. [BOJ] 1002번 터렛 [BOJ] 1002번 터렛 문제 재밌는 기하학 문제다. 처음 보면 어려울 수 있으나, 우린 이 개념을 중학생 때 이미 배웠다. 미사일 터렛은 스타크래프트 1과 2에서 테란 종족이 대공 방어를 위해 건설되는 건물이다. 근데 이 터렛에는 모델링으로도 사람이 존재하며, 스타 1 리마스터 판에 들어서는 아예 사람이 선명하게 앉아 있는 모델링을 볼 수 있다. 근데 놀랍게도 인구수는 안 먹는다. 문제의 디테일은 여기서 마무리하고, 그렇다면 이 문제는 무엇을 물어보는 것일까? 먼저 문제에서는 터렛 두 개의 좌표와 각 터렛이 인지할 수 있는 범위 r1과 r2를 주었다. 그리고 탐지해야 하는 사람의 좌표의 개수를 구하라고 되어있다. 그렇다면 여기서 좌표는 무엇일까? 그렇다. 점이다. 자고로 영역으로 하는 순간 이 문제는.. 2022. 9. 30. [BOJ] 18111번 마인크래프트 [BOJ] 18111번 마인크래프트 문제 굉장히 어려웠던 브루트 포스(brute force) 문제였다. 애초에 이 문제가 브루트 포스라고 감이 오는 사람이 몇이나 있을까 싶기도 하다. 제한시간이 단 1초인 데다가, 최악의 경우 $ 25,000 \times 257 $가지의 경우를 다 둘러봐야 한다. 이 조건만으로 브루트 포스라고 판단하기엔 정말이지 힘들다. 파이썬에서는 대략적으로 1초에 1천만 개의 경우 정도까지가 브루트 포스로 풀 수 있는 최대 경우로 여겨진다. 다행히 이 문제는 $ 25,000 \times 257 = 6,425,000 $이므로 1천만보다는 적으니 브루트 포스로도 풀릴 수 있다. 덤으로 경우의 수가 매우 크다면 기존 파이썬으로는 시간 초과가 날 가능성이 높아서 반드시 Pypy3으로 제출해.. 2022. 9. 27. [BOJ] 10219번 Meats On The Grill [BOJ] 10219번 Meats On The Grill 문제 구성적(Constructive) 문제가 무엇인지 알아보는 좋은 문제다. PS에서 구성적 문제에서 구성적은 구성적 증명(Constructive proof)에서의 구성적이며, 예시를 들어 문제를 증명하는 방식이다. 구성적 문제의 경우 예시 중 하나만 입력해도 답으로 처리해주기 때문에, 해당 문제에서 정답을 이끌어내는 특정한 방법을 구하는 애드 혹(Ad hoc)의 특성도 보인다. [Reference article] Constructive 문제를 어떻게 풀 것인가 - 16silver 즉, 이 문제에서만 풀 수 있는 풀이법을 문제를 읽으면서 캐치하는 것이 핵심이라 보면 되겠다. 일반적으로 이 문제의 일반적은 해를 구하기 위한 방법으로는 도저히 방법이 .. 2022. 9. 17. [BOJ] 14940번 쉬운 최단거리 [BOJ] 14940번 쉬운 최단거리 문제 약간의 변형이 들어간 BFS(Breadth First Search) 문제다. 다만 어디까지나 약간의 변형이므로 BFS 처리에 집중하는 것이 중요하다. 이 문제는 누가 봐도 BFS라는 것을 알 수 있다. 하나뿐인 시작 지점인 2를 찾고, 그 지점에서 BFS를 돌리면서 닿는 구간마다 1을 더해주면 된다. 본인은 여기서 약간의 변형인 "1인 지점이지만 갈 수 없는 곳이라면 -1을 출력한다"에서 실수를 저지르고 말았다. 문제를 끝까지 읽어야 겠다는 생각만 든다... import sys from collections import deque def bfs(I, J, N, M): visited = [[False for _ in range(M)] for _ in range(N.. 2022. 9. 10. [BOJ] 1309번 동물원 [BOJ] 1309번 동물원 문제 꽤 어려웠던 DP(Dynamic Programming) 문제다. 이 문제는 DP 중에서도 2차원 배열을 이용하는 DP 문제다. 1차원 배열 DP 풀이도 있으나 이해하기엔 너무 어렵기에 여기서는 2차원 배열을 이용한다. 핵심은 N번째 층에서 사자가 없을 때 / 왼쪽에 있을 때 / 오른쪽에 있을 때로 나누고, N번째 층의 위쪽(즉, N-1번째) 층에 따라 해당 층에는 어떨 때에 사자를 배치할 수 있는지 없는지를 확인하는 것이다. 또한 사자를 안 두는 방법도 하나의 방법이라는 것도 인지해야 한다. 이를 위해 각 층마다 [사자가 없을 때, 왼쪽에 있을 때, 오른쪽에 있을 때]라는 배열로 둘 수 있다. 먼저 1개의 층만 있을 때를 보자. 간단하게 안 두기, 왼쪽에 두기와 오른쪽의.. 2022. 9. 9. [BOJ] 25487번 단순한 문제 (Large) [BOJ] 25487번 단순한 문제 (Large) 문제 굉장히 흥미로웠던 정수론 문제였다. 물론 25494번 단순한 문제 (Small) 문제도 있지만 그 문제는 브루트 포스로도 풀리며, 당연히 여기서 작성하는 정답을 사용해도 풀린다. 사실 이 문제는 코드만 보면 한없이 쉬운 문제다. 이 문제의 핵심은 "왜 그렇게 풀 수 있는가?" 이다. 먼저 주어진 조건을 여기서 나열해보자. $ 1 \leq x \leq a $ $ 1 \leq y \leq b $ $ 1 \leq z \leq c $ $ (x \; mod \; y) = (y \; mod \; z) = (z \; mod \; x) $ 여기서 $ (A \; mod \; B) $는 $ A\: $를 $ B\: $로 나눈 나머지를 의미하고, $ a $, $ b $,.. 2022. 9. 7. 이전 1 2 3 4 5 다음 728x90
