suyeonme

1. Linear Queue(선형 큐)란? FIFO(First In First Out) en-queue: 큐에 데이터를 넣는 작업 -- O(1) de-queue: 큐에서 데이터를 꺼내는 작업 -- O(n) 데이터가 나오는 쪽은 front, 데이터를 넣는 쪽은 rear라고 한다. 1.1 선형 큐의 단점 큐에 데이터가 꽉 찼다면 데이터를 추가할 수 없다. de-queue시 요소를 하나씩 앞으로 옮겨야 하므로 복잡도가 O(n)이다. 2. Ring Buffer(Circular Queue)란? 원형큐는 배열의 맨 뒤가 맨 앞과 연결되었다고 보며 선형 큐의 문제점을 보완하기 위한 자료구조이다. 선형큐와 다르게 de-queue시, 배열 요소를 앞으로 옮기지 않아도 된다. enqueue시 rear 인덱스에 값을 저장하..

1. 스택(Stack)이란? LIFO(Last In First Out) push: 스택에 데이터를 넣는 작업 pop: 스택에서 데이터를 꺼내는 작업 푸시와 팝이 이루어지는 꼭대기는 top, 스택의 가장 아랫부분은 bottom이라고 한다. 2. 직접 스택 생성하기 static class IntStack { private int[] stack; // 스택 배열 private int capacity; // 스택 용량 private int stackPointer; // 스택에 쌓여있는 데이터 수 // 실행시 예외: 스택이 비어 있는 경우 public class EmptyIntStackException extends RuntimeException { public EmptyIntStackException() {};..

1. 선형 검색(Linear Search) 배열에서 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다. 복잡도는 O(n)이다. static int seqSearch(int[] arr, int n, int key) { int i = 0; while(true) { if(i == n) { return -1; } if(arr[i] == key) { return i; } i++; } } 1.1 보초법(Sentinel Method) 위의 선형 검색은 반복할 때마다 종료 조건 1과 2를 모두 판단한다. 보초법을 사용하여 반복문에서 종료 판단 횟수를 2회에서 1회로 줄일 수 있다. 순서) 1. 검색할 값을 보초로 arr[n]에 대입한다. 2. 배열 요소를 순서대로 스캔한다. static int..

소수(Prime Number): 1보다 크고 자기 자신과 1 이외에 어떤 정수로도 나누어떨어지지 않는 정수 합성수(Composite Number): 나누어떨어지는 정수가 하나 이상 존재하는 수 해결 1) i가 2 또는 3으로 나누어떨어지지 않으면 4, 6으로도 나누어떨어지지 않는다. 즉 2부터 n-1까지의 어떤 소수로도 나누어지지 않는다는 조건을 만족하는지 조사하여, 불필요한 나눗셈을 줄일 수 있다. (7이 소수인지 여부는 7보다 작은 소수 2,5,3으로 나눗셈을 하여 구한다.) public ArrayList getPrimeNumbers(int num) { ArrayList primeNumbers = new ArrayList(); for(int i = 2; i

해결 1) public int[] reverseArr(int[] arr) { for(int i = 0; i < arr.length /2; i++) { int temp = arr[i]; arr[i] = arr[arr.length - i -1]; arr[arr.length - i -1] = temp; } return arr; } 해결 2) public void reverseArr2(int[] arr) { for(int i = 0; i < arr.length / 2; i++) { swap(arr, i, arr.length - i -1); } } public void swap(int[] arr, int idx1, int idx2) { int temp = arr[idx1]; arr[idx1] = arr[idx2]..

Array 특징 배열은 선언하는 동시에 배열의 크기를 지정한다. 그 이후에는 크기를 변경할 수 없다. (크기가 고정적이다) 선언시 별도의 초기화를 하지 않으면 기본값으로 0이 채워진다. 배열의 물리 주소와 논리 주소는 동일하다. 따라서 index를 통해서 요소에 접근할 수 있다. 메모리 공간이 연속적으로 구성된다. 배열은 참조 객체(reference object)이므로 배열을 가리키는 참조 변수는 스택(stack) 영역에 할당된다. 이 참조 변수가 가리키는 주소값은 실제 힙(heap) 영역에 생성되는 배열의 주소값이다. index를 사용하여 요소에 접근한다. 단점 배열의 크기가 고정적이기 때문에 확장성이 떨어진다. 따라서 데이터의 개수가 가변적이라면 배열의 사용을 지양해야한다. 배열 중간의 요소를 제거하..

for loop은 단순하다. 하지만 for loop도 어떻게 작성하느냐에 따라서 퍼포먼스가 달라진다. 예를 들어, n만큼 +와 -를 번갈아 출력하는 코드를 짠다고 해보자. 가장 쉽게 떠올릴 수 있는 방법이다. 하지만 아래와 같이 코드를 작성해야할 경우 2가지 문제가 있다. 1. 반복할 때 마다 if문을 실행해야한다. 2. 변경할 때 유연하게 대응하기 어렵다. (i값을 바꾸고 싶은 경우 i와 n의 값을 마찬가지로 수정해야한다) for(int i = 0; i < n; i++) { if(i % 2 == 0) { System.out.print("+") } else { System.out.print("-") } } 위의 코드를 아래와 같이 최적화할 수 있다. 아래 코드는 반복마다 if문을 실행하지 않는다. 또한 ..

Parameter, Argument 함수에 전달되는 변수는 parameter이다. 함수를 호출할 때 넘기는 value는 argument이다. public int sum(int num) {} sum(3); Operators 단항 연산자(unary operator): a++ 2항 연산자(binary operator): a < b 3항 연산자(ternary operator): a ? b : c 사전 판단 반복, 사후 판단 반복 사전 판단 반복: 실행 전에 반복을 계속할지 판단한다. 따라서 loop 본문을 한번도 실행하지 않을 수도 있다. (while loop, for loop) 사후 판단 반복: 실행 후에 반복을 계속 할지 판단한다. 따라서 루프 본문을 한번은 반드시 실행한다. (do-while loop) 단..