알고리즘 스터디 6주차

학습목표: 자료구조와 알고리즘 with 파이썬 5장 / 백준 자료구조 4문제

Part 2. 알고리즘 _ 5장. 알고리즘 개요

05-1 알고리즘이란?

- 주어진 문제를 해결하기 위한 단계적 절차 

- 특정한 일을 수행하는 명령어들의 집합

 

알고리즘의 조건

• 입력: 모호하지 않고 잘 정의된 입력 (필수X)
• 출력: 명확히 정의된 1개 이상의 출력
• 명확성
• 유한성
• 유효성
• 언어독립성

알고리즘의 기술 방법

• 자연어 표현
• 흐름도 표현
• 특정 프로그래밍 언어 표현
• 유사코드(pseudo code)

 

05-2 알고리즘의 성능 분석

- 연산량: 알고리즘이 얼마나 적은 연산을 사용하는가? (시간 효율성)

- 메모리 사용량: 얼마나 적은 메모리 공간을 사용하는가? (공간 효율성)

 

(1) 실행시간 측정 - time module 사용하기

import time
start = time.time() #시작시각
testAlgorithm(input) #실행시간을 측정하련느 알고리즘 호출
end = time.time() #종료시각
print("실행시간 = ", end-start) #수행시간 출력

 

- 알고리즘을 반드시 구현해야 한다

- 비교하기 위해서는 같은 환경적 조건(하드웨어, 소프트웨어)에서 실행해야 한다

- 실헹된 입력(데이터)에 대한 성능만 논할 수 있다. 즉, 실행되지 않은 입력(데이터)에 대해서는 실행시간을 주장할 수 없다.

 

(2) 시간 복잡도 분석 

: 유사 코드만 이용하여 시간 복잡도 함수 T(n)으로 연산 횟수를 측정할 수 있다

- 시간 복잡도 함수 T(n): 입력 n에 대한 함수의 형태

→ 입력(n)과 시간 복잡도 함수가 비례하는 정도를 통해 알고리즘의 효율성을 비교할 수 있다 

 

복잡도의 점근적 표기

: 여러 항을 갖는 복잡도 함수는 최고차 항만을 계수 없이 취해 단순하게 표현한다

- 정확한 연산의 양이 아니라 입력값에 대해 연산량이 얼마나 빨리 증가하는지(증가속도)를 표현한다

• 빅오 표기법 [상한]

:O(g(n))은 증가속도가 g(n)과 같거나 낮은 모든 복잡도 함수. 어떤 경우에도 g(n)에 비례하는 시간 안에 반드시 완료된다

• 빅오메가 표기법 [하한]

: Ω(g(n))은 증가속도가 g(n)과 같거나 높은 모든 복잡도 함수. 어떤 경우에도 g(n)에 비례하는 시간 이상이 걸린다.

• 빅세타 표기법

: Θ(g(n))은 증가속도가 g(n)과 같은 함수. 상한인 동시에 하한.

시간 복잡도 상한에 대한 평가

 

최선, 최악, 평균적인 효율성

• 최선의 경우: 실행시간이 가장 적은 입력 구성. 알고리즘 성능 평가에서는 큰 의미가 없다.
• 평균적인 경우: 모든 입력과 그 발생 확률을 고려한 입력 구성. 정확한 값을 구하기 어렵다.
• 최악의 경우: 실행시간이 가장 긴 입력 구성. 성능 평가에서 가장 중요하게 사용된다.

 

---

백준/실버

10773번: 제로 (스택)

→ push로 전부 넣고, pop으로 하나씩 뺀다

 

4949번: 균형잡힌 세상 (스택)

→ 교재에 실린 괄호 매칭 알고리즘으로 해결한다 

 

1874번: 스텍 수열 (스택) *

입력 첫 줄에 주어지는 n값. 그 이후 주어지는 n개의 숫자는 숫자 1-n으로 구성된 일련의 수열이다. 1-n까지 오름차 순으로 정렬된 수열을 스택에 넣고 빼면서(출력) 주어진 일련의 수열을 만들 수 있는가? 

→ 불가능한 경우, NO 출력

→  가능한 경우, push를 +로 pop을 -로 과정을 출력

 

백준/골드

1068번: 트리 (트리) ***

입력 첫 줄에 주어지는 노드의 개수(n).

둘째 줄에 주어지는 숫자는 각 노드의 부모 노드이다. 만약 부모가 없다면(루트 노드) -1이 주어진다.

셋째 줄에는 지울 노드의 번호가 주어진다.

번호는 level 순으로 1부터 순서대로 주어진다.

주어진 노드를 지웠을 때, 리프 노드의 개수를 출력하라.

 

Task

1) 부모 노드 정보를 통해 자식 노드를 생성하고 이들을 이어 트리를 완성한다

2) 특정 노드를 삭제하고 난 후의 트리를 완성한다

3) 단말 노드의 개수를 센다

 

Problem

1 - 어떻게 이을 것인가?

2 - 어떻게 (연쇄적으로) 삭제할 것인가 ?

3 - 어떻게 (연쇄적으로) 셀 것인가?

 

Solution 1 : 리스트를 원소로 갖는 리스트를 만든다

[노드 번호, 왼쪽 자식 노드 번호, 오른쪽 자식 노드 번호] ...