데이터 구조1

파란색 : 오프라인 강사님

Data Structure 자료구조

각 데이터의 효율적인 저장, 관리를 위한 구조를 나눠 놓은 것

스택, 큐,덱, 트리, 그래프, 연결 리스트(면접에서 많이 나옴, 잘 안다루기 때문)

데이터 구조 활용

문자열, 리스트, 딕셔너리 등 각 데이터 구조의 메서드를 호출하여 다양한 기능을 활용하기

class (타입), 틀 ⇒ 객채, 붕어빵

class : 변수(속성), 함수(메소드)

메서드

객체에 속한 함수

•  
  객체의 상태를 조작하거나 동작을 수행

객체는 Class 배울 때 다시 등장

메서드 특징

• 메서드는 클래스(class) 내부에 정의되는 함수
• 클래스는 파이썬에서 ‘타입을 표현하는 방법’이며 이미 은연중에 사용해왔음
• 예를 들어 help 함수를 통해 str을 호출해보면 class 였다는 것을 확인 가능

기본형식 : 데이터 타입 객체.메서드()

객체 : 문자열이나 딕셔너리 다 가능

객체가 어떤 타입에냐 따라서 메서드들 행동이 다 달라지고, 모습도 다 달라진다.

메서드는 어딘가(클래스)에 속해 있는 함수 이며, 각 데이터 타입별로 다양한 기능을 가진 메서드가 존재

시퀀스 데이터 구조

문자열

문자열 조회/ 탐색 및 검증 메서드

1. s.find(x) : x의 첫 번째 위치(인덱스)를 반환, 없으면, -1을 반환
   ’x’ 에 문자’열’도 들어갈 수 있다.
2. s.index(x) : x의 첫 번째 위치를 반환, 없으면 , 오류 발생
3. s.isalpha() : 알파벳 문자 여부, 모든 문자열이 알파벳으로 이루어 져야 함 (알파벳+숫자 X) T/F리턴*단순 알파벳이 아닌 유니코드 상 Letter(한국어도 포함)
4. s.isupper() : 문자열이 전부 대문자 여부, T/F리턴
5. s.islower() : 문자열이 전부 소문자 여부, T/F리턴

문자열 조작 메서드 ( 새 문자열 반환)(비 파괴적메소드)

문자열은 불변이기 때문에, 새로 만들어야 함

1. s.repalce(old, new[,count])
   바꿀 대상 글자를 새로운 글자로 바꿔서 반환
   [,count] : 몇번 바꿀 것인가, 필수 인자가 아닌 선택 인자
   * 베커스 나우르 표기법(BNF) :
   파이썬 문법 상 이상함 But 공식문서에 존재⇒ 다양한 프로그래밍 언어들이 있음 ⇒ 통일의 필요성
   확장된 베커스 나우르 표기법(EBNF)을 주로 사용 중
   ⇒ [] 는 optional(선택적) 으로 통일되 있다.
2. text = 'Hello World!' new_text = text.repalce('Hello','Python') #기본적 사용 text = text.repalce('Hello','Python') #덮어쓰기 가능 # 원본 문자열을 바꿀 순 있음
3. s.strip([chars])
   문자열의 시작과 끝에 있는 공백 or 지정한 문자를 제거
4. s.split(sep=None, maxsplit=-1)
   지정한 문자를 구분자로 문자열을 분리하여 문자열의 리스트로 변환
   - sep = None: 공백을 기준으로 하겠다
5. ‘separator’.join(iterable)
   iterable 요소들을 원래의 문자열을 구분자로 이용하여 하나의 문자열로 연결

   # 리스트의 원소가 int일 때  arr = [1,2,3,4] text = ''.join(map(str, arr)) #map을 이용해서 각 원소를 문자로 바꿈 print(text) # 1234

6. s.capitalize()
   가장 첫 번째 글자를 대문자로 변경
7. s.title()
   문자열 내 띄어쓰기 기준으로 각 단어의 첫 글자는 대문자로, 나머지는 소문자로 변환
8. s.upper(), s.lower()모두 대문자로 변경, 소문자로 변경
9. s.swapcase()
   대↔ 소문자 서로 변경

리스트

리스트 값 추가 및 삭제 메서드(파괴적 메소드)

상수 시간(실행 속도) 때문에 append()와 pop() 만 많이 씀

1. L.append(x)
   리스트 마지막에 항목 x를 추가
