본문 바로가기

코딩테스트/파이썬

 (19)
백준 1182번 부분수열의 합 문제 설명 이진 트리를 사용하여 해당 정수를 더할지 말지를 정했다. 이진 트리에서 왼쪽으로 가면 정수를 더하지 않는 것이고 오른쪽으로 가면 정수를 더하는 방식으로 생각했다. cur은 현재 depth을 뜻하고 total은 수열의 합을 뜻한다. cur이 depth인 S와 같아졌을 때 해당 수열의 합이 N과 같으면 count를 1 더하고 함수를 종료한다. cur이 height보다 작을 경우 이진 트리의 왼쪽으로 갈 경우와 오른쪽으로 갈 경우를 나누어 함수를 호출한다. 전체 코드 arr = [] count = 0 N = 0 S = 0 def func(cur,total): global count global N global arr global S if cur == S: if total == N: count += ..
백준 9663번 N-Queen 해당 문제는 파이썬으로 제출할 경우 시간 초과가 발생하기 때문에 pypy3로 제출하였다. 문제 설명 isused는 퀸이 있는 위치, num은 체스판의 길이, count는 퀸을 놓는 방법의 수를 나타낸다. func의 인자로는 해당 위치의 행을 넣고 그 값이 체스판의 길이와 같아졌을 때 count를 1 증가시킨 후 함수를 종료한다. b는 열을 의미하고 for문을 사용하여 모든 열을 검사한다. isused에 값이 있다는 것은 첫째줄이 아니라는 뜻이므로 queen을 놓을 수 있는지 검사한다. isOk는 해당 위치인 (a,b)에 퀸을 놓을 수 있는지 판별하는 bool 값이다. 퀸을 놓을 수 있는지 판별하기 위해 검사해야할 것은 총 세 개다. 1) 같은 열에 있는가 2) 같은 대각선에 있는가 2-1) 왼쪽에서 오른..
백준 1780번 종이의 개수 문제 설명 count_1은 -1로만 채워진 종이의 개수, count0은 0로만 채워진 종이의 개수, count1은 1로만 채워진 종이의 개수를 뜻한다. count_1,count0,count1을 전역변수로 선언하고 재귀함수의 인자로는 검사할 배열의 시작점 (a,b)와 종이의 길이 N을 넣어준다. (a,b)부터 시작하여 이중for문을 사용하여 종이를 확인하고 만약 해당 위치의 종이와 시작점 (a,b)의 종이와 다르다면 배열을 9등분하여 재귀함수를 호출한다. 이중for문을 통과하면 해당 종이는 모두 같은 종이로 되어있음을 뜻하므로 종이의 종류에 맞게 개수를 더해준다. 전체 코드 count_1 = 0 count0 = 0 count1 = 0 arr = [] def func(a,b,N): global count_1..
백준 2630번 색종이 만들기 문제 설명 bCount는 파란색 색종이의 수를 뜻하고 wCount는 하얀색 색종이의 수를 뜻한다. arr은 전체 종이를 담을 배열이다. 재귀함수의 인자로 a와 b는 해당 색종이의 시작점을 뜻한다. 첫 색종이는 [0,0]부터 시작하니 a=0,b=0이 된다. 시작점인 a와 b부터 색을 비교하고 만약 색이 다를 경우 a와 b에 N//2를 알맞게 더해 재귀함수를 다시 호출한다. 만약 이중for문을 통과할 경우에는 색종이의 색깔이 전부 같다는 뜻이므로 해당 색깔에 맞게 count를 늘려준다. 전체 코드 bCount = 0 wCount = 0 arr = [] def func(a,b,N): global bCount global wCount if N == 1: if arr[a][b] == 1: bCount += 1 e..
백준 11729번 하노이 탑 이동 순서 문제 설명 재귀함수의 인자로는 총 세 개를 설정했다. a에서 b로 n개 옮긴다는 뜻이다. n이 1이면 한 개만 옮기면 된다는 뜻이므로 a와 b를 출력했고 n이 1이 아닐 경우 a에서 b가 아닌 다른 쪽, 즉 6-a-b로 n-1개 옮긴 후 a에서 b로 옮긴 후 다시 6-a-b에서 b로 n-1개 옮기도록 했다. 전체 코드 def func(a,b,n): if n == 1: print("%d %d" % (a,b)) return 0 else: func(a,6-a-b,n-1) print("%d %d" % (a,b)) func(6-a-b,b,n-1) return 0 def main(): num = int(input()) print(2 ** num - 1) func(1,3,num) if __name__ == "__ma..
백준 17478번 재귀함수가 뭔가요? 문제 설명 재귀함수의 인자를 두 개로 설정하여 a는 재귀함수의 총 호출횟수를 뜻하고 b는 현재 재귀함수가 몇번째 재귀함수인지를 뜻한다. a와 b의 값이 같으면 마지막 재귀함수라는 뜻이고 같지 않으면 두번째 인자에 b에 1을 더하여 b+1을 넣어서 다시 재귀함수를 호출했다. 전체 코드 def func(a,b): for i in range(b): print('____', end='') print('"재귀함수가 뭔가요?"') if a == b: for i in range(b): print('____', end='') print('"재귀함수는 자기 자신을 호출하는 함수라네"') for i in range(b): print('____', end='') print('라고 답변하였지.') return 0 else: ..
백준 1629번 곱셈 문제 설명 문제를 분석해보면 A의 B제곱을 C로 나눈 나머지는 A의 B/2제곱을 C로 나눈 나머지를 알면 알 수 있다. 이 뜻은 K제곱을 계산했으면 2K제곱과 2K+1제곱을 계산할 수 있다는 뜻이다. 그래서 B가 1이면 A % C를 리턴하고 그렇지 않으면 B를 2로 나눈 값을 인자로 넣어 재귀함수를 실행한다. 전체 코드 def func(a,b,c): if b == 1: return a % c val = func(a,b//2,c) val = val * val % c if b % 2 == 0: return val else: return val * a % c def main(): li = list(map(int,input().split())) print(func(li[0],li[1],li[2]))
프로그래머스 level1 크레인 인형뽑기 게임 문제 설명 answer는 없어진 인형의 갯수고 stack은 바구니다. moves 배열의 크기만큼 for문을 반복하여 board에 인형이 없으면 continue로 스킵하고 있으면 해당 인형의 번호를 peek에 넣는다. 만약 바구니에 인형이 있다면 바구니의 가장 위에 있는 인형과 peek을 비교하여 같으면 pop을 하고 board의 값을 0으로 바꿔준다. 없으면 그대로 바구니에 넣고 board의 값을 0으로 바꿔준다. 전체 코드 def solution(board, moves): answer = 0 stack = [] for i in range(len(moves)): for j in range(len(board)): if(board[j][moves[i]-1] == 0): continue peek = board..

티스토리툴바