말하는대로

오늘은 그리디(Greedy) 알고리즘의 핵심 개념을 활용하는 문제인 백준 2437번: 저울을 풀어보았다. 🧩 문제 요약 여러 개의 저울추가 주어진다. 이 추들을 이용해 측정할 수 없는 가장 작은 양의 정수 무게를 구하는 문제다. 예: [3, 1, 6, 2, 7, 30, 1] → 정답: 21 🔍 핵심 아이디어 추들을 오름차순 정렬한 후, 지금까지 만들 수 있는 최대 누적합을 `target`이라 한다. 매번 다음 추의 무게 `w`를 확인하며, w > target일 경우, 그 순간 target이 측정할 수 없는 최소 무게가 된다. 🤔 왜 그렇게 되는가? 예를 들어, 현재까지 1 ~ 20까지는 만들 수 있었다고 하자. 그런..

이번 문제는 간단한 정규식 패턴 매칭 문제였습니다. 한국이 그리울 땐 서버에 접속하지[9996] 📋 문제 설명 첫째 줄에 파일의 개수 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 패턴이 주어진다. 패턴은 알파벳 소문자와 별표(*) 한 개로 이루어져 있으며, 별표는 문자열의 시작과 끝에 있지 않다. 다음 N개의 줄에는 각 파일 이름이 주어지고, 패턴과 일치하는지 판별해야 한다. 별표(*)는 임의의 문자열(길이 0 이상)을 의미하며, 정규식의 .*와 동일하다. 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고: "DA"는 YES, "NE"는 NO를 의미한다. 🧪 입..

📌 백준 10799번 - 쇠막대기 (스택)문제는 다음과 같음 👇- "(" 막대의 시작을 STACK 에 저장하고,- ")" 를 만날때 레이저이기 때문에 레이저 구성인 '(' 를 스택에서 제거한 뒤- 나머지 스택의 길이를 z(조각)에 저장합니다. (레이저를 만나서 잘린 조각)- 이후 ")"의 전 괄호가 ')' 일 경우에는 하나의 막대가 끝난것이기 때문에 +1을 해줍니다 (끝난 막대의 마지막 잘린 조각 더해줌)코드n = "()(((()())(())()))(())"bar_stack = []z = 0for i, _ in enumerate(n): if n[i] == "(": bar_stack.append(n[i]) else: if n[i-1] == "(": ..

2차원 배열 탐색 문제는 그래프로 모델링해서 BFS/DFS로 접근하면 깔끔하다.이 문제는 상하좌우뿐만 아니라 대각선까지 포함한 총 8방향 탐색이 핵심.BFS 탐색 시, 방문한 위치를 바로 0으로 바꿔서 방문 처리하면 별도의 visited 배열이 필요 없다.입력이 여러 그룹으로 구성되어 있고, 각 그룹이 끝나는 조건(0 0 입력)을 주의해야 한다.입력이 많아질 수 있으므로 sys.stdin.readline()을 쓰는 것이 성능상 유리하다.from collections import dequeimport sysinput = sys.stdin.readline# 8방향 탐색dx = [-1, 1, 0, 0, -1, -1, 1, 1]dy = [0, 0, -1, 1, -1, 1, -1, 1]def bfs(x, y, g..

📘 TIL - 백준 2559번: 수열 + 슬라이딩 윈도우 개념 정리🔍 문제 개요매일 측정한 온도를 정수 수열로 입력받고,연속된 K일 간의 온도 합 중 최대값을 구하는 문제.✅ 사용한 알고리즘: 슬라이딩 윈도우 (Sliding Window)📌 개념 정리슬라이딩 윈도우는 고정된 길이의 연속된 범위를 이동시키며 조건을 만족하는 구간을 탐색하는 기법매번 구간을 슬라이스하거나 합을 새로 구하면 비효율적이기 때문에,앞 원소는 빼고, 뒤 원소는 더해서 빠르게 구간합을 갱신하는 방식✨ 슬라이딩 윈도우 구현 예시 (K=3)temps = [3, -2, -4, -9, 0, 3, 7, 13, 8, -3]k = 3# 첫 윈도우 합 계산res = sum(temps[:k])max_sum = res# 윈도우를 한 칸씩 오른쪽으..

