22.11.10 [자료구조.. & python]

요거 참조하고 읽기.. <튜터님 실강부분>

2022.11.10 - [TIL] - 22.11.09 [파이썬기본문법 2 & 알고리즘]

자료구조..2주차강의요약

목표 

1. 어레이와 링크드리스트에 대해 배우고 차이점을 익힌다.
2. 이진 탐색의 효율성과 전제 조건에 대해 배운다.
3. 재귀함수의 방법과 전제 조건에 대해 배운다.

근데 아마도 ... 이진탐색 전까지만 나가고 3주차로 넘어갈듯 하다 튜터님의 조언..

즉...나머지는 좀 있다 본다.!

 

 

어레이(배열)와 링크드리스트

 

배열...

크기가 정해진 데이터공간..

원소에 즉시 접근가능할수 있다.. = 상수시간내에 접근할수 있다 = O(1)

>> 추가로 첨언이 있었다면... 이렇게 접근하는 경우는 배열의 구성원소를 알고있을경우에만..!

그러나... 원소를 중간에 삽입..삭제하려면... 모든 원소를 다 이동시켜야해...

즉... 최대 ..O(N)만크의 복잡도..

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

 

링크드리스트 ~= 리스트... 

연결고리가있다... 크기가 정해지지 않는 데이터공간..

특정원소에 접근 하려면...연결고리를 따라 탐색..

>즉.. O(N)의...복잡도가 생김..

 >>이걸 보완한 double linked list 이게 있는데 이건 양방향 탐색이 가능..?

    >>그래도 비효율적이다...

연결고리..포인터/// 화물칸..노드

그러나.. 삽입 .,삭제는 쉽다. O(1)의 시간복잡도안에.. 상수시간내에 가능하다..

 

https://www.notion.so/2-9e5eccb6b7ce4c4ba028dae6ad135830#d8c00d29f56543e783d1ea06ab167d8e

 

?

파이썬에서 사용하는 리스트는...어레이(배열)로 구성이 되있다...

그러나... 동적 배열이라고 하여... 배열의 길이가 늘어나도 O(1)의 시간복잡도가 걸리도록 설계

즉.. 파이썬의 배열은 링크드 리스트와 배열... 모두 쓸수 잇따..?

 

 

클래스

속성과... 기능을 가진 객체를 총칭하는 개념 자바와 유사한듯..

쓰이는 방법만 약간 다름.. 생성자... self? 

 

링크드리스트 구현

..각각의 노드 생성하고 ...next이용해서 이어줘야함..

근데 일일히 하기 귀찮으니

클래스 생성해서 그일을 대신 시켜주자..?

근데... 

정리하면,

1) LinkdList 는 self.head 에 시작하는 노드를 저장한다.

2) 다음 노드를 보기 위해서는 각 노드의 next 를 조회해서 찾아가야 한다.

무튼 ...깃허브 참조해보자..!

 

 

흠...

if  in 문법을 알았다.

input = "abadabac"

# 나는 이중 for문에서 ... 더 생각 못하겠다.
def find_not_repeating_character(string):
    aphabet_occurrence_array = [0] * 26

    for a in string:
        aphabet_occurrence_array[ord(a)-ord('a')] +=1

    count = -1
    select_chr =[]
    for b in aphabet_occurrence_array:
        count += 1
        if b ==1:
         select_chr.append(chr(ord('a')+count))

    if count == 0:
        return '_'

    for c in string:
        for d in select_chr:
            if c == d:
               return c

이건 내가 푼 풀이인데.. 이중 for문에서 더 풀 수가 없어서 난 잡하게 되었다..

 

강사님 풀이는

def find_not_repeating_first_character(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")
        alphabet_occurrence_array[arr_index] += 1

    not_repeating_character_array = []
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]

        if alphabet_occurrence == 1:
            not_repeating_character_array.append(chr(index + ord("a")))

    for char in string:
        if char in not_repeating_character_array:
            return char

    return "_"


result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

이중 for문을 if in 문으로 해결 했다

 

if -in 은뭘까..?

 in 뒤에 는 리스트나 ... 문자열인온다.. 문자열은..리스트에 일종이니까 상관없겠지.?

>무튼 그래서 .. ~~ 값이 리스트에 있다면 True를 없다면 False를 반환하는 그런문법

즉

for char in string:
    if char in not_repeating_character_array:
        return char

요부분에서 존재 유무를 돌아가면서 하나 씩 비교하기때문에 

먼저 나온 문자가 있다면 바로 그값을 리턴해주고 종료해라 그런 의미인듯...

그러면 나도 이렇게 정답을 수정하면 이중 for문을 탈출 할 수 가 있겠다..!

for c in string:
    if c in select_chr:
        return c

요렇게 수정하면 이중 for문을 탈출 해서 좀더 간결하게 사용 할 수 있다 .!

 

 

 

range 함수..!

 

어렴풋이 기능을 알겠던 range 함수... 검색해보다 있길래... 공부햇다

 

range 함수는 ... 숫자 리스트를 자동으로 만들어주는 함수 이다

 

1. range(숫자) 는 0부터 숫자 미만의 숫자를 포함하는 range 객체를 만들어준다

 

2.range(시작숫자,마지막숫자) 는 시작수부터 ~ 마지막수 미만의 숫자를 포함하는 range 객체를 만들어준다

 

 

++

추가로 잡당방에 올라온 사이트가 생각보다 공부에 도움이 되었다

https://pythontutor.com/render.html#mode=display

Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java

def summarize_string(target_string):
    
    n = len(target_string) # 19번째라인 문자길이 8개니까 n은8
    count = 0
    result_str = ''

    for i in range(n - 1):   # n-1개..의 리스트만듦.. 즉 0~6번 인덱스번호,,즉 마지막글자는 포함안됨
        if target_string[i] == target_string[i + 1]:
            count += 1
        else:
            result_str += target_string[i] + str(count + 1) + '/'
            count = 0

    result_str += target_string[n - 1] + str(count + 1) #마지막글자의 인덱스번호가 7임 즉 마지막 글자를 위한것

    return result_str


input_str = "acccdeee"  #문자 길이는 8개

print(summarize_string(input_str))

인덱스 값... 0부터 시작 되는거 ... ...주의 하기..

#으로 상세 설명했다!

 

 

어떤 자료구조를 선택해야 되는지 기준..은!

1. 삽입시간 2. 삭제시간 3. 검색시간 4.정렬여부

요걸 기준 삼아서 하면된다... .원하는 기능이 우선순위로 잡으면됨..