본문 바로가기
반응형

Algorithm_몰랐던 함수 및 개념

 (8)
[알고리즘] 백트래킹(Backtracking) ##백트래킹(Backtracking) :재귀 함수를 이용한 브루트 포스중 종료조건을 추가해 의미없는 호출을 줄이는 것을 백트래킹이라고 한다.
[알고리즘] 부르트포스,완전탐색 #브루트 포스 1.문제를 푸는 단계 1) 가능한 경우의 수 계산 2) 가능한 방법들로 만들어보기 -for문, 재귀,순열,비트마스크 -재귀로 순열 ,비트마스크 구현 가능해서 재귀가 중요! 3) 각 방법을 이용해 답 구하기 2.시간복잡도 :대부분 O(경우의 수*1가지 방법을 수핸하는데 걸리는 시간) 3. n의 대략적인 크로 방법 유추 1) 시간복잡도 n! 일 때 =10 이면 약 300만 이어서 n
[알고리즘] 소수,에라토스테네스의 체 ##소수(prime) 1,알고리즘 1) n이 소수인지 판별 (1) 완전탐색 : 2~n-1 까지 약수 있는지 검사 -시간복잡도:O(n) (2) 루트n 까지 : 1~sqrt(n) 까지 나누어 떨어지는지 검사 -시간복잡도:O(sqrt(n)) 1 2 3 4 5 for (int i = 2; i * i
[알고리즘] 최대공약수/최소공배수 ##최대공약수(GCD) 1.구하는 방법 1) 완전탐색 -수 중 제일 작은 수n , 1부터 n까지 나누어 떨어지는 수 구하기 2) 완전탐색 (제곱근 까지) -수 중 제일 작은 수n , 1부터 sqrt(n)까지 나누어 떨어지는 수 구하기 3) 유클리드 호제법 -두수 중 하나의 수로 다른 수를 계속 나누는 방법 -시간복잡도: 제일 빠른 방법 1 2 3 4 5 6 7 8 int gcd (int a, int b) { while (b !=0) { int r = a % b; a = b; b =r; } return a; } cs ##최소 공배수(LCM) 1.구하는 방법 : l = (a/gcd)*(b*gcd)*gcd
[알고리즘] 그래프 02. 그래프 표현 ##인접 행렬 : 행렬 안에 모든 연결 상태 저장 1.구현 -벡터 말도 배열로 구현해야 함 ##인접 리스트 : 연결 리스트로 연결되어 있는 노드만 저장 1.구현 -벡터 배열로 구현 ##간선 리스트
[알고리즘] 그래프 01.개념 ##그래프 : 노드와 엣지로 연결되어 있는 그래프 ##방향/무방향 그래프 1.방향 그래프 : 1->2 로 방향이 존재 2. 양방향 그래프 : 1->2,2->1 두 방향이 동시 존재 ##사이클 : 경로의 시작과 끝이 같은 그래프 ##차수 : 노드에 연결되어있는 엣지의 갯수 1.in-degree/ out-degree -in-degree: 노드로 들어오는 엣지의 갯수 -out-degree: 노드에서 나가는 엣지의 갯수
DFS 기초 동빈나 실전 알고리즘 강좌 ##인접행렬 그래프 dfs 탐색 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #define _CRT_SECURE_NO_WARNINGS #include #include // c 문법 헤더파일 #include // 동적배열 라이브러리 using namespace std; // cin,cout 편하게 사용 라이브러리 int visit[7]; vector adj_arr[8]; // 인접..
개념 시간복잡도 - 대략 1억번 계산에 1초 - 버블정렬: O(n*n) - 선택정렬: O(n*n) - 삽입정렬: O(n*n) // 개념: pow(밑, 제곱승) , 헤더#include // 개념: abs(숫자) :절댓값 , 헤더:#include ##sort 정렬 : 퀵 정렬을 구현 sort(v.begin(), v.end()); sort(v.begin(), v.end(),compare);//사용자 정의 함수 사용 sort(v.begin(), v.end(),greater()); //내림차순 (Descending order) sort(v.begin(), v.end(),less());//오름차순 (default = Ascending order) ## stable 정렬 // : stable_sort() : 입력된 순서를..
반응형

티스토리툴바