Algorithm Study/Python
[백준 파이썬] #1918. 후위표기식
풀기 전 생각해보기😮 stack 구조를 이용 풀이🛫 다른 분의 풀이를 참고했다 inp = list(input()) stack = [] # 스택 저장 공간 res = "" # inp 값의 요소 확인 for i in inp: if i.isalpha(): # i.isalpha(): 만약 i가 영문자라면 True res += i # res에 문자 입력 elif i == '(': # 여는 괄호: stack에 담는다 stack.append(i) elif i == '*' or i == '/': # 곱셈 또는 나눗셈 # stack의 꼭대기 연산자가 같은 우선순위의 연산자일 경우 while stack and (stack[-1] == '*' or stack[-1] == '/'): res += stack.pop() # re..
[백준 파이썬] #17298. 오큰수
풀기 전 생각해보기😮 주어진 조건을 봤을 때 N의 크기가 1 ~ 1,000,000임을 확인할 수 있다. 시간복잡도 O(n)로 알고리즘을 짜야 시간초과 문제가 발생하지 않는다 단순히 for문을 사용하는 방식이나, 리스트의 뒷부분부터 탐색하는 방식이 잘 적용되지 않는다면, 자료구조를 활용하는 방법을 생각해보자 *다른 블로그 풀이를 보고 정리 풀이🛫 N = int(input()) A = list(map(int, input().split())) answer = [-1] * N # 기본값으로 -1을 세팅 stack = [0] # 오른쪽 값이 현재 값보다 작을 때: 스택에 인덱스 값을 push # 오른쪽 값이 현재 값보다 클 때: 스택에서 값을 pop하면서, 더 큰 값이 나올 때까지, 기준점의 오른쪽 값으로 대체 ..
[백준 파이썬] #14502. 연구소
풀기 전 생각해보기😮 벽을 세울 수 있는 곳 중에서 세곳을 선택하고 벽을 세운다 벽을 세운 후 바이러스가 확산되었을 때, 확산되지 않은 방의 개수를 확인한다 다른 세 곳에도 벽을 세울 수 있는 모든 경우에 대해 확인한다 확산되지 않은 방이 가장 큰 경우를 선택한다 바이러스의 확산을 확인하기 위해 BFS를 사용했다 deepcopy 방식을 이용해서 매 경우 마다 사용하는 arr를 초기화 시켜주었다 풀이🛫 # 완전 탐색, BFS from collections import deque # U,R,D,L dcol = [-1,0,1,0] drow = [0,1,0,-1] # BFS: 바이러스의 확산 def spread_virus(lst): global virus # 바이러스가 있는 방 정보 가져오기 queue = de..
[백준 파이썬] #1406. 에디터
풀기 전 생각해보기😮 시간초과가 발생한다면 자료구조를 사용해보기 2개의 스택 구조를 사용해보자 풀이🛫 # pypy3 채점으로 정답 # 스택을 하나 더 사용하는 방식을 사용 left = list(input()) right = [] # 임시 스택 공간 N = len(left) M = int(input()) for m in range(M): ord = list(input().split()) if ord[0] == 'L': # 커서 왼쪽 이동 if left: # inp이 존재할 때 right.append(left.pop()) # right 공간에 저장 elif ord[0] == 'D': # 커서 오른쪽 이동 if right: # temp가 존재할 때 left.append(right.pop()) # temp에서 ..
[백준 파이썬] #2430. AC
풀기 전 생각해보기😮 시간초과가 발생한다면 자료구조를 사용해보기 오류가 발생한다면? : https://www.acmicpc.net/board/view/25456 풀이🛫 from collections import deque T = int(input()) for tc in range(1, T+1): p = list(input()) n = int(input()) inp = deque(input()[1:-1].split(',')) err = False rcnt = 0 for i in p: if i == 'R': rcnt += 1 elif i == 'D': if len(inp) > 0 and inp != deque(['']): # 여기서 문제가 발생 if rcnt % 2 == 1: # 홀수 번 뒤집기가 진행되었을..
[백준 파이썬] #10799. 쇠막대기
풀기 전 생각해보기😮 stack 문항 각각의 경우를 따져서 풀 수 있다 풀이🛫 # 스택 # 모든 경우대로 조건문을 나열 arr = list(input()) stack = [] cnt = 0 for i in range(len(arr)): if len(stack) == 0 and arr[i] == '(': # stack이 아직 만들어지지 않았을 경우 stack.append('(') else: # stack이 존재할 때 # 이전에 들어온 값과 현재 입력되는 값을 비교 # 모든 경우의 수는 4가지 밖에 되지 않음 if arr[i-1] == '(' and arr[i] == '(': # case1 stack.append('(') elif arr[i-1] == '(' and arr[i] == ')': # case2 ..
[백준 파이썬] #2493. 탑
풀기 전 생각해보기😮 stack 문제에 해당 풀이🛫 N = int(input()) # 500,000 이하 -> 완전탐색으로 구현하면 시간초과 발생 우려 towers = list(map(int, input().split())) lst = [(0, 0)] # 초기 값으로 (0, 0)을 보유 ans_lst = [] # 정답 리스트 for i in range(len(towers)): # stack에 쌓여있는 마지막 높이보다 현재의 탑이 더 높을 경우 if lst[-1][0] 현재 탑보다 큰 높이가 나올 때까지 while lst[-1][0] < towers[i]: lst...
[백준 파이썬] #2636. 치즈
풀기 전 생각해보기😮 치즈가 모두 녹는 지점 파악하기 풀이🛫 # 구하려는 것 : 치즈가 모두 녹아 없어지는 시간, 모두 녹기 한 시간 전에 남아있는 치즈조각 # 딥카피 연습: copy_arr = [arr[i][:] for i in range(len(arr))] from collections import deque dcol = [1, 0, -1, 0] drow = [0, -1, 0, 1] # melt() 치즈의 테두리 표시 def melt(): visited = [[0] * R for _ in range(C)] temp_lst = [] queue = deque() queue.append((0, 0)) while queue: col, row = queue.popleft() for v in range(4): ..
[백준 파이썬] #2146. 다리만들기
풀기 전 생각해보기😮 간척 사업 아이디어 적용해보기 중복해서 인식되는 지점을 어떻게 해결할 것인지 메모리 초과 오류 발생 해결 풀이🛫 from collections import deque dcol = [1, 0, -1, 0] drow = [0, 1, 0, -1] def divide_island(): cnt = 1 # 주어진 arr의 모든 부분 탐색 시도 for col in range(N): for row in range(N): if arr[col][row] == 1: # 어느 한 섬에 도달하면 cnt += 1 # 몇 번째 섬인지 표시하기 위해 cnt 활용 queue = deque() # BFS 진행 queue.append((col, row)) checked[col][row] = 1 while queue:..
[백준 파이썬] #14503. 로봇청소기
풀기 전 생각해보기😮 이차원 배열의 탐색은 범위를 항상 조심할 것 구현 문제 풀이🛫 dcol = [0, 1, 0, -1] drow = [-1, 0, 1, 0] def check(col, row, dir): # dir: 바라보는 방향 if dir == 0: if 0