TIl

Start

아크몽 2024. 2. 26. 23:15

코딩문제를 잘 푸는 방법

3단계 전략이 있다.

  1. 이해 : 하나하나 꼼꼼히 한 문장도 빼놓지 않고
  2. 계획 : A4 용지, 펜 // 태블릿
  3. 구현 : 코드로 구현해본다. → 디버깅

3가지 전략

  1. 복잡도 분석 - 시간 복잡도
  2. 표준 입출력 map, 리스트 컴프리핸션 // sys 모듈 ( 파일 입출력 )
  3. 2진수, 10진수 → 10진수, 2진수

SW 문제해결 역량이란?

언어, 라이브러리, 자료구조, 알고리즘에 대한 적재적소에 퍼즐을 배치하듯 이들을 연결하여 큰 그림을 만드는 능력

문제 해결 역량 = 추상적인 기술

  • 프로그래밍 언어, 알고리즘 처럼 정의된 실체가 없다.
  • 알고리즘을 암기하고 문제를 풀어 본다고 해결 X

⇒ 문제해결 역량시키기 위해서 훈련이 필요하다.

문제 해결 과정

  1. 문제를 읽고 이해한다.
  2. 문제를 익숙한 용어로 재정의한다. = 수도코드
  3. 어떻게 해결할지 계획을 세운다.
  4. 계획을 검증
  5. 프로그램으로 구현
  6. 어떻게 풀었는지 돌아보고, 개선할 방법 찾기

알고리즘

사전적 정의 : 문제를 해결하기 위한 절차나 방법

효율

공간적 효율성과 시간적 효율성

  • 공간적 효율성 : 연산량 대비 얼마나 적은 메모리 공간을 요하는 가,
    • 변수나 리스트가 메모리를 얼마큼 썼느냐?
  • 시간적 효율성 : 연산량 대비 얼마나 적은 시간을 요하는 가? 시간복잡도 O
    • 반복문을 얼마나 많이 썼느냐? = 실행시간
  • 효율성을 뒤집어 표현하면 복잡도(complexity) → 복잡도가 높을수록 효율성이 저하된다.

⇒ 시간이 더 빠르고 공간을 조금 사용 == 성능이 좋은 알고리즘

복잡도 점근적 표기

1. O(Big-Oh) 표기법

O- 표기는 복잡도의 점근적 상한을 나타낸다.

O(n) : 오더 앤

복잡도가 $f(n) = 2n^2+ 7n +4$ 이라면, f(n)의 O- 표기는 $O(n^2)$이다.

상수 배수는 하지 않는다 가 가장 중요함

But 단순화된 함수에 임의의 양수인 상수 c를 곱한 $cn^2$이 n이 증가함에 따라 f(n)의 상한이 늘어난다.

⇒ c 배수를 강조해서 알고리즘 성능을 미세하게 비교하고 싶을 경우 상수 붙어서 사용

P : n이 커저도 구할 순 있는 것

$O(1)$: 상수 시간(Constant time)

$O(logN)$ 로그(대수) 시간, 1억회라도 27회 반복

$O(n)$ 선형 시간

$O(nlogN)$ 로그 선형 시간

$O(n^2)$

$O(n^3)$ ‘모든 쌍 최단 경로’

NP : n이 커지면 절대 못 구하는 것

$O(2^n)$ 부분집합, 조합

$O(n!)$ 순열

O(logN)은 O(1) 보다는 느리지만 유사한 성능을 보인다.

O(NlogN) 은 O(N) 보다는 느리지만 유사한 성능을 보인다.

pop(0) 와 popleft() : O(n) 과 O(1)

이진 탐색 : logN

퀵, 힙, 머지 정렬 : nlogN

해쉬 : 1

같은 10억의 n 에 대해서 300년 vs 5분

⇒ 효율적인 알고리즘은 슈퍼컴퓨터보다 더 큰 가치가 있다.

표준 입출력 방법

파일 입력으로 입력 받기 import sys;sys.stdin=open('파일명')

진수

10진수 : 컴퓨터

2진수 : 컴퓨터가 사용하는 진수

16진수 : 2진수를 더 가독성 있게 사용, 수 하나를 0,1 … 9, A,B,C,D,E,F 로 표현

$168_{10} = (1010 1000)_2 =(250)_8 = (A8)_{16}$

왜 16진수를 쓸까?

  • 10진수는 사람이 이해하기 편하지만 연산이 매우 느림

용어 암기

HEX: 16진수

DEC: : 10 진수

OCT: 8 진수

BIN: 2 진수

진법 변환 하는 법 중요

진수표

16진수 0xF9

→ 2진수로 변환하기

1111 1001

0xBB3 ⇒ 1011 1011 0011

비트 연산

1 bit : 0 과 1로 표현하는 정보의 단위

1 Byte : 8 bit 가 1 Byte

컴퓨터의 CPU 는 0과 1로 다루어 동작되며, 내부적으로 비트 연산을 사용하게 된다

⇒ 컴퓨터가 사용하는 연산인 비트연산에 대해 알아야 한다.

논리 연산자 처럼 작동시키기

But 피연산자가 정수일때만 가능

& : 비트 단위로 AND 연산을 한다. (엠퍼센트)

| : 비트 단위로 OR 연산을 한다. (파이프 라인)

^ : 비트 단위로 XOR 연산을 한다. (같으면 0 다르면 1) (Exclusive Or)

<< : 특정 수 만큼 비트를 왼쪽으로 밀어낸다. (우측에 0이 생성됨)

