코딩테스트 | 기초 지식 쌓기

온라인 개발 환경

리플릿 : repl.it 

파이선튜터

오프라인 개발 환경

PyCharm(파이참) 

* 대규모 프로젝트에 사용되며, 디버깅 과정 필요하면 사용하길 권유

*지만, 깃git 이나 블로그에 기록해놓는 방식을 추천드린다

 

자신만의 소스코드 관리하기 

알고리즘 노트 => 팀노트 라고 한다

자주 사용하는 알고리즘 코드를 라이브러리 화 하면 좋다 

*어느 정도 문제유형에 있어서 비슷한 코드 형식을 띈다

 

IT 기업 코딩 테스트 

• 2~5시간
• 출제빈도: 1. 그리디  2. 구현  3. DFS/BFS (삼성전자 주로)

 

알고리즘 성능 평가

• 복잡도 1. 시간 복잡도 : 수행시간 2. 공간 복잡도 : 메모리 사용량
• 낮은 복잡도를 띌 수록 좋은 알고리즘이라 칭한다~
• 빅오 표기법(Big-O Notation) : 가장 큰 차수를 고려, 계수는 고려하지 않는다 
  • 예) 3N³ + 2N :  중에서 큰 차수인 첫 번째 항을 고려하며, 계수인 3은 고려하지 않는다 => N^3

  • 순위	명칭
    O(1)	상수시간(Constant time)
    O(logN)	로그시간(Log time)
    O(N)	선형시간
    O(NlogN)	로그 선형시간
    O(N²)	이차 시간
    O(N³ㅇ)	삼차 시간
    O(2")	지수 시간

  • * 제곱 표시는: ㅊ + 한자 (눌러서 표시해주면 됩니다~)

N개의 데이터의 합을 계산하는 프로그램 예제

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

# 모든 데이터를 하나씩 확인하여 합계를 계산
for x in array:
    summay += x 

# 결과를 출력 
print(summary)

2중 반복문 이용

시간복잡도 개념 이해

빅오표기법(N₂) : O(N²) 

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

for i in array:                # i 가 array 한바퀴 돈다는 의미 : 5번
    for j in array:            # j 가 array 한바퀴 돈다는 의미 : 5번
        temp = i * j
        print(temp)

* 5 * 5 = 25 = 5² = O(N²) 

 

알고리즘 문제 해결

핵심 아이디어를 캐치하면 간결하게 소스코드 작성하는 문제가 다수

 

1. 지문읽기 및 컴퓨터적 사고

2. 요구사항(복잡도) 분석

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩

 

수행시간 측정시간

내가 짠 코드가 얼마나 소요되는지 알 수 있는 방법이다~

코테나 실행시간 궁금할 때 요긴~

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

# 프로그램 소스코드
end_time = time_time()      # 측정종료
print("time", end_time - start_time)     # 수행시간 출력 

 

자료형

모든 프로그래밍 결국 데이터를 다루는 행위

정수형

코테 정수형 많이 쓰임 

양의 정수, 음의 정수, 0

a = 1000            # a 라는 변수에 대입연산자 이용하여 대입
print(a)

a = 777
print(a)           # 어떤 값 할당

a = a+5          # 증가 가능
print(a)           # 782

실수형

소수점 아래의 데이터 포함 

0.7 -> .7  (로 표현 가능함~, 회계 계산기처럼 그런지 궁금했는데 풀림~)

# 소수부가 0 일 때 0 을 생략
a = 5
print(a)    # 5.0

# 정수부가 0 일 때 0을 생략
a = -.7 
print(a)    # -0.7

지수표현 방식

• 유효숫자 e^지수  =  유효숫자 x 10^지수 

# 1,000,000,000 (10억)의 지수표현방식

a = 1e9 
print(a)   # 1000000000.0 (보통 실수형으로 인식)

# 752.5
a = 75.25e1
print(a)   # 752.5

# 3.954
a = 3954e-3
print(a)  # 3.954

• 지수 기본 : 실수형 data 가 기본값임~ 

a = int(1e9)
print(a)    # 1,000,000,000 

• int 를 씌어주면서 실수 연산 오류를 예방할 수 있다~
• *실수 연산 오류란?
  • 1/3 = 0.333333  정확도 십진수에서도 정확하지 않은 연산 존재 , 이진수(컴퓨터)에서 그러한 문제 발생

a = 0.3 + 0.6 
print(a)               # 0.899999999999

if a == 0.9:
     print(True)
else:
     print(False)     # False 가 출력됨!!! : 이진수에서의 실수연산 오류가 발생함 

• 실수 연산 오류 잡는 방법 : round( ) 함수 이용 
  • 소수 셋째짜리에서 반올림 => 소수점 둘째짜리에서 출력됨~
    round(123.456,2)   # 123.46

a = 0.3 + 0.6
print(round(a, 4)
if round(a, 4) == 0.9:       # 0.9
     print(True)
else:
     print(False)               # True

• round 함수 이용함으로써 0.9 의 값과 True 라고 올바르게 출력이 됨~

수 자료형의 연산

• 나누기 연산자 (/) 주의해서 사용 : (/) 는 나눠진 결과를 '실수형'으로 변환
• 다양한 설계할 때, 나머지 연산자(%) 이용 
  • 예) a 가 홀수인지 check    ->   i % 2 != 0    ->    a = 홀수
• 몫 연산자(//) 
• 거듭제곱(**)

a = 7
b = 3

# 나누기
print(a / b)                 # 2.333333335

# 나머지
print( a % b)              # 1

# 몫
print(a // b)               # 2

# 거듭제곱
print(a ** b)               # 125

# 제곱근
print(a ** 0.5)             # 2.2366..

리스트 자료형

여러 개의 data 연속적으로 처리하기 위해 사용하는 자료형~ 임