[항해99] 혼자 알고리즘 공부 끄적끄적 Day 1

6월 11일 AM 8 : 30  -> 6월 12일 AM 2 : 30 분까지 공부 

 

혼자 공부하는 공간으로 사용 중

정리하면서 필요할 때 공부한거와 같이 꺼내볼 것 ! 

처음이라 모르는게 99프로도 아니고 100프로라 길어질 것만 같다. 

익숙해지면 공부할께 좀 줄어들겠지 ㅠㅠㅠㅠ

 

파이썬을 이용해 알고리즘 문제를 해결해보자 !

• 파이썬에서 알파벳 아스키코드 사용하여 숫자로 변경
• 시간복잡도 빅오 O(N)
• 자료구조
  • array, Linked List
• 이진탐색, 순차탐색
• 재귀함수
  • 팩토리얼
  • 회문검사 - 반복문

문자인지 확인하는 방법 

str.isalpha() 를 이용하면 해당 문자열이 알파벳인지 확인가능 !

 

알파벳 별로 빈도수를 리스트에 저장하기

알파벳 별 빈도수를 저장하기 위해 우선 길이가 26인 0으로 초기화된 배열을 만든다.

alphabet_occurrence_array = [0] * 26

컴퓨터는 0, 1밖에 못알아들어서 아스키코드 사용해야함

아스키코드  python char to ascii code 로 구글링

 

아스키코드를 이용해서 문자를 index로 만드는 방법

index를 문자로 만들 수 있다

a - > 0

a -> ord(a) -> 97 - ord(a) = 0

 

0 - > a

0 -> 0 + ord(a) -> 97 -> chr(97) -> a

 

시간복잡도 

 

알고리즘은 항상 최고의 성능인 빅오메가가 나오는 경우가 거의 없으니까

항상 최상의 성능을 확인하는 빅오 O(N)를 사용해 구할것이다!!!!! 

 

너무 어렵고 이해가 안가지만 다시 화이팅 화이팅

 

특정 자료구조는 삽입/삭제가 빠르고

특정 자료구조는 조회가 빠름.

 

경우에 따라 다양한 자료구조와 알고리즘을 사용해야 함. 

 

자료구조

array는 순차적으로 데이터를 저장하는 공간이라면

Linkded List는 다음 노드라고 불리는 공간에 데이터를 저장하고 그 다음공간을 지목하는 포인터라는 공간이 있음

 

자료구조

배열(array)은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다.

최악의 경우 배열의 길이 N만큼을 옮겨야 하기에 O(N)의 시간 복잡도를 가짐.

또한 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조를 가진다.

 

링크드리스트는 리스트는 크기가 정해지지 않은 데이터의 공간임. 연결고리로 이어주기만 하면 자유자재로 늘어날 수 있음.

리스트는 특정 원소에 접근하려면 포인터를 따라 탐색해야함.

최악의 경우에는 모든 화물칸을 탐색해야하기 때문에 O(N)의 시간 복잡도를 가짐.

 

리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 됨.

따라서 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 해결 가능.

 

위의 내용 표로 정리 했을 경우

정리하자면 데이터를 접근하는 경우 즉각적으로 조회하는 경우가 많다면 array

삽입과 삭제가 빈번하다면 LinkedList를 이용하는 것이 좋습니다 !

아래주소나 구글에 동적배열 

https://stackoverflow.com/a/5932364 https://en.wikipedia.org/wiki/Dynamic_array

LinkedList 중간에 추가하고 싶을때 설명

LinkedList 추가 삭제 할때 index가 0일때에 대한 추가적인 처리가 꼭 필요 !!

 

 

이진탐색은 우선 0과 1할때의 이진을 생각하면 됨

순차탐색은 하나하나씩 탐색하는 방법

 

클래스 -> 분류, 집합 같은 속성과 기능을 가진 객체(유일무이한 사물 ex. 사람, 동물, 식물 등등)를 총칭하는 개념.

 

sequential은 순차적으로 탐색한다는 의미

 

숫자 내림 하는방법 

// 연산자를 이용하면 소수점 이하의 수를 모두 버리고 몫만 나타낼 수 있음.

print((4 + 5) / 2)

4.5

print((4 + 5) // 2)

4

 

이진탐색

 

 

 

len재귀란? 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻함. 재귀함수 : 자기 자신을 호출하는 함수  재귀함수로 돌릴때는 무한정 돌게 하면 안됨 언제 재귀함수가 끝날지 알려줘야지 오류가 발생하지 않는다. if number < 0: return 재귀함수는 꼭 끝을 알려줘야한다 !! 팩토리얼  : 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것. 팩토리얼 문제는 재귀함수와 관련되어 나오는 대표적인 문제이다.  ex) 3!은 3*2*1 =6    !는 팩토리얼의 표기 방법       4!는 4*3*2*1= 4*3! =24 이유는 3*2*1과 같기때문에 3!으로도 표현가능한다 즉 Factorial(n) = n * Factorial(n-1) Factorial(n - 1) = (n - 1) * Factorial(n - 2) ... Factorial(1) = 1  1이 되는 구조 계속 반복되는 구조라서 재귀함수를 쓰면된다 !! 회문이란? 회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 말함. ex) 토마토, 오디오, 아시아, 일요일, 소주만병만주소, 가련하시다 사장 집 아들 딸들아 집 장사 다시 하련가 palindrome 은 회문을 의미 is_palindrome("오디오") ->true is_palindrome("tomato") ->False is_palindrome("abcba") -> true 첫번째 글자와 맨 뒤 첫번째 글자가 같아야하고 두번째 글자와 맨 뒤에서 두번째 글짜가 같은 형식으로 이루어짐. 마지막 남은 가운데 글자는 뭐가오든 상관 X 내장함수 len https://wikidocs.net/32

특정구조가 반복되는 것 같은 양상을 보이면 재귀함수로 문제를 축소시키는 추측을 해보도록 하자 !

재귀함수를 쓸때는 꼭 탈출조건을 생각하여 써주자 !!!!