본문 바로가기

알고리즘6

[백준-9184] 신나는 함수 실행 (Python) https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net [풀이] - 문제에서 정의된 w함수를 그대로 구현해주었다. 하지만, 문제에 나온대로만 한다면 백트래킹이 아닌 그냥 재귀함수를 이용한 완전탐색이기 때문에 한 번 호출된 값을 3차원 리스트인 dp에 저장해주었다. - dp리스트의 특정 값이 -1이면 즉, 아직 한번도 구해지지 않았다면 w함수를 호출하여 값을 구하여 저장해주었고 그렇지 않으면 dp리스트를 참조하여 w함수가 중복 실행되는 경우를 없앴다. [깨.. 2021. 2. 23.
[백준-1003] 피보나치 함수 (Python) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net [풀이] - 피보나치 함수가 피보나치 수열과 동일한 점화식 F(n)=F(n-1)+F(n-2)이기 때문에, dp 배열에 그대로 적용해주었다. - 0일 때와, 1일 때를 초기값으로 설정하고 2부터 n까지 점화식을 통해 값을 찾아갔다. T=int(input()) for _ in range(T): n=int(input()) dp=[0]*41 dp[0],dp[1]=(1,0),(0,1) for i in range(2,n+1): dp[i]=(dp[i-1][0]+dp[i-2][0],dp[i-1][1]+dp[.. 2021. 2. 23.
[백준-2580] 스도쿠 (Python) www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net [풀이] - 기본적인 백트래킹 문제였다. - 주어진 maps 리스트에서 빈 칸(0)의 좌표를 blank에 저장하고, 빈 칸 하나하나 1부터 9까지 넣을 수 있는지 없는지 판단하였다. - 가능한 숫자는 maps[x][y]에 저장하고, 다음 빈 칸을 위와 똑같이 채워주었다. - isPossilbe(x,y,num) 함수는 maps[x][y]에 num의 숫자가 가로,세로,작은 사각형 모두 존재하지 않으면 True를, .. 2021. 2. 23.
[백준-17406] 배열돌리기4 (Python) 문제링크 - https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net [풀이] - 일반적인 순열 조합 문제와 배열 돌리기가 합쳐진 문제였다. - 회전 정보로 중복없는 순열을 perm 함수를 구현하고, 회전 정보에 맞춰서 배열을 돌리는 rotate 함수를 구현해주었고, 어렵지 않게 풀 수 있었다. from copy import deepcopy def rotation(n_maps,i): r,c,s=rots[i][0]-1,rot.. 2021. 2. 1.

티스토리툴바