Hungry Cow USACO 2023 February Bronze 1 Bronze 그리디 / 스위핑 문제 분석 Bessie는 매일 저녁에 건초더미가 1개 이상 있으면 1개를 먹는다 Farmer John이 특정 날 아침에 건초더미를 배달한다 (N번, 최대 105회) 첫 T일 동안 Bessie가 먹은 건초더미의 총 개수를 구해야 한다 핵심 제약: T가 최대 1014이므로 날짜별 시뮬레이션은 불가능 배달일 di는 오름차순 정렬되어 주어진다 (1 ≤ d1 2 N ≤ T) 접근법 T가 1014으로 매우 크지만, 배달 이벤트는 최대 105번뿐이다. 이벤트 사이 구간에서는 동일한..
스도쿠백준 2580 백트래킹 비트마스킹 Python Java문제 분석9×9 스도쿠 판의 빈 칸(0)을 규칙에 맞게 채우기행 제약: 각 가로줄에 1~9가 한 번씩열 제약: 각 세로줄에 1~9가 한 번씩박스 제약: 3×3 정사각형 안에 1~9가 한 번씩스페셜 저지: 여러 답 중 하나만 출력하면 됨시간 제한: 1초 (PyPy3: 1172ms) — Python3으로는 통과 불가, PyPy3 필요접근법백트래킹: 빈 칸 리스트를 미리 수집하고, 순서대로 가능한 숫자를 넣어보면서 탐색비트마스크 최적화: 행/열/박스별 사용된 숫자를 비트로 관리하여 O(1) 체크row[i], col[j], box[b]: 각각 사용된 숫자의 비트마스크가능한 숫자 = ~(row[i] | col[j] | box[b]) & 0x3FE (비트 ..
개요 대규모 데이터셋에서 원하는 정보를 효율적으로 저장하고 검색하는 것은 시스템 성능에 매우 중요하다.가령, 웹사이트에 사용자가 로그인했을 때 서버는 해당 사용자의 로그인 상태나 장바구니 정보 같은 걸 기억해야 한다고 가정해보자.사용자가 페이지를 이동할 때마다 이 정보를 빠르게 찾아야 하는데,배열이나 연결 리스트를 이용한 순차 탐색은 데이터 크기에 비례하여 탐색 시간(O(n))이 증가하며, 이진 탐색 트리(O(log n))도 한계가 있다.만약 로그인 시 발급된 고유한 세션ID(Key)에 해당하는 사용자의 정보(사용자 객체, 장바구니 정보 등)를 값(Value)로 저장한다면, 사용자의 요청에 세션ID로 바로 조회해서 사용자 정보를 순식간에 꺼내 쓸 수 있을 것이다.이를 통해 데이터 양과 관계없이 거의 일정..
