📕 그리디 알고리즘
- 현재 상황에서 지금 당장 좋은거 고르는 방법
- 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구
- 그리디 해법은 그 정당성 분석이 중요하다. 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토
➡ 코딩테스트에선, 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다. 즉, 탐욕법으로 얻은 해가 최적의 해가 되는 경우에 한해서 출제를 한다.
예시) 거스름 돈 - 가장 큰 화폐단위부터 시작해서 최대로 줄 수 있는만큼 준다.
문제1. One이 될 때까지
- 아이디어 - 최대한 많이 나누기
- 정당성 - n 값을 줄일 때 2 이상의 수로 나누는 작업이 빼는 것보다 훨씬 많이 줄일 수 있다.
💻 내 코드
public int solution(int n, int k) {
int cnt = 0;
while( n > 1 ) {
if ( n % k == 0) n /= k;
else n -= k;
cnt++;
}
return cnt;
}💻 예제코드
public int solution2(int n, int k) {
int result = 0;
while(true) {
// n이 k로 나누어 떨어지는 수가 될 때까지 빼기
int target = (n/k) * k;
result += (n - target);
n = target;
// n이 k보다 작을 때 (나눌수없을 때)반복문 탈출
if (n<k) break;
// k로 나누기
result += 1;
n /= k;
}
// 마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1);
return result;
}📕 구현
문제의 초점이 구현이 맞춰져 있고, 구현이 어려운 문제를 뜻한다.
즉, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
예시로는,
- 알고리즘은 간단한데 코드가 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
- 시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많다
⚫ 방향벡터
시뮬레이션 및 완전 탐색 문제에서 2차원 공간에서의 방향 벡터가 자주 활용되며, 배열이나 리스트로 구현한다.
🔽 예시문제
여행가 A는 N * N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상,하,좌,우 방향으로 이동할 수 있으며, 시작좌표는 항상 (1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여있다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L,R,U,D 중 하나의 문자가 반복적으로 적혀있다.
- L : 왼쪽으로 한 칸 이동
- R : 오른쪽으로 한 칸 이동
- U : 위로 한 칸 이동
- D : 아래로 한 칸 이동
이때 여행가 A가 N * N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
시간제한: 2초 | 메모리 제한: 128MB
입력조건
첫째 줄에 공간의 크기를 나타내는 N이 주어진다. ( 1 <= N <= 100)
둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 <= 이동횟수 <= 100)
5
R R R U D D
출력조건
첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X , Y)를 공백을 기준으로 구분하여 출력한다.
3 4