미니베리

1. 문제 요약https://www.acmicpc.net/problem/16165여러 개의 아이돌 그룹이 주어진다.각 그룹에는 여러 멤버가 존재한다.이후 두 가지 질의가 주어진다.2. 질의 유형 1) 0번: 그룹 이름 → 멤버 목록 출력 (사전순) 2) 1번: 멤버 이름 → 소속 그룹 출력2. 처음 접근 (리스트 기반)처음에는 단순하게 생각해서:groups: 그룹 이름 리스트members: 각 그룹의 멤버 리스트이렇게 저장했다. groups, members = [], [[] for _ in range(n)] 그리고 질의 처리 시:그룹 찾기 → groups 순회멤버 찾기 → members 전체 순회 + in 검사이후 오답처리되어 딕셔너리 형식으로도 처리해보았다.3. 문제점(오답 코드) 1) 리스트i..

1. 문제 요약https://www.acmicpc.net/problem/13414수강신청 시스템에서 학생들이 신청을 한다.총 L명의 신청 기록이 주어짐같은 학생이 여러 번 신청할 수 있음같은 학생이 여러 번 신청하면 마지막 신청만 유효문제를 처음 보고 든 생각이 문제는 수강신청 대기 명단처럼 보였다.학생들이 순서대로 신청을 하는데, 같은 학생이 여러 번 신청할 수 있고 마지막 신청만 유효하다는 점이 핵심이었다.즉, 단순히 입력을 그대로 저장하는 문제가 아니라중복된 학번을 처리해야 하고마지막 신청 기준으로 순서를 다시 판단해야 한다는 특징이 있었다.처음에는 큐처럼 순서를 관리하면 될 것 같아서 deque를 떠올렸다.2. 처음 시도: deque로 직접 중복 제거하기처음에는 신청 순서를 그대로 넣고,이미 들어..

1. 문제 요약문자열 S가 주어지고, 여러 개의 질의가 들어온다.각 질의는 다음과 같다:alpha[l][r] 👉 구간 [l, r]에서 문자 alpha가 몇 번 등장하는지 구하기2. 처음 접근 (딕셔너리 + 완전탐색)처음에는 문자별 인덱스를 저장하고, 매 쿼리마다 직접 확인했다.panels = dict()for i, c in enumerate(s): if c not in panels: panels[c] = [i] else: panels[c].append(i)for k in panels[alpha]: if l ❌ 문제점질의마다 리스트를 순회 → 최악 O(N)시간초과 발생3. 개선 시도 (누적합 / Prefix Sum)그래서 각 알파벳별 누적합 배열을 만들었다.pa..

1. 문제 요약https://www.acmicpc.net/problem/2559연속된 K일 동안의 온도 합 중에서 최댓값을 구하는 문제다.예를 들어,3 -2 -4 -9 0 3 7 13 8 -3 이 주어졌을 때,K = 2 → 최대 합 = 21K = 5 → 최대 합 = 312. 처음 접근 (시간초과 발생)처음에는 이렇게 풀었다. for i in range(n): for di in range(1, k): pannels[i] += pannels[i+di]3. 문제점매 시작점마다 K개를 다시 더함시간복잡도: O(N × K)최악의 경우:100,000 × 100,000 → 10^10 👉 시간초과 발생4. 핵심 아이디어: 슬라이딩 윈도우이 문제의 핵심은"연속된 구간의 합을 매번 다시 구할 필요가 없다"?..

1. 문제 요약물건 N개 (각각 무게 W, 가치 V)최대 무게 K가치의 합이 최대가 되도록 물건 선택👉 단, 각 물건은 한 번만 선택 가능 (0/1 배낭)2. 처음 접근 (실패 이유)처음에는 이런 식으로 생각했다:각 물건마다 “최적의 조합 하나”만 저장이전 결과랑 비교해서 갱신하지만 이 방식은 틀렸다.🚨 왜 틀릴까?배낭 문제는 한 시점에서도 여러 선택지가 필요하다.예를 들어:조합가치무게A105B93👉 지금 보면 A가 더 좋아 보이지만👉 나중에 물건을 추가하면 B가 더 유리할 수도 있음즉,❗ “현재 최적 하나만 남기면 미래의 최적을 놓칠 수 있다”3. 핵심 아이디어🔥 DP 정의 dp[j] = 무게가 j일 때 얻을 수 있는 최대 가치4. 점화식현재 물건 (w, v)를 고려할 때: dp[j] = ma..

1) 문제수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다.예시A = {10, 20, 10, 30, 20, 50} 가능한 증가 부분 수열 중 하나10 → 20 → 30 → 50 따라서 정답은 4이다.여기서 중요한 점은 "연속된 수열이 아니라 부분 수열"이라는 점이다.즉 중간 값을 건너뛰어도 된다.2) 처음 접근 (실패했던 아이디어)처음에는 다음과 같이 2차원 DP를 생각할 수도 있다.dp[i][j] = i까지 고려했을 때 j를 선택한 경우 하지만 이렇게 설계하면상태 수가 불필요하게 많아지고문제 해결에 필요하지 않은 정보까지 저장하게 된다.LIS 문제에서는 사실 마지막 원소만 알면 충분하다.그래서 1차원 DP로 해결하는 것이 정석적인 방법이다.3) 핵심 아이디어DP 배열을 다음과..

백준 10844번 쉬운 계단 수1. 문제https://www.acmicpc.net/problem/10844 어떤 수의 인접한 자리의 차이가 항상 1이면 이를 계단 수라고 한다.문제는 다음과 같다.길이가 N인 계단 수의 개수를 구하시오.단 0으로 시작하는 수는 계단 수가 아니다.2. 처음 떠올릴 수 있는 방법 (완전 탐색)처음에는 이런 방식이 떠오를 수 있다.1자리 숫자 만들기→ 뒤에 숫자를 붙이기→ 인접한 자리 차이가 1인지 확인 예를 들어1 → 10, 122 → 21, 233 → 32, 34 이런 식으로 계속 숫자를 만들어 나가는 방식이다.하지만 이 방식은 문제가 있다.길이가 최대 100이기 때문에 가능한 경우의 수가 거의 10^100수준이 된다.즉 완전탐색은 불가능하다.3. 핵심 아이디어 (DP)숫자..