최백준 선생님의 코테인강 시작....꾸준히 열심히 제발^^
- 효율성
- 시간이 중요함. 메모리는 부족하면 램을 구매할 수 있음. 즉, 수행 시간이 젤 중요함.
- 복잡한 문제는 정답이 존재하지 않는 문제, 정말 복잡한 문제 등.
- 정답이 존재하고 / 시간 몇 초 안에 풀 수 있는지.
- 알고리즘 문제 해결에 한정지은 것. - 문제의 크기
- 개발 상황에서 접하게 되는 상황은 문제를 해결하는 것. 항상 문제의 크기가 존재.
- 예 1) 쇼핑몰 장바구니 물건의 개수
- 예 2 ) 게임 동시 접속자의 수
- 문제의 크기에 따라 알맞은 방법을 선택하는 것이 좋다. - 시간 복잡도
- N -> 어떤 식.
- 1. 코드를 작성하고 코드를 보고 계산.
- 2. 코드를 작성하기 전에 어떻게 해야겠다는 방법을 보고 계산.
- -> 먼저 계산을 하고 구현을 하는 것이 효율적.
- 표기법으로 대문자 O를 사용함. Big O notation 빅오표기법.
- 즉, 최악의 경우에 시간이 얼마나 걸릴지 알 수 있음.
- 문제의 크기 N
- 빅오표기법에서 상수는 버린다.
- O(3N) -> (N) 이런식으로.
- O(5) -> O(1)
- O(N^2 + N) -> O(N^2) - 메모리
- 메모리 제한은 보통 넉넉하기 때문에, 걱정할 필요 없음.
- 대략적으로 얼마나 공간을 사용할지 예상할 수는 있다.
- 보통 가장 많은 공간을 사용하는게 배열.
- 배열이 사용한 공간 : 배열의 크기 X 자료형의 크기 B
- 4byte 10000 = 4만 바이트.
- 4byte 1000000 = 400만 바이트.
- 1024b = 1KB
- 1024KB = 1MB
- 1024MB = 1GB
- 100만B = 1MB
- 메모리는 크게 걱정하지않아도 됨. 불필요한 공간이 없다면, 대부분 메모리 제한은 알아서 지켜짐. - 입/출력
- 1. 직접 입/출력을 받아야하는 경우
- 2. 함수만 구현
- C의 경우는 scnaf/printf
- C++의 경우에는 scnaf/printf, cin/cout
- JAVA의 경우 Scanner, 출력은 System.out
- 속도가 느림. BufferedReader를 사용.
- BufferedReader br = new BufferedReader(New InputStreamReader(System.in));
- 출력이 많은 경우에는 StringBuilder를 사용해서 한 문자열로 만들어서 출력을 한번만 사용하거나 BufferedWriter를 사용한다.
- 1. 입력/ 출력
- 두 수를 입력받고 A+B를 출력.
- 2. 테스트케이스
- A+B - 3
- 테스트 케이스 형식으로 주어지는 경우에는 각각 독립적인 문제라고 생각하고 풀면 됨.
- 테스트 케이스의 총 개수가 몇개인지 모르기 때문에 입력받고 바로 출력 이런식으로 해야함.
- 또, 전체 입력이 매우 큰 경우에 매우 큰 크기의 배열이 필요하기 때문에..
- A, B 입력받고 바로 A+B 출력.
- A+B - 4 - 언어별 유의사항
- 시간 초과
- Java String의 length() 은 O(1)이다.
- s += "A"; -> StringBulder을 이용해야한다. - 나머지 연산
- (A+B) % M = (A%M + B%M) % M
- (AB) % M = (A%M B%M) % M
- 음수의 경우 결과의 부호가 프로그래밍 언어마다 다르다.
- (A-B)%M = (A%M - B%M+M) %M
- logn = 2^63-1
- int 4byte : 2^31-1
- 문제에서 정담을 ~~로 나눈 나머지를 출력하라는 말이 있는 이유
- 정답 : 경우의 수. 정답이 너무 큼.
- 2와 5로 나누어 떨어지지 않는 정수 N이 주어졌을때, 1로만 이루어진 N의 배수를 찾는 문제
- 1%N
- 11%N
- 111%N
- 1111%N ,,,,,,,,,,,,
- 수의 크기가 int, long의 범위를 넘어갈 수 있기 때문에 수를 실제로 만들 수 없다.
- N의 배수는 N을 나눈 나머지가 0이다. 이 점을 이용해서 나머지만 유지해서 계산.
- 1이 73개 % N = 1
- 1이 74개 % N = ?
- ((1이 73) * 10 + 1 ) % N
- 수가 너무 큰 경우에 그 수의 나머지가 의미가 있으면 그걸 이용해서 계산 가능.
출처 : 2021 코딩 테스트 준비 - 기초 (최백준)
#back_end #developer #🐥
0개의 댓글
