cedis 님의 블로그

[컴퓨터 시스템] 1. 프로그램은 어디에서 실행될까 시스템 공부를 처음 시작하면 C, 메모리, CPU, 운영체제, 스레드가 서로 다른 과목처럼 보이기 쉽습니다. 그래서 초반에는 세부 기술보다 먼저 이 주제들이 모두 같은 실행 장면을 다른 높이에서 설명한다는 감각을 잡아두는 편이 중요합니다.이번 글은 책 소개가 아니라 좌표축을 세우는 글입니다. 프로그램 하나가 저장장치에 놓여 있다가 실행되고, 메모리로 올라오고, CPU가 읽고, 운영체제가 그 과정을 관리하는 흐름을 먼저 정리해두면 뒤의 편들이 훨씬 덜 흩어집니다. 먼저 짚고 갈 용어 CPU: 메모리에서 명령을 읽고 계산을 수행하는 장치RAM: 실행 중인 코드와 데이터가 잠시 머무는 작업 공간운영체제: 하드웨어 ..

이번 문제는 도시를 한 번씩만 방문하고 다시 출발점으로 돌아오는 최소 비용을 구하는 문제입니다. 겉으로 보면 순열을 전부 확인해야 할 것처럼 보이지만, 도시 수가 최대 16개라서 그런 방식은 불가능합니다. 핵심은 현재 도시와 방문한 도시 집합을 하나의 상태로 묶는 비트마스크 DP입니다.핵심 요약상태는 dfs(cur, visited) 로 정의합니다.현재 도시와 방문 집합이 같으면, 그 뒤의 최소 비용은 항상 같습니다.모든 도시를 방문하면 출발 도시로 돌아가는 비용만 더하면 됩니다.길이 없는 경우는 비용이 0이므로 다음 상태 후보에서 제외합니다.시간 복잡도는 O(N² · 2^N) 입니다.1. 문제 설명백준 2098번 외판원 순회 는 한 도시에서 출발해 모든 도시를 정확히 한 번씩 방문한 뒤 다시 출발 도시로..

이번 문제는 백준 골드 1 난이도의 대표적인 그리디 문제인 멀티탭 스케줄링입니다. 처음 보면 구현처럼 보일 수 있지만, 핵심은 지금 어떤 플러그를 뽑아야 이후에 가장 유리한가를 판단하는 데 있습니다. 이 글에서는 문제 아이디어, 왜 그리디가 되는지, 시각화, 코드 해설, 그리고 실수하기 쉬운 포인트까지 한 번에 정리해보겠습니다.핵심 요약이미 꽂혀 있는 기기라면 그냥 사용하면 됩니다.빈 구멍이 있다면 새 기기를 그냥 꽂으면 됩니다.꽂을 자리가 없으면 앞으로 가장 늦게 다시 쓰이거나, 다시는 쓰이지 않는 기기를 뽑아야 합니다.즉, 현재 순간에서 미래 사용 순서를 보고 가장 손해가 적은 선택을 하는 전형적인 그리디입니다.정답은 플러그를 뽑은 횟수의 최솟값입니다.1. 문제 설명멀티탭 구멍의 개수 N 과 전기용품..

이번 문제는 문자열 s를 사전에 있는 단어들로 끊어서 만들 수 있는지 판별하는 Word Break 문제입니다. 얼핏 보면 문자열 탐색 문제 같지만, 실제로는 앞에서부터 어디까지 만들 수 있는지를 저장해 가는 전형적인 DP 문제입니다. 이 글에서는 문제 아이디어, 점화식, 시각화, 예제 분석, 그리고 코드 한 줄 설명까지 한 번에 정리해보겠습니다.핵심 요약문자열을 앞에서부터 잘라 보면서 만들 수 있는 위치를 체크합니다.dp[i]는 s의 앞 i글자까지 만들 수 있는지를 의미합니다.어떤 j에 대해 dp[j] == True 이고 s[j:i] 가 사전에 있으면 dp[i] = True 입니다.핵심은 이전까지 만들 수 있었는가 + 이번 조각이 사전에 있는가 입니다.시간 복잡도는 기본적으로 O(n²) 탐색 구조를 가집..

LeetCode · Dynamic Programming · PythonLeetCode House Robber 파이썬 풀이오늘은 DP 입문 문제로 자주 등장하는 House Robber를 정리해보겠습니다. 단순히 정답 코드만 보는 것이 아니라, 왜 이 문제가 DP인지, 어떻게 값이 쌓이는지 시각적으로, 그리고 코드가 실제로 한 줄씩 무슨 역할을 하는지까지 한 번에 이해할 수 있도록 구성했습니다.핵심 요약서로 붙어 있는 집은 동시에 털 수 없습니다.각 위치에서 현재 집을 털지 / 털지 않을지 비교합니다.점화식은 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 입니다.이번 글에는 시각화와 코드 한 줄 한 줄 해설도 포함했습니다.시간 복잡도는 O(n), 공간 복잡도는 O(n) 입니다.1. ..

