전체 글 검색 결과
73 개의 검색 결과가 있습니다.
PS/Python

[BOJ_Python] 17298. 오큰수

'스택으로 풀 수 있는 꽤 어려운 문제' 라길래 풀어 보았다. from sys import stdin N = int(stdin.readline()) data = list(map(int, stdin.readline().split())) stack = [data[-1]] result = [-1] # 뒤에서 두번째부터 for i in range(len(data)-2, -1, -1): if stack: # 스택의 top이 탐색하는 데이터보다 크다면 == 오큰수가 있음 if data[i] < stack[-1]: result.append(stack[-1]) # 우선 스택에 집어넣는다 stack.append(data[i]) # 스택의 top보다 탐색하는 데이터가 크다면 else: # 스택의 top을 하나씩 빼다가 w..

2021. 3. 11. 17:00
PS/Python

[BOJ_Python] 1707. 이분 그래프

풀다 풀다 안풀려서 검색해서 들어오신 분이라면 아래의 두 가지를 생각해 보시길 바란다. 1. 서로 연결되지 않은 이분 그래프들이 여러 개 들어왔을 경우를 생각해 보았는지 2. 인접 행렬을 사용했는지 메모리 초과를 여러 번 낸 문제다. 메모리 초과가 난 이유는 정점의 개수 V의 범위가 20000까지 늘어나기 때문이라고 생각된다. 인접 행렬을 사용해 풀려고 했었기 때문이다..ㅠㅠ 인접 행렬을 사용하면 만약 정점이 2만 개 주어졌을 때, 2차원 배열이 20,000 * 20,000... 풀이과정 DFS로 탐색하면서 정점에 색이 칠해져 있지 않은 경우 색을 칠해주고, 이미 칠해져 있는 경우 같은 색이면 break 해줬다. 인접 행렬과 더불어 이 문제를 계속 틀렸던 또 하나의 이유는 1에서만 탐색을 시작했기 때문이..

2021. 3. 10. 01:21
PS/Python

[BOJ_Python] 2178. 미로 탐색

BFS 기본적인 BFS 거리 문제. SWEA의 [5105. 미로의 거리] 와 같은 문제이다. from collections import deque def bfs(n, m): visited = [[0] * M for x in range(N)] queue = deque([(0, 0, 1)]) delta = [(0, 1), (0, -1), (1, 0), (-1, 0)] while queue: cr, cc, cd = queue.popleft() if (cr, cc) == (n, m): return cd for dr, dc in delta: nr = cr + dr nc = cc + dc if 0

2021. 3. 7. 22:16
PS/Python

[BOJ_Python] 2206. 벽 부수고 이동하기

BFS 처음에는 벽을 부순다는 조건이 있길래 어? DFS로 풀어야 하나? 했고 틀렸다. 바보같은 생각이었던 것이, DFS는 최단 거리임을 보장하지 않기 때문이다. 그래서 bfs를 사용했고 문제에 나와 있는 테스트 케이스는 가볍게 통과했는데, 막상 제출하니 결과는 &#39;틀렸습니다.&#39; 계속 고민하다가 아래의 반례를 넣어 디버깅 해보고서야 문제가 뭔지 알았다. 혹시 이 문제를 틀렸는데 이유를 모르겠다면 아래의 테스트 케이스를 넣어 보길 바란다. 제대로 된 코드라면 9를 출력해야 한다. 5 5 00000 11101 00000 01111 00010 위의 테스트 케이스를 보면 2행 5열의 1에서 아래로 내려온(벽을 한번 부순 상태의) 3행 5열의 0은 이동 거리가 6이고, 3행 4열의 0에서 오른쪽으로 ..

2021. 3. 7. 21:53
PS/Python

[BOJ_Python] 1012. 유기농 배추

DFS Recursion 재귀 검색해 보았더니 재귀 제한을 주어야지 런타임 에러가 나지 않는다고 한다. sys 모듈의 setrecursionlimit 함수를 사용한다. import sys sys.setrecursionlimit(100000) def dfs_recursion(r,c): delta = [(0, 1), (0, -1), (1, 0), (-1,0)] visited[r][c] = 1 farm[r][c] = 0 for dr, dc in delta: nr = r + dr nc = c + dc if 0

2021. 3. 7. 17:59
PS/Python

[BOJ_Python] 2667. 단지 번호 붙이기

DFS + stack (1) 상하좌우로 탐색했을 때 이동이 가능하다면 해당 좌표를 stack에 추가한 뒤, 그 좌표에 해당하는 stack의 top으로 바로 이동해서 탐색을 해야 한다. break를 하나 넣는 것을 깜빡해서 계속 이상한 곳으로 탐색하고 있었다 ㅠㅠ N = int(input()) arr = [list(map(int, input())) for x in range(N)] delta = [(0, 1), (0, -1), (1, 0), (-1,0)] res = [] def dfs(r,c): global res visited = [[0] * N for x in range(N)] cnt = 1 stack = [(r,c)] visited[r][c] = 1 while stack: top = stack[-1]..

2021. 3. 6. 18:35