파이썬22 [백준][파이썬]11067번: 모노톤길 문제 출처 : www.acmicpc.net/problem/11067 11067번: 모노톤길 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T가 정수로 주어진다. 각 테스트 데이터의 첫 번째 줄에는 카페의 수 www.acmicpc.net 내 풀이 import sys input = sys.stdin.readline t = int(input()) for i in range(t): n = int(input()) answer = [[0, 0]] dic = {} for j in range(n): x, y = map(int, input().split()) if x not in dic: dic[x] = list() dic[x].append(y).. 2021. 4. 14. [백준][파이썬]18870번: 좌표 압축 문제 출처 : www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 내 풀이(시간초과) import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr2 = sorted(list(set(arr))) for i in arr: print(arr2.index(i), end = ' ') 내 풀이(성공) import.. 2021. 4. 14. [백준][파이썬]11403번: 경로 찾기 문제 출처 : www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 내 풀이 각 정점마다 dfs를 돌면서 연결된 정점을 check에 방문처리해 준 후에 출력하도록 코드를 짰다. import sys input = sys.stdin.readline def dfs(v): for i in range(n): if check[i] == 0 and arr[v][i] == 1: check[i] = 1 dfs(i) n = int(input()) arr = [] for i in range(n): arr.append(list.. 2021. 4. 12. 탐색 알고리즘 DFS/BFS 들어가기 전에 그래프를 통한 비교 그래프는 노드(node)와 간선(edge)으로 표현되며 이때 노드를 정점(vertex)이라고도 한다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현 할 수 있다. 1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 2. 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 일반적으로는 인접 리스트의 방식이 더 효율적이다. 인접 행렬의 경우, 정점의 개수 N만큼 도는 2중 for문을 돌려 두 정점 간에 간선이 존재하는지를 확인해야하기 때문이다. 인접 행렬의 시간 복잡도 : O(N²) DFS(깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색한다. 이름에서 알 수 있듯이 단순하게 가장 깊숙이 위치하는 노드에 닿을 때까지 확인(탐색)하면 된다.. 2021. 4. 12. 이전 1 2 3 4 5 6 다음
