1번째 수업 복습

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다.

---

● 알고리즘

- 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태

 

무엇이 가장 중요할까?

1. 수행시간 - 가장 중요하다

2. 사용한 메모리 - 부족하면 추가하면 된다

3. 코드의 길이 - 중요하지 않다

 

시간복잡도

- Big O :  최악의 경우에 걸리는 시간

- N이 1억일때 약 1초 정도 걸린다.

 

메모리

- 보통 가장 많은 공간을 차지하는 것은 배열

- 보통 시간을 지키면 대부분 메모리 제한은 알아서 지켜짐.

 

입출력

- C : scanf/printf

- C++ : cin/cout (scanf/printf보다 느리다.)

- cin/cout의 경우 다음 코드를 추가하면 scanf/printf만큼 빨라짐 (단, 이 경우는 섞어쓰면 안됨.)

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

- Java : Scanner/System.out (입력이 많을 경우 BufferedReader, 출력이 많을 경우 BufferedWriter)

- C++에서 줄바꾸기는 \n이 endl보다 빠르다. (10배 이상)

● 자료구조1

스택

- 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조

- 마지막으로 넣은 것이 먼저 나옴. LIFO(Last In First Out)

- 일차원 배열 하나로 구현 가능

 

큐

- 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조

- 먼저 넣은 것이 가장 먼저 나옴. FIFO(First In First Out)

- 일차원 배열 하나로 구현 가능

 

덱

- 양 끝에서만 자료를 넣고 양 끝에서 뺄 수 있는 자료구조

- Double-ended queue의 약자

● 수학1

나머지 연산

- (A+B)%M = ((A%M)+(B%M))%M

- (A×B)%M = ((A%M)×(B%M))%M

- (A-B)%M = ((A%M)-(B%M)+M)%M

- 음수의 경우 결과의 부호가 프로그래밍 언어마다 다르다.

- (-1)%3 = -2 : C, C++, Java

- (-1)%3 = 1 : Python

 

약수

- N의 약수 : O(N)

- 최대공약수 : a와 b를 나눈 나머지를 r이라 했을 때, GCD(a, b) = GCD(b, r)다. r이 0이면 그 때 b가 최대공약수.

- 최소공배수 : a, b의 최대공약수를 g라 했을 때, 최소공배수 l = g*(a/g)*(b/g)다.

 

소수

- 약수가 1과 자기자신밖에 없는 수

1. 어떤 수 N이 소수인지 아닌지 판별하는 방법

- N을 2부터 N-1까지 모든 수로 나눠보는 방법 : O(N)

- N이 소수가 되려면, 2보다 크거나 같고, 루트N 보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.

- 즉, 루트 N까지만 나눠보면 된다. O(루트(N))

2. N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법

- 에라토스테네스의 체 : 2부터 N까지 모든 수를 써놓고 소수의 배수를 모두 지우는 방법

- 루트(N)까지 진행 후 남은 수가 모두 소수이다.

 

팩토리얼

- N! = 1×2×...×N

 

---

이 포스트는 수업에 참가하지 못해 자료만 보고 혼자 복습한 내용을 정리한 포스트다.