function solution(n) { var answer = 0; let count = 0; let arr = new Array(); //소수가 아닌 것들을 빼면 소수가 됨 //자기자신을 제외한 모든 배수를 n개의 숫자 내에서 확인 //확인된 숫자를 다 0으로 두면 나머지가 소수 //n 까지 숫자를 전부 배열에 일단 넣고 확인하자 for (let i = 2; i

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조이다. 데이터는 후입선출로 이뤄진다는 점이 큐와의 차이점이라고 할 수 있다. 따라서 큐에서의 프론트/리어와 다르게 스택은 탑과 바텀으로 표현하는데, 이것은 후입선출 특징상 꼭대기(탑)에 가까운 데이터만 나가고 들어오기 때문이다. 흔히 '스택을 쌓는다'라는 말이 있는데, 쌓는다는 표현이 바로 정확하게 표현한다고 볼 수 있다. 바닥부터 쌓아올리는 형식을 생각하면, 자료를 넣을때도 뺄 때도 후입선출을 할 수 밖에 없기 때문이다. 스택에서 데이터를 넣는 작업을 푸시(push)라 하고, 데이터를 꺼내는 작업을 pop 이라고 한다. Java에서는 메서드를 호출하고 실행하는 것을 스택방식으로 처리한다. 스택 역시 데이터의 집합이기 때문에 배열로 구현할 수 있다..

큐 형태의 자료구조는 데이터를 쌓아두는 자료구조로, 선입선출(FIFO)인 점이 특징이다. 주로 일시적인 자료의 저장에 많이 사용된다. 큐의 경우 가장 먼저 들어간 데이터를 먼저 꺼내고, 나중에 들어간 데이터를 나중에 꺼내게 되는데 이를 배열로 만들게 될 경우 하나의 데이터를 꺼낼 때 마다 모든 데이터의 위치를 이동해야하는 문제가 있다. 따라서 보통 큐를 만들 때는 Linked list를 이용하거나, ring buffer 형태를 많이 사용한다. 큐에 데이터를 넣는 작업은 인큐(enqueue), 꺼내는 작업은 디큐(dequeue)라고 한다. 데이터를 꺼내는 쪽은 프론트(front)라고 하고 데이터를 넣는 쪽을 (rear)라고 한다. 배열로 큐를 생성할 경우, 인큐의 복잡도는 O(1)이 되지만 디큐의 복잡도는..

본래 점근표기법은 수학적 개념으로, 임의의 함수에 대하여 정의역의 원소가 커짐에 따라 그 원소의 상이 얼마나 빠르게 커지는지를 표현하는 것이다. 그러나 컴퓨터의 경우, 1의 연산과 100, 1000의 연산에 거의 차이가 없다. 이 말은, 컴퓨터가 연산하는 과정을 1의 단위까지 세세하게 고려하더라도 명확한 성능 차이를 드러내지는 않는다는 것이며, 따라서 프로그래밍 과정에서 점근표기법을 통해 프로그램 알고리즘의 복잡도을 표현하는 것은 근사값에 대한 정의를 나타내는 것이다. 즉, 프로그램에 있어서 점근표기법이란, 한 프로그램이 실행되는 과정에 소요되는 시간(단계)를 나타내며, 그 과정에서 계수와 상수를 제거한다. 이는 컴퓨터의 연산속도가 사람과 다르기 때문에 계수와 상수로 이뤄지는 횟수의 차가 실제 차이만큼 ..

오름차순, 혹은 내림차순으로 이미 정렬이 되어있는 배열에서 특정한 값을 찾아내는 것. 방식은 배열 중간의 임의의 값을 선택하여 찾고자 하는 키 값과 비교하는 것을 반복하는 방식으로 진행되며, 크기가 작고 큰지에 대해 이후 탐색해야할 배열의 영역을 정해 다시 탐색한다. 해당 값을 찾을 때 까지 이러한 과정을 반복하게 되며, 따라서 탐색 배열은 한 번 탐색이 끝날 때 마다 배열의 크기가 절반씩 줄어든다고 볼 수 있다. 가령 N개 크기의 배열을 이진 탐색하면 N은 *1/2, *1/4 식으로 줄어들 것이다. 여기서 몇 번 탐색했느냐가 시간복잡도를 나타내게 된다. 따라서 이를 수식으로 세운다면 시간복잡도는 log2N이 된다고 볼 수 있다(2^X(실행탐색회수)=N) public class BinSearch { //..

선형검색의 종료조건 두 가지를 검색을 반복할 때 마다 판단하는 것을 효율적으로 줄이기 위한 개선방법. 검색하고자 하는 키 값을 기존 배열의 맨 끝 자리에 추가로 저장하고 이를 보초(sentinel)라고 부른다. 이는 검색할 때 원하는 키 값이 없을 경우 배열의 마지막에 키 값을 보초로 세워두어 선형검색의 종료조건 중 하나인 [검색할 값을 발견하지 못 하고 배열의 끝을 지나가는 경우]를 없애는 것이다. 따라서 보초법을 사용하게 되면 반복문의 종료 판단 횟수를 2회에서 1회로 줄인다. public class SeqSearchSen { static int seqSearchSen(int[] a, int n, int key){ int i = 0; a[n] = key;//보초를 추가 //배열 요소를 순서대로 검색,..