Skip to content

Latest commit

 

History

History
240 lines (165 loc) · 7.34 KB

200429_Start.md

File metadata and controls

240 lines (165 loc) · 7.34 KB
Raw

Start

1. 학습목표

  • SW 문제 해결 역량이란 무엇인가 이해
  • 효율적인 알고리즘 필요성 이해, 알고리즘 성능 측정방법중 시간복잡도에 대한 이해
  • 프로그램 작성하기 위한 기본중 표준 입출력

2. SW 문제 해결

2.1 코딩교육 이슈

  • 오바마대통령이 모든학생 코딩교육 강조

2.2 왜 알고리즘을 공부해야 하는가?

  • 광범위한 분야의 알고리즘 적용
  • 알고리즘은 오랜 기원을 가지고 있고 새로운 도전의 기회를 준다.
  • 다른 방식으로는 풀 수 없는 문제의 해결 방법 제시
    • 네트워크 연결 문제
      • 한 지점에서 출발하여 다른 지점으로 연결하여 이동하는 방법 문제
  • 과학적 분야에서 수학적 모델 대체
  • 유능한 프로그래머가 되기 위한 방법

2.3 프로그래밍하기 위한 제약조건과 요구사항

  • 프로그래밍 언어의 특성
  • 라이브러리들의 유의 사항
  • 프로그램이 동작할 HW와 OS에 관한 지식
  • 프로그램이 사용할 수 있는 최대 메모리
  • 사용자 대응 시간 제한
  • 재사용성이 높은 간결한 코드 ( 확장가능성 )

2.4 SW문제 해결 역량이란?

  • 프로그램을 하기 위한 많은 제약 조건과 요구사항을 이해하고 최선의 방법 찾아내는 능력
  • 프로그래머가 사용하는 언어나 라이브러리, 자료구조, 알고리즘에 대한 지식을 적재적소에 퍼즐을 배치하듯 이들을 연결하여 큰 그림을 만드는 능력
  • 문제 해결 역량은 추상적인 기술이다.
    • 프로그래밍 언어, 알고리즘처럼 명확히 정의된 실체가 없다.
    • 무작정 알고리즘을 암기하고 문제를 풀어본다고 향상되지 않는다.
    • 문제 해결 역량을 향상시키기 위해서는 훈련이 필요하다.

2.5 문제 해결 과정

  1. 문제의 모델링
    • 문제를 읽고 이해한다.
    • 문제를 익숙한 용어로 재정의한다.
  2. 문제를 해결한 알고리즘 찾기
    • 어떻게 해결할지 계획을 세운다.
  3. 알고리즘의 검증
    • 충분한 성능과 적절한 메모리 사용에 대한 검증.
  4. 프로그램으로 구현한다.
  5. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 만족스러울때까지 찾아본다.

2.6 문제 해결 전략

  • 문제 해결 전략
    • 직관과 체계적인 접근
  • 체계적인 접근을 위한 질문들
    • 비슷한 문제 풀어본적 있는가?
    • 단순한 방법에서 시작할수있는가?
    • 문제를 단순화 할 수 있을까?
    • 그림으로 그려 볼수 있을까?
    • 수식으로 표현 할 수 있을까?

3. 복잡도 분석

3.1 알고리즘?

  • 알고리즘

    • 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법

    • 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법을 말함.

    • 어떠한 문제를 해결하기 위한 절차

    • 예) 1부터 100까지의 합을 구하는 문제

      • 1번 풀이
1+2+3+...+100 = 5050

2번 풀이
100 * (1+100) / 2 = 5050

      • 2번 풀이가 n이 아무리 늘어나더라도 3번의 연산만 하므로 더 좋은 풀이방법이다.

