본문 바로가기

코딩테스트

 (39)
백준 1799번 비숍 문제 설명 N-Queen 문제를 돌려서 생각하여 (왼쪽에서 오른쪽으로 가는) / 모양의 대각선으로 해당 줄을 검사하면서 한 줄 씩 내려갔다. 훑어야 하는 대각선의 총 개수는 체스판의 크기 * 2 - 1 이다. (예를 들어, 체스판 크기가 3이면 ///// 이렇게 5개를 검사해야한다.) / 대각선을 N-Queen의 가로라고 보면 된다. isused는 ＼모양의 대각선으로 이런 식으로 (x,y)에 비숍을 넣으면 isused(x-y+체스판 크기-1)의 값을 1로 설정하여 해당 대각선은 사용되고 있다는 것을 표시해줬다. 함수의 매개변수로 cur, length, count를 설정했는데 cur은 현재 / 대각선의 위치(체스판 크기가 3이면 0부터 5까지다.), length는 / 대각선이 체크할 체스판의 개수, cou..
백준 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]))

티스토리툴바