이 두 가지 자료형은 모든 문제에 빠짐없이 쓰이는 자료형이므로 확실히 이해 하기! 

1. 리스트

• 순서대로 저장하는 시퀀스(입력한 순서대로 유지된다)
• 숫자 외에도 다양한 자료형과 함께 저장 가능 (ex. [1, 2, 3, 5, 4, '안녕', True] )
• 변경 가능한 (Mutable List) 
• 동적 배열로 구현된

장점

리스트의 주요 연산 시간복잡도

리스트 특징 

1) 슬라이싱 

특정 범위 내의 값을 매우 편리하게 가져올 수 있음. 

a[i : j] 일 때, i 부터 j-1 까지 값을 리턴함. 

# 리스트
[1, 2, 3, 4, 5, '안녕', True]

a[1:3]
>> [2, 3]

# 시작 인덱스 생략 가능
# 맨 처음부터 2번째 인덱스까지 반환
a[:3] 
>> [1 ,2, 3]

# 종료 인덱스도 생략 가능 
# 4부터 맨 마지막까지 반환

a[4:]
>> [4, '안녕', True]

# 세번째 파라미터 : 단계(step)의 의미. 

# 맨 마지막 파라미터는 스텝의 의미
# 2씩 건너 뜀
# '1'  2  '3'

a[1:4:2] 
>> [1, 3]

2) 삭제 

1. 인덱스를 사용하여 삭제 - del , pop

[1, 2, 3, 4, 5, '안녕', True]

del a[1]     # 1번 인덱스 삭제 
>> [1, 3, 4, 5, '안녕', True]

[1, 2, 3, 4, 5, '안녕', True]

a.pop(5)    # 다섯번째 인덱스 삭제 
>> [1, 2, 3, 4, 5, True]

2. 값을 통한 삭제 - remove

[1, 2, 3, 4, 5, '안녕', True]

a.remove(3)    # 값이 3인 것을 삭제 
>> [1, 2, 4, 5, '안녕', True]

* 리스트의 형태 
리스트는 객체에 대한 포인터 목록으로 구현되어 있다. 

일반적 정수형 배열 : 정수로만 이루어진 값을 연속된 메모리 공간에 저장
파이썬 리스트 : 연결 리스트에 대한 포인터 목록을 관리하고 있음 

아래 배열을 보자. 

[1, '안녕', True]

파이썬 리스트는 포인터 목록을 관리하고 있다고 했다. 이는 각각의 객체에 대한 참조를 갖고 있다는 것으로 
만약 2번 인덱스 값에 대해 접근하려고 하면 포인터의 위치를 찾아가서 타입 코드를 확인하고 값을 일일이 살펴봐야 한다. 

모두 제각각인 자료형을 단일 리스트에 모두 통합하여 저장할 수는 있지만, (강력한 장점) 

값에 접근하기 위해서는 모든 포인터 위치를 보고 값을 확인해야 하기에 속도를 희생한 측면이 있는 언어이다. (성능상 무의미하긴 하지만..)

2. 딕셔너리 

• 키, 값 구조로 이루어짐
• (*파이썬 3.7 + 기준) 입력 순서가 유지된다.
• 해시 테이블로 구현되어 있음. 
  
  
  

장점

딕셔너리의 주요 연산 시간 복잡도

3.7 이상부터 내부적 인덱스를 이용해 입력 순서를 유지하도록 개선되었지만,
여전히 3.6 이하를 사용하는 곳이 많으므로 입력 순서가 유지될 것이라 가정하는 것은 매우 위험! (버전 잘 확인하기) 

유용한 collections

import collections

collections.OderedDict()        # 입력 순서 유지 
collections.defaultdict()       # 조회 시 항상 디폴트 값 생성 -> 키 오류 방지
collections.Counter()           # 요소의 값을 키로 하고 개수를 값 형태로 만들어 카운팅

딕셔너리 활용 방법

1) 값 추가 

{'key1' : 'value1', 'key2', 'value2'}