>> : 특정 수 만큼 비트를 오른쪽으로 밀어낸다. (우측 비트들이 제거됨)

~ : NOT

print(7 & 5) # 5
print(0b111 & 0b101) # 5
print(bin(0b111 & 0b101)) # 0b101
print(7 | 5) # 7
print(bin(10)) # 0b1010
print(hex(10)) # 0xa
print(int('1011',2)) # 2진수 문자열을 10진수로 변환
print(int('b',16)) # 16진수 문자열을 10진수로 변환
print(int('FF',16)) # 255, 2의 8승은 256이기 때문

xor 비트연산

어떤 값이던 임의의 수로 2회 XOR를 하면 원래 수로 돌아온다. ⇒ 암호화에 사용

7070 ^ 1004 = 6258

6258 ^ 1004 = 7070

Left Right Shift 연산자

for i in range(5):
    # print('0b1'+'0'*i,0b1 << i)
    print(bin(0b1<<i),0b1 << i)

비트 연산

  • 응용 1

1 << n

$2^n$의 값을 갖는다

임베디드 분야에서 계싼을 빠르게 하기 위해 사용

  • 응용 2

i & (1<<n)< code=""></n)<>

  • i의 n번 비트가 1인지 아닌지를 확인할 수 있다.
  • ex) 1101 & (1<<2)위 연산으로 1101 에서 2번 bit가 1인지 확인 가능하다.1101 & 0100 = 0100만약 연산결과가 0 이라면, n번 비트는 0
  • ![](https://blog.kakaocdn.net/dna/cDLXM0/btsFm3ooOKy/AAAAAAAAAAAAAAAAAAAAAAineJZYIy0EdOR861gzNl80S7T5i53llBUlx-V7W56t/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1753973999&allow_ip=&allow_referer=&signature=MzOoytsXnfNMJFw%2FYNbIRdpQa%2FY%3D)
  • 0100은 0 보다 큰 수, 0100 > 0 n번 비트는 1이 확정
  • 1<<2 = 100

곱셈, 나눗셈은 내부적으로 시간을 많이 소모함

⇒ 비트연산은 빠름
⇒ 임베디드에서 많이 사용

if x & 0x01:   print('홀수') else:   print('짝수')

같은 0인데 자리를 두 개나 차지하네 ⇒ 안 좋다

부호와 절대치 나 1의 보수는 0이 2자리를 차지함

그래서 2의 보수를 채택함 ( 1의 보수에서 1을 추가하는 방식) : 첫 번째 이유

2진수가 연산에 유리함 : 두 번째 이유

32bit 표현 가능한 정수 범위는 ? $-2^{32-1} ~ 2^{32-1}-1$ : 21억~ 21억 정도

최대값에서 1 추가되면 overflow가 일어나서 가장 작은값으로 간다

음수 표현 방법

컴퓨터는 음수를 2의 보수로 관리한다

맨 앞자리 bit (MSB)는 음수 or 양수를 구분하는 비트이다.

most significant bit 최상위 비트

msb : 1 → 음수

msb : 0 → 양수

컴퓨터가 2의 보수를 사용하여

2의 보수 예시

  • 1001의 2의 보수→ 1의 보수로 바꾸기(수를 모두 뒤집고) +1을 한다. (뒤집는다 = 0과 1를 바꾼다.)
  • → 01110 + 1 = 01111
  • 1111000의 2의 보수→ 수를 뒤집으면 0000111 이고 +1을 한다
  • → 0000111 + 1 = 0001000

NOT 연산

101 = 5 니까 - 5 가 된다.

왜 2의 보수를 취해야할까?

컴퓨터는 음수를 ‘2의 보수’로 관리한다.

맨 앞자리 bit(MSB)는 음수 or 양수를 구분하는 비트이다.

실수

실수를 변수에 할당할때는 근사값이 저장된다.

⇒ 유효자리 숫자가 매우 중요

0.1  = 0.1000000000000000055511151231257827021181583404541015625000
a = 123 b = 123.455 c = 123.355  print('%d %.2f' % (a,b)) print('%d %.2f' % (a,c))

파이썬은 f-string 문법을 지향한다.

t1 = 10 t2 = 3.141592  print(f'변수 값은 {t1}이다') # t2 값을 소수점 둘째자리까지 반올림하여 표현 print(f'변수 값은 {t2:.2f}이다') # 3.14

파이썬에서의 실수 표현

근사 값으로 저장되는 원리

소수점이 있는 10진수를 2진수로 변환 예시

소수점을 포함한 2진 실수를 10진수로 변환하는 예시

예) 1001.0011

실수인 149.625를 바꾸는 방법

⇒ $1000 0110.101_2$

⇒ $1.0010101101 * 2^7$

⇒ 0 1000 0100 00101011010000000000000(23개)

0/1 지수부 가수부 로 따로 저장해

⇒ 실수로 바꿔서 연산하지마라 라는 TMI

주의해야 할 반올림

코드를 실행해서 비교해봐야함

a = 123
b = 123.455
c = 123.355
d = 123.5
e = 122.5

print('%d %.2f' % (a,b))
print('%d %.2f' % (a,c))
print('%d %.0f' % (a,b))
print('%d %.0f' % (a,c))
print()
print(round(d,0))
print(round(e,0))
print(int(d+0.5))
print(int(e+0.5))
print()
print(f'{a:4d} {d:.0f}')
print(f'{a:4d} {e:.0f}')