컴퓨터공부하기

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

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

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방향을 탐색하며 지뢰찾기를 구현하면 된다.

DFS를 이용한 완전탐색을 수행하였다.

이때, 중간에 계산 한 값이 이전에 계산한 MAX보다 작거나 같은경우는 더이상 들어갈 필요가 없다.

곱해주는 값이 1보다 작은 수 이기 때문에, DFS를 수행할수록 작아질 수 밖에 없기 때문이다.

sum < max 로 하면 시간초과가 발생하고 

sum <= max로 해야 PASS할 수 있다.

아직 방문하지 않은 방이고, 

OPT[i][j] = 좌표 (i, j)에서 가질 수 있는 최대 값으로

이미 값을 가지고 있으면 해당 값을 바로 리턴하며, 아직 구하지 않은 겨우에는 4방향을 탐색하여 값을 계산한다.

OPT[i][j] = OPT[i+k][j+k] + 1;

주어진 문자의 역할대로 코드를 구현하면 된다.

여기서 주의할 점은, '?'는 무작위 방향이 되는데, 이것 때문에 문제가 발생한다.

나는 DFS를 통해 해당좌표가 일정 횟수 이상 들어가거나 DFS콜이 너무 많이 호출되면 불가능하다고 판단하고 빠져나오도록 했다.

계산기로 만들 수 있는 모든 숫자를 미리 계산해 놓으며, 각 숫자를 만드는데 버튼을 몇번 클린해야 하는지 계산해 놓는다.

계산하고자하는 X부터 나누기 시작하여, 필요한 버튼을 계산한다.

1일 때는 버튼 1이 가능한 상태인지만 체크하여 별도로 예외처리가 필요하다.