미니베리

1. 문제 요약https://www.acmicpc.net/problem/1781 각 문제마다데드라인 (d)컵라면 수 (c)가 주어진다.모든 문제는 1시간씩 걸리고,각 문제는 데드라인 이전에만 풀 수 있다.→ 목표:얻을 수 있는 컵라면의 최대 개수2. 처음 접근 (틀린 코드)처음에는 이런 식으로 접근했다.heapq.heappush(heap, (dead_line, -cup)) 데드라인 기준으로 정렬하면서같은 데드라인이면 컵라면 많은 것 우선 선택그리고 하나 선택한 뒤while heap and curr >= heap[0][0]: heapq.heappop(heap) 즉,하나 고르면같은 데드라인 이하 문제는 다 버리는 방식3. 왜 틀렸는가?핵심 문제같은 데드라인에서도 여러 개 선택할 수 있다 반례32 102 92..

1. 문제 요약https://www.acmicpc.net/problem/1202보석 N개 (무게 M, 가격 V)가방 K개 (각 가방은 하나의 보석만 담을 수 있음)가방마다 최대 무게 제한 존재→ 목표: 담을 수 있는 보석 가격 합의 최대값2. 처음 접근 (실패)처음에는 이렇게 생각했다.“가장 비싼 보석부터 넣으면 되지 않을까?”그래서 구현:heapq.heappush(jewels, (-v, m)) # 가치 기준 최대힙 그리고:if bags[0] >= m: heapq.heappop(bags) 문제점이 방식은 보석 중심 사고였다.가치 높은 보석부터 꺼냄가장 작은 가방 하나만 보고 넣을지 결정 문제:뒤에 있는 더 큰 가방에 들어갈 수 있는 보석도 그냥 버려짐 핵심 반례2 210 1002 99210 내 코드 결..

1. 문제를 처음 봤을 때처음에는 단순히“카드를 합치면 비용이 든다 → 그냥 순서대로 더하면 되지 않나?”라고 생각했다.하지만 예시를 보면(10 + 20) + (30 + 40) = 100(10 + 40) + (50 + 20) = 120합치는 순서에 따라 비용이 달라진다여기서 핵심은“어떤 순서로 합쳐야 최소가 되는가?”2. 처음 접근 (잘못된 방식)처음에는 이런 식으로 구현했다.answer += answer + heapq.heappop(heap)즉,이전 결과(answer)를 계속 재활용하면서 더하는 방식하지만 이건 문제의 구조를 잘못 이해한 것이다. 왜 틀렸는가?answer는 “총 비용”이지“카드 묶음”이 아니다나는 answer를 카드 묶음처럼 사용해버림3. 핵심 깨달음이 문제에서 중요한 건 딱 하나였다...

문제: https://www.acmicpc.net/problem/65491. 문제 접근 - 처음 생각했던 방식들히스토그램에서 가장 큰 직사각형을 구하는 문제.처음에는 자연스럽게 브루트포스로 접근했다. 1) 시도 1각 막대를 기준으로좌우로 확장하면서 “자기보다 크거나 같은 구간 길이”를 구함시간복잡도: O(n³) 수준바로 시간초과 예상 2) 시도 2높이 기준으로 접근(예: 높이 1 ~ max 높이까지 각각 구간 계산)시간복잡도: O(n × h)h 최대가 10억이라 불가능→ 여기서 깨달은 점:“이 문제는 구간을 찾는 문제가 아니라각 막대가 ‘최소 높이’가 되는 최대 구간을 찾는 문제다.”2. 핵심 아이디어어떤 막대 하나를 기준으로 보면높이 = 그 막대 높이너비 = 그 막대보다 낮은 막대를 만날 때까지 확장한..

