발자취

알고리즘 문제 중에서는 매우 유명한 N-Queen 문제다. 문제는 다음과 같다. 크기가 NxN인 체스판에 N개의 퀸을 둔다. 퀸은 서로 공격할 수 없는 상태여야 한다. 이때, 퀸을 배치할 수 있는 경우의 수를 출력하시오. 이 문제는 백트래킹을 이용하여 풀 수 있는 문제이다. 백트래킹 알고리즘은 초보자에겐 어려울 수 있으나, 필수적으로 알아야 할 알고리즘이다. 백트래킹 알고리즘을 간단히 정리하면 "가능성이 없는 경우에 대해선 탐색을 하지 않는다" 이다. 즉, 모든 경우에 대하여 탐색을 하지 않고 가능성이 있는 경우에 대해서만 탐색을 하여 답을 찾는것이 이 문제의 목표이다. 이러한 생각으로 문제를 다시 풀어보자. 나는 체스를 모르기 때문에, 퀸이 공격할 수 있는 경우부터 알아보자. 퀸은 가로 세로 대각선 모..

문제의 내용은 간단합니다. 세 자릿수의 수와 세 자릿수의 곱을 다음과 같은 방법으로 계산해야 한다고 생각합시다. 이 때 1과 2의 숫자가 주어지면, 3,4,5,6의 숫자가 차례대로 나오게 하면 되는 문제입니다. 먼저 숫자 1과 2를 받아야 다음 수를 계산할 수 있겠죠. 두 개의 수를 받아줍니다. 문제는 3번 부터 어떻게 해결해 나가는 것이지요. 천천히 생각해 봅시다. 3번의 숫자는 숫자 1과 2의 첫 번째 숫자를 곱한 결과 입니다. 이에 대한 방법은 2에 10을 나눈 나머지랑 곱하게 하면 됩니다. 그렇게 하면 3을 도출할 수 있습니다. 이제 4를 출력해야 합니다. 숫자 4는 1과 2의 두번째 자리를 곱하면 됩니다. 그렇다면 2에서의 두번째 자리를 추출해야 하는데, 어떻게 해야 할까요? 답은 간단합니다. ..

(c언어를 기준으로 하여 풀이를 하겠습니다.) 먼저 문제에 나와있는 윤년의 정의는 이렇습니다. 연도가 4의 배수인 동시에 100의 배수가 아닐 때 또는 400의 배수일 때 이다. 처음 들으실 때는 헷갈리기 쉬운 문장입니다. 하지만 천천히 짚어 보면 어렵지 않은 기초적인 문제입니다. 문제에 나온 문장을 하나씩 되짚어 봅시다. "연도가 4의 배수인 동시에 100의 배수가 아닐 때" -> 4의 배수면 4로 나누었을 때 나머지가 0일 것이고, 마찬가지로 100의 배수면 100으로 나누었을 때 나머지가 0일 것 입니다. 즉, 비교 연산자를 사용하여 표기하면 x%4==0&&x%100!=0 이 됩니다. (여기서 x는 연도 입니다.) 4의 배수인 경우인 동시에, 100의 배수인 경우를 먼저 걸러 줍니다. "또는 400..

문제 : 컴퓨터 바이러스는 네트워크를 통해 전파된다. 만약 한 컴퓨터가 바이러스에 걸리면, 그 컴퓨터와 네트워크로 연결되어 있는 모든 컴퓨터는 바이러스에 감염되게 된다. 위의 사진은 주어지는 네트워크와 컴퓨터의 구조를 예시로 든 것이며, 위의 경우에는 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