Pragmatic Romantist

Recursion(재귀) 자기 자신을 호출하는 함수 문제를 더 작은 문제로 나누어 코드를 간결하게 만들어줌 Breaking Condition이 반드시 있어야 함 (중요) Recursion은 호출 될 때 마다 메소드의 복사본이 메모리에 만들어 진다. 그리고 메소드가 종료될 때 메소드의 복사본들은 삭제됨 Sorting, Search 등의 문제들이 Recursion으로 간단하게 해결 될 수 있음 상황에 따라 Iteration이 좋을지 Recursion이 좋을지 잘 판단하여야함 Recursion의 간단한 예시 public class countDown { public static void main(String[] args) { countDown(3); //출력 결과 : 3 2 1 } public static vo..

Stack 한 쪽에서만 자료를 넣고 빼는 LIFO(Last in First Out) 자료구조 Array 와 달리 i번째 자료에 O(1)(상수시간)으로 접근 할 수 없음 하지만 데이터 추가와 삭제는 O(1)(상수시간)으로 수행 할 수 있음 Array 처럼 원소들을 하나씩 shift해줄 필요없음 스택을 활용하는 것이 좋은 구현인 경우 재귀(Recursion) 알고리즘 웹 브라우저의 방문 기록 (뒤로가기) 실행 취소(undo) 역순 문자열 후위 표기법(연산자가 문자뒤에 오는 표기법) 계산 수식의 괄호 검사 Stack의 Operation (ADT) public interface ADT_Stack { public boolean push (T newEntry); //새로운 요소 넣음 public T pop (); ..

Time Complexity (시간 복잡도) Time Complexity(시간 복잡도)란 알고리즘의 효율성을 판단하기 위한 지표로서, 프로그램이 수행되는데 걸리는 절대적인 시간이 아닌 알고리즘이 수행되는데 사용되는 연산들이 몇 번 이루어지는지 나타낸 상대적 지표이 cf) 알고리즘을 평가하는 지표는 시간 효율성을 나타내는 시간 복잡도와 메모리 효율성을 나타내는 공간 복잡도가 있다. 시간 복잡도 자체가 자료구조는 아니지만 제가 공부한 자료구조 책에서 시간 복잡도를 다루고 있었습니다. 자료구조를 선택할 때 시간 복잡도가 중요한 고려사항이 되기때문에 책에서 다룬 것 같습니다. Big-O Notation 시간복잡도와 공간복잡도를 표현하는 표기법 중 가장 많이 사용되는 표기법 cf) 시간복잡도를 표현하는 표기법에는..

ArrayList 가장 기본적인 자료구조이며, 논리적 저장 순서와 물리적 저장 순서가 동일한 자료구조 따라서 index로 해당 element에 빠르게 접근이 가능 장점 찾고자하는 대상의 index를 알고있으면 O(1)의 매우 빠른 속도로 접근이 가능 단점 List의 Capacity를 늘릴경우 더 큰 Capacity의 새로운 List에 기존 element들을 모두 복사해야 함 java에서는 가변길이의 ArrayList가 이미 구현이 되어있지만, ArrayList를 직접 구현을 할 경우 가변 길이는 상황에 맞는 적절한 방법을 사용하여야함 ex) Default capacity와 number of entries가 같아 질 경우 Default capacity의 2배의 길이로 capacity를 늘림 삭제 또는 삽입..

ADT(추상 자료형)이란? 구현 방법은 명시하지 않고 기능(Operation)만을 나열한 자료구조의 형태 자판기의 경우 외부에서 보았을 때 자판기 안에서 어떠한 원리로 기능이 작동하는지는 알 수 없지만 버튼을 누름으로써 음료수를 뽑아 먹을 수 있음 이 때 버튼을 누르는 것이 Operation을 통해 외부에서 ADT내의 자료에 접근하는 것이라고 할 수 있음 따라서 ADT의 Operation을 알면 실제 구현이 어떻게 되어있는지 몰라도 사용이 가능함 -> What (o), How(x) -> Java의 Interface도 ADT라고 할 수 있음 Bag를 ADT로 표현한 예시 public interface BagInterface { public int getCurrentSize (); //가방 안에 들어있는 품..