본문 바로가기

분류 전체보기368

백준17487-타자 연습 백준 17487 - 타자 연습https://www.acmicpc.net/problem/17487문제 요약QWERTY 키보드에서 영문 문장을 입력할 때, 왼손과 오른손의 키 누름 횟수를 구하는 문제다.핵심 규칙은 다음과 같다.키 배정 — Y·G·B 까지가 왼손 영역이고, 그보다 오른쪽(U·H·N 이후)은 오른손 영역이다.Shift / Space — 이 키들은 양손 어느 쪽으로든 누를 수 있어서, 양손의 누른 횟수 차이를 최소화하는 데 쓴다.동률 시 왼손 우선 — 차이를 줄인 뒤에도 1이 남으면 왼손이 한 번 더 누른다.키 분류QWERTY 배열에서 각 행의 경계를 기준으로 좌우를 나누면 다음과 같다.행왼손오른손상단Q W E R T YU I O P중단A S D F GH J K L하단Z X C V BN M즉, .. 2026. 2. 21.
주간 기록 https://www.acmicpc.net/problem/25558a=map(int,open(0).read().split())n,sx,sy,ex,ey=[next(a) for _ in range(5)]i=1mn=float('inf')r=0while True: m=next(a) d=0 px,py=sx,sy for _ in range(m): cx,cy=next(a),next(a) d+=abs(cx-px)+abs(cy-py) px,py=cx,cy d+=abs(ex-px)+abs(ey-py) if mn>d: mn=d r=i if i==n: break i+=1print(r)def s(): a=.. 2026. 2. 6.
백준2097-조약돌 문제 설명백준 2097번: 조약돌정수 격자점(좌표가 모두 정수인 점) 위에 N개의 조약돌을 원하는 위치에 놓을 수 있습니다. 이때 놓인 조약돌들을 모두 포함하는 축에 평행한 직사각형을 만들고, 이 직사각형의 둘레를 최소화하는 것이 목표입니다.단, 직사각형의 가로와 세로 길이는 각각 최소 1 이상이어야 합니다. 조약돌이 한 줄이나 한 점에 몰려 있어도 길이가 0이 되지 않고 1로 간주합니다.입출력입력: 조약돌의 개수 N (1 ≤ N ≤ 500,000,000)출력: 최소 둘레예제입력출력561412핵심 아이디어격자점 배치 패턴아래 그림은 N=1부터 N=10까지 조약돌을 최적으로 배치한 패턴을 보여줍니다.패턴을 관찰하면 핵심 규칙이 보입니다:가로 a, 세로 b인 직사각형에는 최대 (a+1) × (b+1)개의 격.. 2026. 1. 27.
구간 최댓값 세그먼트 트리 2357번: 최솟값과 최댓값문제 상황길이 $N$인 배열이 주어졌을 때, 구간 $[l, r]$의 최댓값을 빠르게 구해야 한다.방법전처리쿼리브루트포스$O(1)$$O(N)$세그먼트 트리$O(N)$$O(\log N)$핵심 아이디어배열을 이진 트리 형태로 분할하여, 각 노드가 해당 구간의 최댓값을 저장한다. 쿼리 시 필요한 구간만 방문하므로 $O(\log N)$에 처리된다.예) 배열 [2, 5, 1, 4, 9, 3] 9 [0,5] / \ 5 [0,2] 9 [3,5] / \ / \ 5[0,1] 1[2,2] 9[3,4] 3[5,5] / \ / \ 2[0] 5[1] 4[3] 9[4]구현1.. 2026. 1. 23.
백준-17273 카드 공장 (Small) 문제 링크17273번: 카드 공장 (Small) 문제 요약$N$장의 카드가 있고, 각 카드는 앞면과 뒷면에 숫자가 적혀 있다. $M$번의 쿼리가 주어지며, 각 쿼리는 threshold 값 $K$를 의미한다. 현재 보이는 면의 숫자가 $K$ 이하인 카드는 뒤집는다. 모든 쿼리를 처리한 후 보이는 숫자들의 합을 구하라.제한17273 (Small): $N, M \le 10{,}000$Small 풀이: 브루트포스가장 직관적인 방법은 매 쿼리마다 모든 카드를 순회하며 조건을 확인하는 것이다.n, m, *a = map(int, open(0).read().split())cards = []d = n 시간복잡도: $O(NM) = 10^8$카드 정보를 저장하기 위해 불필요하게 추가적인 2차원 배열을 만들고 있으니 입력받은.. 2026. 1. 22.
29358-헐크를 잡아라(Поймать Халка) https://www.acmicpc.net/problem/29358를번역한 문제다.시간 제한메모리 제한2 초1024 MB문제로키가 헐크를 잡으려 할 때, 자신의 힘을 조금 잘못 계산하여 실수로 헐크를 평행한 \(n\)차원 세계로 보내버렸다. 그 후 로키는 헐크를 얼음 덩어리 속에 완전히 얼려버렸다. 최종적인 승리를 위해 로키는 얼음 덩어리에서 불필요한 얼음을 잘라내어 얼어붙은 헐크만 남기면 된다.로키가 모든 일을 옮겨간 공간은 최대 3차원이다. 1차원 공간에서 얼음 덩어리는 어떤 길이의 선분이고, 그 안의 헐크는 그 안에 포함된 선분이다. 2차원 공간에서 얼음 덩어리와 헐크는 좌표축에 평행한 변을 가진 직사각형이며, 헐크는 얼음 덩어리 안에 포함되어 있다. 마찬가지로, 3차원 공간에서 얼음 덩어리와 헐크.. 2026. 1. 19.
Python 3.14 t-strings 알아보기: f-string의 진화, 더 안전한 문자열 처리 Python 3.14에서 템플릿 문자열 리터럴(t-strings)이 공식 도입되었습니다. PEP 750에 의해 제안된 이 기능은 제가 좋아하는 f-string의 편리함은 그대로 유지하면서, 보안성과 유연성을 대폭 강화한 새로운 문자열 처리 방식입니다.t-strings가 무엇인지, 왜 필요한지, 어떻게 활용하는지 예시와 함께 살펴보겠습니다.1. t-strings란 무엇인가?t-strings의 핵심 개념을 한 문장으로 요약하면:"문자열을 즉시 합치지 않고, 재료(템플릿과 값)를 그대로 전달한다"기본 문법접두사: 문자열 앞에 t 또는 T를 붙입니다반환 타입: str이 아닌 string.templatelib.Template 객체보간 문법: f-string과 동일하게 {변수} 사용from string.templa.. 2026. 1. 17.
Python 3.14 달라진 점 1. 소개Python 3.14가 2025년 10월 7일에 공식 출시되었습니다. 이번 버전은 언어, 구현, 표준 라이브러리에 걸쳐 다양한 변화를 가져왔으며, 특히 성능 향상과 개발자 경험 개선에 중점을 두었습니다.주요 변경사항 요약:템플릿 문자열 리터럴 (t-strings) 도입어노테이션의 지연 평가표준 라이브러리에서 서브인터프리터 지원Zstandard 압축 형식 지원Free-threaded Python 공식 지원REPL 문법 하이라이팅JIT 컴파일러 (실험적)성능 개선 (3-5% 향상)참고: 이 글은 Python 3.14 공식 문서를 기반으로 작성되었습니다. 최신 버전은 Python 3.14.2 (2025년 12월 5일)입니다.2. 지연 평가 어노테이션 (PEP 649/749)2.1 개념Python 3... 2026. 1. 7.
백준 17144번: 미세먼지 안녕! 문제 링크📋 문제 요약R×C 크기의 방에 미세먼지와 공기청정기가 있다. T초 동안 매 초마다 다음 두 가지 일이 순서대로 일어난다:미세먼지 확산: 모든 칸에서 동시에 인접 4방향으로 확산공기청정기 작동: 바람이 불어 미세먼지가 순환T초 후 남아있는 미세먼지의 총량을 구하는 문제다.🔍 문제 분석1. 미세먼지 확산 규칙각 칸 (r, c)에 있는 미세먼지 A가 확산될 때:인접한 4방향(상하좌우)으로 각각 ⌊A/5⌋ 만큼 확산공기청정기가 있거나 격자 밖이면 그 방향으로는 확산 안 됨원래 칸에 남는 양: A - ⌊A/5⌋ × (확산된 방향 수)핵심 포인트: 모든 칸에서 동시에 확산이 일어난다. 따라서 확산 결과를 새로운 배열에 저장해야 한다.2. 공기청정기 바람 순환공기청정기는 1열에 두 행을 차지하며 설치되.. 2025. 12. 25.
Gosper's Hack Algorithm n개의 원소 중 k개를 선택하는 모든 조합을 순회해야 할 때, 대부분은 itertools.combinations나 재귀 함수를 떠올릴 것입니다. 하지만 비트마스크를 사용해야 하는 상황이라면 Gosper's Hack을 사용할 수 있습니다.1. 서론발견 계기https://www.acmicpc.net/problem/17127이 알고리즘을 처음 찾게 된 건 "n개를 여러 그룹으로 나누는 모든 경우"를 순회해야 할 때였습니다. n개의 원소를 4개 그룹으로 나눈다면, n-1개의 틈 중 3개를 고르는 문제이고 3중 for문으로 충분합니다.하지만 그룹 수가 가변이거나 많아지면 어떨까요? k중 for문은 비현실적입니다. 점화식으로 "다음 경우"를 구하려 했는데, 조건문과 반복문이 걸렸습니다. 순수 비트 연산만으로 다음 .. 2025. 12. 5.
정사각형 암호 해독: 90도 회전 변환의 원리와 구현 https://www.acmicpc.net/problem/5426문제 개요정사각형 암호(Square Cipher)는 평문을 정사각형 격자에 배치한 후 90도 회전시켜 암호문을 만드는 방식입니다. 이 글에서는 암호문을 복호화하는 과정을 다룹니다.예제:입력: RSTEEOTCP출력: TOPSECRET핵심 원리1. 변환 과정 시각화길이 9인 문자열 "TOPSECRET"을 3×3 격자로 배치:0 1 2 T O P3 4 5 = S E C6 7 8 R E T90도 시계방향 회전 후:R S TE E OT C P1차원으로 읽기: "RSTEEOTCP"2. 수학적 공식 (0-based 인덱싱)2차원 위치를 1차원 인덱스로 표현할 수 있습니다. 나이브한 방법은 "1차원 → 2차원 → 회전 → 1차원" 순서로.. 2025. 11. 16.
평면에 직선 𝑛개를 그을 때 만들 수 있는 최대 영역 수 평면에 직선 $n$개를 그을 때 만들어지는 최대 영역 수를 하노이의 탑과 같은 흐름으로 정리한다. 핵심은 증가량이 등차수열 $(1,2,3,\dots)$이어서 삼각수가 자연스럽게 등장한다는 점이다.1) 문제와 가정(일반 위치)평면에 서로 다른 직선 $n$개.일반 위치(general position) 가정평행 없음(아무 두 직선도 평행하지 않음)세 직선 이상이 한 점에서 만나지 않음목표: 만들어지는 영역(면)의 최대 개수 $L_n$.2) 분해와 점화식직선을 하나씩 추가한다고 보면, 새 직선은 이전 $n-1$개의 직선을 서로 다른 $n-1$개의 점에서 만나고, 그 결과 $n$개의 구간으로 잘린다. 각 구간은 기존의 한 영역을 둘로 갈라 영역 수가 1씩 증가한다.$$\boxed{L_n = L_{n-1} + n,.. 2025. 11. 13.
Concrete Mathatics-Recurrent Problems: Tower of Hanoi 하노이의 탑: 점화식 → 닫힌형 → 최소성(엄밀) → 이동 규칙 공식화 → 구현분해 논리로 점화식을 세우고, 닫힌형을 두 방식으로 유도하고, 최소성을 강한 귀납으로 엄밀히 확정한다. 이어서 어느 디스크가 언제 움직이는가를 $v_2$ 가측과 “ruler function”으로 공식화하고, 재귀·반복 구현까지 연결한다.1) 문제와 불변식세 기둥 $A,B,C$, 크기 다른 $n$개의 원반.제약한 번에 한 원반만 이동.큰 원반은 작은 원반 위에 올 수 없음.목표: 모든 원반을 $A\to C$로 최소 이동으로 옮기기.불변식초기 상태에서 성립하는 제약 1–2는 모든 이동 후에도 유지되어야 한다.기저 $n=0$이면 이동 0회.2) 분해와 점화식가장 큰 원반을 움직이려면 그 위의 $n-1$개를 보조 기둥으로 치워야 한다.. 2025. 11. 6.
백준34510_초콜릿 우유가 좋아.py https://www.acmicpc.net/problem/34510꼭지 높이=a삼각형 높이=b사각형 높이=c1층=a+b+c2층=b+c*23층=a+b*2+c*34층= b*2+c*45층= a+b*3+c*56층= b*3+c*6n층=a*(n&1)+ b*(n&1)+b*(n//2)+c*n =(a+b)* (n&1)+ b*(n//2) +c*ndef s(): a,b,c,n=map(int,open(0).read().split()) print((a+b)*(n&1)+b*(n>>1)+c*n)s() 2025. 10. 27.
푸른 낙동강-박다은 강에 있는 다리를 건너요.또르륵 비가 와요.캄캄한 그림자 밑에여우 발자국이 있어요.물 웅덩이가 생겨요.강에는 오리가 있어요. 2025. 10. 18.

티스토리툴바