24.01.14 백준, 재귀 알고리즘

python 구현 부분이 내가 너무 부족하다는 것을 알아버렸다.

매 문제를 풀 때마다 기본적인 함수를 검색하고, 찾아볼 수 없기 때문에 solved.ac 기초적인 문제로 함수에 익숙해 지도록 했다.

Python

Ascii

• ord(문자) - 아스키 코드를 반환
• chr(숫자) - 숫자에 맞는 아스키 코드 반환

for문 역순

• for(큰 수, 작은 수,-1)

백준

2420

파이썬 절대값 함수 abs()

2475

파이썬 제곱 x ** 2

2738

2중 for문을 이용해서 문제를 해결했다.

3003

띄어쓰기로 구분된 여러개의 숫자

5579

list.remove() 함수를 이용해서 풀었다.

10872

재귀함수 factorial

def factorial(num):
	if num <= 1:
		return 1
	ans = num * factorial(num-1)
	return ans

나도 발전하고 있다 즐거워 즐거워라

1978

소수(PrimeNumber) 찾기

• 소수란 1과 자기 자신만 약수로 가지는

def Prime_num(num):
	for i in range(2,num+1):
		if num % i == 0:
			if num == i:
				return True
		break

• 이걸로 문제를 해결한 것이 아니라 한번 더 안보고 구현해본 코드이다.

9020 골드바흐의 추측

진짜 어썸어썸어썸!!

내가 이걸 풀었다 기분이 너무 조아라

골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것.

이러한 수를 골드바흐 수 라고 한다.

또, 이 두 짝수를 골드바흐 파티션이라고 한다. 이 두 짝수중 두 소수의 차이가 가장 작은것을 출력하는 문제이다.

문제접근

문제를 보자마자 해결법이 나오는 천재는 아니기 때문에 고민을 하기 시작했다.

고민해서 나온 첫 번째 해결 방법이 소수는 대칭으로 나오니 1-n 까지 소수를 구한 다음 그곳에서 파티션을 찾는게 아니라, n/2까지 소수 구하고, 그 소수를 n에서 빼서 나온 값이 소수라면 골드바흐 파티션이 성립하겠다. 라고 생각해서 접근했다.

그리고 작은 소수부터 구하는게 아니라 for문을 역순으로 돌려 큰 소수부터 찾아서 시간을 절약했다

def prime_number(num):
	for i in range(2,num+1):
		if num % i == 0:
			if num == i:
				return True
		break

매개변수가 소수인지 판별하는 함수이다. 1과 자신만 약수로 가져야 한다.

n = int(input())
for i in range(int(n/2), 1,-1):
	if (prime_number(i)):
			if(prime_number(n-i)):
				print(i, n-i)
				break

되게 깔끔하게 잘 짠것 같다.

1914 하노이의 탑

받아온 원반의 개수보다 하나 적은 원반들을 목적지가 아닌곳으로

맨아래 원반 이동 → 다른곳으로 이동시킨 원반을 목적지로

횟수 - 2**n-1

코드를 짜서 맞추긴 했는데, 답을 보고 익숙해진거여서 내일 다시 풀고 올리도록 하겠다.

9663 N-Queen

무너졌다

으악 왜 안되지 내일 조금 더 열심히 해보자 약간 매몰 되어 있는 것 같기도 하다.

pruning(가지치기)

Algorithm

재귀 알고리즘

• 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀(recursion)이라고 한다

자연수의 정의

• 1은 자연수 입니다.
• 어떤 자연수의 바로 다음수도 자연수 입니다.

무한히 존재하는 자연수를 재귀적 정의(recursive definition)을 사용해서 정의

팩토리얼 n! 정의(n은 양의정수)

• 0! = 1
• n>0 , n! = nxn-1!
• 자신과 똑같은 factorial() 함수를 호출 - 재귀호출(recursive call)

재귀 알고리즘의 2가지 분석방법

• 재귀호출을 여러번 사용하는 함수를 순수한(genuinely) 재귀라고한다
  • 하향식 분석
  • 상향식 분석