[2024 동계모각코] 3주차 결과

"Do it! 알고리즘 코딩테스트 with Python" 책에서

03-1 배열과 리스트~03-2 구간 합 부분을 풀어볼 것입니다.

---

 

03-1 배열과 리스트

배열과 리스트의 핵심 이론

배열

배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조입니다.

배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있습니다.

배열의 특징

1. 인덱스를 사용하여 값에 바로 접근 가능.

2. 새로운 값을 삽입 or 특정 인덱스에 있는 값 삭제 어려움. (값을 삽입 or 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.)

3. 배열의 크기는 선언할 때 지정 가능, 한 번 선언 시 크기를 늘리거나 줄일 수 없음.

4. 구조가 간단-> 코딩테스트에서 많이 사용됨.

---

리스트

리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조입니다. 이때 노드는 컴퓨터 과학에서 값, 포인터를 쌍으로 갖는 기초 단위를 부르는 말입니다.

 

 리스트의 특징

1. 인덱스가 없으므로 값에 접근 시 Head 포인터부터 순서대로 접근해야 함. 다시 말해 값에 접근하는 속도가 느림.

2. 포인터로 연결되어 있어 데이터를 삽입하거나 삭제하는 연산 속도 빠름.

3. 선언할 때 크기를 별도로 지정하지 않아도 됨!! 다시 말해 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절함.

4. 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡함.

---

 

문제 001 숫자의 합 구하기

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

 

01단계 문제 분석하기

02단계 손으로 풀어보기

03단계 슈도코드 작성하기

04단계 코드 구현하기

과정을 거쳐서 코드를 구현하였습니다.

 

# 숫자의 합 구하기
n=int(input())  # n 값 받기
numbers=list(input()) # numbers 변수에 list 함수를 이용하여 숫자를 한 자리씩 나누어 받기
# list(input())은 입력 데이터 형태가 연속된 문자열임임
sum=0   # sum 변수 선언

for i in numbers :# for numbers 탐색:
    sum+=int(i) # sum 변수에 numbers에 있는 각 자릿수를 가져와 더하기

print(sum)  # sum출력

저는 위와 같은 코드로 문제를 풀었는데 아래와 같이 푼 사람도 있어서 참고로 남겨봅니다.

# 숫자의 합 구하기(다른 방법)
num=int(input())
numbers=list(map(int, input()))
print(sum(numbers))

 

---

문제 002 평균 구하기

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

# 평균

N=int(input())  # 시험 본 과목의 개수 N
grade=list(map(int,input().split())) # 세준이의 현재 성적 점수들은 리스트로

M=max(grade) # 점수들의 최댓값을 M이라고 하자
for i in range(len(grade)):    
    grade[i]=grade[i]/M*100 # 리스트의 모든 점수들을 점수/M*100으로 고쳐보자

total=0   # 리스트의 모든 점수들의 합인 total 초기화
for i in range(len(grade)):   
    total+=grade[i]
    
print(total/N)
# 리스트의 모든 점수들의 합을 N으로 나눠서 평균을 구하자

---

03-2 구간 합

구간 합의 핵심 이론: 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 합니다. 리스트 A가 있을 때 합 배열 S는 다음과 같이 정의합니다.

 

합 배열 S 정의

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] #A[0]부터 A[i]까지의 합

 

합 배열은 기존의 리스트 데이터를 전처리한 배열이라 생각하면 됩니다. 이렇게 합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)으로 감소하게 됩니다! 

 

 

합 배열 S를 만드는 공식

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

 

 

구간 합을 구하는 공식

S[j] - S[i-1]

 

 

---

문제 003 구간 합 구하기1

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

# 구간 합 구하기1

import sys
input=sys.stdin.readline # 입력 속도 빠르게 하기 위해 사용됨됨

suNo, quizNo=map(int,input().split())# suno(숫자 개수), quizNo(질의 개수)
numbers=list(map(int, input().split()))# numbers 변수에 숫자 데이터 저장
prefix_sum=[0]  # prefix_sum 합 배열 변수 선언
temp=0  # temp 변수 선언

for i in numbers:   # for 저장한 숫자 데이터 차례대로 탐색:
    temp+=i # temp에 현재 숫자 데이터 더해 주기
    prefix_sum.append(temp) # 합 배열에 temp값 저장

# 구간합 배열
array=[0]*quizNo
for i in range(quizNo): # for 질의 개수만큼 반복:
    s,e=map(int,input().split())# 질의 범위 받기(s ~ e)
    array[i]=prefix_sum[e]-prefix_sum[s-1]    # 구간 합 출력하기(prefix_sum[e] - prefix_sum[s-1])
    
for i in range(len(array)):
    print(array[i])

---

문제 004 구간 합 구하기2

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

# 구간 합 구하기2

import sys
input=sys.stdin.readline

n,m=map(int,input().split())    # n(리스트 크기), m(질의 수)
# A(원본 리스트), D(합 배열)
A=[[0]*(n+1)]   # 1-based indexing을 위해 첫 번째 행을 0으로 설정
D=[[0]*(n+1) for _ in range(n+1)] # 모든 값이 0인 (n+1)x(n+1)크기의 배열 생성성

for i in range(n): # for n만큼 반복, 즉 숫자 0부터 n-1까지 반복
    
    # input().split()으로 입력된 문자열을 공백으로 분리해 문자열 리스트로 반환 후,
    # int 함수를 이용해 각 문자열 x를 정수로 변환환
    A_row=[0]+[int(x) for x in input().split()]# 원본 리스트 데이터 저장
    
    A.append(A_row)
    
for i in range(1,n+1):  # for i를 1부터 n까지 반복:
    for j in range(1,n+1): # for j를 1부터 n까지 반복:
    # 합 배열 구하기
        D[i][j]=D[i-1][j]+D[i][j-1]-D[i-1][j-1]+A[i][j]

result=[0]*m
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]
    
for i in range(m):
    print(result[i])

---

문제 005 나머지 합 구하기

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

# 나머지 합 구하기

import sys
input=sys.stdin.readline

n,m=map(int,input().split()) # n(수열의 개수), m(나누어 떨어져야 하는 수)
A=list(map(int,input().split())) # A(원본 수열 저장 리스트)
S=[0]*n #S(합 배열)
C=[0]*m #c(같은 나머지의 인덱스를 카운트하는 리스트)
S[0]=A[0]
answer=0 # answer(정답 변수)

for i in range(1,n): #1부터 n-1까지
    S[i]=S[i-1]+A[i] #합 배열 저장
    
for i in range(n):#0부터 n-1까지
    remainder = S[i] % m # 합 배열의 모든 값에 % 연산 수행
    
    if(remainder==0): # 0~i까지의 구간 합 자체가 0일 떄 정답에 더하기
        answer+=1
    C[remainder] += 1 # 나머지가 같은 인덱스의 개수 값 증가시키기
    
for i in range(m):
    # 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하기
    if C[i]>1:
        answer += (C[i]*(C[i]-1)//2)
        
print(answer)

 

문제를 푸는 방법은 추후에 작성하도록 하겠습니다!