homebrew computer club

삽입 정렬(Insertion sort) 삽입 정렬은 원소가 있어야 하는 자리에 '삽입'한다고 하여 삽입 정렬이다. 5, 7, 2, 4 ,6 이라는 원소가 있고, 여기서 세 번째 원소인 2를 선택했다고 하자. 오름차순 정렬이라면 2는 맨 첫 번째에 위치해야 한다. 방법은 간단하다. 2보다 앞에 위치한 원소를 하나씩 비교하며 앞의 원소보다 2가 더 작다면 한 칸씩 앞으로 보내면 된다. 앞에서 공부한 버블, 선택 정렬과 마찬가지로 두 번째 원소부터 비교를 시작한다. 이전 원소들을 비교해나가기 때문에 첫 번째 원소부터 시작하지 않아도 된다. 버블 정렬, 선택 정렬과 같이 제자리 정렬(in-place) 알고리즘이다. 또한 버블, 선택 정렬에 비해 속도가 빠르다. 배열이 길어질수록 효율이 떨어진다는 ..

선택 정렬(Selection sort) 선택 정렬은 자리를 선택한 다음, 거기에 맞는 원소를 찾아서 위치시킨다. 오름차순 정렬을 한다고 해보자. 첫 번째 자리엔 가장 작은 원소가 있어야 한다. 선택 정렬은 첫 번째 자리를 '선택'한 다음 원소 리스트를 순회하며 가장 작은 값을 찾아서 첫 번째 자리에 데려다놓는다. 그 다음 두 번째 자리를 선택하고 두 번째로 작은 원소를 찾는다. 이 작업을 원소 리스트의 크기 만큼 반복하는 것이 선택 정렬이다. 말하자면 선택한 장소에 마땅히 있어야 할 원소를 찾아서 제자리로 돌려보내는 것이다. 최소값을 찾는다. 그 값을 맨 처음 위치한 값과 바꾼다. 제자리를 찾은 원소를 빼고 1, 2번을 반복한다. 선택 정렬은 원소 리스트를 한 번 순회할 때 하나의 원소만 ..

Github : https://github.com/cocodori/study/tree/main/java-algorithm/algorithm01/sort-algorithm/src/main/java/sorting 정렬 알고리즘(Sorting algorithm) 컴퓨터 과학에서 정렬 알고리즘이란 원소를 어떤 기준으로 정렬하는 것을 말한다. 기준은 알파벳, 날짜, 숫자 등 무엇이든 될 수 있다. 탐색이나 병합 알고리즘 같은 경우 정렬된 리스트여야만 바르게 동작한다. 정렬 알고리즘은 다른 알고리즘의 전제 조건이 되므로 반드시 알아두어야 한다. 거품 정렬(Bubble Sort) 거품 정렬은 가까운 두 원소를 비교하여 정렬하는 알고리즘이다. 원소가 자리를 찾아가며 이동하는 모습이 거품이 수면으로 올라오는 듯한 모습을..

모의고사 문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution ..

programmers.co.kr/learn/courses/30/lessons/68644 코딩테스트 연습 - 두 개 뽑아서 더하기 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한� programmers.co.kr 직접 푼 코드 import java.util.*; class Solution { /** * 정수 배열 numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑은 다음, * 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return한다. * * Logic * 배열의 0번 인덱스부터 마지막 인덱스까지 반복하면서 * ..

선택정렬 SelectionSort 전체 코드 package com.algorithm; import java.util.Arrays; public class SelectionSort { /** * 배열 array와 array의 두 인덱스(i, j)를 매개변수로 받아서 * i번 인덱스와 j번 인덱스에 저장된 요소를 바꾸는 메소드 */ public static void swapElements(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } /** * 배열 array와 start값을 매개변수로 받는다. * array[]의 start번째 인덱스부터 시작하여 마지막 인덱스까지 반복하면서 * 가장 작은 값이..

? 상수시간constant time 실행 시간이 입력 크기에 의존하지 않으면 알고리즘은 상수 시간constant time을 따른다고 한다. 이를테면, n개의 배열에서 브래킷 연산([])을 사용하여 요소 중 하나에 접근할 때 이 연산은 배열의 크기와 관계 없이 같은 수의 동작을 한다. ? 선형linear 실행 시간이 입력 크기에 비례하면 알고리즘은 선형linear이라고 한다. 배열에 있는 요소를 더한다면 n개 요소에 접근하여 n-1번 더하기 연산을 해야 한다. 연산 요소(요소 접근과 더하기)의 총 횟수는 2n-1이고 n에 비례한다. ? 이차quadratic 실행시간이 n^2에 빌례하면 알고리즘은 이차quadratic라고 한다. 말하자면 리스트에 있는 어떤 요소가 두 번 이상 나타나는지를 알고 싶다고 하자...