Twinparadox Factory

시간 제한 : 1 초메모리 제한 : 128 MB 문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 ..

시간 제한 : 1 초메모리 제한 : 128 MB 문제점심시간이 되면 반 학생 모두가 한 줄로 줄을 서서 급식을 탄다. 그런데 매일 같이 앞자리에 앉은 학생들이 앞에 줄을 서 먼저 점심을 먹고, 뒷자리에 앉은 학생들은 뒤에 줄을 서 늦게 점심을 먹게 된다. 어떻게 하면 이러한 상황을 바꾸어 볼 수 있을까 고민하던 중 선생님이 한 가지 방법을 내 놓았다. 그 방법은 다음과 같다.학생들이 한 줄로 줄을 선 후, 첫 번째 학생부터 차례로 번호를 뽑는다. 첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다. 두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다. 0번을 뽑으면 그 자리에 그대로 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다. 세 번째로 줄을 선..

시간 제한 : 2 초메모리 제한 : 128 MB 문제왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 입력아홉 개의 줄에 걸쳐 일곱 난쟁이의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다. 출력일곱 난쟁이의 키를 ..

힙(혹은 히프)은 최솟값(또는 최댓값)을 빠른 시간에 접근하게 만들어진 자료구조로, 최댓값을 접근하려면 최대힙을, 최솟값을 접근하려면 최소힙을 사용한다. 두 힙은 대칭적인 관계를 갖고 있기 때문에, 하나를 이해하면 다른 힙은 쉽게 이해할 수 있다. 힙에 대해 정확히 모르는 사람들을 위해서 이해를 돕기 위한 그림과 힙의 조건에 대해서 이야기를 잠깐 하겠다. 힙은 위 그림처럼, 각 노드의 값이 자식 노드들의 값보다 크거나 작은(클 경우 최대힙, 작을 경우 최소힙) 완전이진트리를 뜻한다. 거의 대부분이 정렬 파트를 다루면서 힙 정렬을 통해 이 구조에 대해서 아는 경우가 대부분이다. 오늘은 힙이 어떤 식으로 생겼는지 보는 것보다는, 힙 자료구조를 구성하는데 요구되는 시간복잡도가 O(n)인 것에 대해서 이야기를 ..

알고리즘 문제를 풀면서 접했던 문제 중 하나로 순서가 정해지지 않은(정렬되지 않은) 방대한 데이터를 입력 받아 특정 구간에서의 최솟값을 구하는 문제가 있었다. 하나씩 모두 비교하는 방법을 사용하는 건 구현은 간단하지만, 전체 구간에 대한 최솟값을 구하는 경우 O(N)의 시간 복잡도를 갖게 되고, 거기에 이러한 쿼리가 최대 M회 실시된다고 하면 O(NM)이며, 쿼리가 N에 근접하는 문제의 경우 O(N^2)의 시간 복잡도로 실행 시간 초과가 발생할 수 있다. 구간별 최솟값을 구해두고 쿼리에 대응하는 방법을 고안해도, 최초 구성 단계에서의 시간 복잡도의 문제가 있고, 내용을 바꾸는 쿼리가 존재한다면 재구성하는 과정에서 시간 투자가 필요하기 때문에, 아무래도 기존의 단순 비교 방식을 이용한 구간 내 최솟값 산출..

대부분의 문제는 테스트 케이스를 입력 받고 그 케이스에 따른 입력값을 받거나,테스트 케이스의 수를 제한하지 않는다고 하더라도 종료를 뜻하는 입력 값을 받는 경우가 대부분이다.그러다 간혹 테스트 케이스의 입력도 없고, 종료 조건도 명시되어 있지 않은 문제들이 있는데EOF의 개념이 없는 사람들은 간단한 문제(심지어 a+b)임에도 풀지 못하는 경우가 있다. 아래 문제는 테스트 케이스 개수나, 프로그램을 종료하는 특별한 입력값을 요구하지 않는다.EOF를 입력받을 때 프로그램을 종료하는데, C와 C++에서 이 EOF는 아래와 같이 처리할 수 있다. https://www.acmicpc.net/problem/10951 while(cin>>a>>b) while(scanf("%d %d",&a,&b)!=EOF)

이전 포스팅에서도 말했다시피, 일반적인 재귀 방법을 사용하는 건 시간이 오래 걸린다는 단점을 가지고 있다. 메모화재귀는 동적계획법을 재귀적으로 사용하는 것으로 동적계획법의 일종으로한 번 계산이 진행된 것은 추가로 진행하지 않는 것을 목표로 하기 때문에깊이 우선 탐색을 응용해 (1,1)에 하위에서 생성된 계산값을 미리 작성해두어만일 다시 접근이 이뤄지면 그 값을 반환시키는 것을 말한다. 깊이 우선 탐색을 통해서 일반적인 재귀 방법으로 접근했을 때 중복되는 작업들을 많이 걸러낼 수 있어서제한 시간 초과라는 문제를 극복할 수 있다. const int h = 5, w = 4; int Memo_recursion[h + 1][w + 1]; int dfs(int nowh, int noww) { if (nowh > h..

B A 아마 고교시절 순열조합 부분에서 자주 접하는 문제 중 하나로,A 지점에서 B 지점으로 갈 때 최단거리의 경우의 수가 얼마나 되는지 구하는 것이 목표인 문제다. 깊이우선탐색을 사용할 때, 모든 기점마다 경로를 선택해야 하고 이 경우 30번정도 그런 과정이 필요하다.따라서 Big O는 O(2^(w+h))가 되어 2^30인데 10억이 넘어가는 수치가 된다.연산 시간이 오래 걸려 썩 좋은 방법이 아니다. 우리는 이 문제를 고교시절 기계적으로 푸는 방법을 터득한 바 있다.바로 이항정리에 근거한 조합을 이용하는 방법이고9C4=126이라는 정답에 빠르게 근접할 수 있다.Big O 또한 O(w+h)로 계산량도 적어 매우 효율적으로 보인다.그러나, 이는 모든 지점을 통과할 수 있을 때나 가능하다는 제한적인 케이스..

입력 받은 배열을 O(n)으로 히프 트리 구조로 생성할 수 있지만, 여기서는 일단 O(nlogn)으로 진행되는 히프트리 구성을 실시했다. (이 부분에 대해서는 차후 포스팅할 생각) 최대 히프트리를 구현했고, 최대 히프트리를 바탕으로 오름차순 정렬을 하는 코드다. 내림차순 정렬을 보고 싶다면, list 배열에 넣는 인덱스 순서만 바꿔주면 되고 공부 삼아 최소 히프트리를 구현하는 것도 나쁘지 않을 것이다. 숙련자가 보기에는 이 소스는 잘 짜여진 소스는 아니라는 것을 말해주고 싶다. 처음 자료구조를 배우던 시절 구조에 대해서만 깨우치고 만든 소스라서, 불필요한 메모리 할당도 있고 히프 트리 구성에서 시간 복잡도 손실을 보기는 하지만, 히프트리를 바탕으로 힙정렬(혹은 히프정렬)을 구현하는 것까지는 문제되지 않아..

https://www.acmicpc.net/problem/7576 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를..