[Python/파이썬] 알고리즘 지엽 정리(계속 수정 및 추가)

1. input().split()을 쓰면 string 타입의 element들을 갖는 List를 얻는다.

 

2. while문에서 while문 밖에 변수랑 안에 변수가 중복되는 것 같을 때 while의 조건을 바꾸고 break를 이용하는 것도 방법이 될 수 있다.

 

3. 하나의 변수에 여러 element가 있는 list를 받으려고 할 때는 그냥 map만 쓰면 안된다. (ex. numList = map(int, input().split())) 밖에 list()로 감싸줘야한다. ( list(map(int, input().split())) ) 또는 파이썬의 컴프리헨션(comprehension)을 이용해 할 수도 있다. [int(i) for i in input().split()] 을 써서 해도된다.

(속도는 comprehension보다 list(map())방식이 더 빠른 것 같다.)

 

4. 리스트에서 (리스트 변수 이름).index(찾으려는 값) 을 이용하면 찾고자 하는 값의 인덱스를 얻을 수 있다. (ex. arr.index(max(arr)))

 

5. 리스트를 0초기화 하려면 data = [0]*100 이런식으로 해주면 된다.

 

6. 리스트에서 (리스트 변수 이름).count(찾으려는 값) 을 이용하면 찾고자 하는 값의 개수를 구할 수 있다. (ex. print(result.count(str(i))) )

 

7. 리스트에서 어떤 값이 있는지 아닌지를 알고 싶다면 if item in list: 또는 if item not in list: 를 이용해 알아낼 수 있다.

(문자열에서도 활용 가능하다. 예를 들어, if '666' in "1666":)

 

8. 리스트에서 중복되는 값을 없애고 싶다면 set() 형변환을 통해 중복값들을 없애버릴 수도 있다. (ex. arr = set(arr))

 

9. 리스트 값들(숫자)의 평균 구할 때 방법 : 1. sum() / len()     2. numpy 모듈 활용 np.mean(리스트이름)

 

10. 어떤 문자열을 input으로 받았을 때, 거기다 list() 로 형변환을 하면 문자열의 각 문자들이 element가 되어 list가 만들어진다. (ex. OOXXOXXOOO -> ['O', 'O', 'X', 'X', 'O', 'X', 'X', 'O', 'O', 'O'] )

 

11. sum() 함수를 이용할 때 리스트에 합쳐지면 안되는 값이 포함되어있다면 슬라이싱으로 제외하고 sum 할 수 있다. (ex. sum(TC[1:]))

 

12. 정수 n의 각 자리 수를 구하고 싶으면 sum( map(int, str(n)) )하면 된다.

 

13. 정수 n의 각 자리수를 쪼개 리스트로 만들고 싶다면 list( map(int, str(n)) )하면 된다.

 

14. 아스키코드 -> 문자 : chr(숫자) / 문자 -> 아스키코드 : ord(문자)

 

15. 문자열의 각 문자들을 반복해서 출력할 때 이중 for문을 사용하기보다는 하나의 for문으로 문자를 하나씩 받으며 (새로 만든 문자열) += (문자) * (반복할 횟수)로 하는 것이 더 좋다.

 

16. 주어진 문자열을 구성하는 알파벳 개수 중 최대 개수를 구하는 문제에서 for문 돌릴 때 굳이 "ABCDEFGHIJKLMNOPQRSTUVWXYZ" 을 넣고 하나씩 문자를 받아오며 .count()로 조사 하지 않고 set(입력받은 문자열)을 넣는 것도 괜찮은 방법이다.

(ex. for alp in "ABCDEFGHIJKLMNOPQRSTUVWXYZ": -> for alp in set(word):)

 

17. 파이썬에서 문자열은 변경할 수 없다. num = "437" 이런 문자열이 있을 때, num[0] = num[2] 이런식으로 조작하려고 하면 오류난다. 대신 replace함수를 써야한다. replace('바꿀문자열', '새문자열')은 문자열 안의 문자열을 다른 문자열로 바꾼다(문자열 자체는 변경하지 않으며 바뀐 결과를 반환합니다).

 

18. 문자열을 역순으로 하고 싶다면 문자열 뒤에 [::-1]  을 하면 된다.

 

19. for문으로 리스트의 element들을 꺼낼 때 인덱스도 함께 필요한 경우 파이썬의 내장함수인 enumerate()를 사용할 수 있다. (ex. for i, dial in enumerate(dials): )

 

20. 문자열에서 해당 문자열의 부분집합 중 하나인 어떤 문자열들의 개수를 세고 싶은 경우 원본 문자열의 특정 부분을 replace함수를 이용해 *과 같은 다른 문자로 치환해 len()으로 문자열의 길이를 구하면 구할 수 있다.

(ex. "ljes=njak"라는 문자열에서 ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z='] 리스트 원소에 해당하는 문자들은 묶어서 한 개의 문자로 치고 리스트 원소에 해당하지 않는 문자들도 한 개의 문자로 칠 때 "ljes=njak" 문자열의 문자 개수를 구하려면,

for chr in (리스트):
    (문자열) = (문자열).replace(chr, '*')

print(len(문자열))

와 같은 방법을 이용할 수 있다.)

 

21. 자연수 N을 2부터 N-1까지의 수들로 각각 나누어 하나라도 0으로 나누어 떨어지지 않았다면 소수이다.

 

