알고리즘(36)
-
백준 4150 피보나치 수(c++)
https://www.acmicpc.net/problem/4150 4150번: 피보나치 수 피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력 www.acmicpc.net 문제를 읽어보면 알 수 있듯이 숫자의 길이가 100자리가 넘어간다. 이런 문제는 long long int도 메모리 초과가 뜨기 때문에 어떻게 풀까? 고민해봐야 된다. 정답은 문자열string을 쓰면 되는데 문제를 풀 때 피보나치 수를 직접 적어보면서 코드를 어떻게 짤지 고민을 해봤다. //1 1 2 3 5 8 13 21 34 55 89 144 23..
2022.04.02 -
팰린드롬(회전문 문제)
bool palindrome(int idx) { for (int i = 0; idx + i < length - i - 1; i++) //하나라도 성립안하면 palindrome 아님 if (S[idx + i] != S[length - i - 1]) return false; return true; } https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net https://www.acmicpc.net/problem/14444 14444번: 가장 긴 팰린드롬 부분 ..
2022.03.23 -
(C++) 백준 1111번 IQ Test
맨 처음에 DivisionByZero라는 런타임 에러가 떴다. 0으로 나눈 것이 없다고 생각했는데 자세히 보니 어디에서 런타임 에러가 뜨는지 확인했고, 빠르게 고쳐서 성공했다. 시간제한이 2초이다. 2초를 보고 오래 걸리는 문제인 거 같아서 바로 for문으로 푸는 방법을 생각해봤다. 부르트 포스처럼 하나하나 다 대입해서 모든 수를 만족하는 함수를 만드고 함수의 개수가 2개 이상이면 B 그렇지 않으면, 내가 만든 함수에 넣는 코드를 짜서 시간복잡도를 계산해보니 8억(8초)이 나오는 것을 확인했다. 다시 마음을 가다듬고 for 문을 푸는 문제가 아님을 직감하고, 어떻게 하면, 풀 수 있을지 고민했다. 일단 case를 나누어봤다. N의 수에 따른 case를 나누어 보겠다. N=1 무조건 A출력 답이 2개 이상..
2021.12.01 -
백준 다리놓기 1010 C++
우선 먼저 했던 코드부터 올려보자면 #include #include #include #pragma warning(disable:4996) using namespace std; int main() { int t = 0; cin >> t; for (int i = 0; i > a >> b; vector b_b; a = min(a, b-a); unsigned long long int sum = 1; for (int q = 1; q = 1; u--) { sum = sum * b; for (int k = 0; k < a; k++) { if (sum% b_b[k] == 0 && b_b[k] != 1) { sum = sum / b_b[k]; b_b[k] = 1; } } ..
2021.11.26 -
1.시간 복잡도 빅오 표기법 O(N)
시간 복잡도(time complexity)란 가장 널리 사용되고 있는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 ㄴ수행하는 기본적인 연산의 수를 입력 크기에 대한 함수로 표한한 것이다. 그리고 표현을 할때 O표기를 하는데 역기서 O표기를 할때 변수의 차수가 큰 것을 따라간다. n^2+5n => O(n^2) n^3+100n^2 => O(n^3) n^2*m+m^2*n+3 => O(n^2*m+m^2*n) 근데 시간복잡도가 낮다고 해서 언제나 더 빠르게 작동하는 것은 아니다. 밑에 그래프를 보면 알 수 있듯이. 복잡도가 낮다고해서 더 빠르게 작동하는 것이 아니라 일정 구간 이상부터 빠르게 작동하는 것을 알 수 있다. 우리가 1부터 n까지의 합을 구할 때 int sum=0; for(int i=0; i
2021.11.05 -
백준 1018 c++ 완전탐색(Brute-force Serch)
원래 티스토리 해보려고 했는데, 귀찮아서 시작 도안하다가 잔머리? 굴려서 푸는 문제 맞히면 기분 좋잖아요? 그래서 기분 좋아져서 시작해봄 완전 탐색, 브루트 포스(Brute-force)는 그냥 쉽게말해서 가능한 경우를 일일이 다 탐색하는 방법임 근데 브루트포스 문제들은 다 탐색하면 타임 에러가 뜨겠죠? 그래서 어떻게 시간을 최소화하는지에 따라서 문제를 맞히고, 틀리고 가 결정됨 여기 문제 보면 알 수 있는 것처럼 브루트 포스 문제는 시간제한이 있음(하나씩 다 검사하다가는 틀린다는 거) 그래서 어떻게 하면 다 대입안 하고, 시간초과 안하고 찾을 수 있을까? 고민해보니까 시작점만 잘 정하면 되겠다고 생각함(어차피 8X8을 구하는 거닌까) 그래서 시작점을 string크기에 따라서 잘 조절만 하면 할 수 있겠다..
2021.11.03