알고리즘 이론

1427. 소트인사이드 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 굉장히 쉽다. 입력받은 후 정렬만하면 끝이다! 문제가 아무리 쉬워도 우리가 확인할 것이 있다. 바로 N의 범위!!! N은 1,000,000,000보다 작거나 같은 자연수이다. 때문에 int를 사용할 수 있다. long long을 사용해야하는 경우가 있을 수 있으니 항상 입력의 범위를 잘 확인하자! 이 문제는 앞서 풀이를 올렸던 문제들의 코드를 합치면 된다. 가장 먼져 N을 입력받고, 각 자리 수를 벡터에 저장한다. cin >> num; while (n..

1065. 한수 https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 제출 수가 굉장히 높은 것으로 보아 이 문제 역시 중요한 기초문제인것 같다. 하지만 필자는 문제의 풀이를 생각해내는데 꽤 많이 고민했다. 문제에서 주어진 '한수'를 어떻게 저장하면 좋을지 고민해가며 100~999까지의 '한수'를 모두 종이에 적어보았지만 어떠한 규칙도 발견하지 못했고, 규칙이 있어도 굉장히 복잡해질 것 같았다. 때문에 입력이 주어지면 입력된 정수까지의 한수를 모두 찾아..

1026. 보물 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 제출 수가 굉장히 큰 것을 보아, 알고리즘의 기초를 다루는데 있어 의미있는 문제라고 생각한다. 풀이: 문제에서 B는 재배열하면 안된다는 조건을 주었지만, 아이러니하게도 해당 알고리즘을 구현하는데 있어서 B의 순서를 바꾸어도 정답에는 아무런 영향이 없다. 우선 주어진 배열의 길이 N은 50보다 작거나 같은 자연수이기 때문에 시간제한은 크게 걱정하지 않아도 된다. 다만 매번 주의 깊게 살펴볼 것은 문제에서 배열의 원소들이 제시될 때, 이 원소..

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 브루트 알고리즘을 활용하는 문제이다. 즉, 모든 경우의 수를 살펴보고 답을 구하는 것이다. 변수 ret에는 M과 3개의 숫자를 선택했을 때의 합과의 차이를 저장한다. 문제에서 3개의 원소의 합이 M을 넘어가면 안된다고 했으므로, M보다 작을 경우에만 저장하면된다. 또한 M과 세개의 수의 합의 차가 가장 작아야하므로, ret가 더 작은 경우가 발생할 경우 값을 업데이..

알고리즘에는 다양한 정렬 방법이 있다. 필자는 매번 다양한 정렬 방법을 잊어 구글링을 한다. 이번 기회를 통하여 완벽하기 숙지할 예정이다. 정렬 알고리즘 1) 버블 정렬 (Bubble sort) 버블 정렬은 O(n^2) 시간에 동작하는 간단한 정렬 알고리즘이다. 이 알고리즘은 n번의 라운드가 진행되고, 매 라운드마다 배열의 원소를 한 번씩 탐색한다. 연속된 두 원소의 순서가 잘못되었을 경우 이를 맞바꾼다. 구현 for(int i=0;i

알고리즘의 시간 복잡도 시간 복잡도란 무엇일까? 시간 복잡도는 입력의 크기를 통하여 알고리즘의 수행 시간을 추정 값이다. 이를 통하여 알고리즘을 구현하기 전, 해당 방법으로 구현하였을 때의 수행 속도를 예상할 수 있다. 시간 복잡도 표현 방법 시간 복잡도는 'O(...)'로 나타낸다. 괄호 안에는 함수가 들어간다. 한번 예제를 통하여 알아보자. 예시01) a++; b++; c = a + b; O(1) : 위와 같이 코드가 단일 명령어로 구성되어 있었을 때의 시간 복잡도이다. 예시02) for (int k = i+1; k