Algorithm/알고리즘 검색 결과

해당 글 9건

[Algorithm] 최대공약수(GCD), 최소공배수(LCM)

최대 공약수(GCD), 최소 공배수(LCM) 1. 알고리즘의 이해 유클리드 호제법을 사용하여 최대공약수를 구한 후, 이를 이용하여 최소공배수를 구한다!! 2. 유클리드 호제법 두개의 정수 사이에 존재하는 최대공약수(GCD)를 구하는 알고리즘 정수 a, b 에서 더 큰 값을 a에 위치시킨다 a를 b로 나눈 나머지를 r 이라고 한다 a는 b의 값으로, b는 r의 값으로 갱신시켜준다 b가 0이 됐을 때의 a값이 GCD 값이다 3. 소스 코드 #include #include using namespace std; int gcd(int a,int b){ // a에 항상 큰 값을 위치시켜야함 int tmp; if(a < b){ tmp = a; a = b; b = tmp; } // 유클리드 호제법 while(b!=0)..
Algorithm/알고리즘 2019. 2. 9. 17:32

[Algorithm] 에라토스테네스의 체

에라토스테네스의 체 1. 알고리즘의 이해 2부터 n까지 반복문을 돌린다 아직 체크가 되지 않은 수를 방문한다 아직 체크가 되지 않았다는 것은 이 수는 소수라는 뜻이다 이 수의 모든 배수는 소수가 아니므로 반복문을 돌며 체크해준다 2. 소스 코드 #include #include #include using namespace std; int prime[1000001]; bool eratos(int n){ memset(prime, true, sizeof(prime)); for(int i=2; i n; if(eratos(n)){ cout
Algorithm/알고리즘 2019. 2. 9. 17:31

[Algorithm] 진법 변환 알고리즘

진법 변환 알고리즘 1. 알고리즘의 이해 몫을 진법으로 나눠가면서 notation 보다 작아질 때 까지 반복한다 몫이 notation 보다 작아졌다면 반복문을 탈출한 뒤, 몫을 변환 결과 앞에 추가시켜준다 2. 소스 코드 #include #include #include #include using namespace std; string convertion(int num,int notation){ string res = ""; int mok = num; int nmg = 0; while(mok >= notation){ nmg = mok % notation; mok /= notation; // 10진법보다 크고 나머지가 10 이상인 경우 if(notation > 10 && nmg >= 10){ res = (c..
Algorithm/알고리즘 2019. 2. 9. 17:30

[Algorithm] 비트마스킹

비트 마스킹 ✅ 비트 마스킹 기본 지식 컴퓨터는 모든 정수형 변수를 이진수로 표현함 예를들어 6비트를 사용해 0~63 까지 표현할 수 있다 0 = 000000 63 = 111111 부호 없는 N 비트 정수형의 경우 2^0 을 최하위 비트 (Least significant bit) 2^(N-1) 을 최상위 비트 (Most significant bit) ✅ 비트연산자 모든 자릿수가 비트 (0 또는 1)로 이루어진 값에 대하여 아래의 연산이 가능함 비트가 1이면 켜져있음 , 0이면 꺼져있음 AND 연산 a & b OR 연산 a | b XOR 연산 a ^ b NOT 연산 ~a LEFT SHIFT 연산 a > b ✅ 피자 가게 예제 10자리 비트(0~9)의 각 자릿수가 피자의 서로 다른 토핑의 첨가 유..
Algorithm/알고리즘 2019. 1. 6. 16:55

[Algorithm] 탐색 알고리즘

탐색 알고리즘 탐색 알고리즘 미로 탐색 알고리즘 다익스트라 알고리즘 ✅ DFS (Depth First Search) '깊이 우선 탐색' 을 뜻한다 스택 또는 재귀를 사용한다 탐색이 막히면 다시 돌아와 다른 곳을 탐색 할 수 있다 (백트래킹) ✅ BFS (Breadth First Search) '너비 우선 탐색' 을 뜻한다 큐(Queue)를 사용한다 탐색이 끝난 노드는 큐에서 삭제 (pop) 한다 ✅ BFS 최단 경로 위 문제의 포인트는 BFS 탐색으로 (0, 0)을 시작으로 해서 맵의 모든 이동 가능한 경로를 움직일 때 마다 비용을 '1'씩 더해주고 최종 (N,M) 을 만나면 종료하도록 해야함 ✅ 다익스트라 알고리즘 (Dijkstra Algorithm) 주어진 시작 지점에서 모든 지점의..
Algorithm/알고리즘 2018. 11. 25. 21:11

[Algorithm] 다이나믹 프로그래밍

다이나믹 프로그래밍: 큰 문제와 작은 문제를 나눠서 해결하는 기법 1. Overlapping Subproblem- 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다- 문제를 작은 문제로 쪼갤 수 있다 2. Optimal Substructure- 문제의 정답을 작은 문제의 정답에서 구할 수 있다- 메모를 한다고 해서 "Memoization" Tob-down1. 문제를 풀어야한다2. 문제를 작은 문제로 나눈다3. 작은 문제를 푼다4. 작은 문제를 풀었으니, 이제 문제를 푼다# 재귀 함수로 구현# 시간복잡도 : 채워야하는 칸의 수(memo 배열) X 1칸을 채우는 시간복잡도Bottom-up1. 문제를 크기가 작은 문제부터 차례대로 푼다2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다3. 작은 문제를 ..
Algorithm/알고리즘 2018. 9. 11. 20:48