매 선택에서 가장 최적인 답을 선택하여 적합한 결과를 도출하자는 모토를 가지는 알고리즘 설계 기법 근시안적으로 해를 구할 당시에 가장 최적인 해를 구함 그리디 알고리즘은 동적 계획법(Dynamic Programming) 보다 효율적이지만 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장은 없음 예제 모음 ▼ 더보기 https://somewheretogo.tistory.com/93 [백준 알고리즘] 11047번 동전 0 (Python) N, K = map(int, input().split()) a = [] for i in range(N): a.append(int(input())) cnt = 0 for i in reversed(a): if K == 0: break if (K // i) >= 1: cnt +..
리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조 특징 - FIFO(First In First Out, 선입선출): 가장 먼저 삽입된 자료가 가장 먼저 삭제된다. - 시작과 끝을 표시하는 2개의 포인터가 있다. (front, rear) - Front: 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터로, 삭제 작업을 할 때 사용 - Rear: 가장 마지막에 삽입된 자료가 위치한 기억공간을 가리키는 포인터로, 삽입 작업시 사용 큐의 연산 - enQueue(item): 큐안에 데이터를 추가한다. - deQueue(): 큐 안의 데이터를 제거한다. - peek(): 큐의 front데이터를 반환한다. - isEmpty(): 스택이 비어있으면 true를 반환..
리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조 특징 - LIFO(Last In First Out, 후입선출) : 가장 나중에 삽입된 자료가 가장 먼저 삭제된다. - 스택의 모든 기억공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로우가 발생하며, 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로우가 발생한다. - Top: 스택으로 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소 - Bottom: 스택의 가장 밑바닥 스택의 연산 - push(item): 스택의 맨 윗부분에 원소를 추가한다. - pop(): 스택의 맨 윗부분의 원소를 제거한다. - peek(): 스택의 맨 윗부분의 원소를 반환한다. - isEmpty(): 스택이 비..
퀵정렬 간단정리 1. 불안정 정렬에 속하며, 다른 원소와의 비교로 정렬을 수행하는 비교정렬이다. 2. 분할정복 알고리즘의 하나이다. 3. 최선의 경우 O(nlogn)의 시간복잡도를 보이지만, 최악의 경우 O(n^2)의 시간 복잡도를 보인다. 4. 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는다는 장점이 있다. 5. 정렬된 리스트에 대해서는 퀵정렬의 불균형 분할에 의해 수행시간이 오래 걸린다. 과정 1. 리스트 안의 요소를 선택하고 이를 피벗(pivot)이라 한다. 2. 리스트를 순회하면서 피벗을 기준으로 피벗보다 작으면 피벗의 왼쪽에, 피벗보다 크다면 피벗의 오른쪽으로 옮긴다. 3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. (재귀) 4. 부분 리스트의 크기가 1이하가 되면 종료한..
버블정렬은 인접한 두 원소를 비교하여 정렬하는 알고리즘이다. 예전에 수업들을때 교수님께서 원소를 버블버블 하나씩 올리는거라 버블정렬이라고.. public class al_02_bubblesort { public static void main(String[] args){ int[] a = {5, 9, 2, 4, 15, 6, 1, 20, 3, 10, 14, 0}; for( int j=0; j a[i + 1]){ //인접한 원소가 오름차순이 아닌경우 swap int temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; } } } System.out.println(Arrays.toString(a)); } } a = [5, 9, 2, 4, 15, 6, 1, 20, 3, 10, 14, 0] ..
가장 작은 요소를 골라 맨 앞으로 보내자! 🦋 핵심 장점: 데이터 양이 적을 때 성능이 좋음 작은 값을 선택하기 위해서 비교는 여러번 수행되지만 교환횟수가 적음 단점: 100개 이상의 자료에 대해서는 속도가 급격히 떨어짐 시간복잡도: 0(n^2) 과정 (오름차순으로 정렬한다고 가정) 1. 주어진 리스트에서 최솟값을 찾음 2. 최솟값을 맨 처음 위치한 값과 swap 3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 반복함 그림으로 쉽게 이해하기 public class A01_selection_sort { public static void main(String[] args) { int[] a = {5,9,2,4,15,6,1,20,3,10,14,0}; //임의로 넣음! //루프를 돌면서 최솟값을 찾고 기..