일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- DP
- folium
- 마이온
- 멋재이사자처럼
- 인턴10
- 온보딩
- 멋사
- likelion
- BFS
- intern10
- parklab
- Join
- pyhton
- 시각화
- 프로젝트
- 마이온컴퍼니
- DFS
- likelionlikelion
- ux·ui디자인
- Plotly
- Python
- TiL
- 그리디
- 멋쟁이사자처럼멋쟁이사자처럼
- 멋쟁이사자처럼
- seaborn
- 파이썬
- SQL
- 알고리즘
- GIS
- Today
- Total
목록STUDY/Python 알고리즘 (23)
지금은마라톤중
이번 문제에서는 런타임 에러와 시간초과로 2번 실패했었습니다. 접근법 - DFS로 접근 - 깊이 탐색 후 방문하지 않은 노드 있을 때 cnt 증가 에러해결 1. 런타임에러 - 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회 → 재귀 최대깊이는 재설정해줌 sys.setrecursionlimit(10000) 2. 시간초과 - input 대신 sys.stdin.readline을 통해 시간초과 해결 input = sys.stdin.readline import sys input = sys.stdin.readline sys.setrecursionlimit(10000) n,m = map(int,input().split()) graph = [[] for _ in range(n+1)] for _ in range(m)..
이 문제 역시 그래프 탐색 문제입니다. 접근법 - DFS로 접근 - DFS로 탐색하면서 cnt를 증가하여 단지 내 건물 수 체크 - 건물 수 담은 리스트 활용하여 결과 출력 n = int(input()) matrix = [] visited = [[False] * n for _ in range(n)] cnt_list = [] dx = [0,0,1,-1] dy = [1,-1,0,0] # mapping matrix for _ in range(n): m = input() matrix.append(m) def dfs(matrix,x,y,visited): global cnt if x = n or y = n : return 0 if matrix[y][x] == "0" or visi..
접근법 - 2명 사이의 촌수를 계산해야하니 DFS로 접근 - 촌수를 계산할 수 없을 때 -1 출력해야하니 check 변수 사용 from collections import deque n = int(input()) a,b = map(int,input().split()) num = int(input()) check = False graph = [[] for _ in range(n+1)] visited = [0] *(n+1) for _ in range(num): x,y = map(int,input().split()) graph[x].append(y) graph[y].append(x) def dfs(graph, c, visited, cnt): visited[c] = 1 global check if c == b :..
이 문제는 BFS에 대해 하나도 모를 때 한번 도전했다가 실패했던 문제입니다. 최근에 DFS와 BFS에 대해 공부해서 다시 도전해봤습니다. BFS로 접근하였고 너비우선탐색이니 큐를 활용했습니다. from collections import deque t = int(input()) dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(matrix, a,b): queue = deque() queue.append((a,b)) matrix[a][b] = 0 while queue: x,y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx = n or ny = m : continu..
그렇습니다. DFS와 BFS입니다..ㅎㅎ 알고리즘을 공부하며 미루고 미루고 미루다가 직면했습니다..하하하 DFS(깊이우선탐색)과 BFS(너비우선탐색)은 코딩테스트에 필수적인 문제 중 하나라고 생각합니다. 알고리즘을 접하지 얼마되지 않았을때 너무 어려워서 외면했는데 최근 기업 공채 코딩테스트를 봐보니 이제는 마주할 때가 되었다고 생각했습니다. DFS(Depth First Search)와 BFS(Breadth First Search)를 탐색 알고리즘입니다. 데이터 속에서 원하는 데이터를 찾을 때 깊이와 너비를 우선적으로 고려하여 탐색하는 방법으로 차이를 둘 수 있습니다. - DFS와 BFS 탐색 그래프 DFS BFS 탐색과정 현재 노드에서 갈 수 있는 끝까지 방문하여 탐색 현재 노드에서 연결된 노드를 방문 ..
가끔 알고리즘 문제를 풀었지만 오랜만에 포스팅 합니다. 이번 문제에서 놓치고 있던 지식을 상기시켰습니다. 바로 자료형의 시간 복잡도 입니다. 기존에 시간초과가 발생했을 때 주로 입력부분과 불필요한 반복문에서 시간초과가 많이 발생하여 자료형에 따른 시간 복잡도를 놓쳤습니다. 이번 문제로 한번 더 상기시킬 수 있는 기회였습니다. 시도 1. input(), list() 활용 - 시간초과로 실패 n,m = map(int, input().split()) n_lst = [ input() for _ in range(n)] m_lst = [ input() for _ in range(m)] lst = n_lst + m_lst lst.sort() total_lst = [] for i in lst : if lst.count..
https://www.acmicpc.net/problem/1977 1977번: 완전제곱수 M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완 www.acmicpc.net 처음에 이렇게 작성을 해서 실패하였다. 시간초과로 실패를 한 것은 처음이다. #1977번- 시간초과로 실패 a = int(input()) b = int(input()) lst=[] for i in range(a,b+1): for s in range(2,i): if s**2==i: lst.append(i) lst.sort() if len(lst)==0: print(-1) else:..