[코테 정리]

0 . 시간 복잡도

입력 범위	시간 복잡도	알고리즘
500	N^3	3중 for, 플루이드
2,000	N^2	2중 for
100,000(10만)	N log N	이때부터 2중 for쓰면 안됨.
20,000,000(2천만)	N
100만	logN	이분탐색

- format 출력 :print( "구구단 {0} * {1}  = {2} ".format( a, b, a*b) # 0,1,2는 인덱스

• in 시간복잡도는 자료형에 따라 다름 -> 리스트말고 dictionary나 set이 더 짧음
•  if arr in set자료형 "하면 set 집합 안에 리스트 값들이 전부 들어가 있는지를 한번에 확인할 수 있다.
•  

0-2. 구현

- DP배열에 초기값 넣을 때 항상 조심하자!!! 초기값은 보통 고정값으로 넣기 때문에 런타임에러가 발생할 수 있다 입력값의 범위 잘 고려하자!!!

- upper(), lower(), isupper(), islower() 
- 특정 위치의 index만 대문자로 바꾸고 싶을때 : s[0].upper() + s[1:]
- title() : 문자열의 첫 문자를 대문자로 변경 + 맨 앞이 알파벳이 아니면 그 다음 알파벳을 대문자로 처리 + 문자열이 여러 문자로 이루어졌을 때, 모든 문자들에 대해 첫글자 대문자로 변경 
- capitalize() : 문자열 첫문자를 대문자로 변경 + 맨 앞이 알파벳 아니면 대문자 처리 안함 + 문자열이 여러 문자로 이루어졌을 때 가장 첫 문자에만 변경
- join함수 : '구분자'.join(리스트) 
- split(" ")으로 분명하게 나눠주는 연습하기!!

 

 

1. 리스트 

- 배열이 있는지 확인 

  # if a in arr:

  # arr.find(a) : 없으면 -1

  # arr.index(a) : 없으면 error 

 

- 리스트 값 삭제하기

  # del arr[index] (인덱스 삭제)

  # arr.pop(index) ( 인덱스 삭제)

  # arr.remove(value) (값 삭제)

- 2차원 리스트 내의 최솟값 : min_value = min( [min(row) for row in board] )

- 두 리스트를 비교해서 차집합 구하는 법  (array = 2차원 list ) : list( set (arrayA) - set(arrayB) ) .차집합의 값이 하나더라도 list로 바꾼 후 int로 변환하기

 

- 배열 -> 리스트

  # ''.join(arr)

 

2.정렬

- 파이썬의 set은 자동정렬이 안된다!!! 

- 정렬된 인풋 받기 : arr =sorted(list(int(input()) for _ in range(N))

- 내림차순 정렬 : arr.sort( reverse = True)

- key값 기준 정렬 :

str_list = ['좋은하루','good_morning','굿모닝','niceday']
>>> print(sorted(str_list, key=len))  # 함수

>>> print(sorted(str_list, key=lambda x : x[1]))  # 람다
['niceday', 'good_morning', '굿모닝', '좋은하루']


>>> tuple_list = [('좋은하루', 0),
    	          ('niceday', 1), 
    	          ('좋은하루', 5), 
    	          ('good_morning', 3), 
    	          ('niceday',5)]
                  
>>> tuple_list.sort(key=lambda x : (x[0], x[1]))  # '-'부호를 이용해서 역순으로 가능
[('good_morning', 3), ('niceday', 1), ('niceday', 5), ('좋은하루', 0), ('좋은하루', 5)]

 

 

3. 이분탐색 ( 이진탐색 )

- 최댓값 / 최솟값 개념이 있다 + 좌표? 리스트의 값들이 정렬되어 있으면 좋고 아니어도 상관 X

- 입력 데이터가 2000만을 넘어가면 이진 탐색으로 접근 O(logN)

##while문 
while left <= right:
	mid = int((left+ right) // 2)
    if arr[mid] ==  target:
    	print(mid)
        break
    elif arr[mid] > target:
    	right = mid -1
    else:
    	left = mid + 1 
    
 # 재귀 
 def binary search( arr, target,left,right):
 	mid_idx = ( left+ right ) // 2
    mid_val = arr[mid_val]
    if target == mid_val:
    	print(mid_idx)
    elif mid_val > target:
    	binary_search(arr,target,left,mid-1)
    else:
    	binary_seacrh(arr,target,mid+1,right)

- 내장 모듈  사용 가능 : from bisect

 # bisect_left(리스트 value) : 왼쪽 인덱스를 구하기 (value 이하 값 중 최댓값의 인덱스!!!)

 # bisect_right(리스트, value) : 오른쪽 인덱스를 구하기 (value초과 값 중 최솟값의 인덱스!!! )

 

 

4. 최단거리- 다익스트라 ( 그리디) 

# 특정 노드 -> 다른 모든 노드를 가는 최단 경로를 구함

# 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택해감 

# '음의 간선'이 없을 때 사용 가능 

# visited !!! distance!!!! 큐엔 (해당 노드까지 최단경로, 노드번호) 쌍으로 입력!!!!

 

5. 플루이드 워셜 (그리디)

# 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 경우 

# 2차원 리스트에 최단 거리 정보 저장

# 2차원 배열로 저장!!! graph[a][b] = 비용 저장 

# 유의사항!!!! K가 가장 바깥쪽 for문에 있음!!!!!!!!! 

#  DISab : a를 거쳐 b로 가는 최단 거리

   * 노드의 개수가 작은 경우, 인접행렬을 사용해서 플로이드 워셜 사용

   * 노드의 개수가 많은 경우, 우선순위 큐를 사용해서 다익스트라 사용 

 

 

6. Union - find( 서로소 집합)

# parent배열 초기값은 자기자신

# 집합 구하려면 find( parent, i) 로 출력 

# 간선으로 이어진 두 노드의 루트 노드를 확인하여, 루트 노드가 서로 같다면 사이클이 발생할 것

 

7. 순열 조합 

- from itertools 필요

- permutations( 배열이름, 원소 개수) : 순열

- product (배열 이름, 원소 개수) : 중복 순열

- combinations(배열이름, 원소 개수) : 조합

- combinations_with_replacement(배열이름, 개수) : 중복 조합

 

 

8. DFS/BFS

 

9. 그 외

- 괄호 / 쌍 관련 문제

- n쌍의 괄호로 만들 수 있는 다른 괄호의 갯수를 구하는 문제, 정사각형으로 이루어진 평면에서 최저경로로 목적지에 가는 경우의 수를 묻는 문제 

->구하고자 하는 쌍이 n개이고, 총 경우의 수를 x라고 할 때