Start
SW 문제 해결
SW 문제 해결 역량이란 무엇인가?
프로그램을 하기 위한 많은 제약 조건과 요구 사항을 이해하고 최선의 방법을 찾아내는 능력
프로그래머가 사용하는 언어나 라이브러리, 자료구조, 알고리즘에 대한 지식을 적재적소에 퍼즐을 배치하듯 이들을 연결하여 큰 그림을 만드는 능력이라 할 수 있다.
문제 해결 역량은 추상적인 기술이다.
-
프로그래밍 언어, 알고리즘처럼 명확히 정의된 실체가 없다.
-
무작정 알고리즘을 암기하고 문제를 풀어본다고 향상되지 않는다.
문제 해결 역량을 향상시키기 위해서 훈련이 필요하다.
문제 해결 과정
-
문제를 읽고 이해한다. (하나하나 꼼꼼히 한문장도 빼놓지 않고)
-
문제를 익숙한 용어로 재정의한다.
-
어떻게 해결할지 계획을 세운다.
-
계획을 검증한다.
-
프로그램으로 구현한다. (디버깅)
-
어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
복잡도 분석
알고리즘
알고리즘 : 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다. 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법을 말한다.
간단하게 말하면 어떠한 문제를 해결하기 위한 절차라고 볼 수 있다.
예를 들어 1부터 100까지의 합을 구하는 문제를 생각해보자
알고리즘의 효율
공간적 효율성과 시간적 효율성
-
공간적 효율성은 연산량 대비 얼마나 적은 메모리 공간(공간 복잡도)을 요하는 가를 말한다.
-
시간적 효율성은 연산량 대비 얼마나 적은 시간(시간 복잡도)을 요하는가 를 말한다.
-
효율성을 뒤집어 표현하면 복잡도(Complexity)가 된다. 복잡도가 높을수록 효율성은 저하된다.
복잡도의 점근적 표기
시간 (또는 공간) 복잡도는 입력 크기에 대한 함수로 표기하는데, 이 함수는 주로 여러개의 항을 가지는 다항식이다.
이를 단순한 함수로 표현하기 위해 점근적 표기 (Asymptotic Notation)을 사용한다.
입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다.
O(Big-Oh)를 표기할 때 상수를 배제하고 판단한다.
메모리/공간 복잡도가 동일하다고 가정할 때, O(N)으로 작성한 알고리즘과 O(N^2)으로 작성한 알고리즘 중 O(N)으로 작성한 알고리즘이 더 좋은 성능을 나타낸다.
O (log N)은 O(1)보다 느리지만, 유사한 성능을 보인다고 결론 내릴 수 있다.
O (NlogN)은 O(N) 보다는 느리지만, 유사한 성능을 보인다고 결론을 낼 수 있다.
진수(진법)
진수
10진수 : 사람이 사용하는 진수, 수 하나를 0 ~ 9로 표현
2진수 : 컴퓨터가 사용하는 진수, 수 하나를 0, 1로 표현
8진수 : 2진수를 더 가독성 있게 사용
16진수 : 2진수를 더 가독성 있게 사용, 수 하나를 0, 1, ... 8, 9, A, B, C, D, E, F로 표현
왜 16 진수를 사용하는 것인가?
2진수를 사람이 이해하기 편하도록, 10진수로 변환 시 -> 인간이 이해하기 편하지만, 연산이 오래 걸림
2진수를 사람이 이해하기 편하도록, 16진수로 변환 시 -> 연산이 더 빠르게 됨
HEX : 16 진수
DEC : 10 진수
OCT : 8 진수
BIN : 2 진수
10진수를 2진수로 변환하는 방법
tar = 149
result = []
while tar != 0:
result.append(tar % 2)
tar //= 2
result.reverse()
print(result)
16 진수 <-> 2진수 변환
2진수, 10진수 간 변환은 연산이 많으나, 2진수, 16진수간 변환은 연산이 없다.
