SW 문제해결 응용 - 구현 - 시작하기

1. SW 문제 해결역량의 의미와 역량강화 방법을 설명할 수 있다.
2. 알고리즘의 필요성과 알고리즘의 성능 측정 방법 중 하나인 시간복잡도에 대해 설명할 수 있다.
3. 비트 수준의 연산과 자주 활용되는 표현을 설명할 수 있다.
4. 다양한 진법들과 이들 사이에 변환 방법을 설명할 수 있다.
5. 컴퓨터에서 실수 자료형의 표현과 특징을 설명할 수 있다.

 

---

 

1차. SW 문제 해결

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

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

 

문제 해결 과정

1. 문제를 이해하자.
2. 문제를 재정의하자.
3. 고려사항을 정리하자.
4. 문제 해결 방안을 마련하자.
5. 계획에 오류가 있는지 확인하자.
6. 프로그램으로 구현하자.
7. 개선사항을 찾자.
8. 종료

 

문제가 어려워요!

1. 비슷한 문제를 푼 경험을 생각해보자.
2. 단순하게 시작해서 좋은 방법을 찾아 보자.
3. 문제를 단순화하자. 그림으로 그리자. 수식으로 표현하자.
4. 문제를 작은 여러개의 문제로 바꿔보자.
5. 뒤에서부터 시작해서 문제를 풀어보자.
6. 특정 형태의 답만이 필요한지 생각해보자.

 

---

 

2차시. 알고리즘 복잡도

알고리즘이란?

• 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법
• 컴퓨터가 어떤 일을 수행하기 위한 절차

 

알고리즘의 효율성

• 공간적 효율성 : 얼마나 많은 메모리 공간을 요하는가?
• 시간적 효율성 : 얼마나 많은 시간을 요하는가?
• 복잡도가 올라가면 효율성은 낮아진다.
• 입력크기가 크면 문제가 된다.
• 복잡도의 점근적 표기는 주로 입력 크기에 대한 함수로 표기한다.
• 단순 함수 표현을 위해 점근적으로 표기하는데, 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다.
• Big-O, Big-Omega, Theta가 있다.

 

 

빅오 표기법

• 복잡도의 점근적 상한을 나타낸다.
• 가장 높은 최고차항에 상수 c를 곱한 값이다.
• 상수 버리는 이유: 어차피 n^2라면 각도만 달라진다. 

 

 

빅-오메가

 

 

세타-표기

 

 

효율적 알고리즘의 필요성

 

 

---

 

 

3차시. 비트 연산

비트 연산자

• 비트연산이 빠른 이유 : 트랜지스터라는 게 있는데 연산하는 반도체 소자이다. 트랜지스터 -ㅁ= 이렇게 생겨서 0과 1을 반환한. 이게 오지게 모인 게 CPU이다. 좋은 컴퓨터일수록 비트 연산 속도가 빠르다.
• 반도체가 뭐지? 반만 도체. 1과 0을 반환. 
• 트랜지스터의 결과를 CPU 가 계산한다. 

• XOR! 둘 중 하나가 1이면 1을 반환하나, 둘 다 1이면 0을 반환한다. (어려워요)
• << 사용했다. 트랜지스터가 << 신호를 보내고 cpu가 연산을 한다. 자바로 코드 짜면 메모리(ram, 휘발성 메모리, 속도가 오지게 빠르)의 stack에 쌓이고, 트랜지스터가 가지고 간다. 
• <<를 사용하면 00000000 00000000 00000000 00001000에서 00000000 00000000 00000000 00010000으로 된다.
• 빠른 이유는 이게 계산 연산 이런 게 아니라서 그렇다. 실제로는 데이터를 변경시키는 것이다. new를 사용해서 새로 생성하는 개념이 아니라서 더 빠르다. 한 개 수를 바꾸는 게 빠르니까 더 빠르다!!!

 

 

비트 연산 예제

 

엔디안

 

 

Byte Alignment

 

 

 

---

 

4차시. 진수

진법 변환

 

 

---

 

5차시. 실수

 

 

부동 소수점 표기법