키리Kirri's IT노트

: 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조. 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO; First In First Out)인 점이 스택과 다르다. *인큐(enqueue): 큐에 데이터를 넣는 작업 *디큐(dequeue): 데이터를 꺼내는 작업 ・배열로 큐 만들기 -인큐: 리어(rear)에 새로운 데이터를 저장. O(1)의 복잡도로 적은 비용으로 구현 가능 -디큐: front에서 데이터를 꺼낸 다음 두 번째 이후의 요소를 모두 맨 앞으로 이동. O(n)의 복잡도, 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어짐 ・링 버퍼(ring buffer)로 큐 만들기 : 배여래의 처음과 끝이 연결되어있는 자료구조로, 배열 요소를 앞쪽으로 옯기지 않는다. 논리적으로..

: 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. (LIFO, Last Input First Out) *푸시(push): 스택에 데이터를 넣는 작업 *팝(pop): 스택에서 데이터를 꺼내는 작업 ・스택 만들기 1. 생성자 IntStack : 스택 본체용 배열을 생성하는 등 준비 작업 수행 1 2 3 4 5 6 7 8 9 public IntStack(int capacity) { ptr = 0; max = capacity; try { stk = new int[max]; } catch(OutOfMemoryError e) { max = 0; } } 2. 푸시 메서드 push : 데이터를 푸시하는 메서드 1 2 3 4 5 public int push(int x) th..

: 데이터가 키 값으로 이미 정렬(sort)되어 있을 때, 선형 검색보다 빠르게 검색 가능 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 ・이진 검색 알고리즘의 종료 조건 ① a[pc]와 key가 일치하는 경우(검색 성공): 대략 ⌈log(n-1)⌉회 비교 ② 검색 범위가 더 이상 없는 경우(검색 실패): ⌈log(n+1)⌉회 비교 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 static int binSearch(int[] a, int n, int key) { int pl = 0; int pr = n - 1; do { int pc = (pl + pr) / 2; // 중앙 요소의 인덱스 if(a[pc] == key) return pc; else if(a[..

: 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘. 배열에서 순서대로 검색하는 유일한 방법이기도 하다. 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)라는 알고리즘이다. ・검색의 종료 조건 ① 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우(검색 실패) ② 검색할 값과 같은 요소를 발견한 경우(검색 성공) -while문 사용 1 2 3 4 5 6 7 8 9 10 11 12 static int seqSearch(int[] a, int n, int key) { int i = 0; while(true) { if(i == ..

: 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘 키: 검색을 수행할 때 주목하게 되는 특정 항목 1. 국적이 한국인 사람을 찾는다. 2. 나이가 21세 이상 27세 미만인 사람을 찾는다. 3. 찾으려는 이름과 가장 비슷한 이름의 사람을 찾는다. 1. 키 값과 일치하도록 지정(한국) 2. 키 값의 구간을 지정(21세 이상 27세 미만) 3. 키 값과 비슷하도록 지정(발음이 가장 비슷한 이름) 1. 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행 2. 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색 수행 3. 해시법: 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색 수행 - 체인법: 같은 해시 값의 데이터를 선형 리스트로 연결 - 오픈 주소법: 데이..