Algorithm Problem

[python] 백준 - 1012. 유기농 배추

🤔문제 해결 S2 | 그래프, DFS 배추밭과 배추의 위치를 2차원배열로 만든다. 배추리스트에서 하나 꺼내서 DFS로 인접한 배추들을 다 0으로 바꿔준다. 💻소스 코드 import sys input = sys.stdin.readline def find_dummy(x: int, y: int): farm[x][y] = 0 stack = [(x, y)] dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] while stack: cx, cy = stack.pop() for k in range(len(dx)): nx = cx + dx[k] ny = cy + dy[k] if 0

[python] 백준 - 14719. 빗물

🤔문제 해결 G5 | 구현, 시뮬레이션 며칠 전 nhn 코테 문제랑 비슷한 문제. 그 때는 자바로 풀었기도 하고, 더 복잡하게 푼거같다. 딱히 어려운 기술을 요구하는 문제는 아니다. 오른쪽으로 가면서 자신보다 높거나 같은 블럭을 찾는다. 가는 중에 자신보다 낮지만가장 큰 놈을 찜해 놓는다. 위의 과정이 끝나면 양쪽의 블럭중 낮은 블럭 만큼의 빗물을 사이의 블럭에 채운다. 💻소스 코드 def find_block(x: int) -> int: # 오른쪽으로 가면서 자신보다 크거나 같은 블럭을 찾는다. # 가는 중에 자신보다 작지만 그 중에 가장 큰 놈을 찜해 놓는다. max_block = [0, 0] for j in range(x + 1, W): if block[j] >= block[x]: return j i..

[python] 백준 - 12865. 평범한 배낭

🤔문제 해결 G5 | DP, 냅색 알고리즘(배낭 알고리즘) 딱 봐도 너무 복잡해 보이는 DP... 2차원 배열로 풀어야할 것 같다. 행은 각 아이템, 열은 현재 무게(?) 아이템 하나를 고른다. 가방의 버틸 수 있는 무게를 0부터 M까지 올려본다. 해당 무게별로 최대로 채울 수 있는 가장 큰 값을 채운다. 사실 그렇게 딱!!! 완전히 이해는 하지 못했다... 역시 DP는 어려움 나중에 비슷한 문제를 한번 더 풀면 이해가 가지 않을까... 💻소스 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) # 물품 수, 최대 무게 items = [tuple(map(int, input().split())) for _ in range(N)..

[python] 백준 - 1325. 효율적인 해킹

🤔문제 해결 S2 | 그래프, BFS(DFS) 단순한 그래프 문제였는데 전부다 시간초과 발생.... 다른 분들 제출한것도 보니까 대부분 시간초과이다. (그래서 pypy3로 제출하니 성공) 풀이방법은 인접리스트 생성 (이 문제에서는 a->b가 아니라 b->a 이다) 모든 노드에 대해서 BFS를 돌린다. 그 때 몇개의 노드를 돌았는지 숫자를 세준다. 가장 높은 카운트의 노드들을 출력한다. 다른 분들의 풀이를 봤는데 풀이가 나랑똑같다. 하지만 어떻게 통과했는지... 💻소스 코드 import sys from collections import defaultdict from collections import deque def bfs(start): q = deque([start]) visited = [0] * (N ..

[python] 백준 - 10773. 괄호

🤔문제 해결 S4 | 스택 너무 기본적인 스택문제라서 포스팅을 안하려고 했지만 input 과 sys.stdin.readline 에 대해서 말하고 싶어서 포스팅했다. 위의 사진을 보면 시간에서 큰 차이가 있을 것이다. 첫번째는 sys.stdin.readline을 사용하고, 두 번째는 input을 사용했다. 엄청난 시간차이가 나타난다. 이렇게 한줄 한줄 읽는 식으로 인풋값을 받을 때는 첫번째 방법을 사용하는 게 훨씬 빠르다. 속도 비교 하기 [python] input, sys.stdin.readline 📗 파이썬 알고리즘 풀 때!! 입력 속도 문제 🔵 input vs sys.stdin.readline 천만개의 숫자를 한줄한줄 입력받을 때의 속도 입력 방법 속도 input() 12.5초 sys.stdin.re..

[python] 백준 - 2512. 예산

🤔문제 해결 S3 | 이분탐색 이분 탐색의 기본문제 이분탐색이란? 탐색 부분을 두 부분으로 분할해서 답을 찾는 과정이다. 1부터 10까지 값이 있다고 가정했을 때 7이란 값을 찾아보자 최소는 1이고 최대는 10이다. 절반으로 나누면 5인데 운이 좋아서 5가 맞으면 정답, 하지만 찾는 값은 7이므로 정답이 아니다 크기를 비교해서 찾는 값이 5보다 작으면 최대를 줄이고, 찾는 값이 5보다 크면 최소를 늘린다. 찾는 값이 5보다 크므로 최소를 늘린다. 최소는 절반+1 최대는 그대로 10이다. 절반으로 나누면 8 찾는 값은 8보다 작으므로 최대를 줄인다. 최소는 6 최대는 절반-1이다. 절반으로 나누면 6 찾는 값이 6보다 크므로 최소를 늘린다. 최소는 절반+1 최대는 7이다. 절반으로 나누면 7이므로 정답! ..