본문 바로가기

Algorithm475

[파이썬] 백준 11403 : 경로 찾기 (실버1) [파이썬] 백준 11403 : 경로 찾기 (실버1) 문제 풀이 0.방향성 생각 방향성 있는 그래프. 입력을 받아서 각 노드에서 몇 번 노드로 갈 수 있는지 arr에 추가해준다. 인접행렬로 표현하라 했으므로 2차원 배열 visit을 만들어주고 BFS로 체크 1. 입력받기, 경로 추가 from collections import deque import sys input = sys.stdin.readline n = int(input()) arr = [[] for i in range(n)] for i in range(n): temp = list(map(int,input().split())) for j in range(n): if temp[j] == 1: arr[i].append(j) 2. BFS 탐색 visit .. 2023. 6. 2.
[파이썬] 백준 11726, 11727 : 2xn 타일링, 2xn타일링 2 (실버3) [파이썬] 백준 11726, 11727 : 2xn 타일링, 2xn타일링 2 (실버3) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 풀이 방향성 생각 계단 오르기 문제와 똑같다. ㅣ1칸, =,ㅁ 두칸이라교 생각하면 된다 2xn 타일링 문제에서는 두 칸을 오르는 방법이 한가지, 2xn 타일링 2 문제에서는 두 칸을 .. 2023. 6. 1.
[파이썬] 백준 1003 : 피보나치 함수 (실버3) [파이썬] 백준 1003 : 피보나치 함수 (실버3) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 방향성 생각 DP문제, 규칙을 나열해보면 알겠지만 0이 호출되는 횟수는 이전 피보나치 수열의 값이다. 다음의 코드로 확인해보면 for i in range(15): if i==0 : print(1,0) else : print(an[i-1],an[i]) 0이 호출되는 횟수는 n==0을 제외하고 피보나치 수열의 이전 값을 따라가는 것을 볼 수 있다. 1 0 0 1 1 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34 34 55 55 89 89 144 144 233 233 377 전체코드 .. 2023. 6. 1.
[파이썬] 백준 9095 : 1, 2, 3 더하기제목 (실버3) [파이썬] 백준 9095 : 1, 2, 3 더하기제목 (실버3) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 방향성 생각 DP 문제이므로 초기 값들 몇개를 찾아서 규칙을 찾는다 규칙을 찾아보면 최근에 나온 3가지 수를 모두 더하면 다음 경우의 수가 나오는 것을 확인할 수 있다. 5 -> 13, 6->24 어떤 자연수 n을 만들 때 1 2 3으로만 만든다고 했으므로 1+(n-1), 2+(n-2), 3+(n-3), 뒤에 나오는 경우의 수들은 앞에서 이미 구한 값들을 통해서 구할 수 있다. an = [0,1,2,4] for i in range(9): an.append(sum(an[-3:])) t =.. 2023. 6. 1.

티스토리툴바