컴퓨터하는 kimmessi

되추적 (Back Tracking) 틀린 답에 접근했을 때, 틀리기 전의 상태로 돌아가서 다른 선택을 하는 알고리즘 만약 답이 나올 때까지가 시간 복잡도가 엄청 복잡하게 나올 수도 있지만, 이 답이 유망했는지 아닌지를 판별하면서 불필요한 노력을 절감할 수 있다. 되추적은 트리의 변형된 깊이우선탐색(DFS)이다. 깊이 우선 탐색 (depth - first search) 부모 마디 우선(preorder) 트리 검색은 트리의 깊이 우선 검색이다. 이는 뿌리마디(root)를 먼저 방문한 후, 그 뿌리마디(node)의 후손들을 모두 방문한다. 예시로는 왼쪽에서 오른쪽의 순서로 마디의 자식을 방문한다. 다음은 깊이우선검색을 하는 간단한 재귀 알고리즘을 쓰는 프로시저이다. void depth_first_tree_se..

탐욕 알고리즘이란? 작은 사례로 나누지 않고 탐욕스러운 선택을 sequence로 계속하면 답에 가까워진다. 선택과정(selection procedure) : 집합에 추가할 다음 원소를 고른다. 그 당시 최적을 선택하는 탐욕 기준에 따라 선택한다. 적절성검사(feasibility check) : 새로운 집합이 해답이 되기 적절한지 검사한다. 해답점검(solution check) : 새로운 집합이 문제의 해답인지 결정한다. 이 과정이 동시다발적으로 진행된다. 거스름돈을 고르는 탐욕 알고리즘 예를 들어 돈이 50원, 25원, 10원, 5원, 1원이 있고 31원을 거슬러 주어야 할 때, (이때, 거슬러 주는 각각의 동전들은 여러개이다.) 1. 50원을 집었다가 내려놓는다. 2. 25원을 집는다. 3. 25원을 ..

분할정복(Divide and Conquer) 알고리즘이란? 문제의 입력사례를 두 개 이상 작은 입력사례로 분할한다. 계속 분할 하다가 바로 답을 얻을 수 있으면 원래 문제의 답은 얻은 답들을 통합해 구하는 알고리즘 하향식(top - down) 문제풀이 방식이다. 상위 입력사례의 해답은 하위의 작은 입력사례들의 해답을 가지고 구한다. 재귀함수의 작동원리가 이런데, 문제 풀이 중심으로 재귀함수를 작성한다. 이분 탐색(binary search) 재귀함수의 재귀 호출은 분할정복의 하향식 문제풀이 방식과 원리가 같다. 1. [분할(divide)] 배열을 정 가운데 원소를 기준으로 반으로 분할한다(divide). $x$가 가운데 원소보다 작으면 왼쪽 배열을 선택, $x$가 가운데 원소보다 크면 오른쪽 배열을 선택한..

www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 해결 알고리즘 1. 큐(q)에 1부터 N까지의 숫자들을 순서대로 push해준다. 2. 큐(q)안에 숫자들이 모두 없어질 때까지 K번 옆으로 갈 때 과정에서 지나치는 숫자들은 큐의 맨 앞에서 맨 뒤로 보내고, K번 가서 도착한 그 숫자는 출력하고 큐(q)에서 pop한다. 여기서 큐의 사이즈가 1이 아니면 뒤에 쉼표(,)를 출력한 후 pop한다. 소스 코드 #include using namespace std; int main(){ int N, K; cin >> N >> K; queue q; cout

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로�� www.acmicpc.net 문제 해결 알고리즘 1. 배열에 방문 하지 않았고, 배열 값이 1인 배열들을 탐색한다(bfs). 탐색이 전부 끝난 상황이면 (3번으로) 2. 탐색(bfs)를 하다가 더 이상 1이 나오지 않으면, 그림의 넓이(cnt)를 벡터(v)에 저장하고, 그림의 개수(num)을 1 더해준다. (1번으로) 3. 마지막으로, 그림의 개수(num)과 vector v에서 최댓값을 출력해준다. 소스코드 #include #..

https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 �� www.acmicpc.net 이 문제를 처음에 풀 때는 간단하게 while문을 이용해 풀려고 했지만, 시간초과가 나는 것이다. #include using namespace std; int main() { int a, b, v, sum = 0, cnt = 0; cin >> a >> b >> v; while (true) { cnt++; sum += a; if (sum >= v) break; sum -= b; ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 우선 피보나치 함수를 구현할 때는 두 가지 방식으로 구현을 할 수 있다. 첫번째 방식 - 재귀 문제의 코드처럼 계속해서 재귀적으로 함수를 호출해서 1 또는 0이 되게 만드는 방식이다. 그렇게 되면 만약 5라는 값이 함수에 들어오게 되면 fib(3)과 fib(4)로 나뉘게 되고 또 그 두 함수들도 계속 쪼개지다가 0과 1이 될 때, 함수 호출을 멈추게 된다. 그렇게 되면 했던 계산을 계속 되풀이할 뿐만 아니라 시간적으로도 엄청난 손해를 보게되는 방식이다. 두 번째 방식 (정답 코드) - DP 두..