소수를 구하는 알고리즘을 통해 답을 구했는데 계속 틀렸다고 나왔다.
그래서 for문을 통한 완전탐색 방법으로 다시 풀었는데 성공했다.
소수를 구하는 알고리즘에서 1에 대한 예외처리를 안해서였다.
소수구하는 알고리즘을 다시 정리하자면
1) 2가 아닌 수에서 2로 나누어 떨어지면 소수가 아니다
2) n 은 2부터 시작에서 n보다 작은 i * i를 만족하는 i로 나누어 떨어지면(합성수)이면 소수가 아니다.
이 모든 필터링을 넘어가면 소수이다. !
'전체 글'에 해당되는 글 203건
- 2015.04.27 2581_소수
- 2015.04.27 2529_부등호
- 2015.04.27 더블릿_토마토
- 2015.04.26 더블릿_줄 세우기
- 2015.04.26 증가하는부분수열(Longest Increase Subsequence)
부등호의 개수와 부등호가 입력으로 주어지면
각 위치에 0~9로 구성된 조건을 만족하는 수열을 찾아내어
그 것을 정수로 환산하여 가장 큰 정수와 가장 작은 정수를 찾는 것이다.
완전탐색의 방법으로 수행한다.
다행이도 중복되는 수를 제외하고라는 조건이 있으므로 10^10이 아니라
10! 이다. 10!은 1초안에 1억번 안으로 수행횟수를 조절 할 수 있으므로 충분히 완전탐색 가능한 숫자이다.
수열을 만들어 나갈 때
조건을 만족 시키지 않으면 바로 재귀호출을 끊어버리는 방법을 통해
9개의 부등호를 만드는 재귀적 호출도 금방 수행을 할 수 잇게 된다.
void make_number(int idx){ if (idx > 1){ char operator_idx = relation[idx - 2]; if (operator_idx == '<'){ if (result[idx - 2] > result[idx - 1]) return; } else{ if (result[idx - 2] < result[idx - 1]) return; } } if (idx == k + 1){ for (int i = 0; i < idx; i++){ result_value[result_idx][i] = result[i]; } result_idx++; return; } for (int i = 0; i < 10; i++){ if (!visited[i]){ result[idx] = i; visited[i] = true; make_number(idx + 1); visited[i] = false; } } } | cs |
부등호의 위치 인덱스 - 2 와 부등호의 위치 인덱스 - 1의 값이 부등호를 만족시키지 않으면 바로 끊어버리는 코드이다.
결과값을 출력하는 부분이 다소 애매했는데 이차원 배열을 만들어서 값을 저장하여 출력하는 식으로 답을 도출해내었다.
오랫동안 풀지 못했던 문제를 겨우겨우 풀어내었다.
물론 약간의 힌트를 얻고 나서였다.
격자 모양의 상자에 토마토가 들어있는데, 토마토는 한 시간당 주위의 것을 익혀나간다.
모든 토마토가 익는데 걸리는 시간을 구하여라 였다.
토마토는 여러 군데 익은 상태의 것이 있을 수 있었고,
어쨋든 나는 bfs로 수행하는 데까지는 잘 방향을 잡았다.
익은 토마토마다 bfs함수를 한 번씩 실행하게 했는데, 이 것이 미쓰였다.
맨 처음에 이미 익은 토마토를 한 번에 큐에 담았다가 bfs를 한 번만 수행하면 되는 것이 포인트였다.
여러 예외 처리를 할 필요도 없고, 그리고 더군다나 이 것이 가장 정확한 방법이었다.
bfs의 원리에 대해서 정확히 알지 못 한채 문제를 풀어서 못 푼 것이었다.
bfs에 대해서 좀 더 정확히 이해할 수 있게 해준 문제
여러 군데에서 동시에 bfs를 수행해야 하는 경우 한번에 큐에 담아 내는 방법에 대해서 활용 할 줄 알고 이해해야 한다.
백준에서 똑같은 문제 7570_줄세우기는 실패했다.. 이유는 무엇일까?
이 문제는 정말 어떻게 푸는지를 몰라서 헤맸고, 결국 인터넷을 통해 풀이법을 공유 받았는데도 이해가 안 가는 문제다.
학생들의 번호를 인덱스로 가지는 배열을 가지고 동적계획법을 활용한 문제인 것은 같으나
그 로직에 대해서 100% 이해가 가지 않는다.
우선, 문제의 핵심은
줄을 세울 때 맨 뒤로 보내거나, 맨 앞으로 보내는 개수의 최소 값을 구하라는 것인데
가장 긴 증가하는 학생들의 수열을 구한 후에 전체 학생 수에서 빼주면 그 것이 최소로 학생들을 맨 뒤로 보내거나,
맨 앞으로 보내게 되는 것이었다.
대충 이해는 가겠으나, 이 것을 코드를 옮기는데 잘 되지 않아,,,(예제 테스트케이스는 맞았으나 그 다음부터 잘 안되어서
다른 코드를 참고 했는데, 보고도 잉?)
나와는 다르게 입력 받은 번호를 인덱스로 활용해서 동적으로 학생들의 증가하는 수열을 구하는 방법이었다.
예제의 테스트케이스를 이용해 설명하자면
5
5 2 4 1 3
1) 입력 5가 들어왔을 때
dy[5] = dy[5 - 1] + 1 // 4번째 학생까지 연속되는 수열 개수 + 1
dy[2] = dy[2 - 1] + 1 // 1번째 학생까지 연속되는 수열 개수 + 1
dy[4] = dy[4 - 1] + 1 // 3번째 학생까지 연속되는 수열 개수 + 1
dy[1] = dy[1 - 1] + 1 // 0번째학생까지(0번째학생은 없다) 연속되는 수열 개수 + 1 => 1
..
입력되는 순서 대로 값이 들어갈 것이므로 완전 머리를 잘 쓰신 분이 짜신 코드 같다.
동적 계획법에 대한 예 중에 대표적인 것이 증가하는 부분 수열 문제이다.
감소하는 부분 수열 문제 역시 둘 다 똑같은 개념이라고 할 수 있겠다.
예를 들어 수열
10, 20, 40, 30, 70, 50, 60이 있다고 한다면
이 중에서 증가하는 부분 수열 중에 가장 긴 것을 찾아라.
라는 것이 증가하는 부분 수열이라고 하겠다.
-----n^2 방법--------
간단히 n^2으로 풀 수 있는 소스를 설명하자면,
(이 부분도 간단히 생각해내기 어려웠다. 동적계획법으로 푸는 n^2 이다)
정말 간단하고 쉬운 방법은 n! 완전탐색이겠다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <iostream> using namespace std; int arr[7] = { 10, 20, 40, 30, 70, 50, 60 }; int dy[8]; int n = 7; int main(){ for (int i = 1; i <= n; i++){ for (int j = 0; j < i; j++){ if (arr[j] < arr[i] && dy[i] < dy[j] + 1){ dy[i] = dy[j] + 1; } } } sort(dy, dy + n); // 중요 cout << dy[n - 1] << endl; return 0; } | cs |
기준이 되는 i값을 빨간색,
그 앞의 값들 j값들을 주황색으로 표현해서 설명하자면,
(1) i = 1 일 때
10, 20, 40, 30, 70, 50, 60
=> dy[7] = {0, 1, 0, 0, 0, 0, 0};
(2) i = 2일 때
10, 20, 40, 30, 70, 50, 60
=> dy[7] = {0, 1, 2, 0, 0, 0, 0};
(3) i = 3일 때
10, 20, 40, 30, 70, 50, 60
=> dy[7] = {0, 1, 2, 2, 0, 0, 0};
(4) i = 4일 때
10, 20, 40, 30, 70, 50, 60
=> dy[7] = {0, 1, 2, 2, 3, 0, 0};
(보충설명) 70이 가지는 증가하는 부분 수열 10, 20, 40, 70이다.
.......
써보면서 알게 되었는데, 최대 증가하는 부분 수열은 연속된 것을 고려하지 않는 듯 하다.
연속 된 것을 찾기 위한 알고리즘은 아닌 듯 하다.
20보다 작은 인덱스들을 처음부터 돌아다니면서
20보다 작고 (arr[i] > arr[j]) ,현재 자신이 가지고 있는 증가수열의 개수보다 크면(dy[i] < dy[j] + 1)
갱신
.....
Sort(정렬)를 반드시 해야 한다.
대충 감이 올지 모르겠다. 나도 글을 써보니까 이해가 될 듯 하다.
-----n*logn 방법--------
1)Lower Bound 방법
Lower Bound란 허용되는 하한값을 가진다는 것을 말한다.
결국 입력 되는 값들을 고대로 인덱스로 가지면서 연산을 해주면 된다는 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <iostream> using namespace std; int arr[5] = {5, 2, 4, 1, 3}; int dy[110000]; int n = 5; int main(){ for (int i = 0; i < n; i++){ dy[arr[i]] = dy[arr[i] - 1] + 1; } for (int i = 0; i < 5; i++){ cout << dy[arr[i]] << " "; } cout << endl; return 0; } | cs |
'알고리즘' 카테고리의 다른 글
| 조합알고리즘의 최적화 (0) | 2015.04.30 |
|---|---|
| 2차원 배열의 경우의 수 구하기 (0) | 2015.04.28 |
| 퇴각 검색(BackTracking) (0) | 2015.04.22 |
| 완전탐색 경우의 수를 재귀로 수행하는 방법 (0) | 2015.04.15 |
| DP(Dynamic Programming)패턴 연구 (0) | 2015.04.03 |
