cedis 님의 블로그

숫자를 하나씩 입력받을 때마다 지금까지 입력된 수들의 중앙값을 즉시 출력하는 문제입니다.단순 정렬로도 풀 수 있지만 N = 100,000에서는 시간초과가 발생합니다.핵심 아이디어: 두 개의 힙(최대 힙 + 최소 힙)을 사용하여 O(log N)에 중앙값을 유지합니다.📋 문제 정보항목내용문제 번호백준 1655번난이도🟡 골드 II알고리즘우선순위 큐 (힙), 두 힙 기법입력첫째 줄: 정수 개수 N (1 ≤ N ≤ 100,000)이후 N줄: 정수 (−10,000 이상 10,000 이하)출력N줄: 각 숫자가 추가될 때마다 중앙값 출력(짝수 개면 두 중간값 중 작은 값)예제 입력1 → 5 → 2 → 10 → -99 → 7 → 5예제 출력1 → 1 → 2 → 2 → 2 → 2 → 5❌ 왜 단순 정렬은 안 되는가?방..

알고리즘 트릭보다 구현 시뮬레이션이 핵심인 문제. 뱀 몸을 리스트(또는 deque)로 관리하고, 매 초마다 이동→충돌→사과→방향 순서를 정확히 따르면 된다. 리스트만으로도 풀 수 있고, 이 글에서는 deque 없이 순수 리스트 버전으로 설명한다.📋 문제 소개항목내용문제 번호백준 3190난이도골드 4분류구현, 시뮬레이션, 큐핵심 자료구조리스트(뱀 몸 관리), 딕셔너리(방향 전환 정보)N 범위2 ≤ N ≤ 100 (보드 크기)시간 제한1초입력 예시출력 예시633 42 55 333 D15 L17 D9🔄 매 초 시뮬레이션 흐름이 문제의 전체 구조는 아래 순서를 무한 반복하는 것이다.순서동작코드 역할①시간 1 증가time += 1②머리 다음 칸 계산nx = head_x + dx[dir]③벽 / 자기 몸 충돌 ..

고민하다 "원형 연결 리스트인데, 포인터를 배열로 구현하면 O(1)"이라는 걸 잡았다. 삽입·삭제마다 배열을 통째로 밀거나 탐색하면 절대 안 되고, prev[x], next[x] 두 배열만 수정하는 방식이 핵심이다.📋 문제 소개항목내용문제 번호백준 23309난이도플래티넘 4분류자료구조, 연결 리스트 (원형 이중 연결 리스트)핵심 자료구조prev_station[], next_station[] 배열 (역 번호를 인덱스로 사용)N, M 범위N ≤ 500,000 / M ≤ 1,500,000 / 역 번호 ≤ 1,000,000시간 제한1초명령동작BN i ji의 다음 역 번호 출력 → i와 그 다음 역 사이에 j 설립BP i ji의 이전 역 번호 출력 → i와 그 이전 역 사이에 j 설립CN ii의 다음 역 폐쇄 ..

블록 없음, 모든 스타일 인라인 -->처음엔 3중 for문으로 접근했지만 문법 오류만 5개가 쏟아졌고, 고치고 나니 이번엔 시간 초과. 핵심은 a + b + c = d를 a + b = d − c로 바꿔 두 수 합을 set에 미리 저장하는 것이었다.📋 문제 소개항목내용문제 번호백준 2295난이도골드 4분류해시 테이블, 정렬핵심 자료구조set() (해시 테이블 기반 O(1) 조회)시간 제한2초N 범위5 ≤ N ≤ 1,000 (원소는 최대 200,000,000)입력첫째 줄: N / 다음 N줄: 집합 U의 원소 (한 줄에 하나씩)출력세 수의 합으로 만들 수 있는 가장 큰 d 출력입력 예시출력 예시5235101818중요한 조건: 문제에서 "x, y, z, k가 서로 같아도 된다"고 명시되어 있다. 즉, 같은 인..

