PS 팁 1

1. sagment fault, 틀렸습니다 의 경우 생각해 볼 수 있는 경우의 수

• 혹시 배열의 사이즈를 넉넉히 잡아 주었는지?
  배열의 마지막엔 null이 오는 경우까지 생각해 주어야 하므로
  input이 1,000,000 인 경우배열의 사이즈를 int input[1000001]로 잡아 주어야합니다.
  
  추가적으로 sagment fault의 대부분의 경우에는 잘못된 주소값에 접근하려 해서 생기는 오류입니다.
  배열의 index가 맞는지 포인터를 현재 잘 쓰고 있는지에 대한 부분을 확인하면 됩니다.
  
  

2. 초기화를 잘하자

• 처음 변수를 선언할 경우 쓰레기값이 들어가게 됩니다.
  그래서 항상 0으로 초기화를 시켜주시는게 좋습니다!
  
  

3. 맞왜틀을 외치기 전에 다시 한번 코드를 보자

• 맞왜틀을 하는 대부분의 경우 자신의 논리가 틀린 경우가 아주 많습니다.
  이러한 일을 사전에 방지하기 위해서는 많은 반례를 넣어 보아야 합니다.
  경계값을 input으로 넣거나 많은 양의 input을 넣어보거나 해보면 자신의 논리를 잘 검증할 수 있습니다.
  
  많은 반례를 넣고 왜 틀렸는지 알고 난 뒤 어디를 고쳐야 할지 상당히 난감한 경우가 많습니다.
  
  코드의 순서를 하나 하나 꼼꼼히 읽고 따라가다 보면 쉽게 해결 할 수 있습니다.
  머릿속으로만 생각하면 생각이 꼬이거나 현재 무슨 값이 있는지 헷갈리는 경우가 많기 때문에
  Visual Studio의 디버깅 기능을 이용하거나 print를 통해 쉽게 틀린 부분을 찾을 수 있습니다.
  
  

4. 보기 쉬운 코드를 짜자

• 코드 작성하실 때 줄바꿈을 하셔서 코드들을 덩어리별로 나누는게 좋습니다.
  
  나중에 프로젝트를 하실 때 다른 사람들이 본인의 코드를 볼 때 훨씬 편하게 볼 수 있습니다.
  혼자 처음부터 끝까지 다 짜는게 아닌한 무조건 다른 사람들과 협업을 해야하기 때문에
  다른 사람들이 보기 편하게 코드를 작성하는게 도움이 많이 되실겁니다.
  그리고 미리 습관을 들이셔야 나중에 안 힘드실 겁니다.
  
  추가적으로 주석을 달아놓는 습관 또한 아주 좋은 습관입니다. (물론 저는 아직 그렇게 못하고 있습니다;;;;;)
  
  

5. 시간 최적화

• 입출력의 경우 C, C++ 을 처음 입출력을 함수를 배우실때 printf, scanf를 배워서 사용하실 겁니다.
  일반적인 연산은 대략 1초에 1억 번 정도의 연산이 가능하다고 알려져 있지만,
  입출력의 경우엔 입력되는 값이 10만개만 되더라도 실행 시간에 적지 않은 영향을 미칩니다. (참고)
  
  
• 그래서 C++을 사용하고 계시는 경우 ios_base::sync_with_stido(bool sync); cin.tie(NULL); 등을 main 함수의 최상단에 미리 선언하시고 사용하면 입출력 시간을 훨씬 단축하실 수 있습니다. (참고)
  그리고 endl 보다 '\n'이 훨씬 빠릅니다.

---

• 비트 연산
  논리설계에서 이진법에 대해 이미 공부하셨다고 생각합니다.
  컴퓨터는 이진법으로 계산합니다.
  그래서 int형 변수
  숫자 1은 0000 0000 0000 0000 0000 0000 0000 0001 이렇게 표현합니다.
  숫자 2는 0000 0000 0000 0000 0000 0000 0000 0010 이렇게 표현합니다.
  숫자 3는 0000 0000 0000 0000 0000 0000 0000 0011 이렇게 표현합니다.
  
  또 컴퓨터는 저희가 쓰는 +,-,*,/ 모두 이진법으로 계산하고 저장합니다.
  그래서 +,- 보다 *,/,% 이 훨씬 느립니다.
  그래서 2를 곱하거나 나누는 경우 <<, >> 비트 이동 연산자를 쓰시는게 좋습니다!
  비트 이동 연산자는 << n은 n 개의 비트만큼 왼쪽으로, >> n은 n 개의 비트만큼 오른쪽으로 옮기는 역할을 합니다.
  
  
  1 << 1 (1 * 2) = 2
  2 << 1 (2 * 2) = 4
  2 << 2 (2 * 4) = 8
  그래서 나누기의 경우에도 반대로 생각하고 이용하시면 됩니다.
  
  • ~n: -n - 1
    
    • 예)
      int num = 15;
      num = \~num;
      결과: num = -16
  • (x+y>>1): 두 수의 평균

 

• 응용:
  비트 연산자는 2의 곱 or 나누기만 된다는 걸 유의하시고 사용하시면 됩니다.
  
  8 숫자 8은 0000 0000 0000 0000 0000 0000 0000 1000 이렇게 표현합니다.
  
  4 숫자 4은 0000 0000 0000 0000 0000 0000 0000 0100 이렇게 표현합니다.
  
  2 숫자 2은 0000 0000 0000 0000 0000 0000 0000 0010 이렇게 표현합니다.
  
  1 숫자 1은 0000 0000 0000 0000 0000 0000 0000 0001 이렇게 표현합니다.
  
  그래서 홀수인 경우에는 마지막 0001이 필요하기 때문에 if(a & 1)로 확인하는 것이 훨씬 빠릅니다!

 

• 많은 분들이 if문으로 홀수 혹은 1 인지 확인할때 if(a == 1) or if(a == 3) 등을 쓰고 계십니다.
  하지만 많은 분들은 이런 비효율적인 조건이 아닌 비트 연산자를 쓰시길 간곡히 부탁드립니다.

---

• 논리의 증명
  예를 들어 브루트 포스(Brute force)를 통해 답은 맞지만,
  브루트 포스가 아닌 그리디, dp 등 처럼 좀 더 효율적인 알고리즘이 없는지 다시 한번 생각해보셔야 합니다.
  
  
• 시간초과가 난 절반의 경우 애초에 접근한 논리가 잘못 됐을 수 있습니다.
  분명 답은 맞지만 생각하신 알고리즘이 아닌 더 효율적인 알고리즘으로 짰었어야 한다는 이야기 입니다.

---

여기 있는 팁 내용들은 차차 추가, 수정해 나갈 예정입니다.

댓글로 추가사항등을 달아 주시면 감사하겠습니다!!!