𝕕𝕖𝕧𝕖𝕝𝕠𝕡 𝕣𝕖𝕔𝕠𝕣𝕕

순열(permutation) - 순서를 고려한 선택 - nPr로 표시 import imertools arr = ['A', 'B', 'C'] perm = itertools.permutations(arr, 2) # 2개 선택 print(list(perm)) # [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')] 조합(combination) - 순서를 고려하지 않은 선택 - nCr로 표시 import itertools arr = ['A', 'B', 'C'] combi = itertools.combinations(arr, 2) print(list(combi)) # [('A', 'B'), ('A', 'C'), ('B', 'C')]

bisect - bisect : 파이썬에서 이진탐색을 쉽게 구현하기 위해 제공하는 라이브러리이다. - 정렬된 배열에서 특정한 원소를 찾아야할 때 자주 사용된다. - bisect_left(), bisect_right() 함수가 가장 중요하게 사용된다. bisect_left, bisect_right - bisect_left(list, n) : 정렬된 순서를 유지하며 리스트 list에 데이터 n을 삽입할 가장 왼쪽 인덱스를 찾는다. - bisect_right(list, n) : 정렬된 순서를 유지하며 리스트 list에 데이터 n을 삽입할 가장 오른쪽 인덱스를 찾는다. - bisect_left(list, n, lo = 0, hi = len(list)) : lo와 hi는 고려할 리스트의 부분집합을 지정하는 데 사..

BFS란? - 큐를 통해 구현이 가능하다. - 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 큐에 넣고, 큐어 들어있던 노드부터 방문한다. - 파이썬에서 큐를 구현할 때, list를 사용하는 경우가 대부분인데. list.pop(0)은 시간복잡도가 O(N)이기 때문에 이렇게 구현할 경우 시간적으로 비효율적이다. 따라서 collections 라이브러리의 deque를 사용하면 시간을 절약할 수 있다. - 또한 인접한 노드 중 방문하지 않았던 노드를 큐에 넣을 때는 set 데이터 타입을 이용하면 쉽게 구현할 수 있다. 타이틀 입력부분2 BFS 구현 - 동작 과정 1) root 노드부터 시작하기 위해 deque에 root를 넣는다. 2) 큐가 빌 떄까지 loop를 돌린다. 3) 큐의 맨앞 노드를..

DFS란? - 그래프 탐색 알고리즘 - 갈 수 있는 끝까지 탐색해 리프 노드를 방문하고, 이전 갈림길에서 선택하지 않았던 노드를 방문하는 탐색 방법 - 스택으로 구현이 가능하다. 스택 대신 재귀함수를 사용해서 구현하는 경우도 많다. 재귀함수 사용 시 종료 조건을 반드시 명시해야 한다. DFS 구현 - 동작 과정 1) 탐색 시작 노드를 스택에 삽입 후 방문처리 한다. 2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 존재하면 그 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3) 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다. def dfs(graph, start): vist = list() stack = list() stack.a..

버블정렬 - 이웃한 두 값을 비교해 정렬하는 방법이다. - 모든 원소를 하나하나 비교하여 swap하는 작업을 반복한다. - 구현이 단순하다. - 최대 O(n^2)의 시간복잡도를 가진다. # 버블정렬 a = random.sample(range(1, 10), 5) print("=== bubble ===") print(a) # 정렬 전 n = len(a) for i in range(n - 1): for j in range(n - 1 - i): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] print(a) 삽입정렬 - 현재 위치에서, 이미 정렬된 이전 배열들의 데이터를 차례대로 비교하여 자신의 위치를 찾아 그 위치에 삽입한다. - 최악의 경우 O(n^2), 최선의 ..

튜플 선언 - 한 번 정해진 순서를 바꿀 수 없다. - 선언 tuple1 = {1, 2, 3, 4} tuple2 = 1, 2, 3, 4 mylist = [1, 2, 3, 4] tuple3 = tuple(mylist) - 튜플은 값의 변경과 삭제가 불가능하다. packing, unpacking - packing : 하나의 변수에 여러 개의 값을 넣는 것 - unpacking : 패킹된 변수에서 여러 개의 값을 꺼내오는 것 c = (3, 4) d, e = c # c의 값을 언패킹하여 d, e에 값을 넣음 f = d, e # d, e값을 f에 패킹 - 튜플의 두 변수 값을 바꿀 때 임시 변수가 필요없다. - 함수의 리턴 값으로 여러 값을 전달할 수 있다. 튜플을 이용한 함수의 리턴값 - 튜플 리스트 list ..

딕셔너리 - 여러 값을 저장해 두고 필요한 값을 꺼내 쓰는 기능 - 이름표를 이용해 값을 꺼내 사용 이름표에는 문자열과 숫자형, 튜플을 사용, 값으로는 어떤 자료형이든 가능 - 리스트와 비슷한 방식 user = { '철수' : 'cheol', '영희' : 'young', '영수' : 'soo' } print(user['철수']) 딕셔너리 수정 - 추가, 수정 dict['three'] = 3 - 삭제 del(dict['one']) dict.remove('two') - 딕셔너리를 합치기 dict1 = {1 : 100, 2 : 200} dict2 = {1 : 1000, 3 : 300} dict1.update(dict2) # {1 : 1000, 2 : 200, 3 : 300} 딕셔너리와 반복문 - 경우에 따라 ..

리스트 관련 메소드 - list1 = [1, 2, 3]일 때 append를 이용해 뒤에 리스트 요소를 추가할 수 있다. list1.append(4) 뒤에 새로운 리스트를 더하는 방법은 다음과 같다. list2 = list1 + [4] - in 연산을 이용해 리스트에 값이 들어있는지 확인할 수 있다. n = 12 # 리스트에 있는지 확인할 값 if n in list1: print('{}가 리스트에 존재.'.format(n)) - 리스트에서 필요없는 값을 지우는 방법 del list[10] # 10번째 값 지우기 list1.remove(4) # 4라는 값이 있는 경우 삭제, 여러 개일 경우 가장 앞 하나만 지워짐 enumerate - 리스트가 있는 경우 순서와 리스트 값을 전달하는 기능 names = ['가..

알고리즘을 다시 시작하며 ,, 요즘 많은 기업에서 코딩 테스트는 필수가 된 것 같다. 이전에 C++로 알고리즘을 했었는데 카카오, 네이버와 같은 기업을 Java를 많이 사용한다. 그에 따라 알고리즘을 Java로 할까 하다가,, 알고리즘을 Java로 하기엔 좀 어려운 감이 있을 것 같다. 그래서 Python으로 알고리즘을 하기로 결정했다. Python 공부 시작 대학교 때 비전공자를 대상으로 파이썬을 가르친 적이 있었는데, 너무 오래돼서 다 까먹은 것 같다. 많은 무료 강의가 있어 그중 하나를 선택해 우선 기초를 공부하기로 했다. 2~3일 동안 파이썬 공부를 하고, 알고리즘 문제를 풀 예정이다. 파이썬 기초를 공부할 사이트 https://programmers.co.kr/learn/courses/2 파이썬 ..