본문 바로가기

알고리즘, 자료구조55

1018 체스판 다시 칠하기 일일이 다 해보면 된다. 단순반복 노동은 한 번만 그 원리를 알면, 나머지는 정말 쉽다. 특히 반복할 때 컴퓨터는 절대 실수하지 않는다. 8x8의 크기의 filter로 체스판을 자르고 올바른 체스판으로 만들기 위해 뒤집어야할 횟수 중 최소가 되는 것을 고른다. 추가 테스트 케이스 9 9 WBWBWBWBB BWBWBWBWB WBWBWBWBW BWBWBWBWB WBWBWBWBW BWBWBWBWB WBWBWBWBW BWBWBWBWB WBWBWBWBW #include char a[52][52]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i=0; i 2019. 7. 18.
[brute-force] 1436 영화감독 숌 N 2019. 7. 16.
6. 브루트포스(brute-force) part 2 6.7 최적화 문제(Optimization problem) 문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제 ex) n개의 사과 중에서 r개를 골라 무게의 합을 최대화 하는 문제 최적화 문제를 해결하는 방법 중 기초적인 것은 완전 탐색 이다. 가능한 답을 모두 생성해 보고 그중 가장 좋은 것을 찾아내면 되기 때문에, 가장 직관적인 방법이기도 하다. 다른 방법으로는 동적계획법(DP), 조합탐색, 결정문제 등으로 문제를 더욱 빠르게 풀 수 있다. ex) 여행하는 외판원 문제 (Traveling Salesman Problem, TSP) 6.10 많이 등장하는 완전 탐색 유형 모든 순열 만들기 가능한 순열의 수 N!, N이 10을 넘어간다면 .. 2019. 7. 15.
[brute-force] 2798 블랙잭 블랙잭 100가지 중에 3가지를 고르는 경우의 수는, 10C3 = 161,700 경우의 수 별로 없으면 컴퓨터의 무식하고 빠른 연산을 살려서 모든 경우를 체크하여 보자. 가능한 조합을 모두 고르는 함수를 마침 공부하였다! sum = 0 인 상황에서 m - sum = 0 && d.. 2019. 7. 15.
6. 브루트포스(brute-force) part 1 브루트 포스 - 무식하게 풀기 6.2 재귀호출과 완전 탐색 재귀호출 재귀호출시 쪼개지지 않는 가장 작은 작업에서 함수를 return 하여 종료시켜야 한다. 가장 작은 단위를 기저 사례 (base case)라 한다. 중첩 반복문 대체 완전 탐색 구현 ex) 모든 조합의 경우의 수 찾기 #include #include /* 모든 조합의 경우를 출력한다. 재귀호출을 이용한다. 다중 for문을 대체할 때 유용하다. */ using namespace std; int cnt = 0; void printVector(vector v){ for (auto i : v) printf("%d ", i); printf("\n"); } // nCm void combination(int n, vector & v, int m){ i.. 2019. 7. 14.
17298 오큰수 일단 비교를 해야하니 담아둘 컨테이너가 필요하다. 배열을 백만개 선언할 수 도있고, 벡터를 이용할 수도 있지만, 간단하게 배열을 써보자. 그렇게 한다면, 최악의 경우 (제일 큰 숫자가 맨 오른쪽에 있는 경우) 탐색시간이 O(백만^2) 이 들어서 시간초과가 날 것이다. 스택에 하나씩 넣고 빼면서 비교해볼까 4 3 5 2 7 을 예로들면, stack 3 stack 3 5 들어간 5가 3보다 크므로 출력 stack 3 5 2 stack 3 5 2 7 들어간 7이 5보다 크므로 출력 들어간 7이 2보다 크므로 출력 7 다음에 들어간 것이 없으므로 -1 출력 .... 흠 무언가 의미가 다가오지 않는다. 이럴 때는 발상을 뒤집어 보자. 배열에 3 5 2 7을 넣어놓고, stack에 배열 끝 자리부터 거꾸로 담는다... 2019. 7. 14.
Greedy 알고리즘 11047가 동전 0 1. 예제 - { 1 5 10 50 100 500 1000 5000 10000 50000 } 이 있을 때, 4200원을 만드는 최소의 방법은 1000 * 4 + 100 * 2 이므로 총 6회이다. 2. 문제해결 - [그리디한 해결전략] 순간의 최적해를 구한다. (위 문제는 순간의 최적해가 최종 문제의 정답의 최적해인 경우라서 문제가 해결된다.) 가치가 가장 큰 동전을 최대한 많이 이용하고, 같은 방법으로 나머지 금액을 가치가 가장 큰 동전을 최대한 많이 이용해서 금액을 다 채울때 까지 반복한다. 2019. 7. 14.
8. 동적계획법(DP) 동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 여기서 어떤 부분 문제는 같은 문제를 두 번 이상 풀 수도 있기 때문에, 이 문제에서 답을 여러 번 계산하는 대신 한번만 계산 하고 계산 결과를 저장해 놓고 재사용한다. 따라서 속도의 향상을 꾀할 수 있다. 중복되는 부분 문제 cache - 이미 계산한 값을 저쟁해 두는 메모리 장소 overlapping subproblems - 중복 되는 부분 문제 ex) 대표적인 문제 - 이항계수 조합 nCr, \( \begin{pmatrix} n \\ r \end{pmatrix} \)은 다음과 같은 성질이 있다. 메모이제이션 memoization - 한 번 계산한 값을 저장해 두었다가 재활용하는 최적화 기법 위와 같은 이항계수 문제를 일반적인 재귀함.. 2019. 7. 14.
1966 프린터 큐 queue를 만들고, 4 2 1 2 3 4 n = 4, m = 2, cnt = 0 2 3 4 1 m = 1 3 4 1 2 m = 0 4 1 2 3 m = 3 1 2 3 m = 2, cnt = 1 2 3 1 m = 1 3 1 2 m = 0 1 2 cnt = 2 6 0 1' 1 9 1 1 1 n = 6, m = 0, cnt = 0 1 9 1 1 1 1' m = 5 9 1 1 1 1' 1 m = 4 1 1 1 1' 1 m = 3, cnt = 1 1 1 1' 1 m = 2, cnt = 2 1 1' 1 m = 1, cnt = 3 1' 1 m = 0, cnt = 4 1 cnt = 5 max 값 있으면 max 값을 pop 할 때까지 front를 pop하고 push함 m 인덱스 갱신 cnt++ max 값 없으면 m 값.. 2019. 7. 1.
11729 하노이 탑 접근 장대 1, 2, 3이 있고, 1에 원판 3개가 있을 때, 이 원판을 모두 크기 순에 맞게 장대 3에 옮겨야 한다. 그 과정을 살펴보자. a b 는 a의 맨위의 원판을 b의 맨 위로 옮긴다는 뜻이다. 자 머리속으로 상상해보자. 그러면서 일반화 해보자.(n개의 원판으로!) 1 3 1 2 3 2 ---------- 1) 지금 이상황은 1에서 제일 큰 원판이, 2에 n-1개의 원판이 순서대로 있는 상황이다. 1 3 ---------- 2) 1에 있는 가장 큰 원판을 3으로 보낸다. 2 1 2 3 1 3 ---------- 3) 2에서 n-1개의 원판을 3으로 보내는 상황이다. 함수 f(a, b, n_disk)를 정의하고 맨처음 상황을 f(1, 3, 3)으로 생각해보자. 1)의 상황을 다시 한번 보자. f(.. 2019. 6. 28.
728x90

티스토리툴바