+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다.
알고리즘의 정의
- 어떤 문제를 푸는 알고리즘: 어떤 입력에도 정확한 출력을 유한한 시간에 내는 프로그램
1. 어떤 입력: 문제가 풀기 쉽든, 어렵든, 입력의 크기가 작건, 크건 문제를 풀 수 있다.
=> 어떤 경우에는 정답을 내지 못한다면, 우리는 그 프로그램을 믿고 쓸 수 없다.
2. 정확한 출력: 문제가 요구하는 조건을 만족한다.
=> 정답이 요구하는 조건이 무엇인지를 명시할 수 있다. (무엇이 정답이고, 오답인지 알 수 있어야 한다)
3. 유한한 시간: 무한 루프에 빠지지 않고 납득할 수 있는 시간에 종료한다.
+ 튜링: 어떤 문제가 무한 루프에 빠질지 아닐지를 판단할 수 없다. (살아 생전에 답을 볼 수 없다.)
=> 현대 컴퓨터는 1초에 1,000,000,000개 연산을 할 수 있다고 가정한다.
=> 어떤 문제의 경우는 풀 수 없을 수도 있다. (예: Halting problem)
=> 쉽게 풀 수 없는 문제. 풀 수 있지만 시간이 매우 오래 걸리는 문제 (예: NP-complete)
알고리즘 창시자
- Muhammad ibn Musa al-Khwarizmi (c. 780 ~ c. 850)
알고리즘 VS 인공지능
- 어떤 입력에도 정확한 입력을 유한한 시간에 낼 수 있는 문제, 없는 문제 차이
예 1) 서울 지하철 노선도에서 두 역을 찍어주면 가장 적은 개수의 역을 지나가는 경로를 찾는 문제
=> 알고리즘 (탐색 + 그래프)
예 2) 재미있게 본 영화와 비슷한 영화를 찾아주는 문제
=> 인공지능 (질의 응답을 통해 답에 가까워져야 한다.)
알고리즘 문제 1
+ 문제의 답을 구하는 것보다 하나의 예가 답인지 아닌지를 파악(점검)하는 것이 더 쉽다.
+ 모든 경우의 수가 정답인지 아닌지를 파악하면 이론적으로 정답을 구할 수 있다. (시간을 고려하지 않는다면)
- 문제: 100명의 학생들의 시험 점수 중 최대값을 구하시오.
- 입력: 100명의 학생들의 시험 점수
- 출력: 입력받은 100개의 시험 점수 중 최대 값
<수학적 귀납법 풀이>
- 1 ~ i번 학생까지의 점수의 최대값을 구할 수 있으면 된다.
- 1번 학생의 점수는 1~1번 학생까지의 점수의 최대값이다.
- 1 ~ i번 학생까지의 점수의 최대값을 구했다고 하자.
- 1 ~ i번 학생에 i + 1번째 학생을 추가하면?
=> max(지금까지의 최대값, i + 1번째 학생의 점수)
정확성
- 마지막 n명 학생을 처리했을 때가 정답이다. (자명하다.)
속도
- 위 방법은 n명의 점수를 읽고, n - 1번 비교한다.
=> 1번 비교할 때마다 답의 후보가 하나씩 준다.
=> 더 빠른 방법은 존재하지 않는다
예) n - 2번 비교하면 답의 후보가 2명이 되기 때문에 누가 최대값인지 알 수 없다.
코드
A = list(map(int, input().split())) # 시험 점수를 저장한 리스트
big = A[0] # 가장 높은 점수를 저장 (초기: 가장 앞에 있는 점수)
for i in range(1, len(A)):
if A[i] > big: # 이전의 가장 높은 점수보다 크면
big = A[i] # 갱신
print(big)알고리즘 문제 2
- 문제: 100명의 학생들의 시험 점수 중 가장 자주 나오는 값을 구하시오.
- 입력: 100명의 학생들의 시험 점수
- 출력: 입력 받은 100개의 시험 점수 중 최빈값
<풀이1>
- 왼쪽부터 자기 오른쪽 값들과 비교해가면서 나오는 횟수를 비교한다.
(자신의 오른쪽 값을 모두 확인해서 몇 번 등장하는지 확인)
=> 비교 횟수: (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2 = O(n^2)
def brutecount(X):
C = [0 for _ in range(len(X))]
# C[i]는 X[i]의 등장 횟수
for i in range(len(X)):
for j in range(i + 1, len(X)):
if (X[i] == X[j]):
C[i]= C[i] + 1
mostfrequent = 0
# 가장 많이 등장한 요소의 인덱스
for i in range(1, len(X)):
if (C[i] > C[mostfrequent]):
mostfrequent = i
return X[mostfrequent]
<풀이 2>
- 주어진 값을 정렬한 후, 왼쪽부터 세어가면서 같은 값이 나온 수를 센다.
+ 정렬하는 이유: 같은 값의 요소들을 모으기 위해
=> 현재 원소가 다음 원소가 같은 경우 누적 개수를 1 증가시키고, 다른 경우 누적 개수를 1로 초기화한다.
(이전까지 가장 많이 나온 수와 비교하여 더 많이 나왔다면 갱신한다.)
- 주의사항: 맨 마지막 원소는 다음 원소가 없으므로 예외 처리를 하거나 배열의 길이를 1 늘려줘야 한다.
=> 비교 횟수: 정렬시 O(n × log n) + 정렬된 값을 왼쪽부터 오른쪽으로 비교하는데 n => 총 O(n × log n)
def sortcount(X):
C = sorted(X) # 배열 X를 오름차순 정렬
current = C[0] # 현재 원소
count = 0 # 현재 원소의 등장 횟수
maximal = C[0] # 가장 많이 등장한 원소
maxcount = 0 # 가장 많이 등장한 원소의 등장 횟수
C.append(C[len(C) - 1] + 1) # C의 마지막 원소 + 1 값을 추가해서 인덱스 범위를 벗어나는 오류 방지
for x in C:
if x == current: # x가 이전 원소와 같다면
count += 1 # 개수 증가
else:
if count > maxcount: # 이전까지 가장 많이 등장한 횟수보다 더 많이 등장했다면
maxcount = count
maximal = current
current = x
count = 1
return maximal
<풀이 3>
- 값들을 이진 탐색 트리에 넣고, 같은 값이 있으면 빈도수를 늘린다.
=> 비교 횟수: 서로 다른 값이 k개라면 O(n × log k), 최악의 경우 O(n × log n)
<이진 탐색 트리의 성질>
1. 왼쪽 자식이 있다면, 왼쪽 자식의 key 값보다 자신의 key 값이 커야 한다.
2. 오른쪽 자식이 있다면 오른쪽 자식의 key 값보다 자신의 key 값이 작아야 한다.
+ 이진 트리의 성질
왜 알고리즘을 배울까?
- 이 문제는 어떻게 풀까?
=> 여러 문제를 푸는 알고리즘을 배운다.
=> 주어진 문제와 유사한 문제의 풀이를 보고, 이를 변형하여 문제를 풀 수 있다.
- 체계적으로 생각하는 훈련
=> 단순히 남이 짠 코드를 cut and paste하는 것이 아닌, 문제를 해결할 수 있는 능력을 키운다.
- 코딩 테스트
=> 코딩 테스트 - 서류 - 면접 (인성, 기술)
=> 프로그래밍을 배웠지만 코드를 짤 수 없는 사람이 많다.
=> 생각을 코드로 옮기는 훈련이 된 사람은 의외로 적다.
좋은 알고리즘의 조건
1. 간결하고 이해하기 쉬울 것
- 이해하기 쉬워야 구현하기도 쉽고, 오류를 고치는 것도 쉽다.
- 코드의 유지 보수에 유리하다
2. 효율적일 것
- 적은 메모리를 사용하고 빠른 시간에 동작해야한다.
- 데이터가 크기가 커질 수록 중요하다.
+ 코딩 테스트: "맞는데 왜 틀려요?"
- 생각하지 않은 경우에 오답
- 정답으로 생각한 코드보다 느려서 시간 제한에 못 들어온다.
알고리즘 문제 3 - 1
- 입력: U = {1, 2, ..., n} 중에서 특정한 수 하나만 빼고, 무작위의 순서로 총 n - 1개의 숫자가 한 번에 하나씩 입력한다..
- 출력: U에서 빠진 하나의 수를 찾는다.
<풀이 1>
- 크기가 n인 배열 A를 만들고 0으로 초기화한다.
- 숫자 k가 들어오면 A[k] = 1로 바꾸고, n -1개의 숫자가 들어온 뒤 A를 처음부터 뒤져서 A[j] = 0인 j를 찾는다.
=> 필요 공간: 배열 A[n]
=> 필요 시간 (비교 횟수): 가장 좋을 때는 1(빠진 수가 1일 때), 가장 나쁠 때는 n (빠진 수가 n일 때), 평균적으로 n / 2
<풀이 2>
- 변수 x를 0으로 초기화하고, 숫자 k를 입력 받을 때마다 x에 k를 더한다.
- n - 1개의 숫자를 입력 받으면, n(n - 1) / 2 - x로 빠진 숫자를 구할 수 있다.
=> 필요 공간: 변수 x가 n(n - 1) / 2를 overflow 없이 저장할 수 있어야 한다.
+ int는 4 byte(32 bit)이므로 2^32 정도를 저장할 수 있다. 따라서 n ^ 2이 2^32을 넘지 않아야하고, n은 2^16을 넘을 수 없다.
=> 필요 시간: 별도의 추가적인 검색 시간이 필요 없다.
알고리즘 문제 3 - 2
- 입력: U = {1, 2, ..., n} 중에서 특정한 수 둘만 빼고, 무작위의 순서로 총 n - 2개의 숫자가 한 번에 하나씩 입력
- 출력: U에서 빠진 두 수를 찾는다.
<풀이 1>
- 알고리즘 문제 3 - 1 풀이 1 방식을 똑같이 사용할 수 있다.
<풀이 2>
- 변수 x를 0으로 초기화하고, 숫자 k를 입력 받을 때마다 x에 더한다.
- 변수 y를 0으로 초기화하고, 숫자 k를 입력 받을 때마다 y에 k^2을 더한다.
- 미지의 수 u, v에 대해 다음과 같은 방정식이 성립한다.
=> u + v = n(n + 1) / 2 - x, (u^2 + v^2) = n(n + 1)(2n + 1) / 6 - y
=> t^2 - (u + v)t + uv = 0 의 두 근이 답이다. (u + v) ^ 2 = u^2 + v^2 +2uv 이용
'Study > Algorithm Study' 카테고리의 다른 글
| [Algorithm] 정렬: 힙 정렬 (1) | 2023.09.24 |
|---|---|
| [Algorithm] 정렬: 병합 정렬, 퀵 정렬 (1) | 2023.09.17 |
| [Algorithm] 정렬: 버블 정렬, 삽입 정렬 (2) | 2023.09.17 |
| [Algorithm] 알고리즘 기초 (3) (0) | 2023.09.16 |
| [Algorithm] 알고리즘 기초 (2) (0) | 2023.09.05 |
