그리디 & 구현 개인공부(이론)

그리디

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 최소한의 아이디어를 떠올릴 수 있는 능력 요구
• 정당성 분석이 중요
• 일반적인 상황에서는 최적의 해를 보장할 수 없을 때가 많지만 코딩 테스트의 경우 대부분 그리디 문제로 얻은 해가 최적의 해가 됨
  • 이를 추론할 수 있는 능력을 길러야함

 

구현:시뮬레이션, 완전 탐색 위주

 

• 구현: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 코딩 테스트에서 구현 유형 문제
  • 풀이를 떠올리는 것은 쉬움, 그러나 소스 코드로 옮기기 어려움
• 예시
  • 알고리즘은 간단하지만 코드가 지나칠만큼 길어지는 유형
  • 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
  • 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
  • 적절한 라이브러리를 찾아서 사용해야하는 문제
    • 파이썬의 경우에는 패키지를 사용해서 쉽게 구현 가능하다네
      • 따라서 많은 문제 유형을 풀어보고 라이브러리의 유무를 인지하고 있는게 중요
  • 시뮬레이션/완전탐색을 기준으로 구현이라 칭함

 

• 일반적으로 알고리즘 문제에서 2차원 공간은 행렬을 의미
• 코딩 테스트의 경우 2차원 공간 행렬을 가정하는 경우가 많음
• 시뮬레이션 및 완전 탐색 문제는 2차원 행렬에서의 방향 벡터가 자주 등장
  • ex
    • #동, 북, 서, 남
    • dx = [0,-1, 0,1]
    • dy = [1,0,-1,0]

 

이론복습 완료 됐으면,

그리디&구현 기초 알고리즘 문제 다시 풀어보고, 익술해질때까지 코드 리뷰하기(주피터 환경, 함수 사용  x)