파이썬16 [그래프] 깊이 우선 탐색 (DFS - Depth First Search) 알고리즘 학습 목표 깊이 우선 탐색 (Depth First Search) 개념, 예시, 의의 깊이 우선 탐색 개념 1) 정의 깊이 우선 탐색이란, 트리 구조나 그래프 데이터 구조를 탐색하는 알고리즘이다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색은 스택 구조를 사용한다. 2) 동작 예시 시작 노드에서부터 왼쪽이 우선 선택되었다고 가정하자. (1) 탐색 시작 노드를 스택에 삽입하고 '방문' 처리한다. (2) 방문하지 않은 인접 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. >> 방문할 수 있는 노드는 모두 방문 후, 없으면 돌아간다는 의미이다. (이 때 스택에서 추가되었던 값들이 하나씩 다시 제거된다.) (3) (2)번 과정을 반.. 2021. 2. 12. 파이썬 백준 2742번 제문 는하력출 지까N 터부1 https://www.acmicpc.net/problem/2742 2742번: 기찍 N 자연수 N이 주어졌을 때, N부터 1까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 자연수 N이 주어졌을 때, N부터 1까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오. 문제 풀이 문제 풀이 1 - Range 함수 이용하기 N에서 부터 1까지 어떻게 역순으로 나열할 수 있을 것인지에 대한 문제이다. Point 1: 반복되는 작업을 하는 내용이므로, for문이 사용될 수 있다. Point 2: 다만, for문이 사용되면 범위를 어떻게 잡아야 N부터 나열될 수 있을 것인가? 기본적으로 for문 iterator에 자주 쓰이는 range 함수를 사용하기로 하였다. impo.. 2021. 2. 12. 파이썬 백준 2438번 별 찍기 - 1 https://www.acmicpc.net/problem/2438 2438번: 별 찍기 - 1 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 www.acmicpc.net 문제 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 문제 설명 별 개수를, 입력 횟수만큼 하나씩 늘려가면서 맞춰서 출력하면 된다. 풀이 과정 Point 1: for문이 돌 때, '한번에' 횟수만큼 별을 찍어줘야 한다. for문 각각마다 어떻게 한번에 별을 많이 찍을지 고민을 좀 하다가, 문자열도 곱셈이 가능하다는 점에 착안하였다. import sys N=int(sys.stdin.readline()) for i in range(1,N+1): print("*"*i) .. 2021. 2. 12. 파이썬 백준 10871번 X보다 작은 수 https://www.acmicpc.net/problem/10871 10871번: X보다 작은 수 첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000) 둘째 줄에 수열 A를 이루는 정수 N개가 주어진다. 주어지는 정수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 정수 N개로 이루어진 수열 A와 정수 X가 주어진다. 이때, A에서 X보다 작은 수를 모두 출력하는 프로그램을 작성하시오. 문제 설명 입력: N과 X를 입력하고, 정수 N개로 이루어진 수열 A를 입력한다. 조건문: 수열 A 내에 X보다 작은 값만 추출한다. 풀이 과정 N,X = map(int, input().split()) A=map(int, input().split()).. 2021. 2. 12. 이전 1 2 3 4 다음
