시간 복잡도 필요로 하는 시간을 따지는 것 : 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가? BIig-O 표기법 시간 복잡도를 표기하는 방법은 3가지가 있다 Big-O (빅-오) - 최악 : "최대 이 정도까지 시간이 걸린다" Big-Ω (빅-오메가) - 최선 : "최소한 특정 시간 이상이 걸린다" Big-θ (빅-세타) - 평균 : "보통 이 정도 시간이 걸린다" 이 중 Big-O 표기법이 가장 자주 사용된다 다른 방법처럼 최악의 경우가 일어나지 않기를 바라는 것보다는 최악의 경우도 고려하여 대비하는 것이 바람직하다 O(1) 입력값의 크기와 관계없이 같은 시간이 걸린다 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다 pub..
Deque (Double Ended Queue, 양방향 대기열) Deque는 Stack과 Queue의 특성들이 혼합된 느낌이다 Stack : 데이터가 한 방향으로 추가되고 삭제할 수 있음 Queue : 데이터가 한방향으로 추가되고 다른 방향으로 데이터가 삭제됨 자료구조 스택 Stack Stack 데이터를 순서대로 쌓는 자료구조 가장 먼저 들어간 데이터가 가장 나중에 나올 수 있다 그림과 같이 길이 막혀 더 이상 진행할 수 없는 경우 분홍색 자동차가 가장 먼저 들어왔지만 뒤 차 e-room.tistory.com 자료구조 큐 Queue 큐는 줄을 서서 기다리다, 대기행렬이라는 뜻이 있다 가장 먼저 들어온 데이터가 먼저 나갈 수 있다 고속도로 톨게이트는 가장 먼저 도착한 자동차가 먼저 통과할 수 있다 분홍색 ..
여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조 복잡한 네트워크망과 같은 모습 Graph의 구조 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다 하나의 점을 그래프에서는 정점(vertex)이고, 하나의 선은 간선(edge)이라고 한다 용어 정리 정점 (vertex) : 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소 간선 (edge) : 정점 간의 관례를 나타낸다 인접 정점 (adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점 가중치 그래프 (weighted graph) : 연결의 강도가 얼마나 되는지 적혀있는 그래프 비 가중치 그래프 (unweighted graph) : 연결의..
나무의 형태를 가지고 있다 하나의 뿌리로부터 가지가 사방으로 뻗은 형태이다 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다 데이터를 순차적으로 나열시킨 선형 구조가 아닌, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다 노드(Node) : 트리 구조를 이루는 모든 개별 데이터 루트(Root) : 트리 구조의 시작점이 되는 노드 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드 Tree의 구조 깊이 (depth) 루..
큐는 줄을 서서 기다리다, 대기행렬이라는 뜻이 있다 가장 먼저 들어온 데이터가 먼저 나갈 수 있다 고속도로 톨게이트는 가장 먼저 도착한 자동차가 먼저 통과할 수 있다 분홍색 자동차가 가장 먼저 도착했기 때문에 가장 먼저 통과하며 파란색 자동차는 앞의 자동차들이 모두 빠져나갈 때까지 기다려야 한다 큐도 마찬가지로 가장 먼저 입력된 데이터가 첫 번째로 출력된다 (가장 나중에 입력된 데이터는 마지막에 출력된다) Queue의 특징 FIFO (First In First Out) 먼저 들어간 데이터가 처음에 나오는 선입선출의 구조를 가지고 있다 데이터는 하나씩 넣고 뺄 수 있다 두 개의 입출력 방향을 가지고 있다 (데이터의 입력, 출력 방향이 다르다)
Stack 데이터를 순서대로 쌓는 자료구조 가장 먼저 들어간 데이터가 가장 나중에 나올 수 있다 그림과 같이 길이 막혀 더 이상 진행할 수 없는 경우 분홍색 자동차가 가장 먼저 들어왔지만 뒤 차가 모두 빠져야만 나갈 수 있다 가장 먼저 들어간 자동차는 가장 나중에 나올 수 있다(= 가장 나중에 들어간 자동차가 가장 먼저 나올 수 있다) Stack의 특징 LIFO (Last In First Out) 먼저 들어간 데이터는 나중에 나오는 후입 선출의 구조를 가지고 있다 데이터는 하나씩 넣고 뺄 수 있다 하나의 입출력 방향을 가지고 있다 (제한적 접근)
재귀 함수란 자기 자신을 호출하는 함수이다 public void recursion(){ System.out.println("This is recursion!"); recursion(); } // 출력 This is recursion! This is recursion! This is recursion! This is recursion! This is recursion! This is recursion! ... 재귀 함수가 적합한 상황 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우 변수 사용을 줄여 변경 가능한 상태를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우 장점 불필요하게 여러 개의 반복문을 사용하지 ..
Write Once, Run Anywhere JVM (Java Virtual Machine) 운영체제로부터 독립적으로 동작할 수 있게 해주는 이유 자바로 작성한 소스 코드를 각 운영체제에 맞게 해석해서 실행하는 별도의 프로그램 (일종의 통역가 역할) 각 운영체제에 적합한 버전이 존재함 JVM 메모리 구조 JVM에 Java 프로그램이 로드되어 실행될 때 특정 값 및 바이트코드, 객체, 변수 등과 같은 데이터들이 런타임 데이터 영역에 저장된다 런타임 데이터 영역은 크게 5가지로 구분되어 있다 Runtime Data Area Stack Area Heap Area Method Area PC Register Native Method Stack Garbage Collection 메모리를 자동으로 관리하는 프로세스 ..
start() : 스래드를 실행 대기 상태로 만든다 sleep(long milliSecond) : milliSecond 동안 스레드를 잠시 멈춘다 interrupt() : 일시 중지 상태인 스레드를 실행 대기 상태로 복귀시킨다 yield() : 다른 스레드에게 실행을 양보한다 join() : 특정 스레드가 작업하는 동안에 자신을 일시 중지 상태로 만든다 notify(), wait() : 스레드 간 협업에 사용