a['key3'] = 'value3'
>> {'key1' : 'value1', 'key2': 'value2', 'key3' : 'value3'}

2) 키 존재하는 지 확인

if 'key4' in a:
	print('존재하는 키')
else :
	print('존재하지 않는 키')

3) 키, 값 조회 

for k,v in a.items():
	print(k, v)

4) 키 삭제 

{'key1' : 'value1', 'key2', 'value2', 'key3' : 'value3'}

del a['key1']
>> {'key2', 'value2', 'key3' : 'value3'}

딕셔너리 모듈

1) defaultdict 객체

# 존재하지 않는 키를 조회할 경우,
# 에러 메시지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템 생성.

a = collections.defaultdic(int)
a['A'] = 5
a['B'] = 4
a 
>> defaultdict(<class 'int'>, {'A':5 , 'B' : 4}) 


a['C'] += 1
a
>> defaultdict(<class 'int'>, {'A':5 , 'B' : 4, 'C' : 1})

'C' 는 없는 키 값이지만,
디폴트인 0을 기준으로 자동으로 생성 후 여기 1을 더해 최종적으로 1인 값과 그의 키인 'C' 를 딕셔너리에 추가한다. 

2) Counter 객체

# 아이템에 대한 개수를 계산해 딕셔너리로 리턴한다. 

a = [1,2,3,4,5,5,5,6,6]

b = collections.Counter(a)
b
>> Counter({5:3, 6:2, 1:1, 2:1, 3:1, 4:1})

키에는 아이템의 값이, 값에는 해당 아이템의 개수가 들어간 딕셔너리 생성. 

가장 빈도 수 높은 요소 추출

b.most_common(2)

>> [(5, 3), (6, 2)]

3) OrderedDict 객체 (파이썬 3.7 미만 버전) 

# 대부분 언어에서 해시 테이블을 이용한 자료형은 입력 순서 유지 X
# 입력 값을 부여할 경우 OrderedDict는 입력 그대로 순서가 유지됨.

collections.OrderedDict({'banana' : 3, 'apple' : 4, 'orange' : 2})

점근적 실행 시간을 표기할 때 사용하는 것이 빅오이다. 
점근적 실행 시간(알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산복잡도) 은 달리 말하면 시간복잡도 이다. 

•  O(1) : 입력값이 아무리 커도 실행 시간은 일정함 
  예시) 해시 테이블의 조회 및 삽입
  
  
• O(log n) : 매우 큰 입력값에도 크게 영향을 받지 않는 편 
  예시 ) 이진 검색 
  
  
• O(n) : 입력값만큼 실행시간에 영향을 받음. 시간은 입력값에 비례 
  선형 시간 알고리즘이라고 함. 
  예시 ) 정렬되지 않은 리스트에서 최댓값 혹은 최솟값 찾기 
  
  
• O(nlogn) : 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 대부분 해당 
  적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 알고리즘은 O(nlogn) 보다 빠를 순 없음 
  
  
• O(n^2) : 버블 정렬 같은 비효율적인 정렬 알고리즘 
  
  
• O(2^n) : 피보나치 수를 재귀로 계산하는 알고리즘 
  
  
• O(n!) : 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루투 포스로 풀이할 때 해당 

상한과 하한

• 빅오 : 상한을 의미 (가장 늦게 실행될 때)
• 빅오메가 : 하한을 의미 (가장 빨리 실행될 때)
• 빅세타 : 평균을 의미 

파이썬 자료형

1. 숫자 

파이썬에서는 숫자 정수형으로 int 만을 제공.

고정 정밀도 정수형은 지원하지 않게됨. 

bool 또한 int의 서브 클래스 

object > int > bool

2. 매핑

매핑이란 키와 자료형으로 구성된 복합 자료형 

파이썬에서 내장된 유일한 매핑 자료형은 딕셔너리 

3. 집합

중복된 값을 갖지 않는 자료형 
set 이 해당 

set은 입력 순서가 유지되지 않는다. 