블록 없음, 모든 스타일 인라인 -->처음엔 브루트포스로 풀면 될 것 같았지만, N이 최대 10만이라 O(N²)은 시간 초과가 난다. 이진탐색을 떠올렸지만 재귀 기준이 모호했고, 결국 정렬 + 투포인터가 핵심임을 깨달았다.📋 문제 소개항목내용문제 번호백준 2470난이도골드 5분류정렬, 투포인터 (Two Pointers)핵심 함수.sort(), abs()시간 제한1초입력첫째 줄: 용액 수 N (2 ≤ N ≤ 100,000)둘째 줄: N개의 정수 (각 -1,000,000,000 ~ 1,000,000,000)출력혼합 특성값이 0에 가장 가까운 두 용액의 특성값 (오름차순)입력 예시출력 예시5-2 4 -99 -1 98-99 98❌ 브루트포스 - O(N²)로 시간 초과처음 떠오르는 방법은 두 수를 모두 골라 합..

처음엔 오른쪽부터 접근했다가 시간 초과가 났다고 들었다. 왜 왼쪽부터 해야 자연스러운지, 스택이 어떻게 O(N)을 만드는지 따라가 봤다. N개의 탑이 왼쪽부터 순서대로 서 있다. 각 탑은 레이저 신호를 왼쪽으로 쏜다.신호는 자기보다 높은 탑을 처음 만나면 그 탑에 수신된다. 각 탑의 신호를 수신한 탑 번호를 출력한다. 아무도 없으면 0.항목내용문제 번호백준 2493난이도골드 5분류자료구조, 스택입력 범위N ≤ 500,000핵심 연산각 탑에서 왼쪽으로 처음 만나는 더 큰 탑 번호 출력예제탑 번호12345높이69574출력 (수신 탑)00224왜 단순하게 짜면 O(N²)인가각 탑마다 왼쪽을 처음부터 다시 탐색하면 이렇게 된다.# 단순 O(N²) 풀이 — 시간 초과for i in range(n): for ..

블록 없이 인라인 스타일만 사용합니다. -->처음엔 split() 없이 풀어보려 했다. 그게 통과는 됐는데, 시간 초과가 났다. 그 다음엔 왜 느렸는지까지 따라가 봤다.문제 — 백준 10828 스택정수를 저장하는 스택을 구현한다. 명령이 주어지면 각각 처리하고 결과를 출력한다.항목내용문제 번호백준 10828난이도실버 4분류자료구조, 스택명령 종류push X, pop, size, empty, top입력 범위명령 수 N ≤ 10,000명령별 동작명령동작출력push X정수 X를 스택에 넣는다없음pop맨 위 원소를 꺼낸다. 비어 있으면 -1꺼낸 값 또는 -1size스택에 들어 있는 원소 수원소 개수empty비어 있으면 1, 아니면 01 또는 0top맨 위 원소를 확인한다. 비어 있으면 -1맨 위 값 또는 -1핵..

블록 없이 모든 스타일이 인라인으로 처리되어 있습니다.-->처음 코드를 쓰고 실행했는데 에러가 없었다. 결과는 틀렸는데 에러가 없으니 더 찾기 어려웠다.N장의 카드가 위에서부터 1번, 2번, …, N번 순서로 놓여 있다. 다음 동작을 카드가 1장 남을 때까지 반복한다.맨 위 카드를 바닥에 버린다.그 다음 맨 위 카드를 맨 아래로 옮긴다.마지막에 남은 카드 번호를 출력한다.항목내용문제 번호백준 2164난이도실버 4분류자료구조, 큐핵심 자료구조collections.deque핵심 연산popleft() — 앞에서 꺼내기, append() — 뒤에 추가입력 범위1 ≤ N ≤ 500,000예제N답64447611처음 작성한 코드 — 버그 4곳n = int(input())list = []for i in range(n)..

예제를 처음 봤을 때 잠깐 멈췄다. 뒤집은 단어가 따로 없는 것처럼 보였기 때문이다. 조건을 다시 읽고 나서 회문이라는 걸 알았다.문제 소개단어 목록에서 비밀번호를 찾는 문제다. 조건은 하나다. 비밀번호를 뒤집은 문자열도 같은 목록에 있어야 한다. 비밀번호를 찾으면 길이와 가운데 글자를 출력한다. 모든 단어의 길이는 홀수로 보장된다.항목내용입력단어 수 N (2 ≤ N ≤ 100), 소문자 단어 N개 (길이 3~13, 홀수)출력비밀번호 길이, 가운데 글자 (답은 유일)핵심 개념문자열 뒤집기, 회문(palindrome), 리스트 탐색난이도브론즈 1핵심 조건 분석예제 2의 입력을 하나씩 확인해보면 이렇다.단어뒤집기목록에 존재?kisikkisik✅ (자기 자신 = 회문)ptqqtp❌tttrpprttt❌tulip..