본문 바로가기
728x90

Baekjoon/[Code.plus] 알고리즘 기초 2／261

[BOJ/백준] 10972 다음 순열 ● [문제번호 10972] 다음 순열 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net ● 알아야 할 것 : NULL ● 풀이 과정 : 브루트 포스로 구현해보려고 고민했지만, 재귀를 이용하면 깊이가 10,000 이나 되어서 '메모리 초과' 가 나올 것 같고, 반복문을 이용하자니 N 값을 몰라 수월한 방법이 떠오르지 않아서, 수열에 대해 분석을 해보았다. : 기존 수열에서 다음 수열로 어떻게 바뀌는 지 분석하니, 1. 기존 수열의 맨 오른쪽부터 하나씩 {왼쪽 원소} < {오른쪽 원소} 인지 검사한다. 2. .. 2021. 9. 2.
[BOJ/백준] 9095 1, 2, 3 더하기 ● [문제번호 9095] 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ● 알아야 할 것 : DP 문제집에 있는 문제 https://pirateturtle.tistory.com/202 ● 풀이 과정 : DP의 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → 각 index의 값은 1, 2, 3의 합으로 나타내는 방법의 수를 나타낸다. 2. 점화식 찾기 → dp[index] = dp[index - 1] + dp[index - 2] + dp[index - 3] dp[index]는 dp[index - 1] 에서 구한.. 2021. 9. 2.
[BOJ/백준] 1748 수 이어 쓰기 1 ● [문제번호 1748] 수 이어 쓰기 1 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) : 숫자 → 문자 변환 방법 : {math헤더 - pow(a, b)} a의 b제곱 ● 풀이 과정 : string 문자열을 이용하여 간단하게 구현하면 '메모리 초과' 결과가 나온다. 조금 더 고민하니 약간의 규칙이 있어서 수학적 계산만 하면 된다. : 입력된 숫자의 자릿수가 len이라고 할 때 len - 1까지 (9 * i * 10^i) 로 구할 수 있다. (단, i < len) 그 다음 len 자릿수들의 길이만큼 더하.. 2021. 9. 2.
[BOJ/백준] 6064 카잉 달력 ● [문제번호 6064] 카잉 달력 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) : 최대공약수, 최소공배수 (유클리드 호제법) ● 풀이 과정 : 이전에 있던 [1476 날짜계산] 과 비슷한 문제다. 대신 최소공배수와 시간복잡도를 줄이기 위한 고려 사항이 추가되었다. 시간복잡도를 줄이는 방법이 마땅히 떠오르지 않아 구글링하였다. : 각 테스트케이스의 마지막 해는 M, N의 최소공배수 이다.. 2021. 9. 2.
728x90

티스토리툴바