# set 
a = {'a', 'b', 'c'}

# dictionary
a = {'a':'A', 'b':'B', 'c':'C'}

4. 시퀀스 

어떤 특정 대상의 순서 있는 나열. 수열 이라고도 함 

• str : 문자의 순서 있는 나열로 문자열을 이루는 자료형 
• list : 다양한 값들을 배열 형태의 순서 있는 나열로 구성하는 자료형. 자유롭게 값을 추가, 삭제 할 수 있는 동적 배열 

불변 시퀀스 : str, tuple, bytes

가변 시퀀스 : list 

# str의 참조 

a = 'abc'

a = 'def'

a가 'abc' 였다가 'def' 가 되었다고 해서 값 자체가 변경된 것이 아니라 
a가 참조하는 주소가 달라진 것이다. 

5. 객체 

파이썬은 모든 것이 객체.

C나 자바는 성능에 대한 우선순위가 높은 언어이며 매우 빠른 연산이 가능. 하지만 공간을 많이 차지 한다. 
하지만 파이썬은 편리한 기능 제공에 우선순위를 둔 언어. 

파이썬은 불변 객체와 가변 객체로 구분

불변 객체

가변 객체 

6. 불변 객체 

파이썬은 모든 것이 객체이기 때문에 원시 타입처럼 각각의 값들이 각 메모리의 다른 영역에 위치하는 게 아니라 
모두 같은 위치에 존재한다. 

10
a = 10
b = a

print(id(10), id(a), id(b))

그렇다면 만약 a 값을 11로 바꾸면 b 도 11로 바뀌어야 하는 게 아닌가?!

-> 그렇지 않다. 

파이썬의 숫자와 문자는 모두 불변이기 때문

값을 담고 있는 변수는 참조일 뿐이고, 실제로 값을 갖고 있는 int 와 str은 모두 불변. 
int, str, tuple 은 불변 객체이르모 dict 의 키나 set 의 값으로 사용 가능하다. 

7. 가변 객체 

list 는 다른 변수가 참조하고 있을 때 값을 변경하면 그 변수의 값이 변경될 수 있다. 

a = [1,2,3,4,5]
b = a
print(b)   # 변경 전 

a[2] = 4
print(a)   # 변경 후 
print(b)

리스트 a의 요소를 변경했더니 b 또한 같이 바뀌는 것을 볼 수 있다. 

출처 : 파이썬 알고리즘 인터뷰 | 박상길

파이썬 고급 문법에 대해 알아보자 

# 인덴트

공백 4칸을 원칙으로 함.

• 첫번째 줄에 파라미터가 있으면 -> 파라미터가 시작되는 부분에 보기 좋게 맞춘다. 
• 첫번째 줄에 파라미터가 없으면 -> 공백 4칸 인덴트를 한 번 더 추가하여 다른 행과 구분되도록 한다. 

# 첫 줄 파라미터 있을 때
foo = long_func_name(var_one, var_two,
                    var_three, var_four)


# 없을 때
def long_func_name(
        var_one, var_two, var_three,
        var_four):
    print(var_one)

# 네이밍 컨벤션

파이썬 변수명 네이밍 컨벤션은 자바와 다르다. 스네이크 케이스를 기본으로 한다. 

• 자바 : 카멜 케이스(단어를 대소문자로 구분하여 섞어서 작명하는 방식)
• 파이썬 : 스네이크 케이스(각 단어를 언더스코어(_)로 구분함)

따라서 파이썬 변수명이나 함수명에는 언더바를 사용해 표기하도록 하자! 

# 카멜 케이스
camelCase: int = 1

# 스네이크 케이스
snake_case: int = 1

# 타입 힌트 

타입 힌트 : 파이썬은 동적 타이핑 언어임에도 불구하고, 타입을 지정할 수 있게 해주는 것

# 타입 지정 안한 경우 -> 어떤 숫자를 넘겨야 하는 지 알 수 없음 
def fn(a):
    
 
# 타입 힌트로 지정한 경우 
def fn(a: int) -> bool:

주의할 점)

파이썬은 동적 할당이므로 아래와 같이 문자열에 정수를 할당하여도 

문자열이 아닌 정수 타입을 반환한다. 

a: str = 1
type(a)

<class 'int'>

# 리스트 컴프리헨션

• 리스트 컴프리헨션 : 기존 리스트를 기반으로 새로운 리스트를 만들어 내는 구문 

파이썬은 map, filter와 같은 함수형 기능을 지원하며 람다 표현식 또한 지원한다.

지나친 리스트 컴프리헨션 사용은 가독성을 떨어뜨리므로 표현식이 2개를 넘지 않게 하는 것이 좋다. 

a = list(map(lambda x :x+10, [1,2,3]))
print(a)

# 결과 [11,12,13]

a = [n  * 2 for n in range(1, 10 + 1) if n % 2 == 1]
print(a)


# 결과 [2, 6, 10, 14, 18]

• 딕셔너리의 경우 

    기존

# 기존 
a = {}
for key, value in dic.items():
    a[key] = value

     리스트 컴프리헨션 사용 시, 

a = {key: value for key, value in dic.items()}

# 제너레이터 

• 제너레이터 : 루프의 반복 동작을 제어할 수 있는 루틴 형태 
• yield 구문을 사용한다. 

기존의 return 구문은 값을 리턴 하고 모든 함수의 동작을 종료한다. 

하지만 yield 는 제너레이터가 여기까지 실행 중이던 값을 내보낸다는 뜻으로 중간값을 리턴한 다음, 함수는 종료되지 않고

계속해서 맨 끝에 도달할 때까지 실행된다. 

def get_natural_number():
    n = 0
    while True:
        n += 1
        yield n 
        
        
 # 종료 구문이 없으므로 값을 계속해서 내보냄

만약 값을 내보내고 싶다면 next()를 통해 추출한다. 

g = get_natural_number()
for _ in range(100):
    print(next(g))

아래와 같이 100까지 출력되는 것을 볼 수 있다. 

여러 타입의 값을 하나의 함수에서 생성하는 것도 가능하다. 

def generator():
    yield 1
    yield 'string'
    yield True


g = generator()
print(next(g))
print(next(g))
print(next(g))

# range 

• range() : 제너레이터의 방식을 활용하는 대표적인 함수

a와 b의 길이를 비교해 보면 둘 다 동일한 100만개가 출력된다. 

a = [n for n in range(1000000)]
b = range(1000000)

print(len(a))
print(len(b))

그러나 차이점은 a는 이미 생성된 값이 담겨 있고, b 는 생성해야 한다는 조건이 있다. 

이제 둘의 메모리를 비교해 보면 확연히 차이가 난다. 

print(sys.getsizeof(a))
print(sys.getsizeof(b))

b가 메모리 점유율이 훨씬 더 적은 것을 알 수 있다. b는 미리 생성하지 않은 값이므로 메모리 점유율이 더 작다.

그렇다고 인덱스에 접근이 안되는 것은 아니다. 

print(b[999])

# enumerate 

• enumerate() : 열거하다 라는 뜻의 함수. 인덱스와 값을 함께 리턴해줌

a = [1,2,3,2,45,2,5]
b = list(enumerate(a))
print(b)


# 결과 [(0, 1), (1, 2), (2, 3), (3, 2), (4, 45), (5, 2), (6, 5)]

인덱스와 값을 함께 출력하고 싶을 때 사용하면 유용하다. 

for i, v in enumerate(a):
	print(i, v)

# 나눗셈 연산자

• // : 정수형을 나눗셈할 때 동일한 정수형을 결과로 리턴함(내림 연산자 역할)
• 즉, 몫을 구하는 연산자이다.

5 // 3

# 결과: 1

• % : 나머지를 구하는 연산자 

5 % 3

# 결과 : 2

몫과 나머지를 동시에 구하려면 divmod() 함수를 사용하면 된다.

