그리디 & 구현

기술면접을 위해 기초 CS에 대한 복습중이다.
공부한 내용 중 요점이나 나중에 기억해야할 부분을 정리해보려고 한다.
내가 아는 부분은 생략되어 있을 수 있고, 혹여나 틀린 부분이 있을 수도 있으니 이 글을 보고 '다른 사람'이 공부하기에는 도움이 되지 않을 수 있으니 주의!

그리디 알고리즘(Greedy)

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 정당성 분석이 중요! 예를 들어, 동전 거스름돈 문제처럼 큰 단위가 항상 작은 단위의 배수일 경우 적합하다.
  • 모든 케이스를 볼 필요 없을 때
  • 정해진 이전 것이 다음에 영향을 미치지 않을 때
  • 현재 조건에서 현재 값이 최적 해일 때

구현(Implementation)

• 구현 유형 == 시뮬레이션 유형 == 완전 탐색 유형
• 2차원 공간은 행렬(Matrix)를 의미한다. 방향 벡터 이용.
  • L일 경우, dx[0]과dy[0]을 더해주면 된다.
• // L, R, U, D에 따른 이동 방향 int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0}; char moveTypes[4] = {'L', 'R', 'U', 'D'};
• char를 int로 변환: n = ch - '0'; 이런 식으로 '0' 의 ASCII코드 값을 빼주면 된다. 그러면 char형의 1이 진짜 숫자 1로 변환된 값을 얻을 수 있다.
• 알파벳을 int로 변환: n = ch - 'a' + 1 이런 식으로 하면 char a가 1로 표현되고, b는 2 이런 식으로 값을 얻을 수 있다.