2. L.extend(iterable)
   리스트에 다른 반복 가능한 객체의 모든 항목을 추가(정수는 안됨)

   x = [1,2,3] x.append([4,5,6] print(x) # [1,2,3,[4,5,6]] 와 x.extent([4,5,6] print(x) # [1,2,3,4,5,6]

   • 원본을 바꾸는 메서드는 리턴을 할게 없어서 리턴값이 없다

   print(x.append([0,9,8]))  # None

3. L.insert(i,x)리스트의 지정한 인덱스 i 위치에 항목 x를 삽입
4. 인덱스를 하나 씩 미루면서 추가되기 때문에 실행 시간이 굉장히 김 ( O(n) : 상수 시간 느리다)
5. L.remove(x)
   리스트에서 첫 번째로 일치하는 항목을 삭제
6. L.pop(i)리스트에서 지정한 인덱스의 항목을 제거하고 반환 = 리턴값
   print(L.pop()) 하면 값이 나온다는 말
   i 를 작성하지 않으면 마지막 항목 제거
7. L.clear()
   리스트의 모든 항목을 삭제, 틀 []은 남아 있음

리스트 탐색 및 정렬 메서드

1. L.index(x, start, end)
   리스트에 있는 항목 중 가장 왼쪽(첫 번째로 일치)에 있는 항목 x의 인덱스를 반환 = 리턴 값 존재
2. L.reverse()
   리스트의 순서를 역 순으로 변경 (정렬 X), [::-1]와 동일
   1,5,3 → 3,5,1 로만 바꿈

   my_list = [1,3,2,8,1.9] reversed_list = my_list[::-1] # 슬라이싱 my_list,reverse() print(my_list) print(revesed_list)

3. L.sort()
원본 리스트를 정렬(매개변수 이용가능) ⇒ 리턴 값 없음
   L.sort(reverse=True) 와 reverse() 다름

   arr = [     [1,'kim',90],     [2,'lee',85],     [3,'park',95],     [4.'kang',95] ] arr.sort() # 기본 정렬 arr.sort(key=lambda x : x[2], reverse=True) #성적 으로 역 정렬 print(arr)

4. L.count(x)
   리스트에서 항목 x의 개수를 반환

   my_list = [1,2,2,3,3,3,3] count = my_list.count(3) print(count) # 4

   # count 메소드 for문 으로 만들기 counts = [0] * 4 for lst in my_list:   counts[lst] +=1 print(counts) # [0,1,2,4]

복사

• 파이썬은 데이터에 분류에 따라 복사가 달라짐
• 변경 가능한 데이터 타입과 변경 불가능한 데이터 타입을 다르게 다룸

변경 가능한 데이터 타입 참조형
list, dict 등

복사해도 같은 주소를 참조한다 , 참조하는 주소값을 복사한다.

⇒ 복사한 데이터를 바꾸면 원본 데이터도 변함

변경 불가능한 데이터 타입 값형
str, int 등

⇒ 흔히 아는 복사가 이루어짐

복사 유형

1. 할당

리스트 전체를 보는 주소와 리스트의 한 원소를 보는 주소 중

리스트의 한 원소를 보는 주소를 바꿔도 리스트 전체를 보는 주소는 바뀌지 않기 때문에, 복사가 제대로 안 이루어진다

⇒ 할당 연사자(=)를 통한 복사는 해당 객체에 대한 객체 참조를 복사

2. 얕은 복사- 슬라이싱 이용

슬라이싱은 새로운리스트를 뽑아내기 때문 = 원본 객체와 독립적으로 존재

a = [1,2,3] b = a[:] print(a)

한계

2차원 리스트와 같이 변경 가능한 객체 안 변경가능한 객체가 있을 때 a,b의 주소는 다르지만 내부 객체의 주소는 같기 때문에 함께 변경됨

3. 깊은 복사 import copy .deepcopy()

내부에 중첩된 모든 객체까지 새로운 객체 주소를 참조하도록 함

참고

1. isdecimal() : 문자열이 모두 숫자 문자(0~9)로만 이루어져 있어야 True
2. isdigit() : isdecima() 과 비슷하지만, 유니코드 숫자도 인식(’①’도 숫자로 인식)
3. isnumeric() : isdigit()과 유사하지만, 몇 가지 추가적인 유니코드 문자들을 인식(분수, 지수, 루트 기호도 숫자로 인식)

isdecimal() < isdigit()< isnumeric()

 

추가로 배운 것

1. __ 로 시작하는 애들은 매직 메서드라고 해서 개발자가 직접 불러오는 것은 아니다.
2. 베커스 나우르 표기법(BNF) :
   s.repalce(old, new[,count]) 에서
   [,count] 은 파이썬 문법 상 이상함 But 공식문서에 존재⇒ 다양한 프로그래밍 언어들이 있음 ⇒ 통일의 필요성
   확장된 베커스 나우르 표기법(EBNF)을 주로 사용 중
   ⇒ [] 는 optional(선택적) 으로 통일되어 있다.
3. 원본을 바꾸는 메서드는 리턴 할게 없어서 리턴값이 없다.

   print(x.append([0,9,8])) # None

4. 파괴적, 비파괴적 메소드

   비파괴적 : Sorted(iterable) 파괴적 : list.sort()

5. set : 메소드로 중복 제거할 때 주로 사용함
6. dict 고유한 항목들의 정렬되지 않은 컬렉션
   1. 메서드 D.key(), D.get()
7. 복사

   call by refrence 참조 : 가변(list, dict) call by value 복사 : 불변(int,float,str)

8. 메모리
   • 메모리에 load 되야 실행이 된다
   • 메모리는 총 4개의 영역위에서부터 code, data(정적영역), heap , stack
     • code : 프로그램이 들어감
     • data : 전역 변수, 정적 변수(static 변수, 파이썬에는 없다)
     • heap : 동적 변수(객체, 리스트 등)
     • stack : 지역변수(함수)

해야 하는것

O(n) : 상수 시간

메소드들 for문으로 만들기

 

def find_min_max(*arr):   for num in arr:     if num< min:       min = num     if num > max:       max = num     pass