알고리즘 스터디 1일차

목차

1. 시간복잡도

2. 디버깅

3. 배열과 리스트

4. [배열과 리스트 실전 문제] 숫자의 합 구하기

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

1. 시간 복잡도

1.1 시간 복잡도 표기법

빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법

빅-세타 : 보통일 때의 연산 횟수를 나타낸 표기법

빅-오 : 최악일 때의 연산 횟수를 나타낸 표기법

 

이 중에서 빅-오(최악일 때)로 가정해서 문제를 풀어야 한다.

 

1.2 시간 복잡도 활용하기

다음 백준 2751번을 풀어보자

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

2751번: 수 정렬하기 2

정렬을 하기 위해 버블정렬과 병합정렬중에 선택을 해야 한다. 해당 문제의 시간제한이 2초이므로 4000만 번 이하의 연산 횟수로 문제를 해결해야 한다. (1초=약 2000만 번의 연산)

따라서 버블정렬(N²)과 병합정렬(Nlog₂N) 의 N값에 빅-오(N의 최댓값인 1,000,000)의 값을 넣어보면 어떤 알고리즘이 적합한지 알 수 있다.

 

1.3 코드로직 개선에 활용

코드를 될 수 있으면 N에 상수를 곱하는 식으로 풀자. 반복문을 중첩해 N²을 계산하는 것보다 (상수)xN이 연산에 더욱 효율적인 구조이기 때문이다. (시간효율: N번 더하기 반복 > N을 중첩)

 

 

 

2. 디버깅

디버깅 : 논리 오류를 찾아 바로잡는 과정

 

다음은 많이 발생하는 오류들이므로 유의해서 디버깅을 하는 것이 좋다.

1) 변수초기화 오류

2) 반복문에서 인덱스 범위 지정 오류

3) 잘못된 변수 사용 오류

4) 파이썬 자동 형 변환으로 인한 오류

 

 

 

3. 배열과 리스트

3.1 배열

메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조.

 

배열의 특징은 다음과 같다.

1. 인덱스를 사용하여 값에 바로 접근할 수 있다.

2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. (해당 인덱스 주변에 있는 값을 이동시켜야 함)

3. 배열의 크기는 선언할 때 지정할 수 있으며, 한번 선언하면 크기를 늘리거나 줄일 수 없다.

4. 구조가 간단하므로 코딩테스트에서 많이 사용한다.

 

3.2 리스트

리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조.

 

리스트의 특징은 다음과 같다.

1. 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근. (값에 접근하는 속도가 느리다.)

2. 포인터로 연결되어 있으므로 데이터를 삽입, 삭제하는 연산 속도가 빠르다.

3. 선언할때 크기를 별도로 지정하지 않아도 된다.

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

 

3.3 파이썬에서의 배열과 리스트

파이썬에서는 배열과 리스트를 구분하지 않는다. 즉 index에 바로 접근이 가능하고 가변적이다.

(다른 언어의 배열과 리스트 특징을 둘 다 가짐)

따라서 파이썬으로 코딩테스트를 풀 때 리스트를 최대한 많이 이용하자.

 

 

 

4. [배열과 리스트 실전 문제] 숫자의 합 구하기

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

11720번: 숫자의 합

풀이코드

N = int(input())
M_list = list(map(int,input()))
print(sum(M_list))