시간복잡도, 공간복잡도를 생각하면서 문제를 풀자.

2023. 10. 29. 23:34· algorithm/BOJ

시간복잡도 팁

- 1억의 연산 당 1초가 걸린다고 생각하자.

- log(1,000,000,000)는 log 안의 0의 개수가 3개면 2^10이라고 가정한다. 즉,log(1,000,000,000)은 2^30(2^10 * 2^10 * 2^10) 번만큼의 연산을 하게 된다.

 

공간복잡도 팁

- 입력의 제한 조건에 따라 공간 복잡도를 계산한다.

- 배열이나, 메모리를 관리할 때 공간복잡도를 차지한다고 생각하면 된다. 이를 유의해서 메모리 초과를 조심하자.

 1,000,000,000
  |   |   |
  G---M---K       byte

 

- 만약 출력 값이 100,000 * 100,000이 넘을 경우, long long 자료형을 생각해봐야한다.

  1.  char : 1byte
  2.  int : 4byte (100,000,000)
  3.  long long : 8byte
  4.  float : 4byte
  5.  double : 8byte
반응형
저작자표시 비영리 변경금지 (새창열림)

'algorithm > BOJ' 카테고리의 다른 글

[백준 1202번] 보석도둑 c++ 풀이  (1) 2023.12.07
[백준 2042번] 구간 합 구하기 c++ 풀이  (0) 2023.10.30
[백준 2143번] 두 배열의 합 C++ 풀이  (1) 2023.10.28
[백준 1062번] 가르침 C++ 풀이  (0) 2023.09.14
[백준 16924번] 십자가 찾기 파이썬 완전탐색 풀이  (0) 2023.03.01
'algorithm/BOJ' 카테고리의 다른 글
  • [백준 1202번] 보석도둑 c++ 풀이
  • [백준 2042번] 구간 합 구하기 c++ 풀이
  • [백준 2143번] 두 배열의 합 C++ 풀이
  • [백준 1062번] 가르침 C++ 풀이
이티권
이티권
programming, design
이티권
ET WORLD
이티권
전체
오늘
어제
  • 분류 전체보기 (85)
    • Web (43)
      • Three.js (1)
      • javascript (6)
      • React (2)
    • algorithm (18)
      • BOJ (6)
    • Record (9)
      • 생각 (6)
      • 경험 (3)
    • Art (7)
    • Technology (8)
      • Data (2)
      • Info (5)

블로그 메뉴

  • WEB
  • RECORD
  • ALGORITHM
  • TECH
  • ART

공지사항

인기 글

태그

  • html tag
  • 순환
  • 깃 CLI
  • 스프레드문법
  • 나머지매개변수
  • 알고리즘
  • 불확신
  • 알고리즘문제
  • 깃허브하는법
  • svgr
  • 깃허브시작
  • 뷰링크
  • 퓨 이벤트
  • 레포지터리만들기
  • C언어
  • HTML
  • 시니어프론트엔드개발자
  • vue.js
  • 뷰라우터
  • 기명함수 표현식
  • 뷰 프롭스
  • 재귀함수
  • ChatGPT
  • 맥북소리녹화
  • 페이지 링크
  • 컴퓨터공학힘든가요
  • 포토샵
  • 컴포넌트 통신
  • js
  • CSS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
이티권
시간복잡도, 공간복잡도를 생각하면서 문제를 풀자.
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.