오늘도 역시 굉장히 어려운 문제였어용.... 문제 : 백준 2468번: 안전영역해당 문제는 그래프 탐색 문제였고, DFS / BFS 의 개념이 필요했습니다.문제를 정확히 풀기 위해 먼저 그래프 탐색의 개념을 정리해보았습니다.📌 그래프(Graph)란?정점(Node)과 정점을 연결하는 간선(Edge)으로 구성된 자료구조입니다.그래프 탐색은 하나의 정점에서 시작해 모든 정점을 탐색하는 것입니다. DFS (Depth-First Search)깊이 우선 탐색 하나의 경로를 최대 깊이까지 계속 들어가며 탐색하고,더 이상 갈 곳이 없으면 이전 경로로 백트래킹(되돌아감)스택 또는 재귀 함수로 구현 가능BFS ( Breadth-Frist Search)너비 우선 탐색현재 위치에서 갈 수 있는 모든 노드를 먼저 탐색하고..

오늘은 바탕화면 정리 드래그 범위 계산 두가지 풀이법에 대해 적겠어용일단 해당문제는 큰 알고리즘 개념이 들어가지 않습니다.문제 설명 요약바탕화면은 문자열 배열로 표현되며, "#"는 파일이 존재하는 위치한 번의 드래그로 모든 파일을 선택할 수 있는 최소 범위를 구해야 함드래그 범위는 [lux, luy, rdx, rdy] 형태로 출력해야 함여기서:(lux, luy) = 드래그 시작점 (최소 행, 최소 열)(rdx, rdy) = 드래그 끝점 다음 칸 (최대 행 + 1, 최대 열 + 1)풀이 1 - re를 사용한 풀이import redef solve(wallpaper): res = [None, None, None, None] file_icon = "#" for i, row in enumerate..

🧮 백준 14495번: 피보나치 비스무리한 수열오늘은 피보나치를 DP로 풀어내는 문제를 풀어볼 거에요.🧩 피보나치 수열?피보나치 수열이란 첫째, 둘째 항이 1이고 그 뒤의 항은 바로 앞의 두 항의 합인 수열입니다.F(n): 1, 1, 2, 3, 5, 8, 13, ...일반적으로 피보나치를 구하는 알고리즘을 코드로 구현할 때는 재귀함수를 사용합니다.def fivo(n): if n 이렇게 재귀함수로 피보나치 수열을 구할 경우 시간복잡도는 O(2^N) 이 됩니다.해당 시간복잡도는 O(n^2)보다도, n^3보다도 성능이 좋지 않습니다.그래서 우리는 이 경우를 피하기 위해, 그리고 DP를 배우기 위해 피보나치를 DP로 구현하게 됩니다.💡 DP(다이나믹 프로그래밍 | 동적 계획법)?자료들이 생각보다 많은..

📌 백준 1929번: 소수 구하기오늘은 백준의 1929번 - 소수 구하기 문제를 풀면서에라토스테네스의 체를 활용하게 되었고, 이에 대해 간단히 정리해보려고 합니다.⏱️ 문제 조건과 제한입력: 자연수 M, N (1 ≤ M ≤ N ≤ 1,000,000)출력: M 이상 N 이하의 소수를 한 줄에 하나씩 출력시간 제한: 2초❌ 일반적인 소수 판별로는 시간 초과예를 들어, M=3, N=16이라면단순히 3부터 16까지 모든 수를 순회하며, 매 수마다 소수 판별을 하면각 수 i에 대해 2부터 i-1까지 나눠야 하므로시간 복잡도: O(N^2)→ 1,000,000 범위에서는 시간 초과 발생합니다.✅ 해결 전략: 에라토스테네스의 체이 문제는 "소수를 빠르게 구해야 하는 전형적인 문제"입니다.따라서 에라토스테네스의 체 알..

프로젝트를 진행하던 중 타입을 선택하는 것에 있어서 고민이 생겼고, 자료를 찾아가며 나름의 기준이 필요했다. 고민의 시작: dataclass 폭탄처음으로는 Dataclass를 사용하였는데 사용하며 좀 마구잡이로 쓴 경향이 있지 않나 싶다. 이 고민은 한 책[전문가를 위한 파이썬(2판]에서 말하기를  추가적인 메서드 동작없이 타입만을 체크하기 위해 Dataclass 로 선언한것이라면, 냄새를 유발할 수도 있다는 의견을 보고 시작되었다. 왜 정적 타입이 필요하지?동적 타이핑을 베이스로 두고 타입추론을 하는 파이썬은 다른 언어에 비해 유연하고 빠른 개발을 할 수 있는 특징이 있다. 하지만 여기서 정적 타입검사는 왜 나왔을까? 이건 동적 타입 언어의 특징에서 찾아 볼 수 있다. exam = "나는문자열"typ..