[스터디 : 시간 복잡도]

시간 복잡도 : 입력 크기와 알고리즘간의 관계

• 알고리즘의 복잡도를 나타내는 지표 중 하나
• 입력 크기에 대해 프로그램의 동작시간을 가늠해볼 수 있는 수단

보다 적합한 알고리즘을 선택할 수 있는 기준

• 올바른 정답을 구하는 알고리즘이 여럿이라면? 구현이 쉬운, 효울적인 방법을 택할 수 있다.

1. 배열의 최댓값을 구하는 함수의 구현
   1-1. 반복문을 통해 모든 원소를 비교하는 방법 (시간복잡도 : O(N))
   1-2. 정렬 함수를 이용하는 방법

Java는 왜 추가시간이 있나요?

• 언어마다 동작 시간이 다를 수 있다.
• java는 컴파일 방식으로만 동작하는 언어보다 느린편
• 대부분의 시간/메모리 제한은 C/C++ 계열 언어 기준

• 참고 지표일뿐 너무 의존하진 말자

문제 : [10158]개미 문제

import java.util.*;

class Main {
    // 가로 w , 세로 h 2차원 격자 공간
    // 문제 : W x H 격자 공간에서 대각선으로 이동하는 개미의 T시간 후 위치
    // 제한 : 2 <= W , H <= 40,000
    // 제한 : 1 <= T <= 200,000,000
    // 개미의 이동 방향 분석 : deltaX, deltaY
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int h = scanner.nextInt();
        int p = scanner.nextInt();
        int q = scanner.nextInt();
        int t = scanner.nextInt();
        int deltaX = 1, deltaY = 1;

        int timeX = t % (2 * w); // 모듈러
        int currentX = p;
        while (timeX-- > 0){
            if(currentX == w) deltaX = -1;
            else if(currentX == 0) deltaX = 1;
            currentX += deltaX;
        }

        int timeY = t % (2 * h);
        int currentY = q;
        while (timeY-- > 0){
            if(currentY == h) deltaY = -1;
            else if(currentY == 0) deltaY = 1;
            currentY += deltaY;
        }
        System.out.println(currentX + " " + currentY);
    }
}

import java.util.*;

class Main {
    // 가로 w , 세로 h 2차원 격자 공간
    // 문제 : W x H 격자 공간에서 대각선으로 이동하는 개미의 T시간 후 위치
    // 제한 : 2 <= W , H <= 40,000
    // 제한 : 1 <= T <= 200,000,000
    // 개미의 이동 방향 분석 : deltaX, deltaY
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int h = scanner.nextInt();
        int p = scanner.nextInt();
        int q = scanner.nextInt();
        int t = scanner.nextInt();
        int currentX = (t + p) % (2 * w);
        int currentY = (t + q) % (2 * h);
        if(currentX > w) currentX = 2 * w - currentX;
        if(currentY > h) currentY = 2 * h - currentY;

        System.out.println(currentX + " " + currentY);
    }
}