본문 바로가기

C++ 코딩 문제 풀이151

[Baekjoon] 1912번: 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 해결 과정 착안 주어지는 임의의 수열 내의 연속된 숫자들의 합 중에서 가장 큰 값을 찾아야하는데, 이때 몇 개의 연속된 숫자의 합이 최대일지는 알 수 없으므로 반복적으로 연속합을 구하고 비교하는 것을 요구한다. 따라서 기존에 구해놓은 연속합의 값을 저장하고, 추가적인 연속된 숫자를 입력받으면 더해서 비교한 뒤 필요하면 다시 저장하여 사용하는 방식으로 동적계획법(dynamic programming) 알고.. 2023. 5. 18.
[Baekjoon] 9184번: 신나는 함수 실행 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 해결 과정 착안 구하고자 하는 값이 어떠한 점화식의 형태를 이용하여 구해지도록 함수를 구현해야 하므로, 동적계획법(dynamic programming)을 사용하여 구현해보고자 하였다. 구현 메모이제이션에 사용할 배열들을 편의상 전역 변수로 만들어 모든 함수에서 접근 가능하도록 구현하였다. * int result[21][21][21] : 계산한 값을 저장. * bool computed[21][21.. 2023. 5. 17.
[Baekjoon] 24416번: 알고리즘 수업 - 피보나치 수 1 https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어진 의사 코드를 그대로 구현하여, 피보나치 수열(Fibonacci sequence)의 \(n\)번째 항을 구하기 위한 재귀 호출(recursive call, recursion)을 통한 계산에서의 코드 1의 실행 횟수와 동적계획법(dynamic programming)을 통한 계산에서의 코드 2의 실행 횟수를 각각 출력한다. * 참고) 경우에 따라, 피.. 2023. 5. 16.
[Baekjoon] 15652번: N과 M (4) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 과정 착안 1부터 \(N\)까지의 자연수를 중복을 허용하되, 비내림차순을 만족하는 순서로 뽑아 수열을 만든다. 따라서 다음 항을 구하는 함수를 실행할 때, 현재 항보다 큰 숫자로만 구할 수 있도록 조건문을 추가하고자 하였다. 이후, 수열의 길이가 \(M\)이 될 때까지 재귀를 통해 수열을 만들고 길이가 \(M\)이 되면 출력한다. 구현 이전 포스트의 코드와 대부분 유사하여 이전 포스트.. 2023. 5. 15.
[Baekjoon] 19532번: 수학은 비대면강의입니다 https://www.acmicpc.net/problem/19532 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 문제 해결 과정 착안 연립일차방정식(system of linear equations)은 행렬의 곱셈의 정의에 의하여 행렬 형태로 나타낼 수 있다. $$a_{11} x_{1} + a_{12} x_{2} + \cdots + a_{1n} x_{n} = b_{1}$$ $$a_{21} x_{1} + a.. 2023. 5. 14.
[Baekjoon] 15651번: N과 M (3) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 과정 착안 1부터 \(N\)까지의 자연수를 중복을 허용하여 뽑아 수열을 만든다. 만들어지는 모든 수열을 출력해야하므로 수열의 길이가 \(M\)이 될 때까지 재귀를 통해 수열을 만들고, 길이가 \(M\)이 되면 출력한다. 구현 이전 포스트의 코드와 대부분 유사하여 이전 포스트의 코드를 수정하여 문제를 해결하였다. 중복된 수를 다시 뽑는 것이 가능하므로, Visited 여부를 확인할 필요.. 2023. 5. 13.

티스토리툴바