성공 코드(내 코드) people을 오름차순으로 정렬한다. 보트에 최대 2명이 탑승 가능하므로 최솟값 + 최댓값을 더해본다. 더해준 값이 limit을 넘으면 2명 탑승이 안되므로 맨 뒤의 사람은 혼자 타야한다. 한명 밖에 타지 못하면 맨 뒷사람을 가리키는 인덱스를 줄여준다. 더해준 값이 limit을 넘지 않으면 2명 탑승이 가능하다. 즉 맨 앞사람을 가리키는 인덱스를 하나 증가시키고 맨 뒷사람을 가리키는 인덱스를 하나 감소시킨다. 이 과정을 맨 앞사람을 가리키는 인덱스가 맨 뒷사람을 가리키는 인덱스보다 작거나 같은 동안 반복해준다. #include #include #include using namespace std; int solution(vector people, int limit) { int answ..
알고리즘 이분 탐색 누적 합 풀이 석순은 아래에서부터 종유석은 위에서부터 자란다. 이를 각각 bottom 벡터과 top 벡터로 나타낸다. 번갈아가면서 석순과 종유석의 길이가 입력되므로 차례대로 입력받은 값을 bottom 벡터 또는 top 벡터에 인덱스로 하여 1씩 더해준다. 실제로 석순의 길이가 3이라면 bottom[1], bottom[2], bottom[3]에 모두 1씩 더해주어야 하는데 이것을 이중 for문으로 다음과 같이 구현하면 시간 초과가 발생하므로 다른 방법을 사용하여야 한다. 시간 초과 코드 #include #include #include using namespace std; int main() { // freopen("input.txt", "rt", stdin); ios_base::sync..
아래 정렬은 모두 오름차순 정렬을 기준으로 정리하였다. 선택정렬(Selection Sort) 가장 작은 수를 찾아 앞으로 보내는 과정을 반복 배열의 처음부터 끝까지 반복문을 통해 돌며 가장 작은 수를 찾는다. 가장 작은 수를 배열의 맨 앞으로 보낸다. 그 다음 배열부터 끝까지 또 작은 수를 찾아 맨 앞으로 보낸다. 이 과정을 배열이 끝날때까지 반복하여 정렬을 한다. 시간복잡도는 O(n^2) #include int main() { freopen("input.txt", "rt", stdin); int a[101], n, tmp, idx, i, j; scanf("%d", &n); for(i=0; i