1. 알고리즘

문제를 해결하기 위한 절차나 방법이다.

컴퓨터가 어떤 일을 수행하기 위한 단계적인 방법을 의미한다.

알고리즘을 표현하는 방법

• 의사코드(Pseudocode)
• 순서도(Flowchart)

의사코드 예시

CalcSum(n)
    sum = 0
    for i : 1 -> n
        sum = sum + i
    return sum

---

2. 알고리즘의 성능

좋은 알고리즘인지 판단할 때 다음 기준을 볼 수 있다.

1. 정확성
   • 얼마나 정확하게 동작하는가
2. 작업량
   • 얼마나 적은 연산으로 원하는 결과를 얻어내는가
3. 메모리 사용량
   • 얼마나 적은 메모리를 사용하는가
4. 단순성
   • 얼마나 단순한가
5. 최적성
   • 더 이상 개선할 여지없이 최적화되어 있는가

---

3. 시간 복잡도

알고리즘의 작업량을 표현할 때 사용하는 방법이다.

실제 실행 시간을 직접 측정하기보다 실행되는 명령문의 개수를 이용해 비교할 수 있다.

예시 — 1부터 n까지의 합

반복문 방식

def calc_sum(n):
    total = 0

    for i in range(1, n + 1):
        total = total + i

    return total

n이 커질수록 반복 횟수도 증가한다.

공식 이용

def calc_sum(n):
    return n * (n + 1) // 2

반복문 없이 일정한 수의 연산으로 계산한다.

---

4. Big-O 표기법

시간 복잡도 함수에서 가장 큰 영향을 주는 항만 남겨 표현하는 방법이다.

상수 계수는 생략한다.

O(3n + 2)
→ O(3n)
→ O(n)

O(2n² + 10n + 100)
→ O(n²)

O(4)
→ O(1)

대표적인 시간 복잡도

O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(n³)
O(2ⁿ)

일반적으로 입력 크기가 커질수록 뒤쪽의 복잡도는 실행 시간이 매우 빠르게 증가한다.

---

배열

5. 배열(Array)

일정한 자료형의 변수들을 하나의 이름으로 여러 개 사용하기 위한 자료구조이다.

파이썬에서는 list를 이용하여 배열처럼 사용한다.

예:

num = [0, 1, 2, 3, 4, 5]

각 값에는 인덱스(index) 로 접근한다.

인덱스 : 0  1  2  3  4  5
값     : 0  1  2  3  4  5

첫 번째 원소의 인덱스는 0이다.

---

6. 배열이 필요한 이유

여러 개의 변수를 각각 선언하면 관리가 어렵다.

num0 = 0
num1 = 1
num2 = 2
num3 = 3

배열을 사용하면 하나의 이름으로 관리할 수 있다.

num = [0, 1, 2, 3]

---

7. 1차원 배열 선언

빈 리스트

arr = list()

또는

arr = []

같은 값으로 초기화

arr = [0] * 10

값을 직접 저장

arr = [1, 2, 3]

---

8. 배열 입력 받기

첫 번째 줄에 정수 N, 두 번째 줄에 공백으로 구분된 N개의 정수가 들어오는 경우:

N = int(input())
arr = list(map(int, input().split()))

---

9. 배열 원소의 합 구하기

배열의 값을 처음부터 끝까지 하나씩 누적한다.

코드

s = 0

for i in range(N):
    s += arr[i]

같은 의미로 다음처럼 작성할 수도 있다.

s = 0

for x in arr:
    s += x

흐름

s = 0
↓
arr[0] 더하기
↓
arr[1] 더하기
↓
...
↓
마지막 값까지 더하기

---

10. 배열에서 최댓값 찾기

첫 번째 값을 최댓값이라고 가정한 뒤, 더 큰 값을 만나면 갱신한다.

코드

max_v = arr[0]

for i in range(1, N):
    if max_v < arr[i]:
        max_v = arr[i]

흐름

첫 번째 값 → max_v로 가정
↓
다음 값을 하나씩 비교
↓
더 큰 값 발견
↓
max_v 갱신

---

11. 최댓값의 인덱스 찾기

최댓값 자체가 아니라 최댓값이 들어있는 위치를 저장한다.

가장 왼쪽의 최댓값 인덱스

max_idx = 0

for i in range(1, N):
    if arr[max_idx] < arr[i]:
        max_idx = i

동일한 최댓값을 만나도 갱신하지 않기 때문에 가장 먼저 나온 최댓값의 인덱스가 남는다.

예:

arr = [2, 7, 5, 3, 1, 7]

결과:

max_idx = 1

---

12. 최댓값이 여러 개일 때 마지막 인덱스 찾기

비교 조건에 =을 포함한다.

max_idx = 0

for i in range(1, N):
    if arr[max_idx] <= arr[i]:
        max_idx = i

예:

arr = [2, 7, 5, 3, 1, 7]

결과:

max_idx = 5

차이

<     # 같은 값이면 갱신하지 않음 → 가장 왼쪽
<=    # 같은 값이어도 갱신 → 가장 오른쪽

---

13. 배열에서 특정 값 찾기

찾는 값이 있으면 해당 원소의 인덱스를 저장하고, 없으면 -1을 유지한다.

idx = -1

for i in range(N):
    if arr[i] == V:
        idx = i
        break

핵심

idx = -1

처음에는 찾는 값이 없다고 가정한다.

break

값을 찾으면 더 이상 반복할 필요가 없으므로 반복문을 종료한다.