코딩테스트1.

방학 기간 중 코딩테스트 교육을 4일 동안 받게 되었다. 

 

필자는 교육내용이 정말 유익해서 블로그 정리를 통해 공부하고자 한다. 

 

먼저 코딩테스트의 기본이 되는 시간복잡도 표기법에 대해 간단히 짚고 넘어가자.

 

 시간복잡도는 본 포스팅에서 다루기엔 양이 방대하므로, 시간복잡도에 대해 자세히 알고 싶다면, 아래의 포스팅에서 확인할 수 있다. 

https://chancoding.tistory.com/43

[Python] 파이썬 자료형 및 연산자의 시간 복잡도(Big-O) 총 정리

 간단하게 빅-오메가, 빅-세타, 빅-오에 대해서만 짚고 넘아가자.

• 빅-오메가(n) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법
• 빅-세타(n) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법
• 빅-오(n) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

다음은 빅-오 표기법에 따라  표현한 시간 복잡도 그래프이다. 각각의 시간 복잡도는 데이터크기(N)의 증가에 따라 성능(수행시간)이 다르다는 것을 확인  할 수 있다.

 

 

 

 

2. 구간 합 구하기 

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 이 문제는 A의 누적합 S를 구하고, S를 이용해서 s와e번째의 A합을 구하는 문제이다.

1. A를 만들어주기

2. A의 누적합S를 만들기

3. s에서 e사이의 A원소들의 합 = S[e] - S[s-1]

 

from io import StringIO
## 항상 추워하심..

import sys
input = sys.stdin.readline
## 입력 문자열
input_str = \
"""
5 3
5 4 3 2 1
1 3
2 4
5 5
"""

## 문자열을 스트림으로 바꾸는 방법
stream = StringIO(input_str.strip())
input = stream.readline

subNo, quizNo = map(int, input().split())
#subNo : 숫자개수
#quizNo : 질문개수
print(subNo, quizNo)
>>> 5 3

A = [0] + list(map(int, input().split()))
print('A : ', A)
>>> A :  [0, 5, 4, 3, 2, 1]

##중복합 만들기 
S = [0] * len(A)

for i in range(1, len(A)):
	S[i] = S[i-1] + A[i]
print('S : ', S)
>>> S :  [0, 5, 9, 12, 14, 15]

for i in range(quizNo) :
	s, e = map(int, input().split())
    print(s,e, '\n')
    print(S[e] - S[s-1])
>>>
1 3
12
2 4
9
5 5
1

1번에서 1차원 리스트의  누적합S를 이용해서 문제를  풀었다. 

 

1차원일때, 경우의 수가 얼마 없기 때문에, 크게 어렵게 느껴지지 않았을 수 있다. 

 

하지만, A가 행렬로 주어지면,  A의 누적합 S를 이용해서  구간 사이의 합을 어떻게 구해야할까??

 

문제 2번에서 다뤄보자. 

 

from io import StringIO

 

## 입력 문자열
input_str = \
"""
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4
"""

 

## 문자열을 스트림으로 바꾸는 방법
stream = StringIO(input_str.strip()),

n,m = map(int, input().split())

 

n,m = map(int, input().split())

print('n,m : ', (n,m))\

>>>n,m : 4 3

 

A = [[0] * (n+1)]

for i in range(n):

    A.append([0] + list(map(int, input().split())))

print('A ': A)

>>>

A :  [[0, 0, 0, 0, 0], [0, 1, 2, 3, 4], [0, 2, 3, 4, 5], [0, 3, 4, 5, 6], [0, 4, 5, 6, 7]]

D = [[0] * (n+1) for _ in range(n+1)] #리스트 컴프리헨션
# '_'인덱스 값을 사용하지 않음. 
# 인덱스 값이 의미가 없을때 사용!
print('0인 D :', D)
print('\n')

>>>

0인 D : [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

for i in range(1, n+1): #행
    for j in range(1, n+1) : #열
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
        
print('채워진 D :', D)
print('\n')

>>> 

채워진 D : [[0, 0, 0, 0, 0], [0, 1, 3, 6, 10], [0, 3, 8, 15, 24], [0, 6, 15, 27, 42], [0, 10, 24, 42, 64]]

 

위 문제의 핵심은 구간행렬을 이용해서, 행렬A의 특정구간의 원소들의 합을 구하는 것이다. 

 

구간 합(행렬) 공식은 다음과 같다.

D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

 

 

 ## 이제 채워진 누적 합률을 마드는건가?싶었지만, 당하지만 않으면 괜찮아

 

## 구간 합 구하기

##구간합 구하기
for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
    print(result)
>>> 
27
6
64