MakerHyeon

동적 계획법 Dynamic Programming - 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 걸 반복 - 분할정복과 비슷한 느낌 DP 구현 2가지 ● Top-down : 구현은 재귀, 저장방식은 Memoization ● Bottom-up : 구현은 반복문, 저장방식은 Tabulation 한 번 구한 답들은 저장해두자 Memoization ● 부분 문제들의 답을 한 번 구했으면 또 구하지 않도록 (중복연산 방지) cache에 저장해두고 다음부턴 갖다 쓰자. ● 메모라이제이션이 아니다. 메모이제이션이다. ● 필요한 부분 문제들만 구한다 Lazy-Evaluation ● Top-down 방식에서 사용 쉽게 말하면, 1+1+1+1+1+1+1+1은 뭐냐고물어보고 아이는 7이라고 답..

파라메트릭 서치 ● 최적화 문제를 결정 문제로 바꿔서 이진탐색으로 푸는 방법 ● 매개변수 Parameter가 주어지면 true or false가 결정되어야 한다. ● 가능한 해의 영역이 연속적이어야 한다. ● 범위를 반씩 줄여가면서 가운데 값이 true 인지 false 인지 구한다. ● 이진탐색과 똑같은 원리 최적화문제 Optimazation Problem - 문제 상황을 만족하는 변수의 최솟값, 최댓값을 구하는 문제 결정 문제 Decision Problem - Yes/No Problem Q(파라메트릭 서치 예시). 큔콴이 대학생들의 외모값과 커플/솔로 여부가 주어진다.커플들은 솔로들보다 외모값이 높다.(^^) 외모값이 최소 몇 이상일 때부터 커플인가?

이진탐색 Binary Search ● 탐색 전에 반드시 정렬되어 있어야 한다. ● 살펴보는 범위를 절반 씩 줄여가면서 답을 찾는다. ● 정렬 O(NlogN) + 이진탐색 O(logN) -> 결과적으로 O(NlogN) ● 미리 정렬되어 들어오면 이진탐색만 하면 되므로 O(logN) ● 한번만 탐색하는 경우,선형탐색 O(N) 이 더 빠를 수도 있다. C++ lower_bound,upper_bound ● lower_bound: 찾으려는 key 값보다 같거나 큰 숫자가(x

길찾기문제 방향값을 미리 코드에 짜두고 for문으로 순회하는 기법을 꼭 익혀두자! 방문체크필요 , 각 칸이 노드, 상하좌우 4방향의 간선 # python from collections import deque dy = (0,1,0,-1) dx = (1,0,-1,0) chk = [[False] * 100 for _ in range(100)] N = int(input()) def is_valid_coord(y,x): return 0

● 인접행렬 - 구현이 빠르다. - 노드가 서로 연결되어 있는지 확인이 쉽다. - 특정 노드에 연결된 모든 노드를 검색할때,adj[i][1]~adj[i][v]를 전부 확인해야한다. - 전체 노드 탐색시 시간복잡도가 O(V^2) 이다. #include using namespace std; int N,M; int adj[10][10]; int main() { cin >> n >> m; for (int i=0;i> a >> b; adj[a][b] = 1; adj[b][a] = 1; } } ● 인접리스트 - 특정 노드에 연결된 노드 바로 검색 가능 - 노드가 서로 연결되어 있는지 확인이 오래걸린다.(특정노드가 검색노드 갖고있는지 리스트 탐색해야함) #include using namespace std; int n..

인접행렬 VS 인접 리스트 1.인접행렬 - edge 가 많은 그래프일 때 쓰는게 좋다.- edge 탐색이 빠르다. 2. 인접리스트 - edge 가 적은 그래프일 때 쓰는게 좋다.- 메모리를 적게 쓴다. 최단 거리를 구할 때는 BFS를 사용DFS는 재귀(or 스택),BFS는 큐로 구현가지치기를 하면 백트랙킹 인접행렬 frm sys import stdin node,edge = map(int,stdin.readline().split()) adj = [0 for _ in range(node) for _ in range(node)] for _ in range(edge): src, dest = map(int, stdin.readline().split()) adj[src][dest] = 1 adj[dest][src]..

◆ 순열 1) python from itertools import permutations v = [0,1,2,3] for i in permutations(v,4): print(i) 2) C++ #include #include #include using namespace std; int main() { vector v{0, 1, 2, 3}; do { for (int i : v) printf(" %d", i); printf("\n"); } while (next_permutation(v.begin(), v.end())); } ◆ 조합 1) python from itertools import combinations v=[0,1,2,3] for i in combinations(v,2): print(i)