알고리즘 1

APS

APS 란?

APS 는 Advanced Planning and Scheduling의 약어로,

우리말로 하면 진일보된 생산계획(Planning) 과 일정계획(Scheduling)을 수립하는 소프트웨어

, 즉 의사결정 툴입니다

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

주로 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법

 

컴퓨터 분야에서 알고리즘을 표현하는 방법은 크게 두 가지

1. 의사코드(슈도코드, Pseudocode)

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

1. 순서도 (현재는 잘 쓰이진 않음)

APS 과정의 목표

좋은 알고리즘을 이해 하는 것

1. 정확성: 얼마나 정확하게 동작하는가
2. 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가
3. 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
4. 단순성 : 얼마나 단순한가(정확성을 놓치지 않는게 제일 중요)
5. 최적성 : 더 이상 개선할 여지없이 최적화되었는가

주어진 문제를 해결하기 위해 여러 개의 다양한 알고리즘이 가능 ⇒ 어떤 알고리즘을 사용해야 되는가?

⇒ 알고리즘의 성능 분석 필요

• 많은 문제에서 성능 분석의 기준으로 알고리즘의 작업량을 비교

1부터 100까지 합을 구하는 문제

덧셈을 100번 할것인가? vs 가우디 법칙을 쓸 것인가?

⇒ 연산량에서 가우스가 더 효율이 좋다.

알고리즘의 작업량을 표현할때는 시간 복잡도로 표현한다

시간복잡도 ( Time Complexity)

• 실제 걸리는 시간을 측정
• 실행되는 명령문의 개수를 계산

def CalcSum(n)   sum <- 0   for i in range(1.n+1) #n번     sum <- sum + i; #n번   return sum; # 1 + n * 2 = 2n + 1 번의 연산이 필요

def CalcSum(n):   return n*(n+1)//2 #3번

시간 복잡도 = 빅-오(O) 표기법

시간 복잡도 함수 중에서 가장 큰 영향력을 주는n에 대한 항만을 표시

계수(Coefficient)는 생략하여 표시

예)

