Do it! 코딩테스트 - 자료구조,배열과 리스트 (1)

onyoo·2022년 12월 6일

알고리즘

목록 보기

9/40

자료구조

자료구조는 데이터를 효율적으로 저장,접근,수정하기 위한 그릇이다. 코딩 테스트에서는 각 문제에 주어진 입력 데이터의 형태와 사용해야 하는 알고리즈에 따라 적절한 자료구조를 선정해 사용하는 것이 매우 중요하다.

배열과 리스트

기본 자료구조인 배열과 리스트는 비슷한 점도 많지만 다른 점도 많다. 파이썬에서는 리스트가 배열의 특성도 함께 내포하고 있어 크게 구분하여 사용하지는 않지만 두 자료구조의 특징과 동작 원리는 이해하고 있는 것이 좋다.

배열과 리스트의 핵심 이론

배열
- 배열은 메모리의 연속 공간에 값이 채워져있는 형태의 자료구조이다. 배열의 값은 인덱스를 통해 참조할 수 있으며 선언한 자료형의 값만 저장할 수 있다.
- 특징
  - 인덱스를 사용하여 값에 바로 접근 할 수 있다.
  - 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.
  - 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
  - 구조가 간단하므로 코딩 테스트에서 많이 사용한다 !
리스트
- 리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다.
- 특징
  - 인덱스가 없으므로 값에 접근하려면 head 포인터부터 순서대로 접근해야한다. 다시말해 값에 접근하는 속도가 느리다.
  - 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.
  - 선언할 때 크기를 별도로 지정하지 않아도 된다. 다시말해 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰때 적절하다.
  - 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.

문제

숫자의 합 구하기

포인트 → 리스트의 인덱스를 이용하기

n = int(input())
arr = input() 
#이런식으로 입력받아도 상관없다. 어짜피 인덱스가 구분지어줄테니까.

answer = 0

for i in range(n):
    answer+= int(arr[i])

print(answer)

평균 구하기

최고점수와 총합을 미리 계산해둔 상태에서 주어진 식에 대입하여 구하면 된다

한 과목과 관련된 수식을 총합한 후 관련 수식으로 변환해 로직을 간단하게 할 수 있다.

n = int(input())
arr = list(map(int,input().split()))

m = max(arr)
tmp = 0

for i in range(n):
    tmp += arr[i]/m*100

print(tmp/n)

#혼자 풀어보았을 때

n = int(input())
arr = list(map(int,input().split()))

m = max(arr)
s = sum(arr)

print(s*100/m/n)

#책 풀이
#좀더 간결하다

구간 합

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 이다.

구간 합의 핵심 이론
- 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다. 리스트 A가 있을 때 합 배열 S는 다음과 같이 정의 할 수 있다.
- S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i]
- 합 배열은 기존의 리스트 데이터를 전처리한 배열이라고 생각하면 된다.
- 합 배열을 미리 구해놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(n)에서 O(1)로 감소한다.
- A[i] ~ A[j] 까지의 리스트 합을 합배열 없이 구하는 경우 최악의 경우 i 가 0이고 j가 n인 경우로 시간 복잡도는 O(n)이다. 이런 경우 합배열을 이용하면 O(1)안에 답을 구할 수 있다.
- 합배열을 구하는 공식 : S[i] = S[i-1] + A[i]
- 구간 합을 구하는 공식 : S[j] - S[i-1]
- A[2] ~ A[5] 까지의 구간합을 구하는 과정을 보자
  - 위의 그림을 보면 합배열과 구간합이 연관되어있다는 것을 알 수 있다.
  - 해당 그림을 보면 구간합 s[5] 에서 s[1]을 빼면 구간합이 나온다는 것을 알 수 있다.
  - 즉, 합배열만 미리 구해두면 구간 합은 한번의 계산으로 구할 수 있는 것이다.

문제

