본문 바로가기

Java

자료구조 스터디 week 6 - 재귀 재귀함수 내부에서 자기 자신을 호출하는 함수, Recursion등차수열, 팩토리얼, 피보나치 수열 등 많은 알고리즘을 재귀적으로 표현할 수 있다// 등차수열public int seq(int n) { if (n == 1) return 1; else return seq(n - 1) + 3;}// 피보나치public int fib(int n) { if (n == 1 || n == 2) return 1; else return fib(n-1) + fib(n-2);}  하노이의 탑하노이의 탑도 재귀적으로 구현할 수 있다a, b, c 3개의 기둥이 있고, 이 3개의 원반을 기둥 b로 옮겨야 하는 작업을 재귀적으로 구현 하노이의 탑을 재귀적으로 표.. 더보기
자료구조 스터디 week5 - 큐 큐(Queue)입장을 위해 줄 서는 모습, 대기열과 같이 먼저 들어온 데이터가 먼저 나가는 방식으로 실행되는 자료구조따라서 선입선출(FIFO)의 특징을 가진다.- 후입선출(LIFO) 특징을 가지는 스택과는 대비되는 개념이다. 배열 자료형을 이용하며, 변수 front와 tail을 통해 큐에 있는 자료를 추가 혹은 삭제할 수 있다.물론 큐의 최대 크기를 예상할 수 있는 경우에는 배열이 가장 효율적이지만, 작업 과정에서 배열의 크기를 예상할 수 없는 경우 배열의 크기를 재할당 받아야하는 단점이 존재한다. 배열을 이용한 큐 구현ADT 큐에는 4개의 필드 queue[], numItems, front, tail이 있고, 5개의 함수가 있다.예) enque(x), dequeue(), front(), isEmpty().. 더보기
자료구조 스터디 week4 - 스택 스택스택이란 맨 위의 원소만 접근 가능한 자료구조를 말한다.맨 위의 원소를 스택탑이라고 하며, 새로운 원소를 저장할 때는 스택 탑 바로 위에 원소를 저장하고, 원소를 삭제할 때는 무조건 탑에 있는 원소를 삭제한다. 스택의 삽입과 삭제의 예시는 다음과 같다. 스택에서 삽입할 때는 아래부터 쌓고 삭제할 때는 맨 위의 원소를 삭제하게 된다. 메모리 구조에서의 스택  프로그램은 위와 같은 가상 메모리에서 수행된다는 가정하에 컴파일러가 컴파일 하고 물리적인 메모리에는 수행시점에 대응된다.(프로그램이 독립적으로 물리 메모리 크기에 구애받지 않고 실행된다는 뜻) 정적 영역에는 컴파일 직후 상대의 위치를 정할 수 있는 모든 정보(수행 코드, 데이터)가 있고, 동적 영역에는 프로그램 수행 중 할당 받는 메모리(힙)와 다.. 더보기
자료구조 스터디 Week3 - 리스트 리스트는 '줄 세워져 있는 데이터' 또는 '죽 늘어선 데이터'를 의미한다.리스트를 관리하기 위해 데이터를 추가 혹은 삭제가 가능하며, 값을 가져올 수도 있다. 리스트는 ADT 리스트로, 구현 방법은 명시하지 않고, 추상화를 통해 자료구조가 제공하는 기능들에 대해서만 명시하는 것을 말한다. 추상 데이터 타입에서 정의되는 핵심 기능은 크게 6가지로 볼 수 있다. - add, append, remove, removeItem, get, setadd() - 특정 인덱스에 데이터 추가 ex) add(3, 250)append() - 리스트 끝에 데이터 추가remove() - 특정 인덱스의 요소를 제거removeItem() - 특정 값의 요소를 제거get() - 특정 인덱스 요소를 반환set() - 특정 인덱스 요소 .. 더보기
자료구조 스터디 Week2 클래스클래스는 '객체'를 만드는 수단이며, 어떤 대상을 추상화하는 의미 단위이다.프로그램은 하나 이상의 클래스를 포함하게 된다. (클래스의 구조)클래스Heap 클래스 내부// 필드private int[] A;private int numItems;// 생성자public Heap(int n) {  A = new int[n];  numItems = 0;}// 메소드public boolean isEmpty() {  return numItems == 0;}public void insert(int newItems) {  ..}private void percolateUp(int i) {  ..}public int delete() {  ..}public static void main(String[] args) {  ... 더보기
알고리즘 수행 시간 / 시간 복잡도 알고리즘은 '자원을 얼마나 효율적으로 사용하는가'로 판단한다. 여기에서 '효율적'이라는 말은 저장공간, 네트워크 등이 될 수 있지만, 대부분은 시간이 얼마나 걸리는지로 판단을 한다. 알고리즘 수행시간이 짧을 수록 프로그램 전체 성능은 향상되고, 일반적으로 시스템 자원을 덜 사용하게 되어 비용절감의 효과도 얻을 수 있다. 직관적이고 효율적인 프로그래밍을 하는 것이 알고리즘을 배우는 핵심이다. 점근적 표기알고리즘은 일반적으로 점근적 표기를 따른다.점근적 복잡도란 입력의 크기가 충분히 클 때의 복잡도이다. lim n→∞​T(n)=2n^2 라는 시간 복잡도가 주어질 때, 점근적 복잡도에서는 n^2라고 표현한다. n이 충분히 클 경우에는 앞의 상수가 주는 영향은 미미하기 때문이다. (T(n)은 알고리즘 수행시간 .. 더보기
객체지향 프로그래밍과 4가지 특징 프로그래밍을 하다 보면 객체, 객체지향이라는 말을 종종 듣게 된다. 이는 프로그래밍 패러다임 중 하나이며, 용어를 그대로 풀어서 쓴다면 객체를 지향하는 프로그래밍을 하라는 뜻이다. 여기서 말하는 객체란 과연 무엇인가? 용어 자체로 이해하는데에는 한계가 있기 때문에 예시를 통해 이해해보도록 하자.  객체란 하나의 단위를 뜻한다. 우리가 흔히 주변에서 볼 수 있는 사물로는 자동차가 있다. 자동차는 각각의 개체로 이루어진 프로그래밍 집합체이다. 자동차에서 핸들, 바퀴, 엔진, 기어 등은 각각의 기능을 가진다.핸들은 움직이는 방향을 조정하는 기능, 바퀴는 굴러갈 수 있도록 하는 기능. 이와 같은 부품들을 각각 객체라고 부르며 기능들이 모인 집합체가 바로 자동차이다. 프로그래밍도 마찬가지이다.(간단한 예시)   .. 더보기

티스토리툴바