발자취

문제 : 컴퓨터 바이러스는 네트워크를 통해 전파된다. 만약 한 컴퓨터가 바이러스에 걸리면, 그 컴퓨터와 네트워크로 연결되어 있는 모든 컴퓨터는 바이러스에 감염되게 된다. 위의 사진은 주어지는 네트워크와 컴퓨터의 구조를 예시로 든 것이며, 위의 경우에는 1번 컴퓨터가 감염되었을 때 2,3,5,6 컴퓨터가 감염이 가능한 것을 알 수 있다. 여기서, 1번 컴퓨터가 바이러스에 감염되었을 때, 1번 컴퓨터를 통해 감염될 수 있는 컴퓨터의 수를 구하시오. 입력 : 첫째 줄에는 컴퓨터의 수, 두번째 줄에는 컴퓨터 간의 네트워크 수, 마지막으로 그 수만큼 한 줄에 한 쌍씩 연결되어 있는 컴퓨터 쌍이 주어진다. 예시) 7 6 1 2 2 3 1 5 5 2 5 6 4 7 출력) 4 이 문제는 간단한 DFS 문제이다. 사실 ..

문제 : 원래 맞춰져 있던 알람을 45분 일찍 출력하게 하면 된다. 시간의 표현법은 24시 이며, 자정은 0:0 이고 끝은 23:59 이다. (자정 1분 전) 입력 : 첫째 줄에 시간과 분 이 공백을 기준으로 입력된다. 입력과 출력은 모두 24시 표현이며, 불필요한 0은 사용하지 않는다. 예시) 입력 : 10 10 , 출력 : 9 25 간단한 사칙연산 문제이다. 조금만 생각을 해보면 누구나 풀 수 있다고 생각한다. 이 문제에는 경우의 수를 나눌 수 있다. 자리빌림 없이 바로 뺄 수 있는 경우 (0 50) , 자리를 빌려야 하는 경우 (1 10), 하루가 넘어가는 경우 (0 10) 으로 나눌 수 있다. 첫 번째 경우에는 45분을 뺀 것을 바로 출력하면 된다. 그렇다면, 자리를 빌려야 하는 2번째 경우는 어..

문제 : 10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오. 셀프 넘버란? 1949년 인도 수학자 D.R.Kaprekar 가 만든 것이다. 양의 정수 x에 대해 d(x) 를 x와 x의 각 자리수를 더하는 함수라고 정의 한다. 예를 들어 44는 44+4+4=52 이고, 52는 52+5+2=59 이다. 이런 식으로 계속 진행할 경우, x를 d(x) 의 생성자라고 정한다. 52는 59의 생성자이고, 44는 52의 생성자이다. 이같은 함수를 정의할 경우, 생성자가 없는 숫자를 셀프 넘버라고 정의한다. 이 문제의 알고리즘 분류를 볼 때, 에라토스테네스의 체를 이용하라고 나온다. 즉, 이 알고리즘을 사용해야지 메모리 제한이나 시간 제한에 걸리지 않는다는 것이다. (에라토스테네스의..

문제: N개의 숫자가 공백 없이 쓰여있고, 이 숫자를 모두 합해서 출력하는 프로그램을 작성한다. 주어진 것 : 첫째 줄에 숫자의 개수 N 이 주어지고, 둘째 줄에 숫자 N개가 공백없이 주어진다. 그리고 숫자 N 개의 합을 출력하자. 언뜻 듣기에는 간단해 보인다. 주어진 숫자를 모두 더하면 되는 것 같다. 하지만 C 언어 에서는 문자열 처리가 다른 언어에 비해 약간 까다롭기 때문에, 만만히 보면 안된다. 나는 getchar 함수를 이용하여 숫자를 각각의 자릿수대로 받게 하였다. scanf 함수는 숫자를 한번에 다 받아버린다. 하지만 getchar는 각 자릿수를 따로 받기 때문에 이 문제에 적합한 함수이다. 예) 100을 입력 scanf 는 100을 받지만, getchar 는 1만 받는다. getchar 를..

