[Python] ECC 1주차 정리 - 자료구조

# 1. 배열과 리스트

• 배열이란?
  • 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조. 
  • 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다.
  • 특정 인덱스의 값을 삽입/삭제하거나 새로운 값을 삽입하기 어렵다. 한번 선언하면 크기를 조절할 수 없다.
• 리스트란?
  • 값과 포이터를 묶은 노드를 포인터로 연결한 자료구조.
  • 인덱스가 없어 접근 속도가 느리지만, 데이터의 삭제/삽입 속도는 빠르다.
  • 크기가 정해져 있지 않다. 다만 포인터를 저장할 공간이 필요하여 구조가 배열보다 복잡하다.
• 파이썬의 배열은 리스트의 특징과 배열 모두 가진다.

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

1546번: 평균

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

my_max = max(my_list) # 입력받은 점수의 최댓값 구하기
sum=sum(my_list)
print(sum*100/my_max/int(n)) # 한 번에 점수 계산이 가능하다.

 

---

# 2. 구간 합

• 구간 합이란?
  • 합 배열 S : S[i] = A[0] + A[1] + ... + A[i] = S[i-1] +A[i]
  • 합 배열을 미리 구해 좋으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.
  • 이를 이용해 i부터 j 까지의 구간 합도 쉽게 구할 수 있다. S[j] - S[i-1]

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

11659번: 구간 합 구하기 4

import sys

input = sys.stdin.readline

n, m =map(int, input().split())
num=list(map(int, input().split()))
my_list = [0] # 처음 저장을 위해 0부터 저장

for i in range(1,n+1):
    my_list.append(my_list[i-1]+num[i-1]) # my_list의 3번째에는 3번째까지의 수의 합이 저장
for j in range(m):
    i, j = map(int, input().split())
    print(my_list[j]-my_list[i-1])

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

11660번: 구간 합 구하기 5

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)] # 구간 합 행렬  Ex) D[1][j] = D[1][j-1] + A[1][j]

for i in range(n):
    A_row = [0] + [int(x) for x in input().split()] # [0] + 입력 받은 한 줄을 저장
    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())
    # 구간 합 배열 공식 Ex) 2 2 3 4 = D[3][4] - D[1][4] - D[3][1] + D[1][1]
    result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
    print(result)

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

10986번: 나머지 합

import sys

input = sys.stdin.readline

n, m =map(int, input().split()) 
# (A+B)%C == ((A%C)+(B%C))%C 이므로 특정 구간 수들의 나머지 연산을 더해 나머지 연산한 값과 구간 합의 나머지 연산 값은 동일한다.
# S[j]%M의 값과 S[i]%M의 값이 같으면 (S[j]-S[i])%M은 0이다.
# 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 후 S[j]와 S[i]가 같은 쌍을 찾으면 된다.
A = list(map(int, input().split()))
S = [0]*n # 합 배열
C = [0]*m # 같은 나머지의 인덱스를 카운트하는 리스트. 즉 m의 나머지므로 0~m-1 까지의 인덱스.
S[0] = A[0]
answer = 0

for i in range(1, n):
    S[i] = S[i-1] +A[i] # 합 배열 저장

for i in range(n):
    remainder = S[i]%m # 합 배열의 값에 % 연산 수행
    if remainder == 0: # 0~i까지의 구간 합 자체가 0인 경우는 무조건 M으로 나누어 떨어지므로 정답에 더하기
        answer +=1
    # print(C)
    C[remainder] += 1 # 나머지가 같은 인덱스의 개수 값 증가시키기

