이 글들은 백준 온라인 저지의 백준님이 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
이 포스트는 수업에 참가하지 못해 자료만 보고 혼자 복습한 내용을 정리한 포스트다.
'공부 > 백준 2020년 1~2월 알고리즘' 카테고리의 다른 글
5번째 수업 (0) | 2020.01.22 |
---|---|
4번째 수업 (0) | 2020.01.19 |
3번째 수업 (0) | 2020.01.15 |
2번째 수업 (0) | 2020.01.11 |
1번째 수업 (0) | 2019.12.31 |