발자취

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 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의 배수를 삭제... 이런 식으로 나아가면 소수만 남게 됩니다. 수가 여러개 주어졌을때도 배열에 ..

문제 : https://www.acmicpc.net/problem/10250 간단히 말하면, H x W (세로 x 가로) 개수의 호텔방이 있고 왼쪽 아래부터 위쪽으로 채우고, 다 채우면 오른쪽 1층부터 다시 채워나가는 방법 입니다. 층수는 H를 C로 나눈 나머지가 됩니다. 단 나머지가 0일 경우에는 H를 출력해야 합니다. 호수는 H를 C로 나눈 몫+1 이 됩니다. 단 나누어 떨어지는 경우는 몫을 출력합니다. 이 생각을 기반으로 해서 코드를 짜 보았습니다. 1234567891011121314151617181920212223242526#include int main(){ int num,H,W,C,Front,Back; scanf("%d",&num); for(int i=0;i

문제 : N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하시오. 예) N=3일때 나머지와 몫이 같은 자연수는 4하고 8이므로, 답은 12이다. 이 문제는 간단한 점화식으로 풀이가 가능합니다. N=2 일경우 3이 가능하고 N=3 일경우 4하고 8이 가능합니다. N=4 일경우 5하고 10하고 15가 가능합니다. 그럼 여기서 점화식을 유추해 볼 수 있습니다. 문제의 답은 조건을 만족하는 모든 자연수의 합 이므로 N에 대한 점화식은 으로 유추해 볼 수 있습니다. (1부터 N-1까지 더한 수에 N+1 을 곱한다.) 더 간단히 나타내야 하는데, 프로그래밍으로 유추하다 보니까 코드가 조금 보기 이상해졌습니다. (함수 dd 를 만들어 유추해서 만들다가 코드가 더러워짐ㅠ) 123456789101112131..

문제 : 영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어집니다. 이 문자열의 단어의 개수를 구하세요. 단어는 띄어쓰기로 구분합니다. 문자열 앞 뒤에 공백이 있을 수 있습니다. 제 문제 해결법은 이렇습니다. 이 문제는 문자열을 받는 문제이므로 fgets 함수를 쓰겠습니다. 그리고 맨 앞에 있을 수 있는 공백을 따로 처리해줍니다. 마지막으로, 공백이 여러 개 붙어 있을경우 세지 않는단 조건을 추가해 줍니다. 123456789101112131415161718192021222324252627282930#include int main(){ int count,i=0; char array[1000001]; fgets(array,sizeof(array),stdin); if(array[0]==' ') { count..

문제 : 설탕봉지는 3kg과 5kg 봉투가 있습니다. 설탕을 배달할 때에 정확히 n kg 배달해야 하고, 최대한 적은 봉투를 써야합니다. 예를들어, 18kg 의 설탕을 배달할 때에 3kg 6개를 들고가도 되지만 5kg 3개와 3kg 1개를 들고가면 적은 봉투로 배달이 가능합니다. 또한, 4kg 같이 3kg봉투와 5kg봉투로 꽉 채우지 못하거나 남는 경우에는 배달이 불가능합니다. 이 때는 -1을 출력합니다. 이 때, n kg의 설탕을 배달할 때 최소로 필요한 봉투의 개수를 출력하세요. 나의 접근법은 이러하다. (내 생각도 중요하지만 당신의 생각도 중요합니다. 내가 무조건 정답은 아닙니다.) n이 5의 배수일경우엔 n/5를 출력하면 된다. 5kg의 봉투로 다 담아서 배달하면 가장 최소가 되기 때문이다. 괜히..

< 문제 : Hello World! 를 출력하시오. 이 문제는 어떠한 프로그램 문제든 간에 가장 기초가 되는 문제이다. c언어 에서는 printf 함수를 사용해서 문제를 풀어보자. 123456#include //stdio.h 헤더 불러오기 int main(){ printf("Hello World!"); //Hello World! 출력}Colored by Color Scriptercs