성공을 즐기자

알았는데요 , 1년동안 안쓰니까 잊어먹었습니다. 이래서 기록이 중요합니다. Permutation은 파이썬에서 제공해주는 함수이다. (itertools에 있음) 순열이라는 뜻으로 학교다닐 때 배우던 순열과 동일한 뜻이다. 고3 확률과통계를 더 열심히 들었어야하는건데 ... => 서로 다른 N 개중에 r개를 고른다!! nPr 로 표시한다. from itertools import permutations arr = ['1','2','3'] npr = permutations(arr,2) print(list(npr)) 이렇게 하면 1,2,3 중에서 2개를 고르는것이다. [1,2 1,3 2,1 2,3 3,1 3,2 ] 가 나올것같다. 출력의 결과는 다음과 같다. [('1', '2'), ('1', '3'), ('2',..

다익스트라는 그리디와 DP의 유형으로 분류되는 최단경로 알고리즘이다. DP는 계속해서 그래프를 갱신하기 때문이고 그리디는 그 순간 가장 짧은 정점을 선택하기 때문이다. 음의 가중치가 적용될 수 없어 일상생활 문제에서 잘 사용될 수 있다. 특정한 한 노드에서 다른 모든 노드로 가는 최단 경로를 찾는 알고리즘이다. 원래는 O(V^2)의 시간복잡도를 가진다. ( 리스트 이용, 돌면서 가장 거리가 짧은 노드를 찾는 경우) 이것은 5,000개 까지는 괜찮지만 개수가 10,000개가 되면 시간초과가 될 가능성이 농후하다. (파이썬은 1초에 2천만 연산이라고 생각하면 됨) 시간초과를 막기 위해서 heap을 이용하면 된다. (방문하지 않은 최단거리의 정점을 찾을 때 이용) 파이썬의 minheap은 heappop을 하면..

Big - O는 알고리즘 성능을 예측한다. 작은 차수는 무시하고 계수도 무시한다. 이진탐색 : O(logn) 재귀 : O(2^n) 정렬 : O(nlogn) heap : - 생성 : nlogn - push, pop : log(n) 여기서 궁금했던 것은 왜 재귀가 2^n 인지이다. 재귀 중 피보나치를 생각했을 때 이렇게 생각하면 된다. T(n) > 2 * T(n-2) T(n) > 2^2 * T(n-4) ... T(0)이 되면 T(n) > 2^(n/2) * T(0) 이다. T(0)은 계수가 되어 의미가 없어지고 1/2도 의미가 없어진다. 즉 재귀의 시간복잡도는 O(2^n)이 된다.

유니온 파인드 : 노드를 UNION하고 부모를 FIND해서 서로소 집합을 찾아내는 알고리즘 UNION연산은 두 원소를 뽑아 원소가 포함된 집합의 부모노드를 비교한다. 만약 다르다면 같은 부모를 가리키도록 만든다. FIND 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 부모노드를 찾아 반환하게 만들면 전부 돌면서 찾아야하는 수가 있다. (시간이 너무 오래걸릴수도) 그래서 일일이 거슬러 부모노드를 찾는 것보다 한번에 빠르게 부모 노드에 갈 수 있도록 하는 경로 압축기법을 사용하면 빠르다. 코드 : def union(a,b) : a = find(a) b = find(b) if a > b : parent[a] = b elif a ..

저학년 때, xor, or , and 와 같은 이진수를 조작하는 연산을 배운적이 있다. 이를 알고리즘 문제를 푸는데 이용하여 수행시간을 빠르고 코드를 짧게 하여 푸는 문제들이 있다. 바로 비트마스킹 문제다!! 언젠가 공부해야지 해야지 했는데 이제야 한다. 1. AND ; 둘 다 1인 경우만 1이 된다. ("&") 2. OR ; 둘 중 하나라도 1이면 1이 된다. ("|") 3. XOR ; 두개가 달라야 (1,0 또는 0,1) 1이 된다. ("^") 4. NOT ; 0은 1으로, 1은 0이 된다. ("~") 5. shift ; 비트를 왼쪽 혹은 오른쪽으로 움직여 빈자리는 0으로 채운다. ("") 전부 1인 배열 만들기 : ( 1

알고리즘을 풀다보면 이차원 배열을 뒤집어야하는 문제가 가끔 나온다. 그럴때마다 그때 그때 이해해서 적었지만 이것을 정리하고 싶어서 글을 쓴다. 1. " * " python에서 아스트리크(*)은 unpack역할을 한다. 첫줄은 이차원 배열 , 두번째 줄은 이차원 배열에서 *를 한 결과이다. 첫줄은 각 리스트들이 하나의 리스트로 연결되어있지만 두번째 줄은 리스트들이 unpack된것을 확인할 수 있다. 2. zip() zip은 iterable한 것들을 엮어준다. 지퍼를 올리는 것처럼 양측의 데이터를 짝을 지어준다. 아스트리크(*)와 zip을 함께 사용하면? 무슨 일이 일어날까? a = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] print(zip(*a)) print(list(zip(*a)))..

중복(허용) 순열 : def dfs(L) : if L == m : for i in range(m) : print(mp[i],end = "") print() else : for i in range(1,n+1) : mp[L] = i dfs(L+1) if __name__=="__main__" : n,m = map(int,input().split()) check = [0]*(n+1) mp = [0]*m dfs(0) 3 2을 입력할 시 이렇게 출력된다. 중복을 허용하여 1~3까지의 수 중 2자리수가 나오는 것이다. 순열 : def dfs(L) : if L == m : for i in range(m) : print(mp[i],end = "") print() else : for i in range(1,n+1) : i..

N개중에서 r개를 뽑는 경우를 어떻게 구할까? 바로 조합을 이용하면 구할 수 있다. 조합은 중복을 허락하지않고 순서를 생각하지 않는다. n = 4, m = 2 아래 사진이 4까지의 숫자에서 2자리 수를 출력하는 코드의 상태트리이다. D(0,1)에서 처음 시작한다. 0은 level을 1은 start를 의미한다. 출력할 숫자를 담을 배열을 res라고 하자 (크기는 m 만큼이다.) 두번째 인수(start)보다 크거나 같은 수를 res 배열의 level 자리수에 넣어가며 for문을 돌린다. 즉, 위와 같은 경우 res는 0,1 index만 존재하기 때문에 level이 2가 종료 조건이다. 첫번째 인수는 Level이므로 한단계씩 진행됨에 따라 1씩 증가시킨다. 두번재 인수는 res에 들어간 수에서 1을 증가시켜 ..

백트래킹은 경우의 수 중에서 유망하지 않은 것을 거르는 방법으로 이것을 구현한는 방법은 다양하며 BFS, DFS등으로 구현할 수 있다. https://what-am-i.tistory.com/286?category=966524 [삼성SW역량][Python/BOJ] 백준 14889 스타트와 링크(DFS, 백트레킹) https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.ne.. what-am-i.tistory.com 여기 이 스타트와 링크문제의 풀이는 백트래킹 구현을 위해 DFS를 ..

heap 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조! MAX heap 과 MIN heap이 있다. MAX heap은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다. MIN heap은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리를 의미한다. 파이썬에서 heap을 구현하려면 ? heapq 모듈을 import 하면 된다. heapq 모듈은 리스트를 최소 힙처럼 사용할 수 있게 도와준다. import heapq heap = [] heapq.heappush(heap,4) heqpq.heappop(heap) heapify를 이용하면 리스트를 힙으로 만들 수 있다. heapq.heapify(heap) 참고 블로그 : https://www..