알고리즘7 탐색 알고리즘 DFS/BFS 들어가기 전에 그래프를 통한 비교 그래프는 노드(node)와 간선(edge)으로 표현되며 이때 노드를 정점(vertex)이라고도 한다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현 할 수 있다. 1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 2. 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 일반적으로는 인접 리스트의 방식이 더 효율적이다. 인접 행렬의 경우, 정점의 개수 N만큼 도는 2중 for문을 돌려 두 정점 간에 간선이 존재하는지를 확인해야하기 때문이다. 인접 행렬의 시간 복잡도 : O(N²) DFS(깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색한다. 이름에서 알 수 있듯이 단순하게 가장 깊숙이 위치하는 노드에 닿을 때까지 확인(탐색)하면 된다.. 2021. 4. 12. [백준][파이썬]2775번: 부녀회장이 될테야 문제 출처 : www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 내 풀이 직접 그려보며 확인해본 결과 k층 n호에 사는 사람의 수는 (k층 n - 1 호에 사는 사람의 수) + (k - 1층 n호에 사는 사람의 수) 라는 규칙이 나왔다. import sys input = sys.stdin.readline t = int(input()) for i in range(t): k = int(input()) n = int(input()) arr = [[i for i in range(n + 1)] for _ in.. 2021. 4. 11. [백준][파이썬]1051번 숫자 정사각형 문제 출처 : www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net 문제 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다. 입력 첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다. 출력 첫째 줄에 정답 정사각형의 크기를 출력한다. .. 2021. 3. 31. 이전 1 2 다음