문제 : 정수 n이 주어졌을 때, n 을 1,2,3 의 합으로 나타내는 방법의 수를 구하는 프로그램을 만들어라. 예시) 4를 1,2,3의 합으로 나타내는 방법은 7가지가 있다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 입력) 첫째줄에 테스트 개수 T 가 주어지고, 각 케이스는 1줄, 출력은 각 경우당 1줄 출력한다. 나는 이 문제를 동적 계획법으로 풀었다. 여러가지 해결법이 있었으나, 가장 합리적으로 보였다. (동적 계획법이란, 문제를 해결하기 위해 이전의 데이터를 이용하는 경우 메모리 어딘가에 저장해 두었다가 다시 꺼내와서 계산하는 방식이다. 주로 배열을 이용한다. 이 방식을 이용하면 함수를 부르는 것에 비해 컴퓨터 자원을 적게 소모하게 된다.) 1일 경우를 생각해보면, 1밖..

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나누어 준다. X가 2로 나누어 떨어지면, 2로 나누어 준다. 1을 빼준다. 이 때 정수N이 주어졌을 때 위 연산 세 개를 적절히 이용해 1로 만들려 한다.이러한 규칙이 적용되었을 때, 연산을 사용하는 횟수의 최솟값은? 조건: 1보다 크고 10^6보다 작은 정수 1개가 입력된다. 예) 2입력, 1출력 (2-1) 10 입력, 3 출력 (10-9-3-1) 나는 이 문제를 다이나믹 프로그래밍으로 풀었다. 문제를 풀기 위한 기법은 BFS 등 여러가지 방법이 있으나, 문제에 접근하기 쉬운 방법으로 풀어 보았다. 몇 가지 예를 들어서 생각해보자. 2-13-14-2-15-4-2-16-2-17-6-2-18-4-2-19-..

문제: a,b,c 가 주어졌을 경우에 Ax+Bsin(x)=C 를 만족하는 x를 찾으면 된다. 단, 0

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 ..

문제 : 두 개의 자연수를 입력받아 최대공약수와 최소공배수를 출력하는 프로그램을 작성하시오. 최대공약수와 최소공배수를 출력하는 문제입니다. 최대공약수의 정의는 두 수를 나누어 나머지가 0이 되게 하는 수 중 가장 큰 수이고, 최소공배수는 두 수의 공통의 배수 중 가장 작은 수를 의미합니다. 저는 유클리드 호제법이라는 알고리즘을 사용할 것 입니다. 예를 들어 12와 40의 최대공약수를 구한다면, 40%12=4 //피연산자와 나머지를 12%4=0 //연산자와 피연산자로 이동해줍니다. 그리고 0이 될때까지 이 과정을 반복합니다. 나머지가 0이 될 때, 그 때의 피연산자가 최대공약수 입니다. 그럼 최소공배수는 어떻게 구할까요? 간단합니다. 두 수의 곱/최대공약수 입니다. 이걸 이용하면 계산을 반복할 필요도 없고..

문제 : M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 소수를 구하는 알고리즘은 여러 가지가 있습니다. 하지만 이 문제는 2초라는 시간제한이 있습니다. 그렇기 때문에 가장 효율적인 알고리즘을 채택해야 합니다. 예를 들어 수 하나(n)가 주어졌을 때 2부터 (n-1) 까지 나누어 본다 하면 연산횟수는 n-2 번이 될 것입니다. 하지만 나오는 수마다 일일이 계산한다면 연산은 배로 많아질 것이고, 이는 효율적이지 못합니다. (실제로 일일이 계산하면 시간초과가 뜬다) 에라토스테네스의 채를 이용합니다. 이 알고리즘을 사용하면 시간복잡도를 줄일 수 있습니다. 2를 제외한 2의 배수를 삭제, 3을 제외한 3의 배수를 삭제... 이런 식으로 나아가면 소수만 남게 됩니다. 수가 여러개 주어졌을때도 배열에 ..