for i in range(m):
    # 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수 더하기
    if C[i] > 1:
        answer += (C[i]*(C[i]-1)//2)

print(answer)

 

---

# 3. 투 포인터

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

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

2018번: 수들의 합 5

import sys

input = sys.stdin.readline

n = int(input())
count = 1 # n 숫자 하나만 뽑는 경우 포함
start_idx = 1
end_idx = 1
sum = 1

while end_idx!=n:
    if sum == n : # 정답인 경우
        count +=1
        end_idx += 1
        sum += end_idx
    elif sum > n : # n을 넘으면 
        sum -= start_idx # sum에서 왼쪽 인덱스의 값 빼기
        start_idx += 1 # 왼쪽 인덱스를 한칸 옆으로
    else:
        end_idx += 1 # 오른쪽 인덱스 한칸 옆으로
        sum += end_idx
print(count)

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

1940번: 주몽

import sys

input = sys.stdin.readline

n = int(input())
m = int(input())
A = list(map(int, input().split()))
A.sort() # 일반적으로 정렬 알고리즘은 nlogn이다. 이번 문제에서 n은 15,000 이하이므로 시간 초과 X.
count = 0
i = 0 # 왼쪽 인덱스
j = n-1 # 오른쪽 인덱스

while i<j : # 포인터를 이동하면서 처리
    if A[i] + A[j] < m :
        i +=1 # 왼쪽 인덱스 이동
    elif A[i] + A[j] >m :
        j -=1 # 오른쪽 인덱스 이동
    else : # A[i]+A[j] 가 m과 같은 경우, 갑옷을 만들 수 있는 경우!
        count += 1
        i += 1
        j -= 1

print(count)

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

1253번: 좋다

import sys

input = sys.stdin.readline

n = int(input())
result = 0

A = list(map(int, input().split()))
A.sort()

for k in range(n):
    find = A[k] # K는 합이 되는 지 판별하는 수
    i=0
    j=n-1

    while i<j: #투 포인터
        if A[i] + A[j] == find: # find가 서로 다른 두 수의 합임.
            if i!=k and j != k: # 또한 자기 자신이 좋은 수 만들기에 포함되면 안됨.
                result +=1
                break
            elif i ==k:
                i+=1
            elif j==k:
                j-=1
        elif A[i]+A[j]<find:
            i+=1
        else:
            j-=1

print(result)

 

---

# 4. 슬라이딩 윈도우

• 슬라이딩 윈도우란?
  • 2개의 포인터로 범위를 지정한 후, 범위(window)를 유지한 채로 이동하며 문제를 해결한다.

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

12891번: DNA 비밀번호

import sys
input = sys.stdin.readline

# 부분 문자열의 길이 p만큼 DNA 문자열에서 이동하며 조건에 맞는지 탐색한다.
# 문자열을 검사할 때 기존 검사 결과에 새로 들어온 문자열, 제거되는 문자열만 반영하여 확인한다.
checkList = [0]*4 # 비밀번호 체크 리스트
my_List = [0]*4 # 현재 상태 리스트 (A, C, G, T)
checkSecret = 0 # 몇 개의 문자와 관련된 개수를 충족했는지 판단

# 함수 정의
def my_add(c): # 새로 들어온 문자를 처리하는 함수
    # myList에 새로운 값을 더하고 조건에 따라 checkSecret을 업데이트
    global checkList, my_List, checkSecret
    if c=='A':
        my_List[0] += 1
        if my_List[0] == checkList[0]:
            checkSecret += 1
    elif c =='C':
        my_List[1] +=1
        if my_List[1] == checkList[1]:
            checkSecret += 1
    elif c =='G':
        my_List[2] +=1
        if my_List[2] == checkList[2]:
            checkSecret += 1
    elif c =='T':
        my_List[3] +=1
        if my_List[3] == checkList[3]:
            checkSecret += 1

def myremove(c): # 제거되는 문자를 처리하는 함수
    # myList에 새로운 값을 제거하고 조건에 따라 checkSecret을 업데이트
    global checkList, my_List, checkSecret
    if c=='A':
        if my_List[0]==checkList[0]:
            checkSecret -=1
        my_List[0]-=1
    elif c=='C':
        if my_List[1]==checkList[1]:
            checkSecret -=1
        my_List[1]-=1
    elif c=='G':
        if my_List[2]==checkList[2]:
            checkSecret -=1
        my_List[2]-=1
    elif c=='T':
        if my_List[3]==checkList[3]:
            checkSecret -=1
        my_List[3]-=1

S,P = map(int, input().split()) # 문자열 크기, 부분 문자열 크기
Result = 0
A= list(input())

checkList = list(map(int, input().split()))

for i in range(4):
    if checkList[i]==0: # 값이 0이면 비밀번호 개수가 이미 만족 되었다는 뜻이므로 +1
        checkSecret += 1
for i in range(P): # 초기 P 부분 문자열 처리 부분
    my_add(A[i])

if checkSecret == 4: # 4 자릿수와 관련된 크기가 모두 충족될 때 유효한 비밀번호
    Result +=1

for i in range(P, S): # 한 칸씩 이동하며 유효한 비밀번호인지 판단
    j = i-P # j가 왼쪽, i가 오른쪽 인덱스
    my_add(A[i])
    myremove(A[j])
    if checkSecret == 4: # 판단
        Result += 1

print(Result)

 

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

11003번: 최솟값 찾기

from collections import deque

N, L = map(int, input().split())
mydeque = deque()
now = list(map(int, input().split()))

# 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄임.
# nlogn인 정렬은 사용 X
for i in range(N): # now리스트를 탐색(now[i]를 현재 값으로 세팅)
    while mydeque and mydeque[-1][0] > now [i]: 
        mydeque.pop() # 덱의 마지막 위치에서 현재 값보다 큰 값은 덱에서 제거
    mydeque.append((now[i], i)) # 덱의 마지막 위치에 현재 값, 인덱스 저장
    if mydeque[0][1] <= i - L: # L의 범위에서 벗어난 값은 덱에서 제거
        mydeque.popleft()
    print(mydeque[0][0], end =' ')

---

# 5. 스택과 큐

• 스택이란?
  • 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조.
  • 파이썬의 스택(리스트로 구현)
    • top : 삽입과 삭제가 일어나는 위치
    • s.append(data) : top 위치에 새로운 데이터 삽입
    • s.pop() : top 위치에 있는 데이터를 삭제 후 확인
    • s[-1] : top 위치에 있는 데이터를 확인
  • DFS(깊이우선탐색), 백트래킹 종류에 효과적이다.
• 큐
  • 삽입과 삭제 연산이 선업선출로 이뤄지는 자료 구조
  • 파이썬의 큐(deque로 구현)
    • rear : 큐에서 가장 끝 데이터
    • front : 큐에서 가장 앞 데이터
    • s.append(data) : rear 부분에 새로운 데이터 삽입
    • s.popleft() : front 부분에 있는 데이터를 삭제하고 확인
    • s[0] : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산
  • BFS(너비우선탐색)에서 자주 사용된다.
  • 사실 deque는 스택 + 큐라고 보면 된다. pop(), popleft(), append(), appendleft() 전부 지원하며 연결리스트이므로 중간에 삽입하는 것도 가능하다.

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

1874번: 스택 수열

import sys
input = sys.stdin.readline

n = int(input())
A = [0]*n

for i in range(n):
    A[i] = int(input())

stack = []
num = 1
result = True
answer = ""

for i in range(n):
    su = A[i]
    if su >= num: # 현재 수열 값 >= 오름차순 자연수 : 값이 같아질 때까지 append() 수행
        while su>=num:
            stack.append(num)
            num +=1
            answer += "+\n"
        stack.pop()
        answer += "-\n"
    else: # 현재 수열값 < 오름차순 자연수 : pop()을 수행해 수열 원소를 꺼냄
        n = stack.pop()
        # 스택의 가장 위의 수가 만들어야 하는 수열의 수보다 크면 수열을 출력할 수 없음
        if n > su:
            print("NO")
            result = False
            break
        else:
            answer += "-\n"
if result:
    print(answer)

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

17298번: 오큰수

import sys
input=sys.stdin.readline
n = int(input())
ans = [0]*n
A = list(map(int, input().split()))
myStack = [] # 스택 선언

for i in range(n):
    # 스택이 비어 있지 않고 현재 수열이 스택 top 인덱스가 가리키는 수열보다 클 경우
    while myStack and A[myStack[-1]] < A[i]:
        ans[myStack.pop()] = A[i] # 정답리스트에 오큰수를 현재 수열로 저장하기
    myStack.append(i) # 스텍에 인덱스 저장

while myStack: # 반복문을 다 돌고 나왔는데 스택이 비어 있지 않다면 빌 때까지
    ans[myStack.pop()] = -1

result = ""

for i in range(n):
    result += str(ans[i])+" " # 출력

print(result)

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

2164번: 카드2

from collections import deque
N = int(input())
myQueue = deque()

for i in range(1, N+1):
    myQueue.append(i)

while len(myQueue) > 1: # 카드가 한 장 남을 때까지
    myQueue.popleft() # 맨 위 카드 버리기
    myQueue.append(myQueue.popleft()) # 맨 위 카드 가장 아래로 이동

print(myQueue[0])

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

11286번: 절댓값 힙

from queue import PriorityQueue # 우선순위 큐
import sys
print = sys.stdout.write
input = sys.stdin.readline
N= int(input())
myQueue = PriorityQueue()

for i in range(N):
    request = int(input())
    if request == 0:
        if myQueue.empty():
            print('0\n')
        else:
            temp = myQueue.get()
            print(str((temp[1]))+'\n')
    else:
        # 절댓값을 기준으로 정렬하고 같으면 음수 우선 정렬하도록 구성
        myQueue.put((abs(request), request))

• 우선순위 큐에서 put()할 때 데이터의 순서가 정렬의 우선순위가 된다.

---

# 회고

 

오랜만에 다시 보는 자료구조 문제이다.

다시 풀어도 못풀겠다...ㅎ 아예 확실하게 관련 문제들을 풀고 넘어가야겠다.

이번에 열심히 해서 골드를 목표로..