Tips

Few tips for each types

Every programming is about treating data. Therefore, understanding of data type is crucial for all the developers.

Int

String

Bool

List [a, b, c]

튜블 (a, b, c)

딕셔너리 {a : 1, b : 2, c : 3 }

set {a, b, c}

Input / Output

Using eval

Using lambda

Using Map

Using Filter

def ft(arr): result = [] for e in arr: if e > 0: result.append(e) return result

def positive(x): return x > 0

list(filter(positive, arr)) list(filter(lambda x: x > 0, arr)) # filter + lambda


## Using zip

- Grouping column in 2d array

``` python
list(zip([1, 2, 3], [4, 5, 6])) # [(1, 4), (2, 5), (3, 6)]
list(zip([1, 2, 3], [4, 5, 6], [7, 8, 9])) # [(1, 4, 7), (2, 5, 8), (3, 6, 9)
list(zip("abc", "def")) # [('a', 'd'), ('b', 'e'), ('c', 'f')]

매개변수 이해와 구조화

  1. 함수의 이름과 역할
  2. 함수의 매개변수

    함수 정의시 위에 주석으로 함수 역할과 인자 설명 써두면 좋음

      # moneySum: 돈의 합 출력
  # N: 사람수, moneyArr: 사람의 돈
  def moneySum(N, moneyArr):
   ret = 0
   return ret

  1. 컨테이너의 역할

    • 자료형에 따른 본인만의 컨테이너 설정과 이해
      • Tuple: 위치에 따른 의미
      • Set: 포함여부 의미
      • List: index와 원소의 관계
      • dp[i][j] : #i 번째 사람이 j 개를 먹는 가지수
      • Dict: key 와 value 의 관계

  2. 컨테이너의 분할

     A = [[0 for i in range(2)] for j in range(100)] # 1번째 값은 순서, 2번째값은 A[i][0], A[i][1]

    위처럼 한번에 하는거보다 A[1000], V[1000] 같이 나눠서 하는게 가독성을 높일 수 있음. 그때그때 편한대로 사용.

  1. 논리/비트 연산자 활용

     a, b = 10, 20
 if a > b:
   if a % 10 == 0:
     print(a)

    4개 이하의 조건이면 중복,반복 제거: 조건 and 사용

       a, b = 10, 20
   if a > b and a % 10 == 0:
     print(a)

    비트 연산자

     a << b
 a & b
 a | b
 a ^ b

  2. 상태를 나타내는 자료 활용하기 check = False 같은 조건 활용

  3. 나눠서 진행: 조건 판별을 다른 함수로 만들어버리는것도 좋음

     def isPrime(N):
 for i in range(2, N):
     if N % i == 0:
         return False
     return True

 for N in range(10, 100):
     if isPrime(N):
         print(“{} if Prime”.format(N))
     else:
         print(“not prime”)

    ex) dfs/bfs: 조건을 반복문이 아닌 함수로 만들면 코드가 더 간결함

    def isRange(a, b, N, M):
      return 0 <= a < N and 0 <= b < M

  1. 여러 자료구조나 메서, 함수 활용

     S = 'hello'
 for i in S:
     if S[i] != S[len(S)-i-1]:
         print("not palin")

     S = 'jello'
 # reversing S
 if S == S[::-1]:
     print("not palin")

  2. 미리 처리한 케이스와 처리할 케이스 주석으로 정리

     # 1. 예제 케이스
 # 2. 조건 A
 # 3. 조건 B
 # 4. 조건 AB
    • 체크가 필요할땐 체크하는 함수를 따로 틀 짜놓고 시작하면 굳 
      def check(x):
    pass

  3. 예제, 최소, 최대, 예외, 랜덤 케이스 만들기

Sort

Implement

탐색

DFS 주의사항

  1. import sys sys.setrecursion0limit(10000) 꼭 추가. 없으면 RE 발생할수있음

  2. 지도와 visited 는 global 선언

Graph representation

2 ways to present graph

     [0]
    /   |
   7     5
  /       |
[1]       [2]
  0 1 2
0 0 7 5
1 7 0 inf
2 5 inf 0 
INF = 999999999

graph = [
  [0, 7, 5],
  [7, 0, INF],
  [5, INF, 0]
]

print(graph) # [[0, 7, 5], [7, 0, 99999999], [5, 99999999, 0]]
print(graph[1][2]) # Faster speed

[0] -> [1(7)] -> [2(5)]
[1] -> [0(7)]
[2] -> [0(5)]

graph = [[] for _ in range(3)]

graph[0].append((1, 7))
graph[0].append((2, 5))

graph[1].append((0, 7))
graph[2].append((0, 5))

print(graph) # [[(1.7), (2.5)], [(0,7)], [(0,5)]]
# need iteration to find info1

그리디

힙

import heapq
heapq.heapify(arr)
a = heapq.heappush(arr, i)
b = heapq.heappush(arr)

집합

def union(x, y): x, y = find(x), find(y) parent[y] = x # 설정 방법은 문제 따라 다름 # number[x] += number[y] # 네트워크 크기 알고싶을 때

parent = [i for i in range(5)] union(1,4) union(2,4) for I in range(1, len(parent)): print(find(i), end=’ ‘)


- 프린터 q: 튜플, enum, lambda 활용

#### itertools 자주 쓰이는것들


| 예 | 결과 |
|---|:---|
product('ABCD', repeat=2) <br>모든거<br>n^r개 | AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD |
permutations('ABCD', r) <br>prod에서 자기자신 뺀거<br> nPr = n!/(n-r)! 개 | AB AC AD BA BC BD CA CB CD DA DB DC |
combinations('ABCD', r) <br>순서 노상관, 중복없음<br> nCr = n!/((n-r)!r!) 개 | AB AC AD BC BD CD |
combinations_with_replacement('ABCD', r) <br>comb 에서 자신 포함<br> (n+r-1)!/(r!(n-1)!) 개 | AA AB AC AD BB BC BD CC CD DD |

| 이터레이터 | 인자 | 결과 | 예 |
|---|---|---|---|
accumulate() | p [,func] | p0, p0+p1, p0+p1+p2, … | accumulate([1,2,3,4,5]) --> 1 3 6 10 15 |
chain() | p, q, … | p0, p1, … plast, q0, q1, … | chain('ABC', 'DEF') --> A B C D E F |
chain.from_iterable() | iterable | p0, p1, … plast, q0, q1, … | chain.from_iterable(['ABC', 'DEF']) --> A B C D E F |
compress() | data, selectors | (d[0] if s[0]), (d[1] if s[1]), … | compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F|

Reference: https://docs.python.org/ko/3/library/itertools.html

#### collections.Counter

- iterable 원소의 등장 횟수 세어줌
  ``` python
  from collections import Counter

  counter = Counter(['r', 'b', 'r', 'g', 'b'])
  print(counter['b']) # 2
  print(counter['g']) # 1
  print(dict(counter)) # {'r':2, 'b':2, 'g':1}

