링크 : 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에..

링크 : https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 M - N; --i) { res = res * i; res = res / tmp++; } C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python..

링크 : https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 문제 풀이 그냥 풀면 N, K가 제한이 1000이므로 시간초과가 나는 문제이다. DP를 활용해야 하는 문제인데, 동적 계획법 파트에 있었으면 좋았을 것 같은 문제다. 이항 계수의 점화식은 아래 사진과 같다. 여기서 dp[1][1], dp[1][0]은 미리 1로 초기화해 주고 시작하면 된다. 파이썬은 바로 % 10007해도 괜찮다. 내장 함수의 힘인 것 같다. C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python 코드 전문 HTML 삽입 ..