[1단원 연습문제 풀이] 파이썬으로 쉽게 풀어 쓴 자료구조

AP과제로 직접 열심히 작성해 본 코드 ㅠㅠ

1장은 파이썬 코드보다는 정의를 물어보거나 활용하는 문제가 많았다.

나도 이 학교에 입학 후 초반에 과제를 할 때 Tistory 신인님들 덕을 받았으니

과제를 하며 어려움을 겪고 있는 여러분께 풀이를 공유합니다...!

어렵거나 궁금한 코드가 있다면 댓글로 물어보세요!!!

#1.1
(1)스택, (2)큐

#1.2
numOF(item)
Bag에 들어있는 item의 숫자를 반환하는 함수

#1.3
Time(h, m, s): 시, 분, 초를 표현하는 추상 자료형
    - h: 시간을 나타내는 정수형 변수
    - m: 분을 나타내는 정수형 변수
    - s: 초를 나타내는 정수형 변수

h(): 현재 시간을 반환하는 함수
    - 반환값: 시간을 나타내는 정수형 변수 h

m(): 현재 분을 반환하는 함수
    - 반환값: 분을 나타내는 정수형 변수 m

s(): 현재 초를 반환하는 함수
    - 반환값: 초를 나타내는 정수형 변수 s

diffSeconds(otherTime): 다른 시간과의 차이를 초 단위로 반환하는 함수
    - otherTime: 비교할 다른 시간 객체
    - 반환값: 현재 시간과 otherTime의 차이를 초 단위로 나타내는 정수형 변수

isAM(): 현재 시간이 오전인지 확인하는 함수
    - 반환값: 오전이면 True, 오전이 아니면 False

isPM(): 현재 시간이 오후인지 확인하는 함수
    - 반환값: 오후이면 True, 오후가 아니면 False

isSame(otherTime): 다른 시간과 현재 시간이 같은지 확인하는 함수
    - otherTime: 비교할 다른 시간 객체
    - 반환값: 현재 시간과 otherTime이 같으면 True, 다르면 False

toString(): 현재 시간을 문자열로 반환하는 함수
    - 반환값: 시간을 "hh:mm:ss AM/PM" 형식의 문자열로 표현

#1.4
(1) O(n^2)
(2) O(n^3)
(3) O(n^3)
(4) O(2^n)
(5) O(n!)

#1.5
T(n)<=30n+4
30n은 n의 증가에 따라 선형적으로 증가, 4보다 큰 영향을 미친다.
그러므로 30(n)+4는 O(n)이다.

#1.6
logn < n < nlogn < n^2 < n^3 < 2^n < n! < 1

#1.8
O(n^2)
O(log(n))

#1.9
    최선 최악
(1) O(1) O(1)
(2) O(1) O(n)
(3) O(n) O(n)
(4) O(n) O(n)

#1.10
O(n)
O(n^2)

#1.11
재귀호출의 종료 조건이 없다.
그래서 무한히 재귀적 호출되어
오류가 나므로 종료조건을 명시해야 함.

#1.12
예를 들어 sub(5) 호출 시 sub(4), sub(3)이 호출됨.
sub(4) 호출 시 sub(3), sub(2)이 호출됨...
이를 보면 피보나치 수열의 n번째 항과 같다.
그러므로 대략적으로 O(2^n)이다.

#1.13
sum(5)호출
=> n이 5이므로 5출력
=> n이 1보다 크므로 else문으로 n+sum(n-1)로 계산
.
.
.
sum(1)호출
=> n이 1로 1출력
=> n이 1보다 작으므로 if문으로 0반환

그러므로
5
4
3
2
1
이다.

#1.14
asterisk(5)는 if문을 만족하고
asterisk(2)도 if문을 만족하고
asterisk(1)는 if문을 만족하지 않는다.
그러므로 "*" 2개가 출력된다.