Python/algorithm 38

TIL - 2025.03.28

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..

Python/algorithm 2025.04.07

슬라이딩 윈도우

📘 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# 윈도우를 한 칸씩 오른쪽으..

Python/algorithm 2025.04.04

DFS - 백준 2468번 :안전영역

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

Python/algorithm 2025.04.03

바탕화면 정리 드래그 범위 계산 – 두 가지 풀이

오늘은 바탕화면 정리 드래그 범위 계산 두가지 풀이법에 대해 적겠어용일단 해당문제는 큰 알고리즘 개념이 들어가지 않습니다.문제 설명 요약바탕화면은 문자열 배열로 표현되며, "#"는 파일이 존재하는 위치한 번의 드래그로 모든 파일을 선택할 수 있는 최소 범위를 구해야 함드래그 범위는 [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..

Python/algorithm 2025.04.02

피보나치 수열과 DP[백준 피보나치 비스무리한 수열]

🧮 백준 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(다이나믹 프로그래밍 | 동적 계획법)?자료들이 생각보다 많은..

Python/algorithm 2025.04.01

에라토스테네스의 체 [소수 구하기]

📌 백준 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 범위에서는 시간 초과 발생합니다.✅ 해결 전략: 에라토스테네스의 체이 문제는 "소수를 빠르게 구해야 하는 전형적인 문제"입니다.따라서 에라토스테네스의 체 알..

Python/algorithm 2025.03.31

[Leetcode] 1528. Shuffle String

Problem 이번 문제는 s 라는 문자열이 주어지고 indices에 s 문자열 각자리의 알맞는 인덱스가 들어가있고 정렬해서 return 해주는 문제이다. 나의 풀이 class Solution: def restoreString(self, s: str, indices: List[int]) -> str: res = '' zipped = sorted(zip(indices, s), key=lambda x: x[0]) for idx,char in zipped: res += char return res zip으로 두개를 묶고 , 인덱스를 기준으로 정렬한 뒤에 res에 더해주고 return 해 주었어용 다른 사람의 풀이 두가지를 보자 class Solution: def restoreString(self, s: str..

Python/algorithm 2023.01.12

[Leetcode] 2236. Root Equals Sum of Children

Problem 이번 문제는 이진 트리를 주고 ? 루트, 왼쪽, 오른쪽 자식 값이 존재한다. left , right 의 합이 root와 같으면 True 아니면 false를 return 한다. 나의 풀이 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def checkTree(self, root: Optional[TreeNode]) -> bool: #print(root.left, root.left.val) #print(root.right,..

Python/algorithm 2023.01.11

[Leetcode] 1365. How Many Numbers Are Smaller Than the Current Number

Problem 이번 문제는 nums 각 값을 nums의 다른 값과 비교하여 작은값의 갯수를 배열로 return 해주는 문제이다 나의 풀이 class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: res = list() for i in nums: cnt = 0 for j in nums: if i > j: cnt += 1 res.append(cnt) return res 열심히 짱구를 굴려봤는데 for 두번을 사용하지않고는 문제가 풀리지 않았다. 다른 사람의 풀이 class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: l1 = ..

Python/algorithm 2023.01.05

[Leetcode] 1281. Subtract the Product and Sum of Digits of an Integer

Problem 이번 문제는 주어진 수 n의 각 자리수를 곱한 값에 더한 값을 뺀 값을 결과로 낸다 나의 풀이 from functools import reduce class Solution: def subtractProductAndSum(self, n: int) -> int: a = list(map(int,str(n))) return reduce((lambda x,y: x*y), a) - sum(a) list로 바꿔주고 functools 에 있는 reduce를 사용하여 문제를 풀었다 더한 값의 경우는 sum 을 사용하면 되지만 곱한 값의 경우는 sum 같은 부분이 없다 ㅠㅠ reduce(sum,[1,2,3,4,5,6])

Python/algorithm 2023.01.04