분류 전체보기407 알고리즘2-2. 이진탐색알고리즘 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 (이진탐색은 시작점, 끝점, 중간점을 이용해 탐색 범위를 설정한다.) 단계마다 탐색 범위를 2로 나누는 것과 동일하기 때문에 연산횟수는 log2N에 비례하고, 시간 복잡도는 O(logN)을 보장한다. // 이진 탐색 소스코드 구현(반복문) public static int binarySearch(int[] arr, int target, int start, int end) { while(start0) { // 양수이면 point.getKey()가 크고, 매개변수 key가 작다. point = point.left; // 왼쪽 서.. 2022. 1. 29. 소수판별 알고리즘 소수(Prime Number) - 소수(prime)란 1보다 큰 자연수 중에서 1과 자기자신 이외의 수로는 나누어 떨어지지 않는 수 - 소수의 반대말: 합성수(세 개 이상의 양의 약수를 갖는 자연수) - 6은 1, 2, 3, 6으로 나누어떨어져서 소수가 아니다. - 7은 1과 7을 제외하고는 나누어떨어지지 않아서 소수이다. 소수 판별기 1) 2부터 주어진 수 n-1까지의 모든 수를 순회하면서 이 중에서 n의 약수가 있는지 확인하고, 약수가 없다면 소수 하나의 수에 대해서 소수인지 아닌지 판별하는 방법 2부터 n-1까지 모든 수를 다 확인하기 때문에 시간이 많이 걸린다. 알고리즘의 시간 복잡도는 O(N) class Main { public static boolean isPrimeNumber(int num).. 2022. 1. 28. 알고리즘2-1. 선형리스트(LinkedList 연결리스트) LinkedList 연결리스트 - 자료들을 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키지만, 자료 순서에 따라 노드의 포인터 부분을 이용해 연결시킨 자료구조 노드의 삽입, 삭제 작업이 용이하다. 기억공간이 연속적으로 놓여있지 않아도 저장이 가능하다. 연결을 위한 포인터가 필요하기 때문에 기억공간이용 효율이 좋지 않다. 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근속도가 느리다. 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다. 노드 구조를 사용하는 트리 등을 표현할 때 가장 적합한 자료구조이다. 리스트의 데이터는 노드(node) 또는 요소(element)라고 한다. 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있다. 처음에 있는 노드: 머리 노드(head node.. 2022. 1. 27. 알고리즘1-6. 정렬(Sorting): 버블정렬, 선택정렬, 삽입정렬, 퀵정렬 정렬이란? 데이터를 특정한 기준에 따라 순서대로 나열하는 것 키 값이 작은 작은 데이터를 앞쪽에 넣으면 오름차순(ascending order)정렬, 그 반대로 놓으면 내림차순(descending order)정렬 정렬 알고리즘의 핵심요소는 교환, 선택, 삽입이다. 내부정렬 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘 외부정렬 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘 1. 버블정렬(Bubble Sort) 오름차순 또는 내림차순으로 정렬할 때 인접한 데이터 두개의 대소 관계를 비교해서 크기 순서대로 교환하는 작업 오름차순으로 정렬할 경우 왼쪽값이 오른쪽 값보다 작아야 한다. 예제) 버블정렬을 구현한 코드 1) 버블정렬을 구현하는 myS.. 2022. 1. 26. 알고리즘1-5. 재귀알고리즘 재귀 함수(Recursive Functions) 하나의 함수에서 자신을 다시 호출하는 함수 일반적으로 재귀적 정의를 이용해 재귀함수를 구현한다. (기본부분:basic part와 유도 파트(inductive part)로 구성 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다. 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다. 재귀 호출은 반복적인 스택의 사용을 의미하고 계속 재귀함수를 호출하면 메모리 및 속도에서 성능저하가 발생한다. 재귀 함수를 문제 풀이에서 사용할 때는 재귀함수의 종료 조건을 반드시 명시해야 한다.(종료 조건을 명시하지 않으면 함수가 무한히 호출될 수 있다.) 예제) 팩토리얼 구하기 1. for문을 이용한 팩토리얼 구하기 import java.util.Sca.. 2022. 1. 26. 알고리즘1-4. 큐(Queue) 큐(Queue) - 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다. - 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO)이다. 인큐(enqueue): 큐에 데이터를 넣는 작업 디큐(dequeue): 큐에서 데이터를 꺼내는 작업 프론트(front): 꺼내는 쪽 리어(rear): 데이터를 넣는 쪽 링버퍼로 큐 만들기 더보기 front = 5, rear = 5 디큐할 경우: 36(queue[0])을 디큐한 후 front값을 que[1]로 업데이트 해준다. (그 다음에 디큐할 경우를 대비해서) 인큐할 경우: queue[5]자리에 64를 저장하고 나서 rear값을 que[0]으로 업데이트 해준다. - 링퍼버: 배열의 처음과 끝이 연결되었다고 보는 자료구조 - 여기서 어떤 요소가 첫 번째.. 2022. 1. 26. 이전 1 ··· 46 47 48 49 50 51 52 ··· 68 다음
