문제시간 복잡도 개념 보러가기 풀이우선 기본 공식을 알아보자. O(g(n)) 은 f(n) 정리하면, a1 * n + a0 a1 * n + a0 그런데 이렇게 제출하면 틀렸습니다. 가 출력된다. 너무 모르겠어서 다른 사람들 블로그를 찾아봤다. 결론부터 말하자면 조건식에 아래 코드를 넣어줘야 한다고 한다.&& a1 그런데 이 부분이 너무 이해가 안 갔다. 제대로 설명하는 사람이 거의 없었다. 내가 이해한 대로 설명을 해보겠다. 혹시 틀리다면, 댓글로 알려주길 바랍니다!! 1. 나온 조건식을 전부 좌항으로 옮기면 아래와 같이 변경된다. 2. 이때, 문제에 나온 조건을 만족시켜야 한다.모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다나는 이를 n 이 어떤 값이건 위..
문제시간복잡도 개념 보러가기 풀이풀이에는 두 가지 방법이 있다.1. 시그마로 계산하는 방법2. 경우의 수 구하기 수학 안본지 6년이 넘어서 .. 공식을 찾는게 너무 어려워 다른 분 블로그를 참고했다. 정리하자면, 아래 경우의 수의 규칙이 아래와 같다. (1,2,3) ... (1,6,7)(2,3,4) ... (2,6,7) 때문에 아래와 같이 나올 수 있게 된다. n = 7i = 1/ j 2/ 3, 4, 5, 6, 7 /5 j 3/ 4, 5, 6, 7 /4 j 4/ 5, 6, 7 /3 j 5/ 6, 7 /2 j 6/ 7 /1i = 2/ j 3/ 4, 5, 6, 7 /4 j 4/ 5, 6, 7 /3 ..
문제시간복잡도 개념 보러가기 풀이반복문이 3번 반복되므로, n의 세제곱이 된다. 최고차항의 차수는 3이 된다. 왜 세제곱을 하는지 궁금하면 여기에서 개념을 확인할 수 있다.2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. 코드package AlgorithmStudy.src.bronze;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.math.BigInteger;public class B24266 { public static void main(String[] args) throws IOException { BufferedRe..
문제시간복잡도 개념 보러가기 풀이n == 7i = 1/ 2, 3, 4, 5, 6, 7,/ 6i = 2/ 3, 4, 5, 6, 7/ 5i = 3/ 4, 5, 6, 7/ 4i = 4/ 5, 6, 7/ 3i = 5/ 6, 7/ 2i = 6/ 7/ 1234567345670456700567000670000700000000000 6 + 5 + 4 + 3 + 2 + 1 로 결과가 나오는 것을 알 수 있다. 이는 위 표를 보면, 6 * 7의 절반인 것을 알 수 있다. 공식은 n(n-1)/2 이다. 코드package AlgorithmStudy.src.bronze;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRea..
문제시간복잡도 개념 보러가기 풀이이중 for 문 구조로, n이 2번 (n*n) 으로 반복되는 것을 알 수 있다. 즉 n의 2제곱이므로 실행 횟수는 n*n, 최고차항의 차수는 2이다.* 500,000 X 500,000 은 250,000,000,000으로 int 의 범위를 벗어남을 유의해야한다. ( int 범위 2,147,483,647) 코드package AlgorithmStudy.src.bronze;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.math.BigInteger;public class B24264 { public static void main(Strin..
문제시간복잡도 개념 보러가기 풀이MenOfPassion 함수를 자세히 살펴보면, for 문을 n 회 반복한다는 이야기라는 것을 눈치챌 수 있다. 즉, 시간 복잡도는 O(n) 이다. 다항식으로 표기하면 n, 1차 다항식이므로 최고차항은 1이다. 코드package AlgorithmStudy.src.bronze;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class B24263 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(ne..
문제 시간복잡도 개념 보러가기 풀이어떠한 반복문도 없이 return A[i] 는 한번 반복한다는 의미이다. 따라서 실행횟수는 1, 상수만 출력되기 때문에 최고차항의 차수는 항상 0이다.* 상수의 최고차항은 항상 0이다. 코드package AlgorithmStudy.src.bronze;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class B24262 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStrea..
문제 풀이문제 자체는 어렵지 않다. 세 점의 좌표가 같은 직사각형을 만들려면, X,Y 축 좌표의 값이 각각 2개씩 같아야 한다.무슨 말인지 이해가 안 된다면, 그림을 그려보면 된다. 즉, 아래 예시 코드에서는 각각 5가 두개씩 있고 7만 하나이므로 나와야 하는 결과는 7 7 인 셈이다.5 55 77 5 코드문제 자체는 쉬웠는데 어떻게 코드로 구현할지 고민했다. 원래는 이중 for 문으로 결과 값까지 구하려고 했는데, 쉽지 않았다.직사각형은 총 4개의 점이니 개수는 고정되어 있기 때문에 0,1,2는 하드코딩으로 넣어주었다.각각의 값을 비교해 두개인 것을 제외한 나머지 하나를 출력하도록 하였다. package AlgorithmStudy.src.bronze;import java.io.BufferedRea..
시간 복잡도란?시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수이다. 1억 번의 연산을 1초의 시간으로 간주한다.ex) 제한시간 2초 : 2억연산 안에 답 도출 내가 짠 코드가 얼마나 효율적인지 > 시간복잡도로 확인 가능하다. 시간 복잡도 유형1. 빅-오메가 최선일 때의 연산 횟수이다. 2. 빅-세타보통일 때 연산 횟수, 평균적인 값을 구한다.N/2 정도의 연산 횟수. 3. 빅-오 (Big O)최악일 때의 연산 횟수를 나타낸 표기법이다.모든 경우를 가정하는 표기법이다. 코딩 테스트 시, 최악의 횟수를 염두에 두고 코딩 테스트에 임해야 한다. > 코딩 테스트 시 빅-오 를 사용해야함 ! 연산 횟수 계산 방법연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기주어진 데이터의 크기를 확인해서, ..
문제 풀이1. N 이 1이 될때까지 반복2. N을 가장 작은 숫자로 소인수분해 시작* 시간 제한 유의 코드package AlgorithmStudy.src.bronze;import java.io.*;public class B11653 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.rea..
