Lecture 3. STRING MANIPULATION, GUESS-and-CHECK, APPROXIMATIONS, BISECTION
이 글은 Mit Open Courseware(OCW)에서 공개한 교육자료이며 OCW의 라이센스정책을 따릅니다.
License : Common Creative License : BY-NC-SA (저작자표시-비영리-동일조건변경허락)
출처 : https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/lecture-slides-code/MIT6_0001F16_Lec3.pdf
1. STRINGS
1) len( ) : 문자열의 길이를 반환하는 함수
s = "abc"
len(s)
=> 3
2) index : 문자열을 개별 문자의 연결로 생각했을때 인덱스를 통해 배열형태로 각 문자 참조가능
s = "abc"
index : 0 1 2
index : -3 -2 -1
s[0] -> "a"
s[1] -> "b"
s[2] -> "c"
s[3] -> Error
s[-1] -> "c"
s[-2] -> "b"
s[-3] -> "a"
시작문자의 인덱스는 0, 마지막 문자의 인덱스는 -1
3) slice
[start:stop:step] 의 형태로 문자열을 자를수 있음.
[start:stop] 두 인자만 있을 경우 step은 디폴트값인 1
[::] 처럼 모두 생략가능. 이경우 [0,문자열길이,1] 과 동일한 의미
s = "abcdefgh"
s[3:6] -> "def" s[3:6:1] 과 동일
s[3:6:2] -> "df"
s[::] -> "abcdefgh" s[0:len(s):1]과 동일
s[::-1] -> "hgfedbca" s[-1:-(len(s)+1):-1] 과 동일
s[4:1:-2] -> "ec"
4) String 은 변경불가 (immutable)
s = "hello"
s[0] = 'y' -> Error
s = 'y' + s[1:len(s)] -> yello 라는 새 문자열이 생성되서 s가 그 문자열을 가리킴. hello가 yello로 수정된것이 아님
5) for LOOPS RECAP (Recapitulation : 반복,되풀이)
앞서 예제에서 반복문의 iteration은 range()를 통한 숫자만 설명했는데 문자열도 가능하다
s = "abcdefgh"
for index in range(len(s)):
if s[index] == 'i' or s[index] == 'u':
print("There is an i or u")
for char in s:
if char == 'i' or char == 'u':
print("There is an i or u")
두 for문은 동일한 결과를 얻는다.
차이는 위 for문은 반복변수를 숫자타입인 index를 사용했으나 아래 for문은 반복변수를 문자로 사용했다.
2. GUESS-AND-CHECK
1) GUESS-AND-CHECK
반복문을 통한 해답찾기.
cube = 8
for guess in range(cube+1):
if guess**3 == cube:
print("Cube root of", cube, "is", guess)
위 코드는 8의 세제곱근을 구하는 코드이다. 0부터 8까지 하나씩 증가하면서 세제곱결과가 8인 값을 찾는다.
이 코드의 개선점은?
- 1 씩 증가시키면서 추측하므로 세제곱근의 값이 정수가 아닌 소숫점이하일 경우 결과를 얻을 수 없다.
- 정답을 찾아도 종료되지 않는다.
- 세제곱값이 음의 수일 경우 처리할수 없다.
cube = 8
for guess in range(abs(cube)+1):
if guess**3 >= abs(cube):
break
if guess**3 != abs(cube):
print(cube, 'is not a perfect cube')
else:
if cube < 0:
guess = -guess
print('Cube root of '+str(cube)+' is '+str(guess))
위의 코드는 첫번째 코드의 문제점 중 두가지는 해결했으나 세제곱근의 값이 정수가 아닌 소숫점이하일 경우 결과를 얻을 수 없다.
이 문제를 해결하기 위해 근사치를 구하는 방법을 알아본다.
2) APPROXIMATE SOLUTION – cube root
cube = 27
epsilon = 0.01
guess = 0.0
increment = 0.0001
num_guesses = 0
while abs(guess**3 - cube) >= epsilon:
guess += increment
num_guesses += 1
print('num_guesses =', num_guesses)
if abs(guess**3 - cube) >= epsilon:
print('Failed on cube root of', cube)
else:
print(guess, 'is close to the cube root of', cube)
guess를 0.0001 씩 증가시키면서 세제곱한 값이 cube와의 차이가 0.01 보다 작을때까지 찾는다.
3. BISECTION SEARCH
increment를 조금씩 증가시키면서 세제곱근을 찾는 방법은 목표값의 크기에 비례해서 시간이 소요된다.
BISECTION SEARCH로 알고리즘을 개선해서 세제곱근을 찾는 방법을 알아본다.
처음에 0과 세제곱값(cube)의 중간값을 세제곱근(guess)로 추측해서 guess의 세제곱과 cube의 차가 epsilon보다 크면 다시 추측하는 방식을 사용한다. 계속 절반씩 추측구간을 줄여나가 정답이나 근사치를 찾는 방식이다.
cube = 27
epsilon = 0.01
num_guesses = 0
low = 0
high = cube
guess = (high + low)/2.0
while abs(guess**3 - cube) >= epsilon:
if guess**3 < cube :
low = guess
else:
high = guess
guess = (high + low)/2.0
num_guesses += 1
print( 'num_guesses =', num_guesses)
print( guess, 'is close to the cube root of', cube)
0부터 increment 하는 방식의 성능이 O(N)이라면 , Bisection Search는 O(log2N) - 수식편집기가 안먹네 ㅡㅡ;;
위 코드는 1보다 작은 값과 음수를 처리하지 못한다. 수정해보시오
0보다 크고 1보다 작은 값은 제곱할수록 숫자가 작아진다. 그리고 음수의 경우 low와 high가 바뀌므로 검색구간에 대한 고려가 필요하다.
댓글