728x90 재귀7 [python] 백준 7490 0 만들기 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 문제 해결 처음 보았을 때 많이 당황스러운 문제였다. 1부터 N까지 덧셈, 뺄셈, 이어붙이기로 각각 계산 따라서 1부터 시작하여 +, -, 이어 붙이기 중 한 가지를 선택한 후 다음 수 2를 붙인다. 이와 같은 일을 N번 반복하므로 재귀를 이용하여 풀 생각을 한다. 필요한 변수는 sum: 1부터 n-1까지 합 (후에 1부터 N까지 합이 0이 되었을 때만 확인하면 되므로) sign: 1이면 덧셈, -1이면 뺄셈, sign 그대로이면 이어 붙이기로 판별.. 2023. 9. 7. [C++] 백준 10451 순열 사이클 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 문제 해결 재귀를 이용해 사이클을 조사하는 것이다. 사이클이 만들어 지는 것을 확인 했으면 다음 만들 수 있는 것을 확인하는데 사이클 만들어지는데 구성 된 숫자는 다음 사이클을 만들 때 구성 될 수 없으므로 visited를 이용해 이미 구성 되었는 지를 확인하도록 한다. CODE #include #include using n.. 2023. 9. 3. [python] 백준 1736 쓰레기 치우기 https://www.acmicpc.net/problem/1736 1736번: 쓰레기 치우기 방은 세로 N, 가로 M (1 ≤ N, M ≤ 100) 크기의 격자 판으로 표현할 수 있다. 왼쪽 위의 위치를 (0, 0)이라 하고, 오른쪽 아래를 (N - 1, M - 1)이라고 하자. 이 판의 몇몇 칸에는 쓰레기가 놓여 있다. 쓰레 www.acmicpc.net 문제 해결 N*M행렬 중 행렬 값이 1인 행,열을 0으로 바꾸는 과정이라고 생각하면 된다. 그렇지만 움직이는 방향은 →,↓ 두 가지로 생각하면 된다. 재귀를 이용해서 1인 행렬값을 0으로 만들어가며 영행렬을 만들 수 있다. 깊이 너비 탐색(dfs)를 최소한으로 했을 때의 개수를 구하면 될 것이다. 사실 아이디어를 생각하기 너무 어려웠고 아이디어를 참고를.. 2023. 5. 13. [python] 백준 12919 A와 B 2 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 문제 해결 처음에 S->T로 만드는 BFS 함수를 생각했다. 하지만 메모리초과, 시간초과 나오는 것을 보고 다른방법을 생각하게 되었다. 이전에 긴 문자열에서 짧은 문자열을 만드는 풀이가 생각이 났다. 역시 문자열을 만드는 것은 긴 문자열에서 짧은 문자열로 생각하는 것이 정답이다.(그래야 비교할 경우의 수가 줄어든다.) CODE S = str(input()).. 2023. 4. 5. 이전 1 2 다음 728x90