bisect

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 9]
x = 4
print(bisect_left(a,x)) # 2
print(bisect_right(a,x)) # 4

def count_by_range(a, l, r): right_i = bisect_right(a, r) left_i = bisect_left(a, l) return right_i - left_i

a = [1, 2, 3, 3, 3, 3, 4, 4, 7, 8] print(count_by_range(a,4, 4)) # 2 print(count_by_range(a,-1, 3)) # 6 ```

그 외 정리

  Def 특이점
BUB for 0 to j-i-1, swap j, j+1 if j > j+1 if swap == 0: break
SEL for i+1 to len - 1, search smallest, swap smallest, i  
INS from i + 1 to 0, swap j, j-1 if j < j-1 until j >= j-1 if j >= j-1: break
     
Recursive call base case+ recursive case act like stack
Every recursion can be expressed w/ while loop
DP start solving from smallest prob, use its solution (saved for Memorization) for larger prob, therefore solve whole (going up) small prob duplicate –> memoization
ex) fibo
D&C divide prob until it cannot divide and conquer by merging together (going down) small prob no duplicate use recursive call
ex) QCK, MER
     
QCK set pivot, sort left, right  
MER 1. divde data by half until len == 1
2. recursively merge		  
     
Graph Node/Vertex + Edge  
  Degree: # connected nodes in undirected  
  In-Degree: # incoming edges in directed  
  Out-Degree: # outgoing edges in directed  
  Path Length: # edges for path  
  Simple path: startfinish path w/o node duplication  
  Cycle: start == finish  
  Acyclic graph: don’t have any cycle in undirected  
  Complete graph: Every single node is connected to each other in undirected  
Undirected graph A—B : (A, B), (B, A)  
  Connected Graph: Every node has path  
  Disconnected Graph: Certain node does not have path  
Directed graph A->B : <A, B>
B->A : <B, A>		  
Weighted graph / Network Edge has weight  
BFS search same level first  
DFS search child node first