Java
-
[JAVA/Level1] x만큼 간격이 있는 n개의 숫자Algorithm/프로그래머스 2021. 6. 14. 21:47
문제 설명 함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. 다음 제한 조건을 보고, 조건을 만족하는 함수 solution을 완성해주세요. 제한 조건 x는 -10000000이상, 10000000이하인 정수입니다. n은 1000이하인 자연수입니다. 입출력 예 x n answer 2 5 [2,4,6,8,10] 4 3 [4,8,12] -4 2 [-4,-8] 풀이 long타입의 배열을 선언하고, 파라미터로 받은 n의 길이만큼 배열의 길이를 설정한다. 반복문을 이용해, 배열 answer의 길이만큼 answer[i]에 x의 배수를 n번까지 넣는다. 배열 answer를 리턴한다. 코드
-
[JAVA/자료구조] 퀵 정렬(Quick Sort)Language/Java 2021. 6. 13. 17:27
평균 수행 시간이 O(logN)인 알고리즘 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다. 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다. 퀵 정렬(Quick Sort) 퀵 정렬은 n개의 데이터를 정렬할 때 최악의 경우 O(n^2)번의 비교를 수행하고, 평균적으로 O(logN)번의 비교를 수행한다. 퀵 정렬은 찰스 앤터니 리처드호어가 개발한 정렬 알고리즘이다. 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있기 때문에 불안정 정렬에 속한다. 퀵 정렬(Quick Sort) 구현 퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬한..
-
[JAVA/자료구조] 힙 정렬(Heap Sort)Language/Java 2021. 6. 13. 00:09
평균 수행 시간이 O(logN)인 알고리즘 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다. 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다. 힙 정렬(Heap Sort) 최대 힙 트리나, 최소 힙 트리를 구성해 정렬을 하는 방법 내림차순 정렬을 위해서 최대 힙을 구성하고, 오름차순 정렬을 위해서 최소힙을 구성한다. 이진 트리를 최대 힙으로 만들기 위해 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어지므로 시간 복잡도는 O(log n)이 걸린다. 힙 정렬(Heap Sort) 구현 n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼..
-
[JAVA/자료구조] 선택 정렬(Selection Sort)Language/Java 2021. 6. 12. 23:11
평군 수행 시간 O(n^2) 알고리즘 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 선택 정렬(Selection Sort) 각 요소가 다른 요소와 평균 한번 이상 씩 비교를 하여 정렬된다. 선택 정렬(Selection Sort) 제자리 정렬 알고리즘 중 하나이다. 1. 주어진 리스트 중 최솟값을 찾는다. 2. 그 값을 맨 앞에 위치한 값과 교체한다. 3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 시간 복잡도는 O(n^2)으로 느리지만, 메모리가 제한적인 경우 성능상의 이점이 존재한다. 선택 정렬(Selection Sort) 구현 선택 정렬(Selection Sort) 구현 결과 반복 - 1 10 50 70 80 60 20 40 30 반복 - 2 10 20 7..
-
[JAVA/자료구조] 버블 정렬(Bubble Sort)Language/Java 2021. 6. 12. 22:22
평군 수행 시간 O(n^2) 알고리즘 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 선택 정렬(Selection Sort) 각 요소가 다른 요소와 평균 한번 이상 씩 비교를 하여 정렬된다. 버블 정렬(Bubble Sort) 두 인접한 원소를 검사하여 정렬하는 방법 시간 복잡도가 O(n^2)으로 느리지만, 코드가 단순하여 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기때문에 지어진 이름이다. 버블 정렬(Bubble Sort) 구현
-
[JAVA/자료구조] 삽입 정렬(Insertion Sort)Language/Java 2021. 6. 12. 00:22
평군 수행 시간 O(n^2) 알고리즘 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 선택 정렬(Selection Sort) 각 요소가 다른 요소와 평균 한번 이상 씩 비교를 하여 정렬된다. 삽입 정렬(Insertion Sort) 삽입 정렬: 이미 정렬된 상태의 요소에 새로운 요소를 추가할 때 정렬하여 추가하는 개념 => ex) 카드게임 두번째 요소부터 이전 요소들과 비교하며 insert될 위치를 찾아가며 정렬하는 알고리즘 삽입 정렬(Insertion Sort) 구현
-
[JAVA/Level1] 최솟값과 최댓값Algorithm/프로그래머스 2021. 6. 11. 23:01
문제 설명 여러 개의 수가 배열에 있을 때 그 중 가장 큰 값과 가장 작은 값을 찾는다. 배열의 몇 번째에 있는지 순서를 찾는다. 반복문을 한번만 사용하여 문제를 해결한다. 수의 예 : [10, 55, 23, 2, 79, 101, 16, 82, 30, 45] 풀이 1. 배열 내 인덱스 0에 위치한 값을 maxNumber변수와 minNumber변수에 저장한다. 2. 배열의 크기만큼 반복문을 이용하여 더 큰수나 작은 수가 나올 경우 maxNumber의 값과 minNumber의 값을 변경시켜준다. 3. 변경될 경우 해당 인덱스의 위치를 저장한다. 코드