본문 바로가기

알고리즘

 (179)
[BOJ 2602] 돌다리 건너기 두루마리에 있는 문자열을 기반으로, 천사 혹은 악마의 돌다리를 건너야 한다. 전체적인 탐색이 필요하고, 탐색에서 중복으로 나타나는 유형은 메모이제이션이 필요하다. 메모이제이션을 위해서, 사용할 변수는 다음과 같다. 1. 천사 돌다리의 인덱스 2. 악마 돌다리의 인덱스 3. 두루마리 문자열의 인덱스 4. 다음 건너야 할 돌다리 이 4가지 변수는 메모이제이션에 있어서 꼭 필요한 것이다. 하나라도 누락된다면, 올바른 값이 다른 값으로 덮어씌워질 수 있다. 전체적인 탐색은, 두루마리의 문자열을 기반으로만 확인해주면 된다. 중요한 것은, 돌다리를 하나 이상 건널 수 있다는 것을 유의해서 코드를 작성해야 한다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19..
[BOJ 11399] ATM 앞에 기다리는 시간은 누적되므로, 누적의 값을 줄여야 총량을 줄일 수 있다. 가장 작은 값들을 먼저 선택해서, 총량을 줄이는 방향으로 코드를 작성한다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include using namespace std; int N; int answer = 0; int acc = 0; vector v; int main() { cin >> N; for(int i = 1; i > tmp; v.push_back(tmp); } sort(v.begin(), v.end()); for(int i = 0; i
[BOJ 1107] 리모컨 0 ~ 500000까지의 채널을 체크하면서, 유효한지를 체크하면 된다. 문자열로 처리하면 시간이 늦어지므로 int로 채널들을 처리하도록 다시 구성했다. 처음에는, 가능성이 있는 채널만 찾아서 체크할려고 했지만 쉽지 않아서 완전 탐색을 했다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include #include using namespace std; int N, M, tmp; int answer; int arr[6]; bool chk[10]; void func(int..
[BOJ 1182] 부분수열의 합(비트마스크, 재귀함수, C++) 이 문제는 비트마스크와 재귀 함수로 풀 수 있다. 비트마스크로 문제를 풀어보았다. 재귀 함수로 풀 경우에는, 함수의 종료 조건을 논리적으로 구성해야 한다. 사실 비트마스크로 문제를 풀기 이전에, 재귀 함수로 문제를 풀었는데 종료조건이 틀렸었다. 합이 S일 때, Return하도록 구성했는데, 인덱스가 N일 때로 구성해야 문제가 없이 답을 구할 수 있다. 1. 비트마스크 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #include using namespace std; int N, S; int arr[21]; int answer = 0; int check[1024*10..
[BOJ 2688] 줄어들지 않아 단계와 끝자리 수를 이용해서 DP를 정의할 수 있다. 단계만을 매개변수로 사용할 경우에는, 점화식을 세울 수 없다. 끝자리 수를 이용해서, 점화식을 완성할 수 있다. DP[i][j] += DP[i - 1][k] (0
[BOJ 2309] 일곱 난쟁이 이 문제는 전체 탐색으로 문제를 해결할 수 있다. 주의해야 할 점은, 100을 만드는 7명의 난쟁이를 찾아야 한다는 것이다. 벡터를 이용해서, 출력문을 손쉽게 해결했다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include #include #include using namespace std; int tall[10]; vector v; bool flag = true; void func(int idx, int sum){ if(idx == 10){ if(sum == 100 && v.size() == 7){..
[BOJ 1254] 팰린드롬 만들기 이 문제는 다이나믹 프로그래밍으로 꼭 풀어야 하는건 아니다. 문자열의 i ~ j 구간의 팰린드롬 여부를 파악하도록 DP를 구성했다. 문자열의 끝에 0개 이상의 문자를 붙여서, 팰린드롬이 이루어지는지 볼려면, 모든 구간을 보는 것이 아니라, 0 > S; for(int i = 0; i
[BOJ 1562] 계단 수 DP를 이용해서 문제를 풀 때, N만으로는 문제를 해결할 수 없다. 추가적으로 정보가 필요한데, 끝자리 수와 0~9 비트마스크가 필요하다. 끝자리 수를 다음에 올 수 있는 수를 확인하고, 0~9 비트마스크를 조작할 것이다. i = N j = 끝자리의 수 k = 0~9 비트마스크(0 ~ 1023) 위의 정보를 이용해서 점화식을 세우면 된다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #include #define mod 1000000000 using namespace std; long long dp[101][10][1024..

티스토리툴바