[이코테] 1. 출제 경향 및 알고리즘 성능 평가
Algorithm/이코테2021

[이코테] 1. 출제 경향 및 알고리즘 성능 평가

반응형

 

 

포스팅 방향성

본 포스팅은 이코테 2021 강의를 " 다시 돌아봤을 때 알기 쉽게 기록하는 것에 초점"을 두고 작성한다.

조금이라도 생소함을 느꼈던 단어 및 개념 들을 정리하여 두고두고 꺼내먹으려 한다.

여기서 나오는 이미지, 소스코드, 개념은 "이것이 코딩 테스트다 with 파이썬"의 저자 나동빈씨로 부터 나온다.

무료로 알고리즘 공부를 할 수 있게 지식을 공유해준 저자에 감사함을 표한다.

코딩 테스트 첫 준비를 독자 분들도 저처럼 이코테로 시작하셨으면 좋겠다.

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=1

 

 

IT 기업 코딩 테스트 최신 출제 경향

대부분의 대기업(삼성전자, 카카오, 라인 포함)은 알고리즘 코딩 테스트를 실시한다.

응시생들에게 2 ~ 5시간 가량의 시간을 주며, 여러 알고리즘 문제를 풀게 한다.

가장 출제 빈도가 높은 알고리즘 유형

  1. 그리디(쉬운 난이도)
  2. 구현
  3. DFS/BFS를 활용한 탐색

친절한 나선생.. 무한 감사
2019ver

2019년 기준.

삼성, 라인 : 코테 통과 시 다음 단계.

카카오 : 코테 통과하고 2차로 개발형 코딩테스트(시스템 개발)까지 해야됨.

2018ver

알고리즘 성능평가

복잡도(Complexity)

복잡도 = 알고리즘의 성능을 나타내는 척도.

시간 복잡도 : 알고리즘의 수행 시간 분석을 목적으로 사용됨.

공간 복잡도 : 알고리즘의 메모리 사용량 분석을 목적으로 사용됨.

* 같은 기능의 알고리즘 이라면, (일반적으로)복잡도가 낮을수록 좋은 알고리즘.

빅오 표기법(Big-O Notation) = 가장 빠르게 증가하는 항만을 고려하는 표기법.

ex. 3N^3 + 9N^2 + 1,000,000 => O(N^3)

명칭에 대해서 인지하고 있어라.

시간 복잡도 계산해보기

array = [3, 5, 1, 2, 4] # 5개의 데이터 (N=5)
summary = 0 # 합계를 저장할 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
    summary += x
    
# 결과를 출력
print(summary)

여기서 시간 복잡도는? ▶ O(N)

 

array = [3, 5, 1, 2, 4] # 5개의 데이터(N=5)

for i in array:
    for j in array:
        temp = i * j
        print(temp)

여기서 시간 복잡도는? ▶ O(N^2)

총 연산 = i * j = 5x5 = 5^2

모든 2중 반복문의 시간복잡도가 O(N^2)은 아님.
for문 안에서 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야함.

 

 

알고리즘 설계 Tip

일반적으로 CPU 기반 개인컴퓨터, 채첨용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우,

  • C  = 1 ~ 3초 시간 소요
  • Python = 5 ~ 15초 시간 소요

(시스템에서 PyPy를 지원하는 경우) PyPy는 때때로 C언어 보다 빠르게 동작 하기도 함.

그래서 채점 서버가 PyPy를 제공한다면, 가능한 PyPy로 제출!!! 하시오.

PyPy가 Python보다 시스템 메모리를 더 잡아먹을 수 있기 때문에 무지성 제출X

Python 제출 한 후에 시간 초과 판정을 받는 다면 PyPy로 제출.(반대로도 가능)

 

 

Q1. O(N^3)의 알고리즘을 설계한 경우, N의 값이 5,000이 넘는다면 얼마나 걸릴까?

 

A1.

5000*5000*5000 = 125000000000 = 1250억의 연산횟수.

Python은 1초에 5000만번 정도 연산 수행.

따라서, 약 2500초 정도 소요됨.

채점용 서버는 1초에 약 2000만번 정도 연산할 수 있다고 가정하고 문제를 접하는 것이 가장 이롭다.

채점용 서버의 컴퓨팅 파워가 천차만별이라 이 점도 유의해!!

 

코테 문제에서 시간 제한은 통상 1~5초 가량..!

문제에 명시되어 있지 않은 경우 대략 5초 정도 라고 가정하고 푸는 것이 합리적인 판단.

 

요구사항에 따라 적절한 알고리즘 설계하기.

문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)임.시간제한이 1초인 문제를 만났을 때의 기준은 아래와 같다.

  • N의 범위가 500인 경우 : 시간 복잡도 O(N^3)인 알고리즘으로 설계하면 문제 풀 수 있음.
  • N의 범위가 2,000인 경우 : 시간 복잡도 O(N^2)인 알고리즘으로 설계하면 문제 풀 수 있음.
  • N의 범위가 100,000인 경우 : 시간 복잡도 O(NlogN)인 알고리즘으로 설계하면 문제 풀 수 있음.
  • N의 범위가 10,000,000인 경우 : 시간 복잡도 O(N)인 알고리즘으로 설계하면 문제 풀 수 있음.

 

알고리즘 문제 해결 과정

  1. 지문 읽기 및 컴퓨터적 사고
  2. 요구사항(복잡도) 분석
  3. 문제 해결을 위한 아이디어 찾기
  4. 소스코드 설계 및 코딩

일반적으로 대부분의 문제 출제자들은, 핵심 아이디어를 캐치하면 간결하게 소스코드 작성할 수 있는 형태로 문제 출제함.

 

 

수행 시간 얻는 방법

import time
start_time = time.time() #측정 시작

#소스코드 시작

#소스코드 끝

end_time = time.time() #측정 종료
print("time :", end_time - start_time)

 

 

 

 

이코테 2021 시리즈 씹어먹기 by 조랭이떡

시리즈 목차

더보기
  1. 코딩테스트 출제 경향 및 알고리즘 성능 평가
  2. 파이썬 문법 부수기
    1. 수, 리스트 자료형
    2. 문자열, 튜플, 사전, 집합 자료형
    3. 기본 입출력
    4. 조건문
    5. 반복문
    6. 함수와 람다 표현식
    7. 자주 사용되는 표준 라이브러리
  3. 그리디
    1. 그리디 알고리즘이란?
    2. 거스름돈
    3. 1이 될 때 까지
    4. 곱하기 혹은 더하기
    5. 모험가 길드
  4. 구현
  5. DFS & BFS (추후링크)
  6. 정렬 알고리즘 (추후링크)
  7. 이진 탐색 (추후링크)
  8. 다이나믹 프로그래밍 (추후링크)
  9. 최단 경로 알고리즘 (추후링크)
  10. 기타 그래프 이론 (추후링크)
  11. 코딩 테스트에서 자주 출제되는 기타 알고리즘 (추후링크)
  12. 개발형 코딩 테스트 (추후링크)

 

반응형

    티스토리툴바