24265번 알고리즘 수행 시간 0(n2)

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

ex ) i = 7

i 는 1~7-1 (6까지)

j 는 1+1~7

1 2 3 4 5 6 7

2 3 4 5 6 7

3 4 5 6 7

4 5 6 7

5 6 7

6 7

​

2 3 4 5 6 7 -> 6

3 4 5 6 7 -> 5

4 5 6 7 -> 4

5 6 7 -> 3

6 7 -> 2

7 -> 1

​

즉 7 입력 시 7-1의 합이 나옴

​

6+5+4+3+2+1 = 21

7(7-1)/2 = 21

​

즉 n(n-1)/2

​

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Long a = sc.nextLong();
        System.out.println(a*(a-1)/2);
        System.out.println("2");
    }
}

https://mathbang.net/609#gsc.tab=0

 

등차수열의 합, 등차수열의 합 공식

이번 글에서는 등차수열의 각 항을 더한 등차수열의 합을 구할 거예요. 아주 간단히 생각만 살짝 바꾸면 등차수열의 합 공식을 유도할 수 있어요. 방법은 어렵지 않으니까 그 원리를 금방 이해할 수 있을 거예요. 등차수열의 합 공식은 두 가지예요. 사실은 한 가지인데, 등차수열에서 어떤 조건을 알려주느냐에 따라 모양이 다르니까 둘의 차이를 잘 비교하세요. 문제를 활용하기에 따라서 쉬운 문제와 어려운 문제의 수준 차이가 많이 나니까 문제를 풀 때 집중해서 잘 봐야 해요. 등차수열의 합 등차수열 1, 2, 3, 4, 5, …, 10을 이루는...

mathbang.net

등차수열 공부해보기

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

⚡️ Time Complexity (시간 복잡도) Time Complexity (시간 복잡도)를 고려한 효율적인 알고리즘 구현 방법에 대한 고민과 Big-O 표기법을 이용해 시간 복잡도를 나타내는 방법에 대해 알아봅시다. ❗️효율적인 알고리즘 고민 알고리즘 문제를 풀다 보면 문제에 대한 해답을 찾는 것이 가장 중요하다. 그러나 그에 못지않게, 효율적인 방법으로 문제를 해결을 했는지도 중요하다. 혹시 문제를 풀다가 ‘이것보다 더 효율적인 방법은 […]

hanamon.kr

시간복잡도 공부해보기

​

• Big-O(빅-오) ⇒ 상한 점근
• Big-Ω(빅-오메가) ⇒ 하한 점근
• Big-θ(빅-세타) ⇒ 그 둘의 평균

​

• Big-O 표기법의 종류

1. O(1) → 일정한 복잡도, 입력값 크기와 관계없이 즉시 출력값을 뽑아낼 수 있는 것(가장빠름)
2. O(n) → 선형 복잡도, 입력값 증가에 따라 시간 또한 같은 비율로 증가, for
3. O(log n) → 로그 복잡도, 탐색기법, O(1) 다음으로 빠름, BST의 값 탐색 등
4. O(n2) → 2차 복잡도, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가 ,2중for , 3중 for → O(n3)
5. O(2n) → 기하급수적 복잡도, 재귀로 구현하는 피보나치 수열 등