python 코딩테스트 대비하기 1

이번 상반기 처음으로 코딩테스트를 보게 되었다!!

일주일정도 시간이 있어서 제주코딩베이스 이호준님 영상 참고해서 공부하려고 한다!

유튜브 + 인프런 눈떠보니 코딩테스트 전날

https://www.youtube.com/watch?v=orf9ailzXvI&t=982s 

재귀함수

1부터 n까지의 합

> 시그마 공식 n*(n+1) // 2

> 수학 공식으로 풀면 시간차이가 엄청 나므로 기본적인 공식 알고 있어야 함

 

재귀 함수로 만들기

def f(n):
	if n <= 1:
    	return 1
    else:	
    	return n + f(n-1)
        
n = 100
print(f(n))

5050

재귀함수 사례

- 반복문은 bottom up, 재귀함수는 top down

- 재귀함수는 종료 조건 필요 (if else 등)

숫자를 꺼꾸로 셀때 편리하다

2진수 구하기

1번 방법

이진수 bin(11)[2:]

8진수 oct()

16진수 hex()

 

2번 방법 (반복문)

문자열로 옆으로 붙이고, 뒤집은 순서로 출력 (아래에서 위로)

x = input()
result = ''
while True:
	if x % 2 == 0:
    	result += '0'
    else:
    	result += '1'
    x = x // 2
    if x == 1:
    	result += str(x)
        print(result[::-1])
        break

3번 방법 재귀함수

def 이진수구하기(입력값):
	if 입력값 < 2:
    	return str(입력값)
    else:
    	return str(이진수구하기(입력값//2) + str(입력값 % 2)
이진수구하기(11)

피보나치

define f(n):
	if n <= 1:
    	return 1
    else:
    	return n * f(n-1)

print(f(n))

세 자리마다 콤마 찍기

- 뒤의 세자리를 먼저 잘라서 ,를 붙이고 앞을 다시 재귀함수로 돌리기

def comma(s):
	if len(s) < 3:
    	return s
    else:
    	return comma(s[:len(s)-3]) + ',' + s[len(s)-3:]
comma('1000000')

# 다른 방법 format 활용
n = 9999999
n = format(n, ',')
print(n)

#9,999,999