정렬 후 기준값이 어떻게 갱신되는지 눈에 보이도록 만든 상세형 버전이다.1. 문제를 아주 짧게 말하면다른 지원자보다 서류와 면접이 모두 밀리는 사람은 선발할 수 없다. 이 조건을 만족하며 최대로 몇 명을 선발할 수 있는지 구하는 문제다. [Source](https://www.acmicpc.net/problem/1946)2. 핵심 아이디어한 기준으로 정렬하고 다른 기준만 본다서류 등수로 정렬하면, 현재 사람보다 앞에 있는 사람들은 모두 서류가 더 좋다. 따라서 현재 사람은 면접 등수만 지금까지의 최솟값보다 좋으면 선발 가능하다.3. 전체 코드 1import sys 2 3input = sys.stdin.readline 4t = int(input()) 5 6for _ in range(t): 7 n = int(..

정렬 뒤 어떤 회의가 선택되고 왜 탈락하는지 흐름 중심으로 정리한 상세형 버전이다.1. 문제를 아주 짧게 말하면회의가 서로 겹치지 않게 하면서 최대 몇 개를 선택할 수 있는지 구하는 대표적인 그리디 문제다. 끝나는 시간이 빠른 회의를 먼저 잡는 것이 핵심이다. [Source](https://www.acmicpc.net/problem/1931)2. 핵심 아이디어왜 종료 시간이 빠른 회의를 먼저 고를까?가장 빨리 끝나는 회의를 먼저 골라야 이후에 더 많은 회의를 붙일 여지가 남기 때문이다.정렬 기준: 종료 시간 오름차순 → 종료 시간이 같으면 시작 시간 오름차순3. 전체 코드 1import sys 2 3input = sys.stdin.readline 4n = int(input()) 5meetings = [t..

코인 하나를 반영할 때마다 배열이 어떻게 바뀌는지 보여주는 상세형 정리다.1. 문제를 아주 짧게 말하면주어진 동전들로 목표 금액 M을 만드는 모든 방법 수를 구하는 문제다. 최소 동전 개수가 아니라 조합의 개수를 세는 것이 핵심이다. [Source](https://www.acmicpc.net/problem/9084)2. 핵심 아이디어dp[x]의 뜻금액 x를 만드는 방법의 수초기값: dp[0] = 1업데이트: dp[money] += dp[money-coin]동전이 바깥 루프여야 순서만 다른 경우를 중복 계산하지 않는다.3. 전체 코드 1import sys 2 3input = sys.stdin.readline 4t = int(input()) 5 6for _ in range(t): 7 n = int(input..

상태 정의와 경로 감각이 중요해서 상태 중심으로 풀어 쓴 상세형 버전이다.1. 문제를 아주 짧게 말하면1번 돌에서 N번 돌까지 앞으로만 이동한다. 이전 점프 길이를 기준으로 다음 점프 길이는 -1, 0, +1만 바꿀 수 있고, 몇몇 돌은 밟을 수 없다. 목표는 최소 점프 횟수다. [Source](https://www.acmicpc.net/problem/2253)2. 핵심 아이디어상태를 두 개로 잡아야 한다현재 돌 번호만 알면 부족하다. 직전에 몇 칸을 뛰었는지도 알아야 다음 점프 후보가 정해지기 때문이다.dp[i][v] = i번 돌에 마지막 점프 길이 v로 도착했을 때의 최소 점프 횟수3. 전체 코드 1import sys 2 3input = sys.stdin.readline 4INF = 10 ** 9 5..

한 줄 해설과 용량별 DP 변화 중심으로 정리한 상세형 버전이다.1. 문제를 아주 짧게 말하면무게 제한 K 안에서 여러 물건 중 일부를 골라 담을 때 얻을 수 있는 가치의 최댓값을 구하는 전형적인 0/1 배낭 문제다. 물건은 각각 한 번만 사용할 수 있다. [Source](https://www.acmicpc.net/problem/12865)2. 핵심 아이디어dp[i][cap]의 뜻앞에서 i개 물건만 고려했을 때, 가방 용량 cap으로 얻을 수 있는 최대 가치현재 물건을 안 넣으면: dp[i-1][cap]현재 물건을 넣으면: dp[i-1][cap-weight] + value3. 전체 코드 1import sys 2 3input = sys.stdin.readline 4n, k = map(int, input()..