-버블 정렬이란 정렬하려는 배열의 값들이 5, 4, 9, 1, 7이고 오름차순으로 정렬하려고 가정했을 때, 1. 처음 인덱스에 있는 값부터 시작하여 끝 인덱스 -1까지 바로 다음에 있는 값과 비교하여 오른쪽에 있는 값이 더 크다면 두 값을 교환한다. 2. 이를 배열에 들어있는 값의 개수만큼 반복한다. 그리고 그림과 같이 값을 교환할 때 나오는 화살표들이 거품이 보글보글 일어나는 것과 비슷하게 생겼다고 하여 버블 정렬이라고 한다. -버블 정렬의 시간 복잡도 버블 정렬은 처음 인덱스부터 끝 인덱스까지 순환(n)하며 값을 교환하고, 이를 다시 배열에 들어있는 값의 길이만큼 돌리는(n) 정렬 알고리즘이기 때문에 n * n = n^2이라는 시간 복잡도가 나온다. -코드(C++)
-설명 정렬 방법 중 하나로써 갖고 있는 값들 중 최솟값을 선택해서(찾아서) 가장 왼쪽에 있는 값과 바꾸고, 그 다음으로 작은 수를 선택해서 그 다음 왼쪽에 있는 값과 하나하나씩 바꾸어가며 정렬하는 방법. -선택 정렬이 갖는 특징 구현이 간단하다. 알고리즘의 시간 복잡도가 O(N^2) 이다. -> 데이터의 수가 N이라면 그중 최솟값을 찾는 작업에 드는 시간 N. 이를 값들 중 왼쪽에 있는 값과 교환 모든 데이터 정렬을 위해 해당 작업을 N번 반복 -예 데이터 : 1 2 5 8 11 51 3 7 1번 반복 : 1 2 5 8 11 51 3 7 (1이 최솟값이라 변화 없음) 2번 반복 : 1 2 5 8 11 51 3 7 (2가 최솟값이라 변화 없음) 3번 반복 : 1 2 3 8 11 51 5 7 (3번째 최솟..
문제 무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. 출력 첫째 줄에 분수를 출력한다. 예제 입력 1 14 예제 출력 1 2/4 제출 코드 출처 - https://www.acmicpc.net/problem/1193
문제 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다. 출력 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다. 예제 입력 1 13 예제 출력 1 3 제출 코드 출처 - https://www.acmicpc.net/problem/2292
문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 출력 상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정..
문제 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다. A, B, C가 주어졌..