이 포스트는 작성중입니다! int binary_search(int data[], int num, int size) { int left = 0; int right = size - 1; int mid; mid = (left + right) / 2; while (left num) right = mid - 1; else left = mid + 1; mid = (left + right) / 2; } return -1; } 오름차순으로 sort된 size만큼의 크기를 가지고있는 정수 배열 num이 data[]에서 몇번째에 위치하는지를 return 하는 함수입니다. num이 data[]에 존재하지 않는다면 -1을 return 합니다.

(이 포스팅은 작성중입니다.) 전형적인 1차원 다이나믹 프로그래밍 문제이다. 계단을 오를때 문제에서 주어진 두번째 규칙인 "연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다."라는 조건때문에 점화식을 세울때 약간의 고민을 했다. 잊을만할때 다시 풀어볼만한 문제

백준 1003번은 기초적인 동적 계획법(DP, Dynamic programming) 문제입니다. 시간제한이 0.25초로 매우 빡빡한 편이라서 시간복잡도 O(n)으로 풀어야 해결 가능합니다. 다음 소스는 문제에서 주어진 $N$번째 피보나치 수를 구하는 C++ 함수입니다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } 이와같이 재귀적으로 N번째 피보나치 숫자를 구했을때 0과 1이 각각 몇번씩 return되는지 구하는 문제인데, $fib(n)$ 을 $n$번째 피보나치 숫자를 반환..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 백트래킹 구현시 항상 search()함수를 void 타입으로 구현했는데, int형으로 수정되어 최초해가 나오면 바로 모든 search()함..

학교에서 배운 최대공약수와 최소공배수의 정의는 다음과 같습니다. 최대공약수(GCD, Greatest common divisor): 여러개의 정수중 그들 모두의 약수가 되는 공약수(Common divisor)중 최대값 최소공배수(LCM, Least common multiple): 여러 개의 정수중 그들 모두의 배수가 되는 공배수(Common multiple)중 최소값 우선, 최대공약수는 유클리드 호제법(Euclidean algorithm)을 사용하여 구할 수 있습니다. 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘입니다. 유클리드 호제법의 정확한 설명은 다음과 같습니다. A를 B로 나눈 나머지 값을 R이라고 할 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다 예를 들어서 62와 2..

주: 이 포스트는 작성중입니다. 소수(Prime number)란 1과 자기 자신으로밖에 나누어지지 않는 1을 제외한 정수입니다. 다음은 C++로 구현한 가장 일반적인 소수구하기 알고리즘입니다. #include using namespace std; bool IsPrimeNumber(int n) { if (n