🧚‍♂️알고리즘🧚‍♂️ - 자료구조 - 배열/리스트/구간합

 doit 코딩테스트 알고리즘-파이썬

<자료구조>

---

<배열과 리스트>

배열	리스트
메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조	노드(값+포인터)를 포인터로 연결한 자료구조
인덱스 사용/값에 바로 접근	값 접근 속도가 느리다
삽입,삭제가 어려움	삽입 삭제 쉬움
선언 후 크기 조정 불가	크기가 정해져 있지 않음
구조가 간단	비교적 구조 복잠

파이썬에서는 배열/리스트 구분이 없음(하나로 합쳐짐)

---

1번

11720번: 숫자의 합

- bool형 숫자 변환을 유용하게 사용해 보자

 

2번

1546번: 평균

sum()max()

---

<구간 합>

시간 복잡도 O(N) -> O(1)

 

합 배열 S

S[i] = A[0]+ A[1] + ....A[i] 

 

합 배열 S 공식

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

 

구간 합 공식(j부터 i 까지)

S[j] - S[i-1]

---

1번

11659번: 구간 합 구하기 4

[:-1] 문자열 받을 때만 하기..

 

2번

11660번: 구간 합 구하기 5

이렇게 갑자기 어려워지나?

- 엇 위에 2번 잘못 생각했다 더한 두 값의 겹치는 부분을 한번 빼야 한다

- 어려운 부분 짤 때 헷갈리지 않도록 처음 값 설정할 때 0 미리 넣어 놓기!(여기서는 첫번째 열/행에서도 전 원소 봐야 하는 이유도)

S = [[0] *(N+1) for _ in range(N + 1)]

이렇게 하면 2차원 배열처럼 나온다!

Nlist = list(map(int,stdin.readline().split()))
Nlist.insert(0,0)
A.append(Nlist)

Nlist = [0] + [int(i) for i in stdin.readline().split()]
A.append(Nlist)

- .insert(인덱스번호,값)

- 위처럼 하려고 했는데 아래같은 신기한 방법도 있다.

from sys import stdin
N, M = map(int,stdin.readline().split()) # 표 크기 / 테스트케이스
A = [[0] *(N+1)] # 1행
S = [[0] *(N+1) for _ in range(N + 1)] #WOW
# 1번
for _ in range(N):
    Nlist = [0] + [int(i) for i in stdin.readline().split()]
    A.append(Nlist)

# 2번 
for i in range(1,N+1): #행
    for j in range(1,N+1): #열
        S [i][j] = S[i-1][j] + S [i][j-1] + A[i][j] - S [i-1][j-1]

# 3번
for _ in range(M): 
    i1,j1,i2,j2 = map(int,stdin.readline().split())
    print( S[i2][j2] - S [i2][j1-1] - S [i1-1][j2] + S [i1-1][j1-1])

휴

 

3번

10986번: 나머지 합

*특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값 = 이 구간 합의 나머지 연산을 한 값은 동일함*

즉 구간합들로 계산해도 됨

구간합들의 하나의 나머지 값과 다른 나머지 값이 같으면, 그 사이 값의 합은 나눈 값으로 딱 떨어지므로,

나머지 값이 같은 두 개 값들의 쌍을 찾으면 됨

from sys import stdin
N, M = map(int,stdin.readline().split()) # 값 크기 / 나눌값
A = list(map(int,stdin.readline().split()))
S = [0] # 구간합
C = [ 0 for _ in range(M)] # 나머지
result = 0 # 답

# 1번
for i in range(1,N+1):
    Asum = S[i-1] + A[i-1]
    S.append(Asum)

# 2번 
for i in range(1,N+1): 
    div = S[i] % M
    C[div] += 1
    if div == 0:
        result += 1

# 3번
for i in range(M): 
    if C[i] > 0:
        result += ((C[i]) * (C[i]-1) // 2) # 조합

print(result)

와 이런 문제는 혼자서 어떻게 풀지?

---

슈도 코드 (의사 코드)

프로그램을 작성할 때 각 모듈이 작동하는 논리를 표현하기 위한 언어

특정 프로그래밍 언어의 문법에 따라 쓰인 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써놓은 코드

---

끗