링크 : 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/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/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번: 최대공약수와 최소공배수 첫째 줄에..

링크 : https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 문제 풀이 나의 설명보다는 아래 링크를 참고하는것이 훨씬 좋을 것 같다. 유클리드 호제법을 활용하면 된다. https://sectumsempra.tistory.com/77 [백준2609]-최대공약수와 최소공배수(C++)/유클리드 호제법 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. ..

링크 : https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 문제 문제 풀이 나는 좀 다르게 풀었는데, 정석적인 방법은 "육각형이므로 가로, 세로의 최댓값이 나온 시점에서 '가로의 index에서 +3, +4 index의 요소들이 작은 사각형의 가로, 세로'" 라고 한다. 그림을 그려보니 아~ 그렇네 싶지만 솔직히 어떻게 발견하나 싶다. 일단 알아만 두어야겠다. point라는 별개의 배열을 만들어서 동서남북이 1, 2, 3, 4로 주어진다 했으니 ..

링크 : https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 문제 풀이 난항을 겪었던 문제다. 어떻게 풀어야할지는 대충 감이 오는데, 구현이 잘 되지 않아 시행착오를 많이 겪었다. 체스판이 W, B 둘 중 하나의 패턴으로 시작한다. 가만히 생각해보면, W나 B가 맨 왼쪽 상단에 있을 때 W와 B의 위치가 정해지는 규칙이 나온다. W가 (0, 0)에서부터 시작한다고 가정하면 (0, 2), (0, 4), (1, 1), (1, 3) ... ..