divmod(5, 3)

# 결과 : (1, 2)

# print

각각의  출력 방법에 대해 알아보겠다. 

1. 기본 띄어쓰기 출력 

print('A1', 'B1')

A1 B2

2. 구분자 지정 출력 -> sep 사용

print('A1', 'B1', sep=',')

A1, B2

3. 줄바꿈 없이 출력 -> end 사용

print() 함수는 항상 줄바꿈을 하기 때문에

end 파라미터를 공백으로 처리하여 줄바꿈을 하지 않도록 제한 가능하다. 

print('aa', end=' ')
print('bb')

aa bb

4. 리스트 출력하기 (한 줄로)

a = ['A', 'B']
print(' '.join(a))


A B

5. format 사용하기 

idx = 1
fruit = "Apple"

print('{0}: {1}'.format(idx + 1, fruit))

# 인덱스 생략도 가능
print('{}: {}'.format(idx + 1, fruit))

# 결과 
2: Apple

6. f- string 사용 ( 3.6 + 에서만 사용 가능) 

print(f'{idx + 1} : {fruit}')

2: Apple

# pass

pass는 널 연산으로 아무것도 하지 않는 기능.

인덴트 오류나 불필요한 오류를 방지할 수 있다. 코드를 인터페이스부터 구현한 다음에 추후 구현을 진행 가능함. 

class MyClass(object):
    def method_a(self):
        pass
    def method_b(self):
        print("Method B")


c = MyClass()

# locals

• locals() : 로컬에 선언된 모든 변수를 조회할 수 있는 명령.

디버깅할 때 많은 도움이 된다. 

import pprint

pprint.pprint(locals())

# 구글 파이썬 스타일 가이드 

YES

if not users:
    print('no users')

if foo == 0:
    self.handle_zero()

if i % 10 == 0:
    self.handle_multiple_of_ten()

NO

if len(users) == 0:
    print('no users')

if foo is not None and not foo:
    self.handle_zero()

if i % 10:
    self.handle_multiple_of_ten()

길이가 없다는 말은 값이 없다는 뜻으로 not users 로도 충분하다. 

값을 비교할 때는 비교 대상이 되는 값을 직접 비교하는 것이 좋다. 

출처 : 파이썬 알고리즘 인터뷰 | 박상길

파이썬 알고리즘 인터뷰 라는 책으로 코딩테스트 연습을 해보고자 한다. 

각각의 장에서 배운 것들을 정리하고 익히도록 하겠다 ~.~

책을 활용하면서 필요한 것들 

2장 프로그래밍 언어 선택

# 파이썬을 활용한 루프 구조 구현 

파이썬은 한 줄로도 루프 구현 가능

그러나 지나친 사용은 가독성을 떨어뜨릴 수 있으므로 적절하게 사용하는 것이 중요.

#파이썬(Python)

# 예시 1
sum = 0
for i in range(1, 10 + 1):
	sum += i
    
    
# 예시 2 
sum = sum(i for i in range(1, 10 + 1))


# 예시 3
sum = sum(range(1, 10 + 1))

# 제네릭 프로그래밍

파이썬은 동적 파이핑 언어로 *제네릭이 필요 없다 

(* 제네릭 : 파라미터의 타입이 나중에 지정되게 하여 재활용성을 높일 수 있는 프로그래밍 스타일)

def are_equal(a, b):
	return a == b
    
are_equal(10, 10.0)

하지만 이는 장단점이 확실하다. 사용하기에는 매우 편하지만, 코드의 복잡성이 높아질 수 있다. 

그래서 다음과 같이 타입을 명시하는 방법도 있다. 

<타입 힌트를 통해 제네릭을 사용하는 방법> 

from typing import TypeVar

T = TypeVar('T')
U = TypeVar('U')

def are_equal(a: T, b: U) -> bool:
	return a == b


are_equal(10, 10.0)

파이썬은 동적 파이핑 언어이지만, 