3.2 알고리즘의 효율

  • 공간적 효율성과 시간적 효율성
    • 공간적 효율성은 얼마나 많은 메모리 공간을 요하는가?
    • 시간적 효율성은 얼마나 많은 시간을 요하는가?
    • 효율성을 뒤집어 표현하면 **복잡도(Complexity)**가 된다. 복잡도가 높을수록 효율성은 저하된다.
  • 시간적 복잡도 분석
    • 하드웨어 환경에 따라 처리시간이 달라진다.
      • 부동소수 처리 프로세서 존재유무, 나눗셈, 가속기능 유무, 입출력 장비의 성능, 공유여부
    • 소프트웨어 환경에 따라 처리시간이 달라진다.
      • 프로그램 언어의종류, 운영채제, 컴파일러의 종류
    • 이러한 환경적 차이로 인해 분석이 어렵다.

3.3 복잡도의 점근적 표기

  • 시간(또는 공간) 복잡도는 입력크기에 대한 함수로 표기하는데, 이 함수는 주로 여러개의 항을 가지는 다항식이다.
  • 이를 단순한 함수로 표현하기 위해 점근적 표기를 사용한다.
  • 입력 크기 n이 무한대로 커질 때 복잡도를 간단히 표현하기 위해 사용하는 표기법이다.
    • O (big-Oh) 표기
    • Ω 오메가 표기
    • Θ 세타 표기
    • Ω < Θ < O

3.4 O (Big-Oh) - 표기 : 정의

  • T(n) : 실행시간
  • n0 보다 크거나 같은 모든 n에 대해서
  • T(n) <= c*f(n) 이 되는 상수 c, n0 가 존재할 때만,
  • T(n) = O(f(n)) 이라고 한다.
  • 단, 상수 c와 초기값 n0 는 n의 값에 독립적이다.
  • 예) T(n) = 2n^2^ - 7n + 4 이라면, T(n)의 O-표기는 O(n^2^) 이다.
    • 실행시간이 n^2^ 에 비례함.

3.5 자주 사용하는 O-표기

  • O(1)
    • 상수 시간
  • O(logn)
    • 로그(대수) 시간
  • O(n)
    • 선형 시간

  • O(nlogn)

3.6 왜 효율적인 알고리즘이 필요한가.

  • 10억 개의 숫자를 정렬하는데 PC에서 O(n^2^) 알고리즘은 300여 년이 걸리는 반면에 O(nlogn) 알고리즘은 5분 만에 정렬한다.
  • 효율적인 알고리즘은 슈퍼컴퓨터보다 더 큰 가치가 있다.
  • 값 비싼 H/W 기술 개발보다 효윩적인 알고리즘 개발이 훨씬 경제적이다.

image-20200429103359783

4. 표준 입출력 방법

4.1 파일의 내용을 표준 입력으로 읽어오는 방법

import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')

text = input()
print(text)
import sys
sys.stdin = open('input.txt', 'r')

T = int(input())
r, c = map(int, input().split())

# field = [ input() for _ in range(r) ]
field = []
for i in range(0, r):
    row = input()
    field.append(row)
    
print(T)
# print(r, c)
# print('\n'.join(field))
print(str(r) + "" + str(c))

for i in range(0, r):
    print(field[i])

5. 비트 연산

5.1 비트 연산자

  • ex)

    num1 = 2 = 0010
num2 = 3 = 0011

num1 & num2 = 0010 (둘다 1 이어야 1)
num1 | num2 = 0011 (둘중 하나라도 1 이면 1)
num1 ^ num2 = 0001 (두개가 다르면 1)
~num1 = 1101 (0이면1, 1이면0 으로 만든다.)
num1 << 2 = 1000 ( 2자리수만큼 왼쪽으로 이동 ) # 2를 2번 곱함, x 2^n
num1 >> 2 = 0000 ( 2자리수만큼 오른쪽으로 이동 ) # 2로 2번 나눔, // 2^n

  • N & 1

    • 변수에 저장된 양의 정수 값의 홀수 짝수 판별 => N % 2
    • & 연산으로 마지막 비트 값이 1 인지 0 인지 판단, 짝수 홀수 판별

  • 1 << n

    • 2^n^ 의 값을 갖는다.
    • 원소가 n개일 경우의 모든 부분집합의 수를 의미한다.
    • Power set (모든 부분 집합)
      • 공집합과 자기 자신을 포함한 모든 부분 집합
      • 각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합의 수가 계산됨

image-20200429103632613