본문 바로가기

Tech/Coding113

백준 34125번: 래환이의 아이브 콘서트 이야기/맨해튼 거리 https://www.acmicpc.net/problem/34125📌 문제 요약콘서트장의 좌석 배치도가 주어졌을 때, 무대와 가장 가까우면서 중앙에 가까운 최적의 빈 좌석을 찾는 문제입니다.입력첫 줄: $N$(행 수), $M$(열 수, 항상 홀수)다음 $N$줄: 각 행의 좌석 상태 (0=빈 좌석, 1=예매된 좌석)출력최적 좌석의 위치 (행 번호, 열 번호)빈 좌석이 없으면 -1🎯 핵심 개념: Distance 공식최적 좌석을 판단하는 기준:$\text{Distance} = R + \left|\frac{M+1}{2} - C\right|$$R$: 행 번호 (작을수록 무대에 가까움)$\left|\frac{M+1}{2} - C\right|$: 중앙 열로부터의 거리이는 사실상 (1행, 중앙열)을 기준점으로 한 .. 2025. 8. 13.
백준 3665번: 최종 순위 - 위상 정렬로 순위 결정하기 https://www.acmicpc.net/problem/3665📌 문제 개요ACM-ICPC 대회에서 작년 순위와 올해 변경된 팀 쌍만 주어졌을 때, 올해의 최종 순위를 결정하는 문제입니다.핵심 요구사항:작년 완전한 순위가 주어짐올해는 순위가 바뀐 팀 쌍만 제공가능한 결과: 유일한 순위 / 불확실한 순위(?) / 모순(IMPOSSIBLE)🎯 위상 정렬(Topological Sort)이란?개념 정의위상 정렬은 방향 그래프에서 모든 방향 간선의 순서를 지키면서 정점들을 나열하는 방법입니다.간단히 말해, A → B 간선이 있다면 결과에서 A가 B보다 앞에 나와야 합니다.실생활 예시대학 수강 신청을 생각해보세요:프로그래밍기초 → 자료구조 → 알고리즘 ↘ 데이터베이스위상 정렬 결과:.. 2025. 8. 5.
달팽이2 문제 링크: https://www.acmicpc.net/problem/19521. 공식 도출 과정1.1 기본 개념 정의달팽이 경로에서 **레이어(layer)**란 표의 가장자리부터 안쪽으로 들어가는 동심원 형태의 고리를 의미합니다.$k = \min(M, N) \text{ (총 레이어 수)}$1.2 표를 이용한 레이어 시각화5×4 표에서의 레이어 구조:┌─────────────────────────────────────┐│ Layer 1 (외곽) ││ → → → → (4칸, 꺾임없음) ││ ↓ ↓ ││ ↓ ↓ ││ ↓ .. 2025. 8. 4.
최장 공통 부분수열(LCS) 과 DP 역추적 백준 17218 비밀번호 만들기 => 최장 공통 부분수열(LCS) 과 DP 역추적두 개의 문자열 s1과 s2가 주어졌을 때, 이 두 문자열이 공통으로 갖는 부분수열(subsequence) 중 길이가 가장 긴 것을 구하는 문제이다. 부분수열은 원래 문자열에서 문자를 삭제해 얻을 수 있는 순서를 유지하는 문자열을 말한다. 예를 들어 “ABCBDAB”의 부분수열로 “BCBA”가 있다.동적 계획법(DP) 점화식크기가 (n+1)×(m+1)인 2차원 배열 dp를 정의한다.dp[i][j]는 s1의 처음 i글자(s1[0..i‑1])와s2의 처음 j글자(s2[0..j‑1])로 만들 수 있는최장 공통 부분수열(LCS)의 길이를 의미한다.$$ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & .. 2025. 7. 21.
파이썬 조건 매핑 함수 구현 방법 관련문제: https://www.acmicpc.net/problem/17072파이썬 조건 매핑 함수 구현 방법: lambda vs bisect특정 입력값 v가 어떤 구간에 속하는지 판단하여 그에 따른 코드를 반환하고 싶을 때, 파이썬에서는 여러 가지 방식으로 조건-값 매핑을 처리할 수 있다.1. lambda를 이용한 조건 매핑rules = [ (lambda v: v 입력값 v가 어떤 조건을 처음으로 만족하느냐에 따라 반환값이 달라진다.예시:get_code(100000) # 출력: 35get_code(600000) # 출력: 43get_code(1200000) # 출력: 462. bisect 모듈을 활용한 고속 구간 매핑bisect 모듈은 정렬된 기준값 리스트에 대해 이진 탐색을 통해 구간 인덱스.. 2025. 7. 3.
도깨비말(Pig Latin) https://www.acmicpc.net/problem/9226문제 설명도깨비말은 언어 유희 중 하나로, 글자를 특정 법칙에 따라 재구성하는 것을 말한다. 영어권에서는 피그 라틴어(Pig Latin)라는 것이 있으며, 어린이들이 종종 자신들만의 은어처럼 사용한다.이 언어에는 다음과 같은 규칙이 있다:단어의 앞에서부터 모음이 나올 때까지 자음들을 잘라낸다.잘라낸 자음들은 단어 끝으로 옮긴다.그 뒤에 ay를 붙인다.만약 단어가 모음으로 시작한다면 그대로 ay를 붙인다.만약 모음이 전혀 없다면, 단어 그대로 뒤에 ay를 붙인다.입력각 줄에 하나의 단어가 주어진다. 모든 단어는 공백 없이 소문자로만 구성되며, 길이는 20자를 넘지 않는다. 입력의 마지막은 # 한 줄이 주어진다.출력각 단어에 대해 피그라틴어 변.. 2025. 6. 23.
색칠 공부 https://www.acmicpc.net/problem/9521색칠 공부 문제 풀이: 브루트포스 + 해시맵1. 문제 요약크기 H×W인 격자에서 일부 칸은 검정색이다. 이 격자에서 가능한 모든 3×3 부분 격자를 보면서, 그 안에 검정 칸이 정확히 i개인 격자의 개수를 구해야 한다. (단, 0 ≤ i ≤ 9)2. 입력 조건 정리H, W: 격자 크기 (최대 109)N: 검정 칸의 개수 (최대 105)다음 N개의 줄: 각각 검정 칸 좌표 (r, c)3. 핵심 아이디어전체 3×3 격자는 (H-2)×(W-2)개 존재하지만, H와 W가 너무 크기 때문에 전부 확인할 수는 없다. 다만, 검정 칸은 최대 105개이므로 검정 칸이 포함된 3×3 격자만 추적해도 충분하다.4. 단계별 구현단계 1. 전체 3×3 격자의 개.. 2025. 6. 22.
17144번: 미세먼지 안녕!(OOP 문제 해결) https://www.acmicpc.net/problem/17144파이썬 객체지향으로 푸는 공기청정기 시뮬레이션 문제1. 문제 구조 요약방은 R×C 격자로 이루어져 있고, 공기청정기가 설치된 두 칸을 기준으로 미세먼지가 확산되고 정화되는 시뮬레이션이 T초 동안 반복된다.2. 객체지향 접근 이유격자 상태를 멤버 변수로 유지확산, 정화 기능을 메서드로 모듈화공기청정기의 위치를 캡슐화하여 코드 안정성 확보3. Room 클래스 구조3.1 생성자 및 공기청정기 위치 확인class Room: def __init__(self, R, C, T, grid): self.R, self.C, self.T = R, C, T self.grid = grid self.cleaner = se.. 2025. 6. 17.
회문 끝말잇기 https://www.acmicpc.net/problem/30641이 문제의 핵심을 요약하면 다음과 같다.게임 규칙길이가 $L$ 이상 $U$ 이하인 영어 알파벳($A$부터 $Z$까지)으로만 이루어진 회문(앞에서 읽으나 뒤에서 읽으나 동일한 문자열)만을 사용하여 끝말잇기를 진행한다.호영이가 선공으로 시작하며, 이후 두 사람은 항상 승리를 위해 최선의 수를 둔다.이미 사용된 단어는 다시 사용할 수 없다.회문의 성질회문은 첫 글자와 마지막 글자가 동일하다.따라서 첫 번째로 골라진 회문의 첫 글자(=마지막 글자)에 따라 이후 모든 단어는 동일한 알파벳으로 시작·끝나야 한다.예를 들어, ‘EYE’를 첫 단어로 선택했다면 이후에는 모두 ‘E…E’ 형태의 회문만 사용할 수 있다.출력첫 줄에 승자: 호영이가 이기면 H.. 2025. 6. 2.
SciComLove (2023) https://www.acmicpc.net/problem/27913SciComLove (2023) 문제를 재미있게 풀어서 풀이를 남기려고 한다.왜냐하면 파이파이로도 파이썬3으로도 속도 1등을 해서다.내가 제출한 시점에 나와 같은 정성스러운 아이디어로 푼 사람이 없어서 그런 것 같다.아주 다양한 아이디어로 풀 수 있는 재미있는 문제였다.문제 요약길이 $N$인 문자열은 “SciComLove”가 무한 반복되는 문자열의 접두사이다.예: $N=15$ → "SciComLoveSciCo"$Q$번의 과정이 순차적으로 수행된다.각 과정 $i$에서 주어진 위치 $X_i$($1 \le X_i \le N$)의 문자를대문자이면 소문자로,소문자이면 대문자로바꾼다.각 과정을 마친 후 문자열에 남아 있는 대문자의 개수를 출력한다.입.. 2025. 5. 27.
ROPE 자료구조: 구조와 동작 원리(Python 예제) 긴 문자열을 효율적으로 처리해야 하는 경우, 문자열의 일부를 잘라내거나 추가하거나 특정 위치에 접근할 때마다 문자열의 길이만큼 O(n) 시간이 걸린다면 큰 문제가 될 수 있다. 이를 해결하기 위해 고안된 자료구조가 ROPE이다.ROPE의 구조: 문자열을 트리 형태로 쪼개어 표현ROPE는 문자열을 이진 트리(Binary Tree) 형태로 저장한다. 각 노드는 다음과 같은 정보를 가진다:왼쪽 자식 (left): 문자열의 앞부분오른쪽 자식 (right): 문자열의 뒷부분weight: 왼쪽 서브트리의 전체 문자열 길이리프 노드: 실제 문자열 데이터 (짧은 문자열)구조 예시예를 들어, 문자열 "Hello_my_name_is_Simon"을 ROPE로 표현하면 다음과 같은 구조가 된다:ROPE의 주요 동작 원리1️⃣.. 2025. 5. 24.
백준 18185 라면 사기 (Small) 1. 문제 설명총 N개의 라면 공장이 있으며, 각 공장에서 구매해야 할 라면의 수 Ai가 주어집니다. 구매 방식은 다음 세 가지입니다:1개 공장에서 라면 1개: 3원2개 연속된 공장에서 각 1개씩: 5원3개 연속된 공장에서 각 1개씩: 7원2. 초기 아이디어: 개당 단가가 싼 3개 묶음 우선?각 방식의 개당 단가는 다음과 같습니다:1개 묶음: 3원 (개당 3원)2개 묶음: 5원 (개당 2.5원)3개 묶음: 7원 (개당 약 2.33원)그래서 대부분은 3개 묶음을 우선 사용하는 전략을 떠올리지만, 이 전략은 일부 경우에 손해를 볼 수 있습니다.3. 예상치 못한 '함정'과 반례📌 반례 1입력: N = 4, A = [2, 3, 2, 1]공장 위치초기 라면 수처리 내용비용누적 비용0~2[2, 3, 2]3개 묶음.. 2025. 5. 21.
펫 코드import ioinp=io.BufferedReader(io.FileIO(0),1=0: c,i=inp().split() if c==b'#':break else: w+=(((c==b"E")*-2)+1)*int(i) if (o/2) 2025. 5. 20.
2399번-거리의 합 거리의 합시간 제한메모리 제한1 초128 MB문제수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n²개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오.즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다.입력첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다.출력첫째 줄에 답을 출력한다.예제예제 입력 151 5 3 2 4예제 출력 140나이브하게 풀면 이렇습니다.n,*a=map(int,open(0).read().split())t=0for i in range(n-1): for j in range(i+1,n):.. 2025. 5. 15.
스파이럴 수열 나선형 화살표 총 길이의 일반식 도출다음과 같은 그림에서는 격자 안을 나선형으로 도는 화살표들이 있습니다. 이 화살표들의 전체 길이를 어떻게 계산할 수 있는지 수학적으로 알아보겠습니다.1. 기본 조건 정리격자의 세로 칸 수: n격자의 가로 칸 수: m이때 나선형으로 돌며 그려지는 화살표들의 전체 길이를 계산합니다. 방향은 오른쪽 → 아래 ↓ 왼쪽 ← 위 ↑ 로 반복됩니다.2. 예제 분석예시 1: 세로 6, 가로 11총 길이 = (6-1) + (11-2) + (6-2) + (11-3) + (6-3) + (11-4) + (6-4) + (11-5) + (6-5) + (11-6) + (6-6) = 세로 이동: 5 + 4 + 3 + 2 + 1 + 0 + 가로 이동: 9 + 8 + 7 + .. 2025. 5. 14.

티스토리툴바