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

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. CS 공부 ( ~계속) 최근 면접 및 면접준비간 기초적인 이론에 대한 심화적인 답변이 불가능한 수준 개발자에게 중요한 CS 이론으로 JAVA, Spring, DB, SPA 등 기본적인 동작 원리와 개발이론(애자일, TDD 등), 디자인 패턴 및 알고리즘 작성, 계산법에 대한 이론공부가 필요하다고 생각함. 2. 코딩테스트 준비 ( ~계속) 최근 IT기업 채용간 코딩테스트는 필수 절차가 되고있음. 동작이 되는 코드가 아닌 효율성 관점에서 접근하여 알고리즘 공부 및 코딩테스트 풀어보기 풀이방법에 대해 스스로 고민해볼 것, 작성완료 이후 다른 사람들의 코드와 비교해볼 것. + 자료구조와 알고리즘 공부내용 정리 필수 자료구조: 스택, 큐, 리스트, 트리, 맵 등 알고리즘: 정렬, 탐욕법, 탐색(깊이우선탐색(..

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

Spring Bean의 Scope 스프링에서는 Bean으로 지정된 객체는 기본적으로 싱글톤 객체로 관리하게 됩니다. 하지만 요구사항에 따라 싱글톤이 아닌 방법으로 빈을 구성해야 하는 경우가 있는데, 이와 같은 경우를 명시적으로 구분하기 위해 스프링에서는 scope라는 키워드를 사용합니다. Scope 종류 1. Singleton 하나의 Spring 컨테이너에는 하나의 Bean 객체만 존재할 수 있다. 장점 : 고정된 메모리 영역을 사용하므로 메모리 절약, 데이터 공유 용이, 데이터 무결성, 접근성 확보 단점 : 너무 많은 일을 하거나 많은 데이터를 공유시킬 경우 다른 클래스의 인스턴스들 간에 결합도가 높아져 "개방-폐쇄 원칙" 을 위배하게 된다. 2. Prototype Bean 호출 시 마다 새로운 인스턴..