SW검정준비

팩토리얼로 나타났을 때, 소인수분해하기에라토스테네체의 체1\. 처음에 다 default true로 하기2\. i\*i < n 인 i 까지 반복(sqrt(N))3\. %i == 0 이면 false로 바꾸기현재 위치가 소수이면 primes vector 배열에 넣기소수

생각이 나는대로 짜는 방식...최적부분구조 : 해결한 부분은 되돌아보지 않는 구조중복부분구조 : 그 부분에서 최적값이 한개가 나오는데, 합쳐놓고 보니 오답이 나오는 구조\-> 탐욕알고리즘 완전 탐색으로 해결해야 한다!\-> 항상 증명을 해야하거나, 알고 있는 경우 (다

탐욕알고리즘 (일부분 검증)분할검증 (일부분 검증)백트래킹(가지치기) (완전 검증) - ad 시험동적프로그래밍(완전 검증) - pro 시험dp : 반복문 vs 재귀호출\-> 반복문 구조가 덜 메모리 사용하고, 더 빠르다.\-> 그러나 tc마다 반복문 개수가 다를 때 재

입력값의 개수에 따라 달라짐.6C3 중 비용합 최소

1) 1 - (1 - A 성공) \* ( 1 - B 성공))2) n번 독립시행확률: nCr (성공확률)^r (1-성공확률)^(n-r)3) dp4) %f: 여섯번째자리까지 = %.6fcout은 안됨

1) 괄호 검사2) 문자열 계산기sol1 - stack중위 표현식 -> 후위 표현식으로 바꾸기ex) a - b => a b -stack : 나보다 서열이 낮을 때 까지 빼기후위 문자열 배열: 피연산자 들어오기so2 - 이진트리3) dfs : 모든 경우의 수 - stac

무향 그래프유향 그래프가중치 그래프사이클 없는 방향 그래프 (DAG)(사이클: 두개 이상의 노드를 거쳐서 되돌아 올 수 있는 구조) \- 위상정렬 문제 \- 최장거리 구하기 : 가중치에 음수로 바꿔서 최단거리 문제(다익스트라) 로 구하기 완전 그래프: 정점들에 대

크기 주로 4를 곱해서 사용treeN ~ tree2\*N -1 : leaf nodetree1 ~ treeN-1 : 중간 노드리프 노드가 N부터 시작하므로, 트리의 구조는 여전히 1-based 인덱스처럼 동작.N이 홀수든 짝수든, 부모 인덱스 k에 대해 2k(짝수), 2

최적 경로: 모든 노드를 지났을떄 최단 경로최단 경로: 모든 노드가 아님표준 TSP: 다 돌고,다시 돌아오는 거거리 계산: 매번 재귀에서 하는 것 보단 배열에 저장하고, 참조하는게 더 나음.(두 점 조합- for문으로 계산)