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

링크 : https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 문제 풀이 이항 계수는 팩토리얼로 풀어쓸 수 있고, 이는 아래와 같으므로 그대로 구현하면 된다. 파이썬은 math 함수를 사용했다. C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python 코드 전문 HTML 삽입 미리보기할 수 없는 소스 소감

링크 : https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 문제 문제 풀이 기약분수로 출력해야 해서 생각할 여지가 있는 문제다. 그래도 이때까지 gcd를 활용했으면 최소공배수로 숫자를 나눠서 출력하면 나오겠다는 생각이 바로 들 수 있을 것이다. 참고하면 좋을 강좌를 첨부한다. https://sectumsempra.tistory.com/77 [백준2609]-최대공약수와 최소공배수(C++)/유클리드 호제법 https://www.acmicpc.net/problem/2609 2609번:..

링크 : https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 문제 문제 풀이 문제 그대로 구현하면 시간초과가 날 것 같고, 솔직히 어떻게 접근해야할지 몰라서 인터넷 검색을 통해 알게 된 문제다. 내 설명보다는 아래 첨부한 링크들을 참고하는것이 훨씬 도움이 될 것 같다. 나중에 제대로 공부하고 다시 풀이를 써야겠다. https://pangsblog.tistory.com/62 [백준 2981] - [수학 최대공약수] - 검문 (JAVA) 문제 링크 : https://..

링크 : https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 문제 문제 풀이 앞선 문제와 거의 같은 문제다. 같은 알고리즘인 유클리드 호제법을 사용하면 된다. 참고하면 좋을 강좌도 첨부한다. https://sectumsempra.tistory.com/77 [백준2609]-최대공약수와 최소공배수(C++)/유클리드 호제법 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에..