고오급 개발자가 되는길

재귀 용법 (Recursive call, 재귀 호출) • 함수 안에서 동일한 함수를 호출하는 형태 팩토리얼 예제 public class Factorial{ public int factorialFunc(int n){ if(n > 1){ return n * this.factorialFunc }else{ return 1; } } } 시간/공간 복잡도 O(N) 동적 계획법과 분할 정복 • 동적 계획법 (Dynamic Programming, DP) - 입력 크기가 작은 부분 문제들을 해결한 뒤, 해당 부분의 해(풀이)를 활용해서 보다 큰 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 - 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용하여 쉬운 문제를 해결하는 방식 - Memoizat..

기본 정렬 알고리즘 공간 복잡도(Space Complexity) - 프로그램을 실행 및 완료한느데 필요한 저장공간의 양 - 총 필요 저장 공간 • 고정 공간 : 코드 저장 공간, 단순 변수 및 상수 EX) 코드의 양,줄 • 가변 공간 : 실행 중 동적으로 필요한 공간 EX) for문을 통한 반복 횟수 버블 정렬 (Bubble Sort) - 인접한 두 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘 import java.util.ArrayList; import java.util.Collections; public class BubbleSort { public ArrayList sort(ArrayList dataList) { // 입력한 dataList의 siz..

데이터 구조 : 힙(Heap) 1. 힙(Heap) 이란? - 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 • 완전 이진 트리 (Complete Binary Tree) - 노드를 삽입할 떄 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 2. 힙을 사용하는 이유 - 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸린다. => 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸린다. - 최대값 또는 최소값을 빠르게 찾아야하는 자료구조 및 알고리즘 구현 등에 활용 • 힙과 이진트리의 공통점 - 모두 이진 트리 이다 • 차이점 - 힙은 데이터 삽입 시 무조건 왼쪽에서 부터 데이터를 넣어, 왼쪽 및 오른쪽 자식의 노드 값은 어느것이 큰지 모른다. - 이진 탐색 트..

트리(Tree) 구조 • 트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 - 이진 트리(Binary Turee) 탐색 알고리즘 구현을 위해 많이 사용됨 용어 • Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) • Root Node : 트리 맨 위에 있는 노드 • Level : 최상위 노드를 Level 0으로 하였을 떄, 하위 Branch로 연결된 노드의 깊이를 나타냄 • Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 • Child Node : 어떤 노드의 상위 레벨에 연결된 노드 • Leaf Node : Child Node가 하나도 없는 노드 • Silbing : 동일한 Parent No..

해쉬 테이블 (Has Table) 1. 해쉬 테이블 • 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조 • 해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산 • Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라짐 • 미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당, 키에 따른 데이터 저장 및 탐색 지원 2. 용어 • 해쉬 함수(Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수 • 해쉬, 해쉬 값 , 또는 해쉬 주소 : 해쉬 함수를 통해 리턴된 고정된 길이의 값 • 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접..

알고리즘 복잡도 표현 방법 1. 알고리즘 복잡도 계산이 필요한 이유 - 다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산 2. 계산항목 1. 시간 복잡도 : 알고리즘 실행 속도 * 2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문이다. 알고리즘 성능 표기법 • Big O (빅-오) 표기법 : 0(N) - 알고리즘 최악의 실행 시간을 표기 - 가장 많이 / 일반적으로 사용 - 최악의 실행 시간을 표기하는 이유는 최악의 상황에도 이정도 성능은 보장한다는 의미 • Ω (오메가) 표기법 : Ω(N) - 알고리즘 최상 실행시간 표기 • Θ (세타) 표기법 : Θ(N) - 알고리즘 평균 실행시간 표기 3. ..

더블 링크드 리스트 (Doubly linked list) - 이중 연결 리스트라고도함 - 양방향으로 연결되어 있어서 노트 탐색이 양쪽으로 모두 가능 public class DoubleLinkedList{ public Node head = null; // 앞 참조 public Node tail = null; // 뒤 참조 public class Node{ T data; Node prev = null; Node next = null; } public Node(T data){ this.data = data; } public void addNode(T data){ if(this.head == null){ this.head = new Node(data); this.tail = this.head; }else{ No..

스택 (Stack) • 데이터를 제한적으로 접근할 수 있는 구조 - 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 - 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 - LIFO(Last-In, First-Out) 정책, 큐와 반대 • 주요기능 - push() : 데이터를 스택에 넣기 - pop() : 데이터를 스택에서 꺼내기 • 사용법 Stack stack = new Stack(); stack.push(값) stack.pop(값) 링크드 리스트(Linked List, 연결 리스트) - 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 - 데이터와 다음데이터의 주소를 저장하는 공간을 같이 저장 - 중간에 있는 데이터를 삭제해도 포인터 (데이터주소)를 이용하여 찾아갈 수..

자료구조 1. 구조 배열 (Array) // new 키워드를 사용해서, 배열을 미리 선언하고, 데이터를 넣을 수도 있다 Integer[] data_list = new Integer [10] data_list[0] = 1 // 직접 배열 데이터 선언 시 넣을 수도 있다. Integer data_list1[] = {5,4,3,2,1} Integer[] data_list 2 = {1,2,3,4,5} datalist_1[0] // 5 datalist_2[0] // 1 // 배열 내용 출력 Arrays.toString(배열) • List 와 ArrayList List는 인터페이스고, ArrayList 는 클래스이다 List list1 = new ArrayList // 인터페이스로 선언한 list1의 구현 클래스는..

이번에 패스트캠퍼스에서 진행하는 100% 환급 챌린지를 통하여 언젠가는 해야지 하는 자료구조와 알고리즘에 대한 강의를 신청하게 되었다. 나는 약간 이렇게 환급이라는 강압적인 단어가 있을 때야 비로소 더 집중적으로 하는 것을 알기에 이 기회에 환급도 받고 계속 미루어 왔던 자료구조와 알고리즘에 대해 집중적으로 공부할 수 있는 계기가 되어 이 기회를 놓치지 않고 신청하였다 강의 이름은 한 번에 끝내는 코딩 테스트 369 Java 편 초격자 패키지 Online이라는 강의이며 자료구조 및 알고리즘을 오랜만에 보면서 기본부터 어려운 내용까지 한 번에 다루는 강의여서 신청하게 되었다. 1일 차에서는 우선 이 강의가 어떤 식으로 진행되는지에 대한 커리큘럼과 자료구조 및 알고리즘을 실행할 수 있는 환경 세팅을 설정하였..