doit 코딩테스트 알고리즘-파이썬
<자료구조>
<배열과 리스트>
배열 | 리스트 |
메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 | 노드(값+포인터)를 포인터로 연결한 자료구조 |
인덱스 사용/값에 바로 접근 | 값 접근 속도가 느리다 |
삽입,삭제가 어려움 | 삽입 삭제 쉬움 |
선언 후 크기 조정 불가 | 크기가 정해져 있지 않음 |
구조가 간단 | 비교적 구조 복잠 |
파이썬에서는 배열/리스트 구분이 없음(하나로 합쳐짐)
1번
11720번: 숫자의 합
첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다.
www.acmicpc.net
- bool형 숫자 변환을 유용하게 사용해 보자
2번
1546번: 평균
첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보
www.acmicpc.net
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
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
[:-1] 문자열 받을 때만 하기..
2번
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
이렇게 갑자기 어려워지나?
- 엇 위에 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번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
*특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값 = 이 구간 합의 나머지 연산을 한 값은 동일함*
즉 구간합들로 계산해도 됨
구간합들의 하나의 나머지 값과 다른 나머지 값이 같으면, 그 사이 값의 합은 나눈 값으로 딱 떨어지므로,
나머지 값이 같은 두 개 값들의 쌍을 찾으면 됨
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)
와 이런 문제는 혼자서 어떻게 풀지?
슈도 코드 (의사 코드)
프로그램을 작성할 때 각 모듈이 작동하는 논리를 표현하기 위한 언어
특정 프로그래밍 언어의 문법에 따라 쓰인 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써놓은 코드
끗
'📊 Algorithm > Algorithm 주제별 정리' 카테고리의 다른 글
🧚♂️알고리즘🧚♂️ - 정렬 - 버블정렬 (0) | 2022.12.27 |
---|---|
🧚♂️알고리즘🧚♂️ - 자료구조 - 투 포인터 / 슬라이딩 윈도우 (0) | 2022.12.25 |
🧚♂️알고리즘🧚♂️ - 자료구조 - 스택.큐.덱 (0) | 2022.11.16 |
🧚♂️알고리즘🧚♂️ - 그리디 - 그리디 (2) | 2022.11.07 |
🧚♂️알고리즘 공부🧚♂️ (2) | 2022.09.26 |