[백준] 1463번: 1로 만들기 (C언어)

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 난이도: solved.ac 실버 3 매우 유명한 dp문제다 arr[N]을 N→1로 만드는데 필요한 연산의 최소 횟수라고 해보자 arr[N]은 다음 3개의 값 중 최소값이 된다 arr[N / 3] + 1 (N이 3으로 나누어 떨어지는 경우) arr[N / 2] + 1 (N이 2으로 나누어 떨어지는 경우) arr[N - 1] + 1 이를 코드로 나타내면 다음과 같다 #define _CRT_SECURE_NO_WARNINGS #include #define min(A,B) A

• format_list_bulleted PS/백준
• · 2023. 2. 17.
• textsms

[백준] 9461번: 파도반 수 (C언어)

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 난이도: solved.ac 실버 3 그림이 있어 규칙찾기 매우 쉬운 dp문제다 N번째 삼각형 변의 길이를 tri[N]이라고 해보자 그림을 자세히보면 tri[6]부터는 바로 앞 삼각형인 tri[N-1]의 변과 tri[N-5] 변이 한 변이 되는 걸 알 수 있다 tri[N] = tri[N-5] + tri[N-1] (N ≥ 6) tri[1]부터 tri[5]까지는 각 값을 지정해주고 (tri[0]은 그냥 0으..

• format_list_bulleted PS/백준
• · 2023. 2. 16.
• textsms

[백준] 1003번: 피보나치 함수 (C언어)

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 난이도: solved.ac 실버 3 피보나치 수열은 dp(다이나믹 프로그래밍, 동적 계획법)를 이용하면 매우 빠르게 n번째 수열을 구할 수 있다 이번 문제는 n번째 수열을 찾는 게 아니라 f(0)과 f(1)을 몇 번 호출하는지 구하는 문제이다 이것도 dp를 이용해 금방 구할 수 있다 일단 n = 0일 때는 f(0)을 1번 출력하고 f(1)을 0번 출력한다 이를 2차원 배열로 나타내보자 f[n][0]은 n번째 피보나치 수열의 f(0)을 호출하는 횟수, f[n][1]은 n번째 피보나치 수열의 f(..

• format_list_bulleted PS/백준
• · 2023. 2. 15.
• textsms

[백준] 24416번: 알고리즘 수업 - 피보나치 수 1 (C언어)

https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 난이도: solved.ac 브론즈 1 #define _CRT_SECURE_NO_WARNINGS #include int f[41] = { 0,1,1 }; int cnt1 = 0; int cnt2 = 0; int fib(int n) { if (n == 1 || n == 2) { cnt1++; return 1; } else return (fib(n - 1) + fib(n - 2)); } ..

• format_list_bulleted PS/백준
• · 2023. 2. 15.
• textsms

[백준] 1744번: 수 묶기 - C언어 (2036번과 같은 문제)

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 난이도: solved.ac 골드 4 분명히 내가 사용하는 visual studio로는 예제에 나온 input이나 ​ 질문 게시판에 나온 반례들을 모두 만족하길래 ​ 도대체 어디가 틀렸는지 화가 났던 문제다 ​ 그래서 알고리즘 톡방에 질문을 올렸는데 ​ 아주 고마운 분께서 정성스럽게 답변을 해주셨다... ​ 내가 빠트렸던 부분(잘 몰라서...) 은 맨 아래에서 설명하겠다 ​ 일단 내 풀이 방식은 ..

• format_list_bulleted PS/백준
• · 2023. 2. 14.
• textsms

[백준] 17413번: 단어 뒤집기 2

https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 난이도: solved.ac 실버 3 복잡해 보이지만 꽤 간단했던 문제다 문자열 S를 통째로 받아서 ' ', ''를 제외한 나머지 문자들이 나오면 stack에 모두 담았다가 ' '가 나오거나 '

• format_list_bulleted PS/백준
• · 2023. 2. 13.
• textsms