구간 합 구하기 1

 n,m = map(int,input().split())
 
 arr = list(map(int,input().split()))
 
 s = sum(arr)
 answer = []
 
 for i in range(m):
     start,end = map(int,input().split())
     answer.append(sum(arr[:end]) - sum(arr[:start-1]))
 
 for i in range(m):
     print(answer[i])
    # 처음에 작성한 코드

 n,m = map(int,input().split())
 
 arr = list(map(int,input().split()))
 s_arr = [0] #시작 인덱스가 1이되도록 함
 s = 0
 answer = []
 
 for i in range(n):
     s += arr[i]
     s_arr.append(s)
 #합배열 구하기
 
 for i in range(m):
     start,end = map(int,input().split())
     print(s_arr[end]-s_arr[start-1])
 #합배열 공식 사용

사담이지만 해당 코드 자체가 아예 틀린건 아니지만, 백준 채점에서 시간초과가 떳다. 왜 떳나 싶어서 찾아봤더니.
input과 sys.stdin.readline의 차이점 때문이었다.
input() 내장 함수는 parameter로 prompt message를 받을 수 있다.따라서 입력받기 전 prompt message를 출력해야 한다.
input() 내장 함수는 입력받은 값의 개행 문자를 삭제시켜서 리턴한다.
즉 입력받은 문자열에 rstrip() 함수를 적용시켜서 리턴한다.
sys.stdin.readline()은 prompt message를 인수로 받지 않는다.
sys.stdin.readline()은 개행 문자를 포함한 값을 리턴한다.

즉 input 내장 함수는 sys.stdin.readline()과 비교해서 prompt message를 출력하고,개행문자를 삭제한 값을 리턴하기 때문에 느리다.

from sys import stdin

n,m = map(int,stdin.readline().split())
numbers = list(map(int,stdin.readline().split()))

hap_numbers = [0]
tmp = 0

for i in numbers:
    tmp += i
    hap_numbers.append(tmp)

for i in range(m):
    s,e = map(int,stdin.readline().split())
    print(hap_numbers[e]-hap_numbers[s-1])

#수정된 코드

11659번: 구간 합 구하기 4

구간 합 구하기 2

해당 문제의 경우는 2차원 배열로 구간합을 구해야하기 때문에 상당히 어렵다고 느꼈다.
앞선 문제와 같이 해당 문제를 풀기전에 일단 준비해야할게 있다. range 에러를 피하기 위해서는 2차원 배열의 크기를 하나씩 늘려준다. n+1 * n+1로 늘려준 뒤 맨 첫번째 리스트와 각 리스트의 첫값은 0으로 세팅해준다.
구간합을 저장할 이차원 배열은 모두 0으로 초기화 해주는 것이 정신건강에 이롭다 → 왜냐면 값 계산할 때 이전 구간합을 사용하는 연산이 있는데 맨 처음값의 경우에는 해당 값이 없다 ! 그걸 예외 처리를 해주지 않으려면 0으로 모두 초기화 하는것이 좋다.

2차원 배열의 구간합을 구하는 공식 h[i][j] = h[i][j-1] + h[i-1][j] - h[i-1][j-1] + n[i][j]
구간 합을 이용하여 지정된 범위의 합을 구하는 공식 퍼즐처럼 큰 범위를 먼저 구한다음, 거기에서 겹치는 부분은 신경쓰지 않고 빼버린다 그런뒤 겹쳣던 범위를 다시 더해주는 것이다.
```
h[x2][y2] - h[x1-1][y2] - h[x2][y1-1] + h[x1-1][y1-1]
```

from sys import stdin

n,m = map(int,stdin.readline().split())

numbers = [[0] * (n+1)]
hap_numbers = [[0] * (n+1) for _ in range(n+1)]

for i in range(n):
    arr = [0] + list(map(int,stdin.readline().split()))
    numbers.append(arr)

print(numbers)

for i in range(1,n+1):
    for j in range(1,n+1):
        hap_numbers[i][j] = hap_numbers[i][j-1] + hap_numbers[i-1][j] - hap_numbers[i-1][j-1] + numbers[i][j]

for _ in range(m):
    x1,y1,x2,y2 = map(int,stdin.readline().split())
    answer = hap_numbers[x2][y2] - hap_numbers[x1-1][y2] - hap_numbers[x2][y1-1] + hap_numbers[x1-1][y1-1]
    print(answer)