[이것이 취업을 위한 코딩 테스트다 with 파이썬] 2. 그리디 & 구현

그리디 알고리즘(탐욕법)

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구
• 정당성 분석 중요
  • 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

예시

루트 노드부터 시작하여 거쳐 가는 노드의 합을 최대로 만들고 싶음

-> 최적의 해는 무엇? / 단순히 매 상황에서 가장 큰 값만 고른다면?

 

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때 ↑

But, 코딩 테스트에서 대부분의 그리디 문제

-> 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제

 

---

구현(Implementation)

• 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 구현 유형의 문제 = 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
• 예시
  • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
  • 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
  • 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
  • 적절한 라이브러리를 찾아서 사용해야 하는 문제

2차원 공간 = 행렬(Matrix)

for i in range(5):
	for j in range(5):
    	print('(', i, ',', j, ')', end=' ')
    print()

 

시뮬레이션 및 완전 탐색 문제: 2차원 공간에서의 방향 벡터 자주 활용

 

# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

# 현재 위치
x, y = 2, 2

for i in range(4):
	# 다음 위치
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny)

---