이렇게 타입을 명시하면 가독성이 좋아지며 버그 발생 확률을 줄일 수 있다. 

# 배열 반복

파이썬은 다른 언어에 비해 문자열 자료형이라는 선언 조자 필요가 없다.

#Python
foo = ['A', 'B', 'C']
for f in foo:
	print(f)

#Java
String[] foo = new String[]{"A", "B", "C"};
for (String f : foo) {
	System.out.println(f);
}

# 구조체

배열 : 순차적으로 메모리를 할당함.

구조체 : 메모리의 어느 영역에나 어떤 크기로든 할당할 수 있는 복합 자료형.

파이썬에는 구조체가 없을 뿐더러, 클래스 또한 데이터 타입을 지정할 수 없다. 

구조체와 같은 형태를 정의하려면 네임드 튜플을 사용해야 한다. 

from collections import namedtuple

MyStruct = namedtuple("MyStruct", "field1 field2 field3")
m = MyStruct("foo", "bar", "baz")

파이썬 3.7 부터는 dataclass 를 지원한다. @dataclass 데코레이션(자바에서는 어노테이션) 으로 

다음과 같이 class를 이용해 구조체 형태로 정의 가능하다. 

from dataclasses import dataclass

@dataclass
class Product:
    weight: int = None
    price: float = None

apple = Product()
apple.price = 10

# 클래스 

파이썬에서의 클래스는 위에 언급한 dataclass 데코레이션을 이용해 클래스를 선언한다. 

from dataclasses import dataclass

@dataclass
class Rectangle:
    width: int
    height: int
    
    def area(self):
        return self.width * self.height

rect = Rectangle(3, 4)
print(rect.area)

출처 : 파이썬 알고리즘 인터뷰 | 박상길

283. Move Zeroes : https://leetcode.com/problems/move-zeroes/

class Solution {
    fun moveZeroes(nums: IntArray): Unit {
        val arr = arrayListOf<Int>();
        val numList = arrayListOf<Int>();
        
        nums.forEach{
            when(it) {
                0 -> arr.add(it)
                else -> numList.add(it)
            }
        }

        //원본 배열에 덮어씌우기 
      
        val sorted = numList + arr
        
        nums.indices.forEach{
            nums[it] = sorted[it]
        }
        
    }
}

주어지는 배열은 수정 불가 배열

수정 가능한 배열 : arrayListOf() 와 mutableListOf() 

indices => index value of list 

977. Squares of a Sorted Array : https://leetcode.com/problems/squares-of-a-sorted-array/

class Solution {
    fun sortedSquares(nums: IntArray): IntArray {
        for(i in 0 until nums.size){
            nums[i] *= nums[i];
        }
        var arr = nums.sortedArray()
        return arr
    }
}

- 정렬 결과 배열을 반환하는 함수 : 

sortedArray() : 오름차순으로 정렬한 결과를 반환

sortedArrayDescending() : 함수는 내림차순으로 정렬한 결과를 반환

위 두 함수는 정렬 결과를 반환

- 배열에 대해 정렬만을 수행하는 함수:

sort() , sortDescending()

위 두 함수는 정렬 대상인 배열에 대하여 정렬만 함

35. Search Insert Position : https://leetcode.com/problems/search-insert-position/

이진탐색 활용

class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        var low = 0;
        var high = nums.lastIndex;
        
        while(low<=high){
            var mid = (low + high)/2;
            when{
                target == nums[mid] -> return mid
                target > nums[mid] -> low = mid + 1
                else -> high = mid - 1
            } 
        }
        return low
    }
}

704. Binary Search : https://leetcode.com/problems/binary-search/submissions/

class Solution {
    fun search(nums: IntArray, target: Int): Int {
            //nums에 특정 값 있는 지 확인
            var check = nums.contains(target) 
            if(check == true){
                var idx = nums.indexOf(target) //배열의 인덱스를 확인 
                return idx 
            }
            else{
                return -1
            }  
        }
}

코틀린 공부하기..