본문 바로가기

Dev/coding

그리디 그리디 탐욕 알고리즘은 이후의 선택이 가져오는 이익을 내다보지 않고, 현재 당면한 상황에서 가장 최적의 선택을 한다. 그렇기 때문에 그리디 알고리즘으로는 최적의 해를 구하지 못하는 경우도 있다. Prim Prim,Kruskal, Dijkstra 더보기
백트래킹 백트래킹 N-Queen 문제 ==CSP(Constrain satisfaction problems)문제 Backtracking은 CSP를 해결 하는 방법론! 개념! 왜냐하면 조건이 만족하는 경우라는 조건이 있기 때문이다. 응용 사례: 조합의 숫자를 셀 때, 어떠한 조건들을 가지고 있다면, 모든 조합이 아닌 특정조건에 한정해서 조합을 카운트 할 수 있다. 검색 성능은 향상된다. 트리상황을 예를 들면, DFS나 BFS 할때마다 invalid()해서 원하는걸 체크하는데 이게 은근히(매우) 중요하다는 것 일반적으로 백트래킹 구현 방법은 DFS,BFS 가 있다. DFS(깊이 우선탐색)을 통하여 구현하는데 BFS(넓이 우선탐색)의 경우 상대적으로 많은 메모리가 필요하기 때문이다. 다 가지고 있어야하니깐 시작부터.. 더보기
동적계획법 회사에서 심심할 때 보는 컴싸 동적계획법 알고리즘 설계 기법 알고리즘 패러다임(사고의 틀, 체계, 분류, 방법론): 동적계획법, 그리디, 백트래킹, 정렬 구현 알고리즘: Djikstra, DFS, Breadth First Search, BFS, 최선 우선 탐색(Best First Search/Heuristic Search), Prim Kruskal, Dijkstra, Juffman coding n 동적계획법(DP) 답을 구하고 재활용하는 것, 재귀생각하면 됨 f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 ) f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1 이럴 때 그냥 계산시(재귀겠져) 5번, 동적계획법쓰면 4번 이 차이는 갈수록 커짐 (a,b) .. 더보기
[python] python searching string within list import re li = ['df 1','as 3'] regex=re.compile("(df).*") for l in li: for m in [regex.search(l)]: if m: print(m.group(0)) 더보기
[python] **dictionary 1. 함수에서 매개변수로 쓰는경우: 키워드인자모으기 def print_kwargs(**kargs): print(kwargs) 라고 정의했을때 print_kwargs(wine='좋은와인', dessert='마카롱') 결과는 {'dessert:마카롱', 'wine':'좋은와인'} 이런식으로 딕셔너리가 형성됨 2. 인자에 **dictionary를 쓰는 경우 def foo(x, y): print(x, y) >>> d = {'x':1, 'y':2} >>> foo(**d) 1 2 딕셔너리를 넘기면 알아서 인스턴스변수에 분배됨 destructuring 후 collecting keyword argument 된거지 더보기
[python] string format Why is %s better than + for concatenation? hello = "hello" world = "world" print hello + " " + world print "%s %s" % (hello, world) print "{} {}".format(hello, world) print ' '.join([hello, world]) Readability. The format string syntax is more readable, as it separates style from the data. Also, in Python, %s syntax will automatically coerce any non str types to str; while concatenation only wor.. 더보기
[python] 파이썬 인스턴스 변수와 클래스 변수 공부하다가 파이썬은 클래스 속성값에 대해서 프로퍼티 데커레이터 이용해서 프로퍼티 맹글링해서 의도적인 직접접근 방지 그래서 파이써닉한거는 속성을 안써주는a건줄알았는데.. 애초에 클래스 변수와 인스턴스 변수가 있었음 >>> class Account: num_accounts = 0 def __init__(self, name): self.name = name Account.num_accounts += 1 def __del__(self): Account.num_accounts -= 1 >>> class Account: num_accounts = 0 def __init__(self, name): self.name = name Account.num_accounts += 1 def __del__(self): Accou.. 더보기
[python] range() return value Python range() The range() constructor returns an immutable sequence object of integers between the given start integer to the stop integer. range() constructor has two forms of definition: range(stop) range(start, stop[, step]) 더보기