0x01, 02 기초 코드 작성 요령
바킹독님의 실전 알고리즘 강의를 듣기 시작하였고, 들으면서 정리한 내용을 바탕으로 기록을 남기려 한다.
기초 코드 작성 요령은 2개의 강의에 걸쳐 진행되는데 각각 3개, 총 6개 소단원으로 같이 정리하려고 한다.
0x00 시간 / 공간 복잡도
시간 복잡도 (Time Complexity)
공간 복잡도 (Space Complexity)
512MB = 약 1.2억개의 int 기억해서 코딩하기
0x01 정수 자료형
char ( 1byte ) short ( 2 bytes ) int ( 4 bytes ) ~약 21억 long long ( 8 bytes )
0x02 실수 자료형
float ( 4 bytes )
- 유효숫자 6자리 → 오차 10^(-6)
double ( 8 bytes )
- 유효숫자 15자리 → 오차 10^(-15)
IEEE 754 format
실수 자료형의 성질
- 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다.
- double에 long long 범위의 정수를 함부로 담으면 안된다. (유효 숫자가 다르기 때문)
- 실수를 비교할 때는 등호를 사용하면 안된다 Ex_ 0.1+0.1+0.1 != 0.3
0x02 기초 코드 작성 요령2
0x00 STL과 함수 인자
0x02강은 먼저 함수 인자에 대해 복습하는 문제가 주어졌다.
3개의 출력값을 예측해보는 문제이다. 1번과 2번은 너무나 익숙한 문제여서 고민없이 답이 나왔지만 3번은 헷갈렸다.
struct를 파라미터로 보내면 값이 복사된다는 것을 확실히 다시 상기시키는 문제였다. (주소값 x)
참조자 (Reference)
swap함수의 예를 보며 참조자에 대해서 알게되었다. C++에서는 해결법이 하나 더 있었고, 바로 참조자(reference)였다. a와 b를 int reference로 만들면 함수 내의 코드에서는 그냥 int를 쓰듯이 사용하지만 모두 다 원본을 바꾸는 것이다.
참조자는 C에서 포인터와 거의 비슷한 기능을 하지만 포인터에서 Null pointer에 값을 넣는다거나 type이 다른걸 마음대로 캐스팅한다거나 하는 문제들을 덜 할 수 있게 하는 패러다임이다.
STL(Standard Template Library)의 함수 인자
STL도 구조체와 비슷하게 복사본을 만들어 보낸다. 따라서 크기가 N인 벡터의 복사본을 만드는 과정이 O(N)의 시간이 든다.
하지만 이렇게 참조자를 이용하면 참조 대상의 주소정보만 넘어가기 때문에 O(1)의 시간으로 의도에 맞게 코드를 짤 수 있었다.
0x01 표준 입출력
- 공백포함 문자열 처리 (c++ string) : getline 함수
- cin, cout 사용시
- ios::sync_with_stdio(0) : C stream과 C++ stream의 동기화를 끊음으로 프로그램 수행시간에서 이득을 챙길 수 있다. 하지만 이후에 printf와 cout 병행금지!!
- cin.tie(0) : 입출력이 번갈아 실행되고 화면에 나올경우 버퍼로 인해 순서가 꼬일 수 있다. 따라서 cin 명령어 수행 전에 cout 버퍼를 비워주는데 온라인 저지 사이트는 출력 글자만 확인하기 때문에 버퍼를 비울 필요가 없다.
- endl 사용금지!! : 개행문자를 출력하고 출력 버퍼를 비우는 명령어. 버퍼를 비울 필요가 없기 때문에 개행문자를 따로 출력해야한다.
0x02 코드 작성 팁
- 코딩테스트와 개발은 다르다.
- 깔끔한 코드보다는 조금 더럽더라도 내가 빠르게 짤 수 있는 방식으로 구현하는게 훨씬 더 중요!!
- 출력 맨 마지막 공백 혹은 줄바꿈이 추가로 있어도 상관이 없다.
- 디버거는 굳이 사용하지 않아도 된다 → cout 이용해서 중간 출력
문제 풀이
강의를 듣고나서 이번 강의에 해당하는 문제를 풀었다. 27개의 문제였지만 백준 브론즈에서도 쉬운 문제에 속하는 기초적인 문제였고 대부분 고민없이 해결하였다.
Note_ 10093번 숫자, 이 문제는 정수가 int에 담기지 않는 큰 수를 다루기 때문에 long long으로 선언해주어 문제를 해결하였다.
10804 카드 역배치, 이 문제는 swap을 이용해 역배치 하려고 했지만 찾아보니 vector의 reverse 함수를 이용해 더 쉽게 푸는 방법도 있었다.
2309 일곱 난쟁이, 이 문제는 브루트포스 알고리즘에 해당하는 문제였다. 처음 봤을 때 정답이 보이지 않았고 쉬운 문제라고 방심하다가 뒤통수를 맞은 기분이였다. 일곱 난쟁이의 합이 100이 아닌 sum - 다른 두 난쟁이의 키로 구할 수 있었다.
리뷰
정말 무턱대고 지금까지 온라인 저지 사이트에서 코딩을 해왔는데 시간초과를 비롯해 엄청 많은 오류들과 실패라는 단어를 봤었다.
너무나 실망하고 힘들었지만 찾아보면서 대충의 내용은 알고 있었다.
하지만 이렇게 필요한 내용을 정리해서 보기 편하게 되어있어서 더욱 알기 쉬웠고 더 깊이 알 수 있었다.
이제 이렇게 다시 한번 정리하면서 어떤 이유로 인해 어떤 방향으로 코드를 짜야하는지 알게되었고 기초지만 primary라는 바킹독님의 말이 마지막에 떠오르는 강의였다.
이렇게 다시 기초를 튼튼하게 다질 수 있었다.
다음은 0x03강 배열로 찾아오겠다.
출처: 바킹독님의 실전알고리즘 강의