Hayden's Archive
[알고리즘] 알고리즘에서의 효율성, 빅오 표기법, 입/출력 본문
- 알고리즘 문제의 효율성 : 1. 수행 시간 / 2. 사용한 메모리 / 3. 코드의 길이
- 효율성 중에서 수행 시간이 가장 중요하다. 보통 메모리는 넉넉하므로 걱정할 필요가 없다. 시간 안에 풀었다면 메모리 부족을 겪지 않는다.
- 보통 배열이 가장 많은 공간을 사용한다. 배열의 크기가 크면 시간 초과를 받는 경우가 많다.
- 불필요한 공간 없으면 보통 공간 복잡도(Space Complexity)는 신경 안 써도 된다.
- 시간 복잡도(Time Complexity)를 통해 작성한 코드의 시간을 예상할 수 있다.
- 99%의 케이스가 0.01초가 걸린다고 해도 1%의 케이스가 100초가 걸린다면 그 경우 시간 복잡도는 100초가 걸리는 셈이다.
- 시간 복잡도를 계산할 때 보통 빅오 표기법(Big O Notation)을 쓴다.
- 대표적인 빅오 표기법 예시) O(1), O(N), O(N^2), O(N^3), O(2^N), O(N!)
- 빅오 표기법에서 1) 상수는 버린다( O(3N^2) = O(N^2) ) 2) 두 가지 항이 있을 경우 변수가 같다면 큰 것만 빼고 다 버린다. 큰 것에 비하면 작은 것은 미미하기 때문이다.( O(N^2+N) = O(N^2) ) 3) 두 가지 항이 있는데 변수가 다르다면 놔둔다. 둘 중 어느 변수가 더 큰 지 알 수 없기 때문이다. ( O(N^2 + M) )
- 빅오 표기법 참고 : https://blog.naver.com/kks227/220769859177
빅오 표기법(Big-O notation), 시간복잡도, 공간복잡도
자료구조나 알고리즘에서 성능 측정의 가장 중요한 지표인 개념을 먼저 소개해드려야 할 것 같습니다.그건 ...
blog.naver.com
입출력
- C++의 입출력 : scanf/printf, cin/cout (scanf/printf와 cin/cout를 섞어서 쓰면 안 된다. scanf/printf가 더 빠르다.)
- 자바의 입출력 : Scanner보다 BufferedReader가 더 빠르고, System.out보다 BufferedWriter가 더 빠르다.(출력시 StringBuilder를 사용해서 한 문자열로 만들어서 출력을 한 번만 사용할 수도 있다.)
- 자바의 입출력 관련 코드 및 포스팅 https://hayden-archive.tistory.com/186?category=745677
[알고리즘] 백준 2884번 : 알람 시계 / 백준 15552번 : 빠른 A+B
현재 프로그래머스 알고리즘 문제를 따로 풀고 있지만 백준 알고리즘 문제는 처음으로 풀어보았다. 프로그래머스는 기본적인 코드의 폼을 제공하지만 백준은 빈 화면만 제공한다. 그래서 처음�
hayden-archive.tistory.com
- 참고 : 입력 속도 비교 https://www.acmicpc.net/blog/view/56
- 참고 : 출력 속도 비교 https://www.acmicpc.net/blog/view/57
- 입력이 몇 개인지 주어지지 않은 경우에는 입력을 EOF(End-of-File)까지 받으면 된다. ( 자바의 EOF 처리 관련 포스팅 https://hayden-archive.tistory.com/187?category=745677 )
