코딩테스트 기초이론

ref: do it! 알고리즘 코딩테스트

3. 자료구조

---

3-1 배열과 리스트

파이썬에서는 배열과 리스트를 구분하지 않는다.

• 배열 : 메모리의 연속공간에 값이 채워져 있는 형태의 자료구조
  • 인덱스를 이용해 배열의 값 참조가능
  • 인텍스가 없으므로 값에 접근하려면 head 포인터부터 순서대로 접근해야 함.
    • 접근하는 속도가 느림
  • 포인터로 연결되어 있으므로 데이터 삽입, 삭제 속도가 빠름
  • 선언할때 크기지정 불필요
  • 배열보다 구조가 복잡리스트 : 값과 포인터를 묶은 노드라는것을 포인터로 연결한 자료구조

3-2 구간합

 

S[i] = A[0] + A[1]+ A[2]+ … + A[i-1]+ A[i]

S[i] = S[i-1] + A[i]

구간 합을 만드는 공식 ( i ~ j )

S[j] - S[i-1]

 

#백준 구간합 구하기 4 11659
import sys

input = sys.stdin.readline

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

prefix = [0]
for i in n_list:
    prefix.append((i+prefix[-1]))
# print(prefix)

for i in range(m):
    tmp = list(map(int, input().split()))
    print(prefix[tmp[1]]- prefix[tmp[0]-1])

합배열[1][j] = 합배열[1][j-1] + 숫자리스트[1][j]

                  2. 계산의 편의를 위해 0행, 0열은 0으로 채움

                  3. 구간합 구하기붉은 영역([2, 2] ~ [5, 5]) 구간합 구하기

 

 

합배열[i][j] = 합배열[i][j-1] + 합배열[i-1][j] - 합배열[i-1][j-1] + 숫자리스트[i][j]

• 붉은영역 구간합을 구할떄 필요없는부분(파란부분1, 2)을 빼주고, 두번 빼진 부분(노란영역)을 더해주면 간단하게 해결된다.

합배열[i][j] = 합배열[i][j-1] + 합배열[i-1][j] - 합배열[i-1][j-1] + 숫자리스트[i][j]

붉은영역 구간합 = 합배열[5][5] -파란색합배열[1][5] - 파란색합배열[5][1] + 노란색합배열[1][1]

•  

# 백준 구간합구하기 5 11660
import sys
input = sys.stdin.readline

a, b = map(int, input().split())
table=[[0]*(a+1)]
prefix=[[0]*(a+1) for _ in range(a+1)]

for i in range(a):
    row = [0] + [int(x) for x in input().split()]
    table.append(row)

for i in range(1, a+1):
    for j in range(1, a+1):
        prefix[i][j] = (prefix[i-1][j] + prefix[i][j-1] - 
                        prefix[i-1][j-1] + table[i][j] )

# print(prefix)
for i in range(b):
    x1, y1, x2, y2 = map(int, input().split())
    answer = (prefix[x2][y2] + prefix[x1-1][y1-1] 
              - prefix[x2][y1-1] - prefix[x1-1][y2])
    print(answer)

3-3 투 포인터

2개의 포인터로 알고리즘 시간복잡도를 최적화합니다.

• 투포인터 이동 원칙
  • sum > Nstart_index++
  • sum = sum - start_index
  • sum < Nsum = sum + end_index
  • end_index++;
  • sum == Nsum = sum+end_index;
  • count ++
  • end_index++

3-4 슬라이딩 윈도우

2개의 포인터로 범위를 지정한다음, 범위(window)를 유지한채로 이동(sliding)하여 문제를 해결합니다.

• 투포인터와 유사한 방법
• 맨 앞값과 맨 뒷값을 계속하여 빼고 더하는 업데이트 방식

3-5 스택과 큐

• 스택 : 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조

 

• 큐 : 삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조