22. 리스트는 딕셔너리의 key가 될 수 없다.

 

23. from collections import Counter 의 Counter 클래스는 데이터의 개수가 많은 순으로 정렬된 배열을 리턴하는 most_common이라는 메서드를 제공한다. (데이터와, 빈도수를 함께 담은 튜플의 형태들의 리스트를 반환한다.)

(ex.

from collections import Counter

Counter('hello world').most_common() # [('l', 3), ('o', 2), ('h', 1), ('e', 1), (' ', 1), ('w', 1), ('r', 1), ('d', 1)])

이 메서드의 인자로 숫자 k를 넘기면 가장 빈도수가 높은 k개의 데이터만 반환한다.

 

24. import sys를 한 후 sys.stdin.readline()로 input(입력)을 받아오면 뒤에 개행문자 \n가 포함된다.

(ex. 'abc\n')

 

25. sys.stdin.readline()에서 뒤에 .rstrip()를 붙이면 개행문자가 없어진다. (sys.stdin.readline().rstrip())

 

26. 리스트가 비어있을 때를 조건문에서 확인할 때는 len(리스트) == 0 이럴 필요없이 그냥 리스트 변수만 써주면 된다. 만약 리스트가 비어있으면 해당 조건문은 false가 되고 비어있지 않으면 true가 된다. (딕셔너리도 마찬가지다.)

(ex. while stack:  (이때 stack은 리스트 변수 이름이다. stack이 비어있을때까지 while문이 돈다.))

 

27. stack 자료구조 같은 경우에는 input을 받을 때 뒤에 " " <- 이렇게 공백을 추가하는 식으로 하여 어디서 문자열이 끝났는지 체크하는데 이용할 수도 있다.

(ex. sentence = input() + " ")

 

28. 공백없이 붙어있는 문자열을 (ex. "abc") 각각 쪼개 리스트로 만들고 싶은 경우 (ex. ['a', 'b', 'c']) input().split()를 쓰는게 아니라 list(input())을 해야한다.

 

29. list로 슬라이싱 하거나 insert() 메소드를 사용하는 것 보다 문자열 자체를 직접 슬라이싱하고 합치는 방법이 더 빠르다.

 

30. for문 안쓰고 리스트에 있는 값들을 붙여서 출력하고 싶을 때 print("".join(리스트))하면 된다.

 

31. 파이썬의 deque은 from collections import deque로 내장함수 deque을 이용할 수 있다.

만약 직접 구현하는 경우 stack 두개로 구현하면 낮은 시간복잡도로 구현할 수 있다.

 

32. 파이썬에서 queue 자료구조를 사용해야 할 경우 deque를 이용하는게 시간복잡도 면에서 리스트보다 낫다.

(deque는 from collections import deque 를 해준 뒤, queue = deque() 해주면 사용할 수 있다.)

(넣을때는 .append(), 뺄때는 .popleft()를 사용하는 것이 관행이다.)

 

33. DFS는 구현시 Stack 자료구조를 활용하고 BFS는 구현시 Queue 자료구조를 활용한다.

(DFS 구현의 경우 Stack은 재귀함수로 표현이 가능하므로 주로 재귀함수를 통해 구현한다.)

 

34. 파이썬에서 리스트를 복사하는 경우 그냥 list2 = list1 하면 안된다. 이렇게하면 둘이 가리키는 주소가 같아져 list2를 조작하면 list1도 바뀐다. 따라서 서로 다른 주소를 가리키게 해야한다. 그러려면 list2 = list(list1) 해주면 된다.

 

35. DFS 문제의 경우 대부분 스택과 재귀를 이용하여 문제를 풀 수 있으며, BFS의 경우 큐를 이용하여 풀면 되기에 deque 모듈을 사용하여 풀면 좋다.

 

36. 시간제한을 보면 X초 이런식으로 되어있는데 1초에 2억까지 계산할 수 있다. 따라서 시간복잡도 계산했을 때 2억보다 적게 나오면 가능한 것이다.

 

37. 1e10은 10의 10승을 뜻한다. 10의 10승에 1을 곱한 것이다. e는 10^n을 의미하며 n은 e뒤에 붙는 숫자에 따라 달라진다. 예를 들어 2e6의 경우 2 * 10^6 인 것이다.

 

38. 재귀를 이용해서 풀 때는 sys.setrecursionlimit(10 ** 6) 꼭 해주기!! 파이썬에는 기본적으로 재귀 깊이 제한이 있는데 이걸로 풀어줄 수 있다. 재귀 깊이 제한 늘려서 런타임에러 없애기용이다.
(다만, 너무 크게해주면 메모리 초과날수도 있다. N-Queen 문제에서 10 ** 6 으로 했다가 메모리 초과났다. 10 ** 4로 바꾸자 해결됐다.)

 

39. DP문제 풀 때 어떻게 할 지 모르겠으면 하나씩 그려보면서 규칙을 찾자. 점화식을 명확히 세우고 코드를 짜야한다.

 

40. DP문제 풀 때 (특히 Bottom-Up 방식으로 풀 때) 초기 DP의 memoization 리스트 초기화할 때 입력받은 N에 대해서 dp = [0] * (N + 1) 와 같이 초기화하면 런타임에러가 발생하는 경우가 잦다.

문제에서 N이 1<=N<=100과 같이 주어졌다면 그냥 dp = [0] * 101으로 초기화해주면 런타임에러가 나지 않는다.