그리디 알고리즘
현재 상황에서 가장 좋은 것만 고르는 방법
최소한의 아이디어는 필요함
단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지를 검토한다
- 최적의 해를 보장할 수 없는 경우가 많은데, 코테에서는 그리디 알고리즘으로 얻은 해가 최적의 해가 되도록 설정해서 문제를 낸다.
예시
거스름 돈 : 거슬러 줄 때 동전의 최소 개수를 구한다
아이디어 : 가장 큰 화폐 단위부터 돈을 거슬러 준다.
why?
가지고 있는 동전 중에서 큰 단위는 항상 작은 단위의 배수가 될 수 있기 때문에, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.
반례 : 500, 400, 100 원의 동전이 있을 경우에는 400원이 500원을 만들 수 없기 때문에 가장 큰 동전의 수부터 나누어주면 답이 나오지 않음.
분석
화폐의 종류가 K일 때 시간 복잡도는 O(K)로 화폐의 개수만큼만 복잡, 금액 자체와는 무관하며 동전의 종류와만 관련이 있다.
문제 1 : 1이 될 때까지
N을 K로 나누거나 1을 빼서 1이 될 때까지 과정을 수행한다. 이 때의 최소 횟수를 구하는 프로그램
idea
while문을 이용해서 무조건 K로 나누는게 더 최소의 횟수를 가질 테니까 K의 배수인지 확인하고 아니면 K의 배수가 될 때까지 나눈다. 그 과정에서 1이되면 break하고 횟수를 return
문제 2 : 곱하기 혹은 더하기
각 자리가 숫자로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 모든 숫자를 확이낳며 숫자 사이에 'X' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.
idea
0일 경우에 곱하면 0이 되어버리므로, 0일 때는 값을 더해준다.
1인 경우에는 곱하면 자기 자신이지만 더할 경우 +1만큼 늘어나기 때문에 더하는 것이 효율적이다.
따라서 0일경우, 1일 경우를 제외하고 모두 곱해서 값을 도출한다.
문제 3 : 모험가 길드
마을의 모험가 N명의 공포도를 측정했다. 공포도가 X인 모험가는 반드시 X명 이상 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있을 때 최대 모험가 그룹의 수를 구하여라
idea
공포도가 작은 애들끼리 먼저 붙여서 그룹을 생성
오름차순 정렬 이후에 공포도가 가장 낮은 모험가부터 확인한다
그룹의 수와 현재 공포도를 비교해서 공포도가 더 낮으면 그룹으로 묶는다.
구현(Implementation)
-
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 '구현문제'라고 보통 칭한다. -
구현 문제의 예시
- 알고리즘은 간단한데 코드가 지나칠만큼 길 경우
- 실수 연산을 다루고, 특정 소수점까지 출력해야하는 문제
- 문자열을 끊어 처리해야하는 문제
- 적절한 라이브러리르 찾아서 사용하는 문제 (순열, 조합)
-
일반적으로 2차원 공간은 행렬의 의미로 사용된다. 행렬에 대한 개념 이해 필요!
행렬
- 2차원 배열이라고 부르는 것과 같다. python에서는 2차원 list를 의미.
행과 열의 idx증가 감소를 잘 판단할 것 - 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.
ex)
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0] # 동, 북, 서, 남을 각각 의미
x, y = 2, 2 # 현재 위치에서
nx = x + dx[i]
ny = y + dy[i] # 를 이용해서 방향을 지정할 수 있다.
문제 1 : 시각
정수 N이 입력되었을 때 00시 00분 00초부터 N시 59분 59초까지의 시각 중에서 3이 하나라도 포함되어 있는 모든 경우의 수를 구하는 프로그램을 작성
idea
1분에 60초, 1시간에 60분 > 1시간에 3600초이므로
시간에 3이 들어가면 + 3600
분에 3이 들어가면 + 60
초에 3이 들어가면 + 1
... 도 가능하지만 사실 하루는 28800초밖에 안되기때문에 그냥 세어도 된다 >> 완전 탐색
문제 2 : 왕실의 나이트
왕국의 정원은 체스판과 같은 8x8 좌표 평면인데 이 나이트는 L자 형태로만 이동하고 정원 밖으로 나갈 수 없다. 나이트는 특정 위치에서 (수평+2,수직+1)이나 (수직+2,수평+1)로만 이동할 수 있다. 이 때 나이트가 이동할 수 있는 경우의 수를 구하기
idea
각 위치로 이동할 수 있는지 확인만 하면 된다.
2차원 배열을 이용해서 문제에 따라 이동할 수 있는 방향을 한 번에 정리해준 후에 사용해도 가능
문제 3 : 문자열 재정렬
알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어질 때, 알파벳을 오름차순으로 정렬해서 출력하고, 모든 숫자를 더한 값을 이어서 출력한다
idea
알파벳이면 각각 list에 담은 후 오름차순 정렬로 출력 + 숫자는 더해가면서 출력 이 때 알파벳 > isalpha()함수 이용할 것
