쌓고 쌓다

1번 문제 코드 import java.util.Scanner; class MyPoint { int x; int y; MyPoint(int x, int y) { this.x=x; this.y=y; } public String toString() { return "Point("+x+","+y+")"; } boolean equals(MyPoint mp) { if(this.x==mp.x&&this.y==mp.y) return true; return false; } } public class Extest{ public static void main(String[] args) { MyPoint p = new MyPoint(3,50); MyPoint q = new MyPoint(4,50); System.out.pri..

탐색 여러 개의 자료 중 원하는 자료를 찾는 것 탐색키 : 항목과 항목을 구별해주는 키(key) 배열, 연결 리스트, 트리 그래프 등 다양한 방법으로 탐색 자료구조로 씀 순차 탐색 (sequential search) 탐색 방법 중 가장 간단하고 직접적인 방법 정렬 안된 배열을 처음부터 마지막까지 검사 평균 비교 횟수 성공 시 : (n+1)/2번 비교 -> 한 번에 찾을 경우 1, 최악의 경우 n이니 나누기 2 실패 시 : n번 비교 시간 복잡도 : O(n) 예시 코드 int seq_search(int key, int low, int high) { for (int i = low; i right)); } return height; } int get_balance(AVLNode* node) { if (node..

이진트리로 메시지의 내용을 압축한다. 각 글자의 비트수를 최소로 해서 문자를 압축하는 것이다. 예로 e, t, n, i, s 5개의 문자로 이루어진 문자열이 있다고 가정해보자. 그럼 각 글자의 빈도수와 표현에 필요한 비트수를 구해본다. ( 한 글자를 표현할때 필요한 비트는 3비트라고 가정) 글자 빈도수 비트수 e 15 3x15=45 t 12 3x12=36 n 8 3x12=24 i 6 3x6=18 s 4 3x4=12 즉 e t s i s 로 각각 해당 문자의 빈도수만큼 표현한 문자열은 총 비트수가 135이다. 즉, 135 비트를 차지함 하지만 아래와 같이 허프만 코드를 이용해 압축을 한다면 글자 빈도수 비트코드 비트수 e 15 00 30 t 12 01 24 n 8 11 16 i 6 100 18 s 4 10..

소스 코드 import java.util.Scanner; public class Extest{ static String readString() { StringBuffer sb = new StringBuffer(); Scanner scanner = new Scanner(System.in); while(true) { String line = scanner.nextLine(); if(line.equals(";")) break; sb.append(line); } return sb.toString(); } public static void main(String[] args) { int cnt[]= new int[26]; String res = readString().toLowerCase(); for(int i=0..

배열의 문제점 고정된 크기 삽입, 삭제시 위치 조정이 까다로움 컬렉션 : 요소(Element)라고 불리는 가변 개수의 객체들의 저장소 객체들의 컨테이너라고도 불림 요소의 개수에 따라 크기 자동 조절 요소의 삽입, 삭제에 따른 요소의 위치 자동 이동 ( 객체의 개수, 자리이동 등 편리 ) 다양한 객체들의 삽입, 삭제, 검색 등 관리가 용이 (컬렉션 인터페이스와 클래스) 컬렉션의 특징 컬렉션은 제네릭(Generics) 기법으로 구현 제네릭 특정 타입만 다루지 않고, 여러 종류의 타입으로 변신할 수 있도록 클래스나 메소드를 일반화 시킴 클래스나 인터페이스 이름에 , , 등이 '타입 매개변수'이며 이것을 포함 E : Element (요소) T : Type V : Value K : Key 를 의미 벡터 Vecto..

Priority queue 우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다. 스택이나 큐(FIFO)를 우선순위 큐로 구현할 수 있다. 스택 -> 가장 최근에 들어온 데이터가 삭제 ( 시간이 우선순위 ) 큐 -> 가장 먼저 들어온 데이터가 삭제 ( 시간이 우선순위 ) 우선순위 큐 -> 가장 우선순위가 높은 데이터 최소 우선순위 큐 최대 우선순위 큐가 존재 우선순위 큐의 추상자료형 (Abstract Data Type) 객체 n개의 element형의 우선순위를 가진 요소 연산 create() : 우선순위 큐를 생성 init(q) : 우선순위 큐 q를 초기화 is_empty(q) : 우선순위 큐 q가 비어있는지를 검사 is_full(q) : 우선순위 큐 ..

해싱 대부분 탐색 방법은 키 값 비교로 탐색하고자 하는 항목에 접근하지만 해싱은 바로 접근한다. 즉, 키 값에 대한 산술적 연산으로 테이블의 주소를 계산하여 항목에 접근 key를 넣었더니 value가 나오는 것 해시 테이블(hash table) : 키 값의 연산으로 직접 접근이 가능한 구조로 키 값으로 value를 찾는 것이다. 해시 함수(hash function) 키를 input으로 넣었더니 value로 해시 주소(hash address)를 생성하는 함수이다. 이 해시 주소가 배열로 구현된 해시 테이블(hash talbe)의 인덱스이다. 헤시 테이블 ht M개의 버켓(bucket)으로 구성된 테이블 ht[0], ht[1], ... , ht[M-1]의 원소를 가짐. 하나의 버켓에 s개의 슬롯(slot) ..

설치 git clone https://github.com/namhyung/uftrace.git github의 저장소를 복사해 가져옵니다. sudo misc/install-deps.sh uftrace 폴더로 이동하여 위의 쉘을 실행시킵니다. ./configure make sudo make install 차례대로 입력하여 또 설치 uftrace의 명령어 record : runs a program and saves the trace data replay : shows program execution in the trace data report : shows performance statistics in the trace data live : does record and replay in a row (defau..