Easy-So-Easy

백준 1259 문제(Problem) 풀이(Solution) 필자는 팰린드롬수와 같은 문제를 풀 때 문자열로 받아서 해결한다. 숫자로 받는 것보다 훨씬 편하니 문자열로 받는 걸 추천한다. 사용한 변수를 먼저 말하자면 다음과 같다. - s : 입력받은 문자열 - len : 입력받은 문자열의 길이 문제를 해결한 방법은 아래와 같다. 1. 문자열로 해당 입력을 받는다. 2. i가 0부터 len / 2까지 for문을 반복하여 s[i]와 s[len-i-1]가 다를 경우 팰린드롬수가 아니기 때문에 "no"를 출력한다. 3. 팰린드롬수이면 "yes"를 출력한다. 아래 코드를 보면 필자는 goto구문을 사용하여 더욱 용이하게 로직을 구현하였는데, "no"가 출력될 때는 "yes"가 출력되면 안 되니 goto 구문으로 f..

백준 10872 문제(Problem) 풀이(Solution) 팩토리얼 문제는 재귀함수의 대표적인 문제이다. 문제를 요약하자면 N! 를 구하는 건데, 혹시 이게 뭔지 모를 분들을 위해 설명하겠다. N! 는 N 팩토리얼로, 1 x 2 x 3 x 4 x ... x (N-1) x N 을 구하는 문제이다. 여기에서 사용한 함수는 fact함수로 재귀호출을 할 함수이다. 기저 조건은 n이 0일 때나 n이 1일 때 1을 반환하도록 하였고, n*fact(n-1) 로 계속 재귀적으로 호출하도록 함수를 만들었다. n*fact(n-1)은 다음과 같이 바뀐다. n * (n-1) * (n-2) * (n-3) * (n-4) * .... * 1 메인 함수에서 호출한 fact(n)이 위의 식이 되기에 바로 출력하면 된다. 전체 코드(..

백준 2231 문제(Problem) 풀이(Solution) 이 문제는 닥치는 대로 해보자는 용기를 가지고 있는 사람이라면 매우 쉽게 풀 수 있는 문제이다. 왜냐면 브루트포스 문제이기 때문이다. 이 문제를 요약하자면 M의 분해합이 N인경우, M을 N의 생성자라고 부르는데, N이 주어졌을 때 가장 작은 생성자를 구하고, 생성자가 없는 경우는 0을 출력하는 문제이다. M > n; for(int i=1; i

백준 2798 문제(Problem) 풀이(Solution) 이 문제는 브루트포스로 쉽게 풀 수 있는 문제이다. 문제에서 집고 가야 할 핵심 포인트는 'N장의 카드 중에서 3장의 카드를 뽑는다는 점'과 '고른 카드의 합은 M을 넘지 않으면서 최대한 가깝게'라는 점이다. 몇 장을 뽑아야 하는지는 이미 문제에서 나왔으니, 그리고 3장 밖에 뽑지 않으니 필자는 단순하게 3중 for문을 사용하였다. (3장 이상을 뽑아야 하거나 몇 장 뽑아야 하는지 나오지 않으면 재귀함수를 이용하는 것을 추천한다.) 각 케이스 마다 최대값과 비교하여 M을 넘지 않으면서 M에 최대한 가까운 값을 max 변수를 갱신함으로써 문제를 해결하였다. 번외: max 변수는 long long 타입으로 작성하지 않아도 된다. 하지만 필자는 최대값..

백준 2580 문제(Problem) 풀이(Solution) 이 문제는 빈칸의 위치를 배열이나 벡터에 따라 저장해놔야겠다! 고 생각이 들었다면 So-easy 하게 풀 수 있는 문제이다. 필자는 빈칸의 위치를 v라는 벡터에 따로 담아두었고, 이를 이용한 백트래킹을 사용하였다. 여기에서 사용한 함수는 func 함수와 check 함수이다. 각각 어떤 용도로 사용하였는지는 아래에 설명하겠다. void func(int n) { if(n==v.size()) { done=1; return; } int x=v[n].first, y=v[n].second; for(int i=1; i

백준 9663문제(Problem) 풀이(Solution) 이 문제를 풀기 전에 퀸이 움직일 수 있는 방향을 알아야 한다. 필자는 체스를 안한지 오래되어 찾아보았다. 퀸이 움직일 수 있는 방향은 아래 그림과 같다.(대각선 네 방향 + 상하좌우) 하지만 우리는 퀸보다 위에 있는 방향만 체크할 것이다. 왜냐면 백트래킹을 사용할 것이기 때문이다. 필자가 사용한 함수는 다음과 같다. - setting 함수: 퀸을 놓는 함수 - check 함수: 현재 위치에 퀸을 놓을 수 있는지 확인하는 함수 (매개변수 depth: y값이라고 생각해도 무방하다) 먼저, 퀸을 (0,0)자리에 놓을 수 있는지 check 함수를 통해 확인한다. 가능하다면 놓고, setting(depth+1)로 재귀 호출을 해준다. 여기에서 depth+..

백준 15652 문제(Problem) 풀이(Solution) 이 문제는 조합과 재귀함수를 이용하여 풀 수 있는 문제이다. 문제의 포인트는 같은 수를 여러번 골라도 되고, 수열은 사전 순으로 증가하는 순서로 출력해야한다는 점이다. 이는 재귀적으로 함수를 호출 할 때 인자값으로 pos를 보냄으로써 해결할 수 있다. 재귀적으로 호출할 함수는 func 함수이다. depth가 M이 되었을 때 즉, 조합이 M개 이루어졌을 때 해당 조합의 원소를 출력한다. func 함수의 인자값을 통해 받은 pos부터 반복문을 시작하여, 출력할 a배열을 업데이트 해주어 서로 다른 조합을 생성하였다. 이 문제는 재귀 함수를 통해 조합을 만들 줄 알기만 하면 어렵지 않은 문제이다. 코드(Code) #include using namesp..

백준 15651 문제(Problem) 풀이(Solution) 이 문제는 재귀함수와 조합을 이용하여 푸는 문제이다. 문제의 핵심 포인트는 같은 수를 여러번 골라도 되어 visited 배열을 통해 따로 사용 여부를 체크하지 않아도 된다는 점과 중복되는 수열을 여러 번 출력하면 안된다는 점이다. func 함수를 통해서 재귀함수와 조합을 이용하였다. depth가 M이 되면, 즉 func 함수가 M번 재귀 호출되면 arr 배열에 담아 있는 원소들을 출력하도록 코드를 구현하였다. 또한 func 안의 for문을 통해서 arr 배열에 원소를 계속 업데이트 해주었다. 이 문제는 15649번과 15650번 문제를 풀었다면 아주 쉽게 풀었을 문제이다. 코드(Code) #include using namespace std; i..