백준

[python] 백준 - 1655. 가운데를 말해요

🤔문제 해결 G2 | 우선순위 큐 처음에는 가볍게 정렬로 풀었지만, 시간초과가 발생했다. ( 바이너리서치는 통과 된다고 함 ) 가운데 값 구하기를 열심히 찾아봤지만 없었다. 어쩔 수 없다. 이 문제의 의도는 우선순위 큐를 활용하는 것이다. 파이썬의 힙큐 모듈을 사용하면 되는데, 최소힙 기준으로 되어있다. 최소힙은 가장 작은 원소가 루트에 위치하는 것이다. 우리는 가운데 값을 찾아야 하기 때문에 힙을 두개 만들어서 왼쪽의 가장 큰 수와 오른쪽의 가장 작은 수를 비교하여 가운데 값을 구할 것이다. 이렇게 두 부분으로 나누면 가운데 값을 구 할 수 있다. 하지만!!!!!!!!!!! 최소힙으로 힙큐 모듈이 구성되어 있으므로, 왼쪽의 구성은 음수를 붙여서 거꾸로 만들어야한다. 이렇게 하면 왼쪽의 0번과 오른쪽의 ..

[python] 백준 - 1747. 소수&팰린드롬

🤔문제 해결 G5 | 에라토스테네스의 체, 문자열 소수를 찾고, 그게 소수이면 팰린드롬인지 확인한다. 팰린드롬인지 확인하는 법은 간단하다. 문자를 뒤집어서 같으면 True 브루트포스로 찾아도 문제해결은 가능하지만 에라토스를 쓰는것과 시간이 10배 이상 차이난다. 에라토스테네스의 체를 써서 제한 숫자까지 소수들을 구해놓는다. 그 소수이면서 팰린드롬이면 값을 반환하고 끝 💻소스 코드 def make_eratos(l: int) -> list: eratos = [1] * (l + 1) eratos[0], eratos[1] = 0, 0 for i in range(2, l): if eratos[i]: for j in range(i * 2, l, i): eratos[j] = 0 return eratos def is_..

[python] 백준 - 16916. 부분 문자열

🤔문제 해결 G4 | 문자열, KMP 딱 봐도 너무 쉽지만 G5니까…. 다른 방법으로 풀어야 한다고 생각했다. 들어는 봤어도 한 번도 써본 적 없는 KMP 알고리즘을 써야 문제를 해결할 수 있다. KMP를 쓰면 브루트포스로 문자열 탐색하는 것보다 아주 빠르다. O(M+N) 한 시간 넘게 찾아가면서 공부했지만 설명하기는 너무 어렵다. 이해가 잘 안 된다. 나중에 한 번 더 봐야겠다. 대충 말해보자면 비슷한 패턴을 기억해뒀다가 패턴을 만나면 점프... (무슨 말인지 모르겠다) 어째 됐든 이 알고리즘은 많이 쓰이진 않지만, 적당히 알아만 두면 좋을 거 같다. 💻소스 코드 def kmp_match(txt: str, pat: str) -> int: # 스킵테이블 만들기 def make_skip_table(skip..

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