링크 : https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 문제 문제 풀이 fib(n) { if (n = 1 or n = 2) then return 1; # 코드1 else return (fib(n - 1) + fib(n - 2)); } 코드 1은 return 1이다. 그런데 잘 생각해보면 이 피보나치 함수는 1의 합으로 피보나치 수를 구하게 된다. 어차피 숫자는 1밖에 없기 때문에 바로 알아챌 수 있다. 그렇다면 코드 1은 n의 ..

링크 : https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 문제 풀이 우선 스도쿠의 규칙에 따르면 체크해야 할 조건이 두 가지가 있다. 같은 행, 열에 같은 숫자가 존재하면 안된다. 속해있는 3x3 정사각형 안에 같은 숫자가 존재하면 안된다. C++ 상세 풀이 더보기 다양한 풀이가 있겠지만 나는 백트래킹 방법, 그 중에서도 9 x 9칸을 해결할 때까지 순회하는 방법을 사용했다. for (int i = 0; i < 9; ++i) for (in..

링크 : https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 문제 풀이 백트래킹 문제이며, 우선 팀을 반으로 어떻게 나눌까? 하는 생각에서 출발하게 된다. C++ 상세 풀이 더보기 2차원 벡터에 행렬을 담아주었다. N이 4에서 20까지이므로 visited 배열을 크기 20으로 설정해 전역으로 선언해두었다. C++ 코드 void dfs(std::vector &v, int cur, int idx) { // cur이 N / 2와 같다면 한 팀에 총 인원의 반이 담겨졌다..

링크 : https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 문제 풀이 우선 나는 문제 접근을 하나씩 다 해보는건 어떨까? 하는 생각에서 시작했다. 연산자의 우선순위는 생각하지 않는다고 했으니 첫번째부터 차근차근 사칙연산을 하면 성공할 것 같다고 생각했다. C++ 상세 풀이 더보기 원래 전역변수를 남발하는 것은 좋지 않다고 배워서 쓰지 않으려고 노력했는데, 항상 백트래킹 문제를 풀다 보면..

링크 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 문제 풀이 유명한 백트래킹 문제다. 옛날에 알고리즘을 공부할 때 접해본 적이 있어 빨리 풀었지만, 아마 처음 접했다면 시간을 엄청 오래 썼을 것 같다. 우선 N-Queen 게임에 대한 이해가 필요하다. 퀸의 특성상 체스판 한 행에 한 개의 퀸만 존재할 수 있다. 서로 다른 퀸은 대각선상에 존재할 수 없다. 한 행씩 퀸을 배치하면서 총 배치 횟수가 N이 된다면 모두 배치를 성공했다는 뜻이므로 해당 변..

링크 : https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 문제 풀이 앞선 문제들(N과 M (1), N과 M (2), N과 M(3))과 같은 맥락을 공유하는 문제다. 특히 N과 M(3)과 아주 유사하다. C++ 상세 풀이 더보기 전 문제와 유사하게 해당 문제는 굳이 visited를 사용할 필요가 없다. 비내림차순으로 출력하면 된다고 했으니, C++의 경우는 간단하게 이전 숫자와의 크기를 비교하도록 조건문을 하나 추가해준다. if (v[va..

링크 : https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 문제 풀이 앞선 문제들(N과 M (1), N과 M (2))와 같은 맥락을 공유하는 문제다. 이번 문제는 같은 수를 여러 번 골라도 된다는 조건이 붙어있다. 그래서 굳이 visited를 사용할 필요 없이, 그냥 dfs를 통해서만 해결하면 된다. (자세한 풀이는 N과 M (1) 문제를 참고해주세요.) for (int i = 1; i

링크 : https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 문제 풀이 N과 M (1)과 거의 유사한 문제다. (자세한 풀이는 N과 M (1)을 참고해주시길 바랍니다.) 핵심적인 부분은 거의 같지만 오름차순이어야 하기 때문에 dfs 안에서 for문을 돌 때 i를 dfs에 다시 인수로 넣어주고, 해당 인수부터 다시 for문을 돌리도록 하면 자연스레 오름차순이 된다. C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python 코드 전..

링크 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 문제 풀이 백트래킹 + DFS 문제다. 수열은 사전 순으로 증가해야 하며, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열이므로 DFS를 활용하면 되겠다는 생각이 들었다. C++과 파이썬의 풀이가 살짝 다르지만 이번 문제는 모든 분이 C++ 상세 풀이를 보시면 도움이 될 것 같습니다. C++ 상세 풀이 더보기 void dfs(std::vector &v, int N, int..

링크 : https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 문제 풀이 이전 문제와 비슷한 유형의 문제지만, 문제 조건에 정수 범위가 2,000,000,000이므로 조금 다른 알고리즘을 써야 하는 문제다. nCm = n! / (n-m)! * m! 이므로, 팩토리얼의 0의 개수를 구했던 것처럼 n!, (n-m)!, m!의 2와 5의 개수를 구하면 되는 문제이다. 어떻게 구하느냐가 관건인데, 이는 간단한 반복문을 통해 구할 수 있다. N!에서 k의 지수 개수를 구하는 방법은 k^i로 N을 계속 나눠주면 된다. 아래 예시들을 보자. ..

링크 : https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 문제 풀이 나의 수학실력에 다시 한번 감탄하게 된 문제다. 분명 난이도는 실버 5인데 풀리지가 않아서.. 당연하게도 N이 500까지이므로 N!을 직접 구해 해결하는 방법은 불가능하다. 이 문제의 핵심은 뒤에 0이 나오는 경우는 10이 곱해졌을 때라는 것을 알아차리는데에 있다. 그렇다면 0의 개수는 어떻게 구할까? 10의 0의 갯수는 1개이고, 이는 2 x 5다. 100에서 0의 갯수는 2개이고, 이는 2 x 2 x 5 x 5다. 200에서 0의 갯수는 2개이고, 이는 ..

링크 : https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 문제 문제 풀이 풀이는 이 분이 간단하게 잘 말해주셨다. 중고등학생 때 많이 하던 수학 문제다. 구현을 하는 법은 이전에 해왔던 대로 C++은 map을 활용해서, 파이썬은 dict나 Collections를 사용하면 된다. 아래의 코드는 Counter을 사용했는데, dict를 사용하면 values에..