백준
[백준 파이썬] #11003. 최솟값 찾기
풀기 전 생각해보기😮 정렬을 사용할 수 없음 : 최대범위 값이 너무 크다 슬라이딩 윈도우, 덱 자료구조를 이용해서 O(n) 시간복잡도로 풀기 풀이🛫 from collections import deque N, L = map(int, input().split()) arr = list(map(int, input().split())) myDeque = deque() # ([인덱스][값]) 형태로 myDeque에 데이터 관리 for i in range(N): # 새로운 값이 기존의 값보다 클 때까지 기존의 값 (끝에서부터) 제거 while myDeque and myDeque[-1][0] > arr[i]: myDeque.pop() myDeque.append((arr[i], i)) # 새로운 값 입력 # 슬라이딩 윈..
[백준 파이썬] #11725. 트리의 부모 찾기
풀기 전 생각해보기😮 가급적 pypy3로 채점할 것을 추천한다 - python3로 채점이 정말 오래 걸렸다 트리 구조를 그리고, 각 노드의 부모를 찾는 문제 DFS로 풀 경우 recursionlimit을 10**6까지는 열어둬야 한다 풀이🛫 BFS 풀이 from collections import deque def bfs(node): queue = deque() queue.append(node) while queue: n = queue.popleft() for i in graph[n]: if parent[i] == -1: parent[i] = n queue.append(i) N = int(input()) graph = [[] for _ in range(N+1)] parent = [-1 for _ in ra..
[백준 파이썬] #1967. 트리의 지름
풀기 전 생각해보기😮 루트노드로부터 가장 먼 지점을 찾고, 해당 지점을 다시 루트 노드로하는 가장 먼 지점을 찾으면 트리의 지름을 구할 수 있다 recursionError가 발생하면 setrecursionlimit을 먼저 적용해보자 풀이🛫 구글링 참고 # 루트노드로부터 가장 먼 지점(가중치의 합)이 가장 큰 지점을 찾는 과정을 두번 반복 # visited를 음수값으로 설정하고 확인할 때마다 값을 바꿔준다면 방문 여부의 확인과 함께 거리를 나타낼 수 있다 import sys sys.setrecursionlimit(10**6) # 최대 재귀 깊이를 늘려주는 코드 def dfs(node, weight): for n, w in graph[node]: if visited[n] == -1: # 확인한 적이 없는 노..
[백준 파이썬] #2206. 벽 부수고 이동하기
풀기 전 생각해보기😮 일반적인 브루트 포스 방식으로 접근했을 때 시간초과가 발생했다. 모든 벽을 부셔서 최단 거리를 구해보는 알고리즘으로 풀 수 없다? → 시간초과 발생 : BFS 기본 시간 * 부술 수 있는 벽의 수 : 문제에서 1000*1000으로 시간제한에 걸린다 참고: https://www.acmicpc.net/board/view/84960 벽을 단 한번만 부실 수 있다는 조건을 이용해서 3차원으로 푸는 것이 일반적인 해답인 듯 하다. 풀이🛫 구글링을 참고 # 구글링 : 3차원 풀이 방식 사용 # 벽을 단 한번만 부술수 있기 때문에 벽을 부쉈는지의 여부를 하나의 차원에 나타내서 풀 수 있다 # 3차원방식 도입 풀이 from collections import deque dcol = [-1, 0, 1..
[백준 파이썬] #1717. 집합의 표현
풀기 전 생각해보기😮 재귀 호출 깊이를 지정해주지 않았을 때 recursion error가 발생했다. import sys 또한 빠뜨리지 않도록 주의하자 (import를 빼먹으면 name error 발생) 풀이🛫 import sys sys.setrecursionlimit(10**5) # 서로소 집합 문제 # pypy3 채점 def find(x): # x의 부모 값을 return if x == p[x]: # 자기 자신을 부모로 갖는 경우 return p[x] # 그대로 return # return x를 해도 동일함, 그러나 return 값을 p[x]로 맞춰주기 위해 p[x]로 연습하자 # 자기 자신을 부모로 갖지 않는 경우 p[x] = find(p[x]) # path compression 진행 return ..
[백준 파이썬] #1021. 회전하는 큐
풀기 전 생각해보기😮 회전하는 큐의 특성에 맞게 함수를 작성해서 풀이 풀이🛫 # 1. 첫번째 원소 뽑아내기 # 2. 왼쪽으로 한 칸 이동 # 3. 오른쪽으로 한 칸 이동 from collections import deque def pop_idx0(): lst.popleft() queue.popleft() return def move_left(): global exe queue.append(queue.popleft()) exe += 1 return def move_right(): global exe queue.appendleft(queue.pop()) exe += 1 return N, M = map(int, input().split()) lst = deque(map(int, input().split()))..
[백준 파이썬] #1987. 알파벳
풀기 전 생각해보기😮 DFS로 풀이했다면 pypy3로 채점을 시도, BFS로 풀이했다면 python3로 채점할 수 있다고 한다. (자세한 이유까지는 모르겠다) 풀이🛫 # dfs 풀이는 pypy3로 제출해야 한다고 함: 자세한 이유는 모르겠다.. # 문제 채점 과정이 매우 오래 걸린다 # 정답 # U,R,D,L dcol = [-1, 0, 1, 0] drow = [0, 1, 0, -1] def dfs(col, row): global level, max_level visited[col][row] = 1 # 방문 처리 alpha_lst[ord(arr[col][row])-65] = 1 # 방문한 지점의 알파벳 처리 level += 1 # 재귀가 반복될 때마다 깊이(level) 증가 max_level = max(l..
[백준 파이썬] #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하면서, 더 큰 값이 나올 때까지, 기준점의 오른쪽 값으로 대체 ..