Programming [Python] (411) 썸네일형 리스트형 #146 백준 파이썬 [2606] 바이러스 - BFS https://www.acmicpc.net/problem/2606 #Solution 문제의 카테고리가 플로이드 와샬 알고리즘으로 되어있어, 이 방법으로 계속 풀다가 시간 복잡도, 구현 방법 등등에 있어서 BFS(너비 우선 탐색) 알고리즘이 훨씬 더 효율적이므로 이를 통해 해결하였다. 결국 1과 연결된 것만 구하면 되니까. + 양방향 그래프라서 네트워크 정보를 한 번 뒤집어서 2차원 배열에 넣어줬다. computer = int(input()) network = int(input()) virus_map = [[0 for _ in range(computer + 1)] for _ in range(computer + 1)] #2차원 배열 안에 넣어주기 for _ in range(network): x, y = ma.. #145 백준 파이썬 [1967] 트리의 지름 - BFS https://www.acmicpc.net/problem/1967 #Solution 상당히 오래 걸린 알고리즘이다. 다음과 같은 순서대로 풀이하였다. 1) BFS로 최상단(1) 부터 최하단 까지 정렬 2) 정렬된 bfs_node함수의 끝부터 pop하기 3) 최하단에서 각 node에 도달하는 단방향 값들 산출(diameter) 4) 최하단에서 각 node에 도달하는 단방향 최댓값 산출(max_node) 5) 각 node의 지름 최댓값 산출(max_diameter) 6) 지름 값 중 최댓값 출력(max(max_diameter)) node = int(input()) tree_info = [[] for _ in range(node + 1)] for _ in range(node - 1): parent, child.. #144 백준 파이썬 [1991] 트리 순회 https://www.acmicpc.net/problem/1991 #Solution 전위 중위 후위순위를 푸는 방법은 트리의 탐색 순서에 따라 다르다. 순회 순서가 명확해야 알고리즘도 짜기 쉬워진다. https://codingstarter.tistory.com/6?category=935492를 참조하면 순서대로 쉽게 이해할 수 있다. 아울러 파이썬으로 짤 때는 딕셔너리를 이용하여 빠르게 찾았다. {'A': [B, C]} 이런 식으로 부모 자식간의 관계를 만들어줬다. 이해를 쉽게 하기 위해서 해당 딕셔너리를 node_graph로 바꾸다 보니 함수들이 길어졌다. 포인터가 없는 파이썬은 C와는 다르게 트리가 구현된다. node = int(input()) node_graph = {i:[] for i in "AB.. #143 백준 파이썬 [11725] 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 #Solution https://claude-u.tistory.com/180참고하였음. 시간 초과가 너무 나서 찾는 데 한참 걸렸다. (if node not in visited:) 라는 함수는 O(n)의 시간 복잡도를 가지고 있는데, 편하다고 그냥 막썼다. 리스트 내부 탐색은 훨씬 더 효율적인 함수들을 써주는 것으로 하자. - 결국 트리를 그래프 형태로 구현해서 부모 노드를 찾는 방식으로 진행하였다. - 다만 그래프처럼 순회하지 않고, 한 방향으로만 쭉쭉 내려가므로 visited 리스트는 제거해 주었다. - bfs, dfs 어느 것을 사용해도 무방하다. import sys node = int(input()) node_graph = [[].. #142 백준 파이썬 [2163] 초콜릿 자르기 https://www.acmicpc.net/problem/2163 #Solution 가로 세로 길이에 상관없이 잘라야 하는 수는 공식을 통해 똑같이 나온다. N, M = map(int, input().split()) print(N-1 + (M-1)*N) #141 백준 파이썬 [1476] 날짜 계산 https://www.acmicpc.net/problem/1476 #Solution E, S, M이 각각 15, 28, 19일 경우의 반례를 고려해야한다. E, S, M = map(int, input().split()) for i in range(1, 7981): if i % 15 == E or (i % 15 == 0 and E == 15): if i % 28 == S or (i % 28 == 0 and S == 28): if i % 19 == M or (i % 19 == 0 and M == 19): print(i) #140 백준 파이썬 [2455] 지능형 기차 https://www.acmicpc.net/problem/2455 #Solution passenger = [] in_train = 0 result = 0 for _ in range(4): passenger.append(list(map(int, input().split()))) for [out_p, in_p] in passenger: in_train += in_p - out_p result = max(result, in_train) print(result) #139 백준 파이썬 [2744] 대소문자 바꾸기 https://www.acmicpc.net/problem/2744 #Solution word = list(str(input())) answer = [] for character in word: if character in 'abcdefghijklmnopqrstuvwxyz': answer.append(character.upper()) else: answer.append(character.lower()) for character in answer: print(character, end = '') 이전 1 ··· 31 32 33 34 35 36 37 ··· 52 다음
