Coding Test(Algorithm) - Python

문제 해결 과정

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

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

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

4. 소스코드 설계 및 코딩

시간 복잡도

O(n^2) => O(xlogx) => O(x) => O(logx)

 

<시간제한 1초>

N의 범위 500 : O(N^3)

N의 범위 2,000: O(N^2)

N의 범위 100,000 : O(NlogN)

N의 범위 10,000,000 : O(N)

 

수행 시간 측정 

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

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

지수 표현 방식

#1,000,000,000 지수 표현 방식
a = 1e9 

#752.5
a = 75.25e1

#3.954
a = 3954e-3

소수 구하기

#2 ~ (x-1) 사이의 값이 x와 나누어 떨어지면 안된다는 소수의 특성을 이용하여 구할 수 있음

for i in range(2,a):
    if(a%i==0):
      return False

#에라토스테네스의 체 이용 O(NloglogN)

def isprime(m, n):
  n += 1                            # for문 사용을 위한 n += 1
  prime = [True] * n                # n개의 [True]가 있는 리스트 생성
  for i in range(2, int(n**0.5)+1): # n의 제곱근까지만 검사
    if prime[i]:                    # prime[i]가 True일때
      for j in range(2*i, n, i):    # prime 내 i의 배수들을 False로 변환
        prime[j] = False

  for i in range(m, n):
    if i > 1 and prime[i] == True:  # 1 이상이면서 남은 소수들을 출력
      print(i)

약수 구하기

for a in range(1, n+1 ): #O(n^2)
    if n % a == 0:
        print(a)

n = 10
for i in range(1, n//2 + 1): #O(n^3/2)
    if n % i == 0:
        print(i, end=" ")
print(n)

n = 20
for i in range(1, int(n**0.5)):
    if n % i == 0:
        print(i, end=" ")
        print(n//i, end=" ")
i += 1
if i**2 == n:
    print(i)

하노이의 탑

data = []
def hanoi(N, start, to, via):
    if N == 1:
        data.append([start,to])
    else:
        hanoi(N-1, start, via, to)
        data.append([start,to])
        hanoi(N-1, via, to, start)

n = int(input())
hanoi(n, '1', '3', '2')

print(len(data))
for i in data:
    print(' '.join(i))

백트래킹(Backtracking)

길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행

즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적

보통 재귀로 구현하며 조건이 맞지 않으면 종료한다.

DFS(깊이 우선 탐색) 기반