복잡한 문제를 쉽게 풀어주는 Recursion (Divide & Conquer algorithm), String

index로 푸는 것보다, 바로 물어보는 게 더 편하다

 

 

 

👩‍💻 문제

Exercise: is in
ESTIMATED TIME TO COMPLETE: 18 minutes

We can use the idea of bisection search to determine if a character is in a string, so long as the string is sorted in alphabetical order.

First, test the middle character of a string against the character you're looking for (the "test character"). If they are the same, we are done - we've found the character we're looking for!

If they're not the same, check if the test character is "smaller" than the middle character. If so, we need only consider the lower half of the string; otherwise, we only consider the upper half of the string. (Note that you can compare characters using Python's < function.)

Implement the function isIn(char, aStr) which implements the above idea recursively to test if char is in aStr. char will be a single character and aStr will be a string that is in alphabetical order. The function should return a boolean value.

As you design the function, think very carefully about what the base cases should be.

 

 

💡 풀이

#Baseline
def isIn(char, astr):
    if astr == '':
        return False
    
    if len(astr) == 1:
        return char == astr
    
    #나머지 경우
    midindex = len(astr)//2
    midchar = astr[midindex]

    #중간값인 경우
    if char == midchar:
        return True
    #더 작은 경우
    elif char < midchar:
        return isIn(char, astr[:midindex])
    #더 큰 경우
    else:
        return isIn(char, astr[midindex+1:])
    
print(isIn('x', 'acdfgrsuvxz'))

#값
True

 

 

✍️ 해설

char 이 astr 안에 있으면 true, 없으면 false !! 

baseline은 2개가 있다 (astr=0인 경우, astr=1인 경우 그 값이랑 바로 비교 가능, 그 외의 경우)

1) aStr이 알파벳 순서로 정렬되어 있다

2) aStr 중간값 = char : 종료 (bisection search)

3) 아닐 경우,  smaller/ bigger 값 받아서, smaller이면 high = 중간값, bigger이면 low = 중간값으로 옮긴 후

    그것의 중간값인지 또 물어본다

4) 최종적으로는 중간값을 return하는 것으로 종료

 

🥳 배운점

너무 코드 길이 줄이려고 하지 말고, 

일단 baseline부터 먼저 생각해서 만들고 나서, 그 다음 값들은 if, elif, else 문으로 차근차근 풀어나가면 된다.

그리고 인덱싱할때 +1, -1 하면서 해당 값을 포함할지 말지 꼭 잘 계산해보기 !!! 

 

 

---

 

 

.py 파일은 그냥 import 가능하고, 그 안에 있는 함수들을 모두 사용 가능하다.

 

 

 

import circle -->  circle.area 하는 식으로  불러올 수가 있고

from circle import * --> 그냥 area 하는 식으로 생으로 다 쓸 수도 있다

 

 

---

 

👩‍💻 GRADE PROBLEM !!! (Polysum)

Grader
10/10 points
A regular polygon has n number of sides. Each side has length s.

The area of a regular polygon is: 
The perimeter of a polygon is: length of the boundary of the polygon
Write a function called polysum that takes 2 arguments, n and s. This function should sum the area and square of the perimeter of the regular polygon. The function returns the sum, rounded to 4 decimal places.

 

💡 풀이

from math import tan, pi
def polysum(n, s):
    # polygon의 영역 + (둘레의 길이)^2
    # 소숫점 4자리까지 나오는 sum을 리턴
    '''
    n: 변의 갯수, s: 변의 길이
    모든 변의 길이는 같은 다각형이라고 가정
    '''
    area = (0.25*n*s*s)/tan(pi/n)
    perimeter = n*s
    return round(area + perimeter**2, 4)

print(polysum(4, 3)) 
# 9 + (12)^2 = 9 + 144 = 153

 

🥳 배운점

from math import tan, pi 라고 부르면 그냥 tan, pi 로만 쓸 수 있고

import math 라고 부르면, math.pi, math.tan 으로 써줘야 한다