[코딩테스트] 시간복잡도 묘수로 빠른 알고리즘 접근하기

2024. 7. 23. 22:58· Tip💡
목차
  1. 1. n개수와 시간 복잡도 
  2. 2. 시간 복잡도와 초 
  3. 3. 시간복잡도에 따른 알고리즘 

코딩테스트는 기업이 지원자의 minimum quality를 보장하고 싶어서 만든 제도이다.

따라서 기본지식을 테스트하기 위해 문제마다 핵심 알고리즘을 넣는 게 현재까지의 코테 트렌드이다.

 

이 사고를 바탕으로 핵심 알고리즘 1개 들어갔다는 가정을 세운다.(어려운 문제는 1개+α)

그러면 n과 시간복잡도 관계에 따른 핵심 알고리즘 추리로 빠른 문제 전개를 진행한다.

 

문제 순서도

1. n개수를 파악하여 최대 시간 복잡도(빅오 표기법)를 생각한다.

2. 시간복잡도에 따른 알고리즘을 생각한다.

3. 시간복잡도에 따른 초변환을 하여 가능한 시간인지 파악한다. 

4. 해당 알고리즘과 문제를 대입해 보며 가장 적절한 알고리즘을 빠르게 찾아낸다. 

 


1. n개수와 시간 복잡도 


2. 시간 복잡도와 초 


3. 시간복잡도에 따른 알고리즘 

O(1): 해시테이블(검색)

O(logN):이진트리, heapq(우선순위 큐), 이진탐색, 소수 구하기(약수제거) => 에라토스테네스의 체(n**0.5)

O(N): dp(10만 개 이상)

O(NlogN): 정렬+투포인터, 정렬, LIS(이진탐색 쓸 경우)

O(N^2): 2차원 배열 완전탐색(bfs,dfs), 그래프 완전탐색, 슬라이딩 윈도우, 브루트포스, 다익스트라, 프림(MST)

O(N^3): 플로이드

'Tip💡' 카테고리의 다른 글

[팁] 변수표기법  (0) 2023.09.02
  1. 1. n개수와 시간 복잡도 
  2. 2. 시간 복잡도와 초 
  3. 3. 시간복잡도에 따른 알고리즘 
'Tip💡' 카테고리의 다른 글
  • [팁] 변수표기법
code_wizard
code_wizard
헛둘헛둘
code_wizard
코드의 신비: 컴퓨터 마법사의 일기
code_wizard
전체
오늘
어제
  • 분류 전체보기 (61)
    • 생각정리 (2) N
    • Project (7)
      • Caston Design (5)
      • 상명대 축제 2023 "비상(飛上)" (1)
      • 취뽀Lab (1)
    • Solo Project (4)
      • 소셜로그인+JWT (4)
    • Back-end (4)
      • Spring (4)
      • Test (0)
    • DevOps (1)
      • Docker (1)
    • Tip💡 (2)
    • CS🖥️ (5)
      • Operating System (1)
      • Network (0)
      • OOP (4)
    • Programming (35)
      • Data Structure (3)
      • Algorithm(Python) (26)
      • Java (1)
      • Python (5)
    • DeepLearning (1)
    • sw마에스트로 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • jpa
  • Docker
  • 오버라이딩
  • 평균오차제곱
  • 20115번
  • 백준
  • 그리디알고리즘
  • SWEA
  • 프로그래머스
  • 오블완
  • 21966번
  • 구현
  • Baekjoon
  • 도커커맨드
  • 티스토리챌린지
  • 리트코드
  • 문자열
  • super
  • 경사하강법
  • 오버로딩
  • 축제사이트
  • BFS
  • java
  • SW마에스트로
  • 캡스톤디자인
  • MSE

최근 댓글

최근 글

hELLO
code_wizard
[코딩테스트] 시간복잡도 묘수로 빠른 알고리즘 접근하기
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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