Read & Analysis | 시간복잡도, 공간복잡도 등

 

파인만 알고리즘

 

 

 

@Read & Analysis

-문제를 읽을 때, 어떤 부분을 초점을 두고 읽어야 할까?

-문제의 조건들을 추상화하는 연습

-시간복잡도, 공간복잡도 어림잡기

 

 

 

 

@가장 먼저 체크할 것

-시간 제한(안 써있으면 질문)

-메모리 제한

-입력 범위

 

 

 

 

@시간복잡도

-어떤 코드의 실행 시간이 오래 걸릴까?

 -> 연산이 많은 코드

 

-계산량은 어떤 값과 상관 있을까?

 -> 입력

 

-연산에 따라 속도가 다름

 

-모든 연산을 다 카운팅할 수 없음

 

-최악의 경우와 최선의 경우?

 -> 알고리즘에 따라 다름

 

-카운팅에 따라 실행시간도 다름

 -> 서버와 컴퓨터의 속도 차 등

 

 

 

=> 대충 계산하자! (접근적 표기법)

     Big-O Notation

 

 

 

 

log가 붙으면 절반이나 뭐 그렇게 균등하게 쪼개 볼 때 많이 사용한다고 보면 됨

 

 

 

 

@시간 | 공간복잡도

-Big-O notation은 점근적 표현법

 시간과 공간 차원에서 각각 다룰 수 있음 => 시간복잡도와 공간복잡도

 계산 + 시스템에 대한 감(센스)이 중요

 

 

 

 

@방법

-Navie한 풀이 떠올리기 (제한 상관 없이)

 중복되는 과정을 어떻게 줄일 수 있을까 고민하는 과정이 필요

 그렇기에 본인이 생각하는 가장 쉬운 풀이를 떠올리기

 

-중간 과정에 반드시 필요한 로직 생각하기

 

-예제 보기

 

-코드 짜기

 

 

 

 

@읽기와 분석 외전

-입력과 초기화 팁

-에러 메시지 이해하기

-추상화와 기능 분리: 함수 활용

-가독성: indent 줄이자

-명명법은 통일

 

 

 

 

@Map과 Comprehension

 

-입력의 대표적인 3가지

 : 수, 문자열(문자 배열), 배열

 

num = int(input())

string = input()
char_lst = list(input())

lst = list(map(int, input().split()))

input()은 문장(str) 단위로 받기 때문에 숫자면 형변환 필수

char형으로 받고 싶다면 string 자체로는 내용물을 바꾸지 못하기 때문에 list 씌워줘야 함

 

map(x, y)은 x함수를 y의 원소에 모두 적용한 map 객체 반환

나중에 char_lst 내용을 문자열로 만들고 싶다면? join 메서드

 

 

 

-List 초기화는 Comprehension으로!

 

lst_1d = [0 for _ in range(N)]
lst_2d = [[0 for _ in range(N)] for j in range(N)]

0을 N개로 채운 1D 배열 만들어라

0을 N개 만들고 그 N개 짜리를 또 N개 만들어라

 

 

 

 

* 문제 풀 때는 메인 함수가 최소화 돼야 하기 때문에 기능을 함수로 만드는 게 좋음

 

-간략한 psedo-code 느낌으로 작성

 디테일한 부분은 함수를 만들며 수정

 

 

 

 

@명명법

 

• 카멜 표기법 (Camel Case): 각 단어의 첫 글자를 대문자로 적는다. 단, 가장 첫 글자는 소문자를 사용한다.

  • 예시: camelCase, variableN, thisIsCamelCase, howToSolveThisProblem

• 스네이크 표기법 (Snake Case): 소문자만 사용하고, 각 단어의 사이에 언더바(_)를 넣어서 적는다.

  • 예시: snake_case, variable_n, this_is_snake_case, how_to_solve_this_problem

• 파스칼 표기법 (Pascal Case): 카멜 표기법과 같지만, 가장 첫 글자도 대문자를 사용한다.

  • 예시: PascalCase, VariableN, ThisIsPascalCase, HowToSolveThisProblem