이자다의 기록

계산 복잡도와 시간 복잡도: 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한지를 나타낸 정도를 '계산 복잡도'라고 한다. 계산 복잡도는 '시간 복잡도'와 '공간 복잡도'로 나눌 수 있다. 빅 오 표기법: 계산 복잡도를 표현하는 방법에는 여러가지가 있는데, 그 중 '빅 오 표기법'을 주로 사용한다. 이 글에선 시간복잡도와 빅 오 표기법을 공부할 예정이다. 알고리즘이 빠르다, 느리다는 시간으로 표현하지 않는다. 다시말해, 초, 분, 시간으로 표현하지 않는다는 말이다. 왜나하면 같은 알고리즘이라도 하드웨어의 차이로 인해 수행시간이 달라지기 때문이다. 문서 작업용 노트북의 처리속도와 게이밍 컴퓨터의 처리속도가 같을 수는 없다. 따라서 알고리즘의 스피드는 곧 '알고리즘이 완료까지 걸리는 절차의 수..

def sum_mul(n): sum=0 for i in range(1, n+1): sum=sum+(i**2) # 거듭제곱은 ^ 기호가 아니라 ** 기호더라 return sum print(sum_mul(10)) def sum_mul2(n): return n*(n+1)*(2*n+1)//6 print(sum_mul2(10)) 1-1. 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for문으로 만들기 배운걸 응용하기만 하면 됐고 거듭제곱 기호가 C와는 다르게 ' ^ '가 아니라 ' ** '인 것을 알게 되었다. 1-2. 연습문제 1-1의 시간복잡도는 O(1)인가 O(n)인가? O(n). 입력값n과 계산 횟수(거듭제곱 한 번, 덧셈 한 번)가 정비례하여 증가하기 때문에 O(n)이다. 1-3. 1부터 ..

def sum_n(n): s=0 for i in range (1, n+1): # 1 이상 n+1 미만 s=s+i return s print(sum_n(10)) print(sum_n(100)) def sum_n2(n): return n*(n+1)//2 # /는 소숫점 나오는 나눗셈, //은 정수 나눗셈 print(sum_n2(10)) print(sum_n2(100)) 첫 번째 방법은 흔히 프로그래밍을 처음 입문하는 사람들이 배우는 방법인데 이는 숫자가 1 늘어나면 계산 횟수가 1회 늘어나는 방식이다. 즉 1000을 입력하면 1000번 더해야한다. 0 + 1 + 2 + 3 + 4 + 5 -> 5를 입력하면 5번 더하게 된다. 두 번째 방법은 가우스가 만들었다 알려진 공식을 이용하는 방법이다. 이 공식을 이용..

전에 한전KDN 공모전 본선에 나갔을 때 내 팀이나 다른 팀들이 평가받는 것을 보면서 공모전에서 고려해야할 점을 몇가지 알게 됐는데 여기에 한번 정리해본다. 1. 개발할 것은 철저한 검증을 거친 후에 선정하라. 어느 팀은 서버실에 화재가 난다면 즉시 알 수 있는 작품을 들고 갔는데 반응이 좋지 않았다. 심사위원님은 "이건 필요 없다.", "서버실에 한번이라도 견학을 해봤다면 이걸 만들었을 리가 없다." 등의 혹평을 내뱉었다. 이미 있는 것, 필요 없는 것은 만들어 가도 좋은 소리는 듣지 못하고 특히 본인이 선정한 주제에 대해 상술한 상황처럼 제대로 조사하지 않은 게 확연히 드러나면 혹평을 받게 된다. 우리 팀도 프로그램을 기껏 만들어 갔는데 이미 사용중인 프로그램이라는 소리를 들었다. 분명 사전에 검색을..

모두의 파이썬 day15인 타자 게임 만들기를 해봤다. time 모듈에 좀 더 익숙해진 것 같다. 이번 챕터에서 배운 것을 아래에 정리해둔다. import random import time wordList=["cat", "dog", "fox", "monkey", "mouse", "panda", "frog", "snake", "wolf"] qnum=1 #문제 번호 print("[타자게임] 준비되면 엔터!") input() #무언가를 입력받아야 넘어가는 함수. 엔터를 쳐야 다음으로 넘어간다. start=time.time() #시작시간 기록 q=random.choice(wordList) #무작위 선택 while qnum

모두의 파이썬 교재와 파이참으로 파이썬을 공부하다가 AttributeError를 만나게 되었다. AttributeError은 모듈명과 변수명을 똑같이 작성한 것이 원인이 되어 나타났다. 구글링을 해보니 나처럼 모듈 이름이랑 변수 이름을 똑같이 해버린 사례가 꽤 있었다. 모듈에서 가져올 속성의 이름이 오타가 나서 이 모듈에 이런 속성은 없다고 AttributeError가 나온 경우도 있었고. 나의 사례를 코드로 설명하자면 아래와 같다. 주석에 주목하자. import random as r #random 모듈을 r 이라고 사용하겠다고 선언 (문제의 원인) def make_question(): a=r.randint(1,40) # 아래의 for문 블럭이 한바퀴 실행된 후 이 줄에 문제가 생긴다. b=r.randi..