알고리즘 썸네일형 리스트형 [Introduction to Algorithms] 2. 시작하기 2. 시작하기 많은 알고리즘에서는 루프를 사용하여 문제를 해결하곤 한다. 우리는 코드가 문제없이 작성 되었다면, 그 루프가 정상적으로 작동하여 문제를 해결할 것을 알고 있다. 그러나 이를 논리적으로 증명하기는 어려웠다. 이때 사용할 수 있는 것이 루프 불변성(Loop Invariant)이다. 루프 불변성은 루프를 사용한 알고리즘이 타당(correct)한지 증명하기 위해 사용된다. 루프 불변성임을 확인하기 위해서는 세 가지 특성이 만족되어야 한다. 초기조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다. 유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면, 다음 반복이 시작되기 전까지도 계속 참이어야 한다. 종료조건 : 루프가 종료될 때 그 불변식이 알고리즘의 타당성을.. 더보기 [Introduction to Algorithms] 1. 알고리즘의 역할 1. 알고리즘의 역할 1.1 알고리즘 이 장에서는 우리가 알고리즘을 배우는 이유와 배워서 어떻게 사용할 수 있는지에 대해 간략하게 설명해준다. 먼저, 알고리즘이란 한 값을 입력받아 다른 값으로 출력하는 계산 절차라고 한다. 가장 대표적으로는 임의의 수열을 정렬시키는 정렬 기법이 있다. 여러 알고리즘을 익히고, 사용할 수 있게 된다면 더 훌륭한 프로그래머가 될 수 있을 것이다. 마치 요리사 지망생이 요리사가 되기 위해 많은 레시피를 배워가는 것처럼. 1.2 기술로서의 알고리즘 어떤 문제를 풀기 위해서 여러 개의 알고리즘을 구현했다고 했을 때, 가장 최적의 알고리즘을 선택하는 기준은 무엇이 있을까? 나는 효율성이 대표적인 기준이 될 수 있다고 생각한다. 효율이라는 것은 시간과 메모리 두 차원에서 생각해볼 수.. 더보기 [1Day 1Algo] 백준 11653번 소인수분해 (C++) 해당 문제를 보고 처음에는 "2부터 N-1까지 나눠주면 되겠지~" 라고 생각했다. 그러나 혹시 놓치고 있는 소인수분해에 대한 개념이 있을 수 있어 검색을 했다. 눈에 띄는 부분은 소수로 자연수를 나누는 것 이었다. 그래서 처음 생각했던 개념을 조금 발전시켰다. "2부터 N-1까지 소수인 수로 나눠줘야지~" 그리고 아래와 같은 방식으로 코드를 작성했다. 그러나 시간제한에 걸려 틀렸다. #include #include using namespace std; bool isPrime(int x) { for (int i = sqrt(x); i > 1; i--) { if (x % i == 0) return false; } return true; } void primeFactorization(int x) { for (.. 더보기 유클리드 알고리즘 (Euclid’s algorithm) 유클리드 알고리즘 (혹은 유클리드 호제법)이란? 두 양의 정수 A, B에 대한 최대공약수를 구하는 알고리즘이다. 이는 O(log N) 으로 가장 효율적으로 GCD를 구한다. * 최대공약수(Greatest common divisor, GCD)란, A, B를 나누는 자연수 중에서 가장 큰 자연수를 말한다. * 호제법이란, 두 수가 서로 상대의 수를 나누어 원하는 수를 얻는 알고리즘을 말한다. 최대공약수는 다음과 같은 성질을 갖는다. 식에서 mod는 나머지를 구하는 모듈러 연산(%) 이다. 성질을 이용한 예시는 다음과 같다. 다음은 C++로 구현한 코드이다. int gcd(int a, int b) { if (b > 0) return gcd(b, a % b); return a; } 더보기 이전 1 다음