1. 문제 요약한 줄로 서 있는 사람들 중에서 서로 볼 수 있는 쌍의 개수를 구하는 문제이다.→ 두 사람이 서로 볼 수 있으려면 사이에 있는 사람들 중에서 둘 중 하나보다 더 큰 사람이 없어야 한다.2. 처음 접근 (실패한 방식)처음에는 이렇게 생각했다.각 사람 i 기준으로 오른쪽을 보자- 계속 비교하면서- 처음 나보다 큰 사람을 만나면 상태 전환- 이후 감소하면 종료 즉, 흐름을 이렇게 단순화했다.V 형태는 가능^ 형태는 불가능그래서 아래처럼 구현했다.for i in range(n): check = False for j in range(i+1, n): if not check: answer += 1 if heights[i] heights[j..

1. 문제 한 줄 요약https://www.acmicpc.net/problem/6198 각 빌딩에서 오른쪽을 보면서 자신보다 높거나 같은 빌딩이 나오기 전까지 볼 수 있는 빌딩 수의 총합을 구하는 문제.2. 처음 접근 (실패한 방법)처음에는 이렇게 생각했다."각 빌딩마다→ 나보다 큰 빌딩이 처음 나오는 위치를 찾으면→ 그 전까지 개수를 세면 되지 않을까?"그래서 다음과 같이 접근했다:오른쪽 빌딩들을 스택으로 관리뒤에서부터 순회하면서stack[-1][index] - 현재 index로 개수를 계산memo[i] = stack[-1][0] - i3. 왜 틀렸는가이 방식은 겉보기엔 맞아 보이지만 핵심적인 문제가 있다. 1) “가장 가까운 큰 빌딩 하나”만 보면 안 됨이 문제는 단순히“막는 빌딩 위치 하나 찾기”가..

1. 문제 요약https://www.acmicpc.net/problem/2164 1부터 N까지 카드가 순서대로 쌓여있다.다음 과정을 반복한다:맨 위 카드 버리기그 다음 카드 맨 아래로 이동→ 마지막에 남는 카드 번호를 구하는 문제2. 예시로 이해하기N = 6일 때123456→ 1 버림: 23456→ 2 아래로: 34562→ 3 버림: 4562→ 4 아래로: 5624→ 5 버림: 624→ 6 아래로: 246→ 2 버림: 46→ 4 아래로: 64→ 6 버림: 4 → 정답: 43. 접근 방법이 문제는 가장 아래있는 수를 제어해야 하므로 큐 문제핵심 연산앞에서 제거 → popleft()뒤에 추가 → append()→ deque 사용 필수4. 내가 작성한 코드from collections import deque..

1. 문제 요약https://www.acmicpc.net/problem/2493 각 탑은 왼쪽 방향으로 신호를 보낸다.이때 자신보다 높은 탑 중에서 가장 가까운 탑이 신호를 받는다.→ 각 탑마다 “왼쪽에서 가장 가까운 높은 탑의 위치”를 구하는 문제2. 처음 접근 (완전탐색)처음에는 단순하게 생각했다.“각 탑마다 왼쪽을 쭉 탐색하면서 처음 만나는 큰 탑 찾으면 되겠네?”그래서 구현한 코드는 다음과 같다.import sysinput = sys.stdin.readlinen = int(input())top = list(map(int, input().split()))answer = [0] * nfor where in range(n - 1, -1, -1): height = top[where] for ..

1. 문제 요약https://www.acmicpc.net/problem/20166N×M 격자에서 시작8방향 이동 가능 (대각선 포함)환형 구조 (wrap-around)→ 경계 넘어가면 반대편으로 이동같은 칸 재방문 가능문자열을 만들고, 주어진 K개의 문자열에 대해 경우의 수 계산1. 처음 접근 (DFS + 문자열마다 탐색)처음에는 이렇게 풀었다:for god_like in god_likes: for 모든 시작점: DFS로 문자열 생성2. 문제점문자열마다 DFS 수행 → 중복 탐색 발생같은 경로를 계속 다시 탐색K 최대 1000 → 시간초과3. 깨달음이 문제는 이렇게 풀면 안 된다:❌ "문자열이 주어졌으니까 → 찾아야지"대신 이렇게 바꿔야 한다:✅ "만들 수 있는 문자열을 전부 만들어놓고 → 조회하자" ..

1. 문제 요약온라인 스트리밍으로 진행된 개강총회에서출석 인정 조건은 다음과 같다. 1) 입장 확인 - 시작 시간 S 이전 또는 정확히 S 시각에 채팅한 사람 2) 퇴장 확인 - 종료 시간 E 이후부터 스트리밍 종료 Q까지 채팅한 사람즉,S 이전에 채팅 + E~Q 사이에 채팅둘 다 만족하는 사람 수를 구하는 문제2. 접근 아이디어이 문제는 딱 보면 복잡해 보이지만 핵심은 단순하다.→ 사람을 두 번 필터링하면 된다. 1) 입장 체크time → 이때 채팅한 사람들을 enter 집합에 저장 2) 퇴장 체크 E 이때 채팅한 사람 중에서 이미 enter에 있었던 사람만 카운트3. 핵심 포인트 1) 입력 끝 처리이 문제는 채팅 개수가 안 주어짐해결방법:fo..