Optional

✅️[문제/problem] https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ✅️[풀이/Explanation] 백트래킹 문제이다. 재귀함수랑 백트래킹은 유사성이 크다. 일단 isarr 배열로 1~n까지의 숫자가 쓰인 여부를 체크한다. arr 배열은 숫자를 저장할 배열이다. 종료 조건은 k == n일때 숫자를 출력하고 return;을 반환한다. ✅️[코드/code] #include using namespace std; int n,m; bool i..

✅️[문제/problem] https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net ✅️[풀이/Explanation] 재귀 문제이다! 종료 조건(base_condition)은 n=3일때 그리고, 종료한다. 그림에서 가로는 n, 세로는 n/2 인걸 알 수 있다. (x,y) 기준으로 재귀적으로 3개의 삼각형을 그려주면 되는데, (x+n/2, y), (x, y+n/2), (x+n/2, y+n)의 좌표를 호출하면 된다! memset으로 배열을 공백으로 초기화하고 별을 찍을때 *값을 대입했다. ✅️[코드/code]..

✅[문제/Problem] https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ✅[풀이/Explanation] BFS 문제이다. 단순히 for 문을 돌려 1일때 큐에 좌표값을 넣고, BFS를 돌려 넓이 값을 벡터에 넣어주면 된다. 주의할 점은 입력을 받을때 숫자가 띄어져 있지 않으므로, 문자열에 입력받아야 한다. 이것이 은근 헷갈린다. 마지막으로인자를 넣은 벡터의 사이즈와 배열 값을 출력한다. The solving method is to use BFS..

✅️[문제/Problem] https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net ✅️[풀이/Explanation] 재귀 문제이다. 재귀 문제를 풀때 baseConditon(종료 조건)과 n, n+1일때 풀이에 집중해야 한다. 종료 조건은 처음 주어진 수와 반복문 내에서 배열 값이 같지 않을때 종료하도록 한다. 재귀함수에서 n/2를 호출하여 좌표값을 부르면 된다. Solving method is the recursive fu..

✅️[문제] https://www.acmicpc.net/source/47203953 로그인 www.acmicpc.net ✅️[풀이] BFS 문제이다. 입력받은 좌표에 대해 arr의 값을 1씩 증가시키고, arr이 0인 것에 대해 BFS를 돌려 횟수를 증가시킨다. ✅️[코드] #include using namespace std; #define X first #define Y second int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; int main(){ ios::sync_with_stdio(0); cin.tie(0); int m,n,k; cin >> m >> n >> k; int arr[m][n]; bool vis[m][n]; memset(arr, 0, sizeof(..

✅️[문제] https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net ✅️[풀이] 재귀 문제이다! 재귀 문제를 풀때에는 수학적 귀납법을 이용하면 된다. 수학적 귀납법은 k=1이 성립하고, k와 k+1이 성립하면 식은 참이 된다. 이 문제에서 b가 1일때 나머지를 구할수 있고, 2b와 2b+1의 나머지를 구할 수 있다. 즉 b가 1일때는 a%c를 리턴하고, b/2를 재귀적으로 호출한다. 이때 b/2가 홀수라면, a를 한번 더 곱하여 나머지를 리턴하고, 짝수라면 그냥 나머지를 리턴하면 된다. ✅️[코드] #include ..