알고리즘

Algorithm, 공간복잡도란?

파이썬에서 배열을 지정할때 '몇칸 쓸게요~' 처럼 공간을 지정할 수 있다고 했을 때 이 공간을 적게 쓸수록 공간 복잡도가 낮아진다고 한다. 이렇게 공간의 복잡도를 수치화하여 나타낸것이 공간복잡도이다. 그렇다면 "hello my name is salt" 라는 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어있는지 반환하는 코드를 생각해보자. + 이때 생각해보면 좋을 것은 isalpha() 함수와 ord()함수이다. print("a".isalpha()) # True print("1".isalpha()) # False s = "abcdefg" print(s[0].isalpha()) # True 위는 문자열이 알파벳인지 확인하는 isalpha() 내장함수이다. alphabet_occurrence_arr..

Algorithm, 시간복잡도란?

python 기준으로 배열을 입력하고 for문을 한 번 돌릴때 돌려야하는 최대 횟수를 배열의 개수만큼, n번이라고 가정한다. 그래서 for문 하나당 N번을 돈다고 가정해서 for문 하나 = N 이라는 식이 성립하다면, 이중 for문은 어떻게 표현할 수 있을까? N2이다. 그러므로 어떤 배열이 주어졌을때 input = [3, 5, 6, 1, 2, 4] 이 배열에서 최대값을 찾아야 한다면 2가지 방법이 존재하게된다. 첫번째 방법은, 첫번째 값을 변수에 저장하고 다음 값과 비교해서 큰 수를 변수에 다시 저장하는 방법이고 두번째 방법은, 비효율적인데 값 하나당 모든 값과 비교해서 어떤 수가 가장 큰지 확인하는 방법이다. 실제 코드를 살펴보자. 1번 방법 : 첫번째 값을 변수에 저장하고 다음 값과 비교해서 큰 수..

Algorithm, Class

클래스 정의하고 생성자 만들기 클래스를 이용하면 같은 속성과 기능을 가진 객체를 묶어 정의할 수 있다. 새롭게 만들어진 생성자는 주소값으로 구분이 가능하다. * Person() : 생성자 # Person을 정의한다. class Person: pass # 새로운 객체를 만든다. person_1 = Person() print(person_1) # person_2 = Person() print(person_2) # 클래스 생성자 설정하기 생성자(constructor)란, 객체를 생성할 때 쓰는 함수이다. 생성자 설정을 위해 클래스 내부에 __init__ 함수를 만들어야 한다. class Person: def __init__(self): print("i am created", self) person_1 = Pe..

Algorithm, Array와 Linked List 개념정리

Array 크기가 정해진 데이터의 공간, 한 번 정해지면 바꿀 수 없다. 원소에 즉시 접근가능하다. (*상수 시간 내에 접근할 수 있다. *O(1)) 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다. (최악의 경우 O(N)의 시간 복잡도를 가진다.) 원소 새로 추가시 새로운 공간을 할당해야 한다. 그러므로 추가/삭제에 사용할 시 매우 비효율적인 자료구조다. Linked List 크기가 정해지지 않은 데이터의 공간이다. 연결만 해주면 자유자재로 늘어날 수 있다. 각 노드는 연결부인 포인터로 연결되어있다. 원소에 접근하려면 연결부를 따라 탐색해야 한다. (최악의 경우 모든노드를 확인해야 하므로 O(N)의 시간 복잡도를 가진다.) 원소를 중간에 삽입/삭제 하려면 앞 뒤의 포인터만 변경해주면 된다...