파이썬

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

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

[python] SWEA - 10912. 외로운 문자

🤔문제 해결 lv3 | 문자열 💨 붙어있는 문자끼리 삭제하는 것이 아니라, 어디에 있던 두 문자를 찍지으면 된다. 💻소스 코드 for tc in range(int(input())): word = list(input()) word.sort() stack = [] for w in word: if stack and stack[-1] == w: stack.pop() else: stack.append(w) if stack: print(f'#{tc + 1} {"".join(stack)}') else: print(f'#{tc + 1} Good') 📕문제 확인 출처: SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexper..

[python] SWEA - 10804. 문자열의 거울상

🤔문제 해결 lv3 | 문자열 💻소스 코드 for tc in range(int(input())): word = input() answer = '' for i in range(len(word) - 1, -1, -1): if word[i] == 'b': answer += 'd' elif word[i] == 'd': answer += 'b' elif word[i] == 'p': answer += 'q' else: answer += 'p' print(f'#{tc + 1} {answer}') 📕문제 확인 출처: SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com

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