컴퓨터공부하기

이진 탐색 알고리즘은 정렬된 배열에서만 사용 가능하다.

아주 많은 데이터가 저장되어 있는 배열에서 순차탐색보다 효과적으로 값을 찾을 수 있다.

기본 원리는 배열에서 중간 위치를 기준으로  찾고자 하는 값이 더 작으면 중간 위치의 왼쪽에서 계속 탐색,

찾고자 하는 값이 더 크면 중간 위치보다 오른쪽에 있는 값들을 탐색하며,

다음 위치는 계속 남은 배열의 중간위치를 기준으로 탐색한다.

위 그림의 예시에서 1부터 10까지 저장된 배열에서 2를 찾을 것이다.

초기값으로 front = 0, rear = 9가 되며, mid = (0 + 9 ) / 2 = 4 를 가진다.

mid인덱스에서 가지고 있는 값은 5이므로, 찾고자 하는 숫자가 더 작다. 

그러므로 rear의 값을 mid - 1로 바꿔서 다시 탐색한다.

그러면 front = 0, rear = 3, mid = 1이 된다.

1번 인덱스는 2이므로, 찾고자하는 숫자와 일치하므로 이진 탐색을 종료한다.

반복문을 사용하는 방법과, 재귀호출을 통한 구현이 모두 가능하다.

일반적으로는 반복문을 사용해서 구현하면 된다.

 long long으로 해결할 수 없다고 댓글에 달려있어서

vector를 이용하여 , 숫자를 문자열 곱셈으로 답을 구했다.

normalize, multiply는 곱셈에 관련된 함수로, 주어진 a^b을 수행한다 즉 a * a * a ...를 이용해 곱셈 답을 찾아내고

그 이후에 계산한 값들을 다 더해준다.

가장 작은 값이 합칩합의 대표 원소로 나타낼 수 있도록 기록해 놓는다.

문자열을 앞에서부터 탐색하며, 주어진 부분 문자열이 존재하는지 확인한다.

존재하는 경우 카운트 해주면된다.

STL multiset을 이용해 새로운 숫자가 입력될 때마다 정렬이 되도록했다.

그리고 새로 입력된 수와 이전 중간값을 비교하여 iterator의 위치를 변경해주어 중간 위치를 유지하도록 하였다.

DFS로 4방향 탐색을 통해 모든 경우의수를 다 계산한다.

중복되는 탐색이 많기 때문에, DP로도 가능할 것 같다.

나는 100만 이하의 소수를 모두 구하면서, 해당 소수의 홀수 약수의 합을 미리 다 계산해 놓고,

A~B구간에서 F(B)-F(A-1)을 통해 합을 계산했다.

처음 소수를 구하는데 시간이 오래 걸려서 수행시간이 4초가 넘는다.

다른사람들은 100ms가 안되는 사람도 있는데 

어떻게 구한것인지 궁금하다.

소수를 굳이 구하지 않아도 되는건가?

Knapsack이랑 완전히 같은 문제이다.

제한 칼로리가 가방의 무게가 되며, 점수가 물건의 코스트가 된다.

DP를 이용하여 문제를 해결할 수 있다.

OPT[i][j]배열은 0~i번째 까지 재료를 이용하여 j칼로리를 넘지 않는 점수의 최대값을 저장하게 된다.

그러므로, OPT[i][j]에서 새로 넣은 i번째 재료의 칼로리가 j보다 크다면, 이전에 기록해 놓은 i-1번째 재료까지를 사용하여, j칼로리를 채웠을 때인 OPT[i-1][j]를 넣으면 된다.

그외에는 이번 i번째 재료를 넣을 때와, 안넣을때의 큰값인 max(opt[i-1][j], OPT[i-1][j-v] + c[i]) 값을 넣으면 된다.

8방향을 탐색하며 지뢰찾기를 구현하면 된다.