Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 백준1946
- 리눅스환경
- 페이로드
- 배열빈도수
- docker
- 도커권한설정
- 우분투
- 유니캐스트
- filezilla
- 모래시계출력
- wan
- 도커
- 브로드캐스트
- 백준
- 디비버
- dbeaver
- 배열복사
- 포트포워딩
- 오름차순
- EC2
- 다차원배열
- 1946
- Decapsulation
- 리눅스계열
- 객체배열
- 네트워크모델
- 포트포워딩 안될때
- 배열최소값최대값
- 센토스
- ubuntu
Archives
- Today
- Total
다잘하고싶어
[알고리즘] 빅오표기법(Big-O Notation), 시간복잡도, 공간복잡도 본문
빅오표기법
: 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법
예1) 6N+5 의 경우, 총 소요시간은 5보다는 6N에 좌우된다.이때 상수 6도 제외하고 그냥 N에 집중하는 것. => O(N)
예2) 2N+10logN의 경우 N이 커질수록 10logN보다는 2N이 훨씬 클테니 2N만 남기고, 상수도 제외함. => O(N)
예3)N2(제곱)+2N+4 => O(N제곱)
시간복잡도
뒤로 갈 수록 시간 복잡도의 차이가 수행시간에 아주 큰 영향을 준다.
이때 O(2의N승) 은 N이 25이하 정도로 아주 작은 수가 아니면 코딩테스트 시간 복잡도를 통과하기 어렵다. 팩토리얼은 그보다 더 큰 폭으로 시간 복잡도가 올라가기 때문에 11이하의 수가 아니면 시간 제한 통과하기가 어렵다.
공간복잡도
: 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
예) 크기 N짜리 2차원 배열이 필요하면 O(N²), 따로 배열이 필요 없으면 O(1)
코테는 보통 시간복잡도 문제를 해결하면 되므로, 메모리 제한이 512MB일 때 int변수를 대략 1.2억개 정도 선언할 수 있다는 것만 기억해두기. (int 1개가 4바이트) -> 떠올린 풀이가 크기가 5억인 배열을 필요로 할 때 해당 풀이는 주어진 메모리 제한을 만족하지 못하므로 틀린 풀이이다!!
정수자료형
int의 최댓값은 21억
Integer Overflow
127에 1을 더하면 ?
컴퓨터 상에서는 01111111에 1을 더한다 -> 10000000이 된다 -> 최대범위보다 커짐.
실수자료형
- 실수의 저장 및 연산 과정에서는 반드시 오차가 발생한다.
-> 실수자료형은 필연적으로 오차가 있으므로, 문제상에서 절대/상대 오차를 허용한다는 단서를 준다. 없다면? 정수자료형을 사용하는 문제일 확률이 높다. - double 에 long 범위의 정수를 담아서는 안된다. 오차가 섞인 값이 저장될 수 있다. int는 담더라도 오차가 생기지 않음.
- 실수를 비교할 때는 등호를 사용하지 않는다.
'알고리즘' 카테고리의 다른 글
백준 1946. 신입사원 (Comparator 를 사용하여 객체배열 오름차순) (0) | 2024.01.31 |
---|---|
length, length(), size() (0) | 2022.11.03 |
[알고리즘] BFS 너비우선탐색 (0) | 2022.10.06 |
[알고리즘]BufferedReader 사용 (1) | 2022.10.06 |
알고리즘 개념 공부 순서 (1) | 2022.09.21 |