지잉지잉 개발일기 지잉지잉 개발일기

그리디 알고리즘(Greedy Algorithm)이란? 탐욕 알고리즘, 욕심쟁이 알고리즘이라고 불림. 매 단계별 현재 최선의 답을 선택해 나가는 알고리즘 백트래킹을 통해 추가적인 검증을 하지 않음. 현재의 선택을 검증하지 않고 바로 다음단계로 이동. 속도가 매우 빠르지만 현재만의 최선의 답을 선택해 나가는 이유로 결과는 최선이 아닌 경우가 있다.

BFS(Breadth First Search, 너비 우선 탐색) 정점들과 같은 레벨에 있는 노드를 먼저 탐색함. 구현에 큐를 사용한다. Root Node로부터 가장 가까운 Node부터 탐색하므로 Root Node와 가까이 있는 Target Node를 찾는데 유용하다. 최단거리 탐색, SNS 친구추천 등에 사용되고 있음. 시간복잡도 O(N) DFS(Depth First Search, 깊이 우선 탐색) Root Node에 이어진 Child Node들 부터 먼저 탐색함. 구현에 스택을 사용한다. BFS보다 속도가 느릴 수 있다. 미로게임 등에서 경로가 존재하는지 여부를 판단할 때 유용하다. 시간복잡도 O(N) 탐색 방식 비교 BFS: A - B - C - D - G - H - I - E - F - J DFS:..

퀵정렬 (Quick Sort) 매우 빠른 수행속도를 자랑하는 정렬방법, 분할 정복 알고리즘에 해당 분할 정복(divide and conquer) 방법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 합쳐 원래의 문제를 해결하는 전략. 과정 배열 내에서 하나의 요소(피벗(pivot))를 선택한다. 피벗을 기준으로 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 분류한다. (Divide) 왼쪽, 오른쪽 배열도 피벗을 선택한 후 왼쪽/오른쪽 배열로 분류한다. (재귀) 배열의 크기가 0 혹은 1이 될 때까지 반복한다. (Conquer) 모든 정렬된 배열을 합친다. (Combine) 구현 public class Main { public static void quickSort(int[] arr..

삽입정렬 (Insertion Sort) i번째 데이터를 이전의 원소부터 0번째까지의 데이터들과 비교하여 자리를 교환하는 정렬방식. 예) [1, 3, 5, 2, 4] 배열에서 원소 "2"는 이전의 원소 "5"보다 작으므로 자리교환 -> [1, 3, 2, 5, 4], 그 이전의 원소 "3" 보다 작으므로 자리교환 -> [1, 2, 3, 5, 4] 구현 public static void main(String[] args) { int[] array = {2, 4, 1, 5, 3}; int length = array.length; for (int i = 1; i = 0 && target < arra..

선택정렬 (Selection Sort) 가장 작은 원소를 찾아 앞의 데이터와 자리 교환하는 정렬방식. 예) [2, 3, 1, 5, 4] 배열에서 원소 "1"은 가장 작은 원소이므로 원소 "2"와 자리교환 -> [1, 3, 2, 5, 4] 구현 public static void main(String[] args) { int[] array = {2, 4, 3, 5, 1}; int length = array.length; for (int i = 0; i array[j]) minIndex = j; } int temp = array[i]..

버블정렬 (Bubble Sort) 인접한 두개의 원소를 비교, 자리를 교환하는 정렬방식. 구현 public class Main { public static void main(String[] args) { int[] array = {2, 4, 3, 5, 1}; int length = array.length; for (int i = 0; i array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } }​ 배열의 길이만큼의 for문을 2번돌리기에 시간복잡도는 O(N^2)

1. 시간복잡도란? 문제를 해결하는데 걸리는 시간과 입력한 함수 관계로, "연산의 횟수(시행 횟수)"를 센다. 컴퓨터는 코드를 수행하는데 있어서, 유한한 메모리 자원과 시간을 사용한다. 이 때, 메모리를 사용하는 데 평가기준인 공간복잡도(Space Complexity)와 시간을 사용하는 데 평가기준인 시간복잡도(Time Complexity)를 알고리즘 평가 척도로 사용하기도 한다. 2. 중요성 요즘의 컴퓨터는 메모리의 성능향상으로 인해 시간복잡도를 더욱 중요시 판단한다고 한다. 물론 메모리의 낭비를 계산하는 공간복잡도도 중요한 판단 척도이다. 3. 알고리즘의 성능평가 1. 최선의 경우 (Best Case, Big-Ω(오메가 표기법, Ω(n)) - 최적의 입력을 한 상태에서 작업을 완료하는데 가장 빠른 시..

SOLID 란? 객체지향 프로그래밍에서 지향하는 개발 원칙 5가지. Single Responsibility Principle (SRP, 단일 책임 원칙) Open/Closed Principle (OCP, 개방/폐쇄 원칙) Liskov Substitution Principle (LSP, 리스코프 치환 원칙) Interface Segregation Principle (ISP, 인터페이스 분리 원칙) Dependency Inversion Principle (DIP, 의존관계 역전 원칙) 1. Single Responsibility Principle (SRP, 단일 책임 원칙) 소프트웨어의 설계 부품(클래스, 함수 등)은 단 하나의 책임만을 가져야 한다. 책임이 많아지면 클래스 내부의 함수끼리 강한 결합을 발생..