O(3n + 2) = O(3n)     =  O(n)  최고차항(3n)만 선택   계수 3제거 O(2n**2 + 10n + 100 => O(n**2) O(4) => O(1)

n개의 데이터를 입력 받아 저장한 후 각 데이터에 1씩 증가시킨 후 각 데이터를 화면에 출력하는 알고리즘의 시간복잡도는?

O(n)

요소 수가 증가함에 따라 각기 다름

해쉬가 O(1) 로 빠르다.

O(1) : hash

O(logn) : 이진탐색

O(n) : 순차탐색

O(nlong) : Quick, Heap, Merge Sort

O(n^2) : Bubble, Select room, Insort room Sort

O(2^n) : Power Set ( 모든 부분집합) , 집합

O(n!) : 순열

배열

• 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
• 메모리 주소에 찾아가서 참조해온다, 물리적으로 연속된 공간안에 위치한다.
• 4개의 변수를 사용해야 하는 경우 → 배열 하나로 바꿔서 사용
  • 변수가 단독주택이라면 배열은 아파트
• 하나의 선언으로 둘 이상의 변수를 선언 가능
• 단순히 다수의 변수 선언을 의미 하는 것이 아님,
  • 다수의 변수로는 하기 힘든 작업을 하기 위함

num0 = 0 num1 = 1    => num = [0,1,2,3] num2 = 2 num3 = 3

 

간단한 것부터 손으로 그려보는 연습해봐야 된다.

생각해볼 주의할 점

1. 1번 ~10번 수학점수를 인덱스 0~9 에 넣을 때0부터 세기 때문에 헷갈릴 가능성이 있음
2. ⇒ 신경 써서 인덱스 연산을 한번 해줘야 되는 단점
3. 1번~10번 수학점수를 인덱스 0을 가만히 두고 1~10에 넣을 때관련 있는 정보를 같은숫자로 일치시키겠다.⇒ arr = [0]*10 해놓고 arr[10] 을 호출하면 안된다.
4. 1번부터 N번까지 N명의 점수니까 [0] * N 으로 해놓고 10번째 사람을 구하겠다고 arr[10]에 접근한다. (사실상 9번째 사람의 점수임) ⇒ 처음 선언할 때 개수에 신경써야함 (N 명의 점수 == 1~N+1 명)

Gravity 문제

''' 9 7 4 2 0 0 6 0 7 0 ''' N = int(input()) # 상자가 쌓여있는 가로 길이 arr = list(map(int,input().split())) """ 오른쪽으로 자기보다 낮은 애들의 갯수 = 떨어질 수 있는 길이 7 은 7칸을 떨어질수 있겠네 4 2 0 0 6 0 0 4 은 5칸 2는 4칸 0은 0, 0은 0 6은 2개 0은 0개 7은 1개 0은 0개 여기서 최대값을 찾아라 => 7 리스트를 하나 생성하고, max(lst) 로 구하는 흔한 방법 (X) 경고!!  권장방법 : max_v 를 0으로 초기화 하고 0 ~ n-1 (모든 상자에 대해)  for i:0-> N-1: # 낙차구하는 위치   cnt <- 0   for j: i+1 이상 N-1 이하 # i와 비교할 위치,      if arr[i] > arr[j]       cnt +=1     if max_v < cnt     max_v = cnt """ max_v = 0 # 가장 큰 낙차 # for i : 0 -> N-2, i 낙차를 구할 위치, 이상이하 for i in range(N-1): #이상미만   cnt = 0 # 오른쪽에 있는 더 낮은 높이의 개수   #for j : i+1 -> N-1 # 이상이하   for j in range(i+1, N):  #이상미만     if arr[i]>arr[j]:       cnt +=1   if max_v < cnt: #최대 낙차보다 크면     max_v = cnt print(max_v)

T = int(input()) # 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다. for tc in range(1, T + 1):   N = int(input())   arr = list(map(int,input().split()))   # 오른쪽으로 자기보다 낮은 애들의 갯수 = 떨어질 수 있는 높이, 이것의 최대값을 구해야된다.   max_val = 0 #max_val 을 초기화   # for i:0 -> N-2, 총 N-1개(마지막 블럭은 떨어질게 없어서) index는 0이상 n-1미만, 낙차 구하는 위치   for i in range(N-1): # 기준이 되는 막대기 오른쪽으로의 막대기 갯수 만큼 돌아라 N-1~0개 = N-1개 만큼     cnt = 0 # cnt 초기화     # for j : i+1 ~ n-1 까지 각 막대기의 갯수     for j in range(i+1,N): #range(숫자) 가 아니기 때문에, i+1~N = N-i-1개       if arr[i] > arr[j]: # 기준(i)이 되는 막대의 블럭 개수가 비교(j)하는 막대의 블럭 개수보다 클 때만          cnt += 1 # cnt를 하나씩 추가시킨다.     if max_val < cnt: # 가장 낙차가 큰 값(max_val) 이 cnt 보다 작을 때       max_val = cnt # 교체한다.   pass   print(f'#{tc} {max_val}')

 

풀이 방법 중 본인이 할 수 있는(풀 수 있는) 부분(슈도부터?, 구현부터? 등등)부터 해라

물어볼 때 구체적이고, 단계적으로 물어봐라

슈도 코드를 씀으로서 다른 언어로의 방법도 같이 연습할 수 있다.

정렬 방식 - 버블 정렬

인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식 (비교, 교환)

과정

1. 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막자리까지 이동한다.
2. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.

$$시간 복잡도 : O(x^2)$$

구간의 갯수가 n개면 0번 인덱스부터 n-1번 인덱스까지 한다.

…

구간의 갯수가 2개면 0번 인덱스부터 1번 인덱스까지 한다

n개의 데이터를 버블 정렬로 정렬 하기 위해서는 n-2번쨰 인덱스까지 봐야되구나

⇒ n-1번째 인덱스를 i로 시작해서 1번째 인덱스까지 뒤에서 부터 결정한다

⇒ 왜냐? 버블소트의 가장 첫 시행 때 가장 큰 수가 가장 마지막에 정렬된다.

for i:N-1 -> 1 #정렬될 구간의 끝   for j:0 -> i-1  # 비교할 원소 중 왼쪽 원소의 인덱스        # N-2 가 아닌 이유 : 뒤에서 부터 정렬이 완료되기 때문에,        #  정렬을 해야되는 갯수가 줄어들기 때문     if A[j] > A[j +i] # 왼쪽 원소가 더 크면  A[j] <-> A[j + 1] #오른쪽 원소와 교환  #파이썬 코드  for i in range(N-1,0,-1): #범위의 끝 위치   for j in range(0,i): #비교할 왼쪽 원소     if a[j] > a[j+1]:  a[j], a[j+1] = a[j+1], a[j]

배열을 활용한 버블 정렬

N = 6 arr = [7, 2, 5, 3, 1, 5]  def asc(arr, N): #오름차순   # for i : N-1 -> 1, 정렬할 구간의 마지막 인덱스   for i in range(N-1,0,-1):     # for j : 0 -> i-1 , j는 비교할 두 원소 중 왼쪽의 인덱스     for j in range(i):       if arr[j] > arr[j+1]: # 오름차순은 큰 수를 오른쪽으로         arr[j], arr[j+1] = arr[j+1],arr[j] def dec(arr, N): #내림차순   # for i : N-1 -> 1, 정렬할 구간의 마지막 인덱스   for i in range(N - 1, 0, -1):     # for j : 0 -> i-1 , j는 비교할 두 원소 중 왼쪽의 인덱스     for j in range(i):       if arr[j] < arr[j + 1]:  # 내림차순은 작은 수를 오른쪽으로         arr[j], arr[j + 1] = arr[j + 1], arr[j] asc(arr, N) print(arr) dec(arr, N) print(arr)

# 추가로 배운것

알고리즘 문제 해결 순서

1. 문제를 3번 읽어라
2. 손으로 코딩을 먼저해라 (수도코드) 정확하게 생각해야 함