Algorithm272 [ 파이썬(python) ] 백준 2606 - 바이러스(DFS) 📌 백준 2606 - 바이러스(DFS) 문제 설명 💡 나의 풀이 코드 업에서 풀었던 문제인데, 다시 풀어봤다. DFS를 이용해서 방문하지 않은 노드가 있을 때 cnt를 누적하는 방법으로 구현했다. 중요한 점은 cnt를 전역변수로 사용했기 때문에 파라미터로 전달하지 않았다. import sys input = sys.stdin.readline def dfs(graph, v, visited): global cnt visited[v] = True for i in graph[v]: if not visited[i]: cnt += 1 dfs(graph, i, visited) PC = int(input()) network = int(input()) graph = [[] for _ in range(PC + 1)] vis.. 2021. 4. 19. [ 파이썬(python) ] 백준 11724 - 연결 요소의 개수(DFS) 📌 백준 11724 - 연결 요소의 개수 문제 설명 💡 나의 풀이 이번 문제는 BFS와 DFS 모두 이용해서 풀었는데 시간 차이가 많이 나지 않았다.(근소하게 DFS가 48m/s정도 빨랐다.) 무방향 그래프가 없을 때는 입력값을 반대로 바꿔서 넣어줘도 된다. 예제 입력1을 그림으로 표현하면 다음과 같다. 문제를 쉽게 그림으로 표현했다. graph의 index가 노드이다. DFS로 풀 때는 최대 재귀 값을 더 열어줘야 풀린다. import sys sys.setrecursionlimit(1000000) input = sys.stdin.readline def dfs(graph, v, visited): # dfs implementation visited[v] = True for i in graph[v]: if .. 2021. 4. 19. [ 파이썬(python) ] 백준 11724 - 연결 요소의 개수(BFS) 📌 백준 11724 - 연결 요소의 개수 문제 설명 💡 나의 풀이 이번 문제는 BFS와 DFS를 이용해서 풀었는데 시간 차이가 많이 나지 않았다.(근소하게 dfs가 48m/s정도 빨랐다.) 방향 그래프가 없을 때는 간단하게 입력값을 반대로 바꿔서 넣어주면 된다. 이후에 몇 번 노드끼리 이어졌는지를 graph에 입력하면 되는데 무 방향 그래프기때문에 순서가 바뀌어도 된다. 예제 입력1을 그림으로 표현하면 다음과 같다. 문제를 쉽게 그림으로 표현했다. graph의 index가 노드이다. from collections import deque import sys input = sys.stdin.readline def bfs(graph, start, visited): # BFS implementation queu.. 2021. 4. 19. [ 파이썬(python) ] 백준 2468 - 안전 영역 📌 백준 2468 - 안전 영역 문제 설명 💡 나의 풀이 문제를 이해하는 데는 어렵지 않았지만, 구현하는데 나름대로 어려웠던 문제였다. 아직 구현 실력이 뛰어나지 않아서 그런 것 같다. N의 최대 범위가 100 * 100이어서 시간 복잡도가 O(N^3)이어도 시간초과가 나지 않을 것이라고 판단했는데, 같은 지역에서 내리는 비의 양에 따른 모든 경우를 조사해야 하기 때문에 이중 반복문에서 삼중 반복문으로 늘어났다. 모든 높이를 조사할때는 입력값 중 가장 작은 값부터 가장 큰 값을 범위로 잡았다. 여기서 pythonic코드를 배웠는데 2차원의 배열에서 min, max값을 찾을 때 map함수를 사용하면 간단하게 출력할 수 있다. 반복문 안에서 가장 큰 값의 범위를 설정할 때는 +1을 해주자 아니면 오답 판정 .. 2021. 4. 19. [ 파이썬(python) ] 이것이 코딩 테스트다 공부 1 ~ 39일차 정리내용 티스토리로 넘어오기 이전에 벨로그에서 이것이 코딩테스트다 서적을 하루도 빠짐없이 1일차에서 39일차까지 공부했었다. 정리내용은 다음 링크를 들어가서 참고해주세요! 링크: 0_velog 2021. 4. 18. 이전 1 ··· 42 43 44 45 46 47 48 ··· 55 다음
