알고리즘 코딩테스트 - 자료구조 (배열, 리스트, 구간합)

1. 배열과 리스트

 

(1) 배열

• 연속 공간에 값이 채워져 있는 형태의 자료구조
• 장점 : 인덱스를 사용하여 값에 바로 접근할 수 있음
• 단점 : 삽입&삭제가 어려움, 배열의 크기는 선언할 때 지정할 수 있음
• 구조상 간단함으로 코딩테스트에서 많이 활용됨

 

(2) 리스트

• 값과 포인터를 묶은 노드라는 것을 포인터로 연결
• 장점 : 선언할 때, 크기를 별도로 지정하지 않아도 됨 (즉, 크기가 변하기 쉬운 데이터를 다룰 때 적합함)
• 단점 : 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 함

-> 그러나 파이썬에서는 배열과 리스트를 구분하지 않음 (컴퓨터 공학에서는 배열과 리스트가 명확하게 구분되는 자료구조는 맞음)

 

 

(3) 문제 실습 1

 

백준 11720 : 숫자의 합 구하기

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

11720번: 숫자의 합

 

이 문제는 쉬워서 딱히 풀이가 필요 없습니다 !

• numbers 이라는 변수에 list 함수를 이용하여 숫자를 한 자리씩 나누어 받음
• 주의해야 할 것 : list 함수를 쓴 후, 각각은 int 형태가 아니라, str 형태임. 따라서 sum 변수에 더해줄 때, int형으로 변환시켜줘야 함

 

n = input() # 숫자의 개수
numbers = list(input()) # 공백 없이 주어진 n개의 숫자
sum = 0

for i in numbers :
  sum = sum + int(i)


print(sum)

 

 

(4) 문제실습 2

 

백준 1546 : 평균 구하기 

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

1546번: 평균

 

이 문제의 교훈은 로직을 쉽게 생각할 수 있는 법을 찾자 ! 입니다.

• 문제 그대로 로직을 구현해보면 ( A / M * 100 + B / M * 100 + C / M * 100) / 3 = ( A + B + C ) * 100 / M /3 
• 훨씬 더 코드가 간단해짐
• map 함수 : 여러 인자에 같은 함수를 적용할 때, 편리하게 적용시킬 수 있는 함수 ( map과 int가 세트라고 생각하면 쉬움)

# 백준 1546
n = int(input())
mylist = list(map(int, input().split()))
max_number = max(mylist)

total_number = 0
for i in range(0, n) :
  total_number += mylist[i]

print(total_number * 100 / max_number / n)

 

---

2. 구간 합

(1) 구간 합의 핵심 이론 

• 합 배열 : 기존의 리스트 데이터를 전처리한 배열
• 합 배열 만드는 공식 : S[i] = S[i-1] + A[i]

• 구간 합 만드는 공식 : S[j] - S[j-1]

 

(2) 문제 실습 1

 

백준 11659 : 구간 합 구하기 

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

11659번: 구간 합 구하기 4

 

구간 합 배열은 n인지, n-1 인지 주의해야 함

• 한 두줄 입력받는 문제들과는 다르게 반복문으로 여러 줄 출력해야 함으로 sys.stdin.readline을 이용 (코랩에서는 지원안됨)
• map 함수를 이용해서 변수들 값을 받음
• list를 list()로 선언하는 것이 아닌, [0]으로 선언하고, append 함수로 합 배열을 만들어 줌 (그렇기에 n-1을 잘 봐야함)

 

import sys
input = sys.stdin.readline

# 변수 선언
numbercount, sumcount = map(int, input().split())
numbers = list(map(int, input().split()))
prefix_sum = [0]
temp = 0

for i in numbers :
  temp = temp + i
  prefix_sum.append(temp)


for i in range(sumcount):
  s,e = map(int, input().split())
  print(prefix_sum[e] - prefix_sum[s-1])

print(prefix_sum )

 

 

백준 11660번 : 구간 합 구하기 2

 

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

11660번: 구간 합 구하기 5

 

이 문제는 많이 어렵습니다 ! 앞의 문제에서 2차원으로 확장된 것으로 생각하여 구간 합 배열을 고민하는 것이 핵심입니다 

• 2차원 구간 합 배열의 1행, 1열부터 구하기

• 나머지 이차원 구간 합 배열 채우기

• 따라서, 나머지 값을 채우는 구간 합 공식은 : D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
A = [[0] * (n+1)]
D = [[0] * (n+1) for _ in range(n+1)] # 2차원 배열 만들기

for i in range(n) :
  A_row = [0] + [int(x) for x in input().split()]
  A.append(A_row)

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]

for _ 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)

 

많이 어렵네용 ㅠㅠ

 

 

 

* do it 알고리즘 코딩테스트 내용을 참고하였습니다.