1. 최대공약수 구하기
- 숫자 두 개가 주어졌을 때 곱셈, 나눗셈, 나머지 연산을 사용하지 않고 최대 공약수를 구하는 효율적인 알고리즘을 설계하라
2. 배열에 존재하지 않는 가장 작은 양의 정수 찾기
- 길이가 n인 배열이 있을 때 A에 존재하지 않는 양의 정수 중 가장 작은 숫자를 찾는 알고리즘을 설계하라.
- A의 내용을 보존할 필요는 없다.
- 예로 {3, 5, 4, -1, 5, 1, -1} 에 존재하지 않는 가장 작은 양의 정수는 2이다.
풀이 방법
- 정렬 해서 찾거나 O(nlogn)
- 해시 테이블을 이용하는 방법도 있다. O(n), 공간 복잡도 O(n)
- A를 수정할 수 있으므로 모든 원소를 순회하며 각 숫자를 해당 인덱스에 배치해 준 뒤,
- 다시 순회하며 인덱스에 해당 숫자가 없는 경우 해당 숫자를 리턴하면 된다.
- 그러면 공간 복잡도가 상수 이다.
3. 주식 최대 k번 사고팔기
- 주식을 주어진 기간 안에 k번 사고팔 수 있다고 했을 때 이윤을 최대화하는 프로그램을 작성하라.
풀이 방법
- 매수-매도 거래가 하나 남아있을 때 얻을 수 있는 최대 수익 계산을 고려해 보자.
- 먼저, k >= n/2 라면, 원하는 만큼 사고팔 수 있으므로, 최적 전략은 증가하는 모든 범위의 시작점에서 구입해 최고점에서 판매하는 것이다.
- k < n/2 라면, …
응용
- 무제한으로 주식을 사고 팔 수 있고, 대신 이전에 주식을 팔았다면 하루가 지난 이후에 주식을 살 수 있을 때 최대 이윤을 구하는 프로그램을 작성하라
4. 하나를 뺀 나머지를 모두 곱했을 때의 최댓값 구하기
13. 합당한 보너스 구하기
- 개발자들 배열이 주어졌을 때, 모든 개발자들에게 티켓을 하나 이상 주어야 하고,
- 한 개발자가 옆의 개발자 보다 많이 일했다면 티켓을 더 많이 받게 배분하려 한다.
- 배분하는 티켓의 최소 갯수는 얼마인가
풀이 방법
- 모든 방법을 고려하는 방식은 티켓의 개수를 k, 개발자의 수를 n이라 했을 때, 시간 복잡도가 O(kn^2)이다.
- 우선 모든 개발자에게 티켓을 하나씩 주고, 옆보다 일을 더 했는데 못받은 경우 티켓을 더 주는 방식이다.
- 다른 방법으로 힙을 이용해 가장 생산성이 낮은 개발자 순으로 티켓을 배분하는 방법이 있다.
- 배열을 두번 읽어 해결 가능하다.
- 왼쪽에서 오른쪽으로 읽어가며 티켓을 배분하고, 오른쪽에서 왼쪽으로 읽어가며 티켓을 배분한다.
- 시간 복잡도는 O(n)이다.
15. 두 개의 정렬된 배열에서 탐색하기
- 정렬된 배열 두 개와 양의 정수 k가 주어졌을 때, 두 개의 배열에서 k번째로 작은 원소를 찾는 알고리즘을 설계하라.
- 배열의 원소는 중복되어 나타날 수 있다.
풀이 방법
- 첫 배열의 첫 k번째 원소와 두 번째 배열의 첫 번째 k 원소는 초기 후보군이다.
18. 가장 많은 점을 지나는 선 구하기
- 평면상에 점들이 놓여 있다. 각 점은 정수 좌표로 이루어져 있다. 가장 많은 점을 지나는 선을 찾는 알고리즘을 설계하라.
풀이 방법
- 기울기!!
- 함수는 기울기와 Y절편을 이용해 나타낼 수 있다.
- 유한 정밀도에 의한 오차를 없애려면 기울기를 분자와 분모 정수 쌍으로 관리하는 것이 낫다.
31. 가둬둔 물의 양 구하기
- 물을 담는 컨테이너의 각 너비는 일정하며 각 숫자는 높ㅣㅡㄹ 의미한다.
- 컨테이너에 담을 수 있는 용ㅑㅇ을 구하는 알고리즘을 설계하라
풀이 방법
- 최대 용량에 도달하면 단면적은 수면 높이가 감소하지 않는 영역과 수위가 증가하지 않는 영역으로 구성된다.
- 감소하지 않는 영역에서 증가하지 않는 영역으로 바뀌는 순간은 최댓값 근처에서 발생한다.
- m에서 최댓값일 때,
- 0~m-1 구간과 m~n-1구간으로 나누고,
- 각 구간의 최댓값을 m으로 둔뒤,
- 0 에서 부터 m 에서 뺸 값을 더해가고,
- n-1에서 부터 m 에서 뺀 값을 더해간다.
32. 일정 횟수 이상 등장한 단어 찾기
- n/k 번 이상 등장한 단어를 구하는 알고리즘을 설계하라.
풀이방법
Leave a comment