반응형 Computer Science6 [알고리즘] 최대공약수(GCD), 최소공배수(LCM) - JAVA 최대공약수(GCD)GCD는 Greatest Common Divisor의 약자로 최대공약수이다. 두 수의 약수들의 공통된 값 중 최댓값을 말한다. GCD를 구하는 방법을 알아보자. 1. BigInteger 내장 함수private static int gcd(int a, int b) { BigInteger n = BigInteger.valueOf(a); BigInteger m = BigInteger.valueOf(b); return n.gcd(m).intValue();}2. 재귀private static int gcd(int a, int b) { if(b == 0) { return a; } return gcd(b, a % b);}3. 반복문private static.. 2024. 5. 18. [자료구조] 스택 & 큐 스택Stack 클래스에서 구현된 메서드는 다음과 같다. - `E push(E item)`: 스택의 맨 위에 요소를 추가한다. - `E pop()`: 스택의 맨 위 요소를 제거하고 제거된 요소를 반환한다. - `E peek()`: 스택의 맨 위 요소를 제거하지 않고 반환한다. - `boolean empty()`: 현재 스택에 요소가 존재하지 않을 경우 `true`, 그 외의 경우 `false`를 반환한다. - `int search(Object o)`: 스택의 상단부터 탐색하여 지정된 객체가 있는 요소의 위치를 반환한다. 없을 경우 `-1`을 반환한다. 스택은 먼저 들어온 데이터가 마지막에 나가는 구조이다. 페이지 뒤로가기, 실행 취소, 수식 괄호검사 등에서 응용된다. Stack 클래스는 .. 2024. 5. 18. [알고리즘] 이분 탐색 - JAVA 이분 탐색이분탐색은 탐색할 대상이 정렬된 상태에서 사용한다. 데이터의 특정 값을 찾기 위해 대상을 둘로 나눠 절반씩 줄여나가는 원리이다. 대상을 반씩 줄이기 때문에 시간복잡도는 O(logN)이다. 주어진 데이터에서 중복되지 않은 값이 주어질 때, 데이터 내에 특정 값이 존재하는지 여부를 확인하는 방법으로 많이 사용한다. 동작 방식은 다음과 같다. 1. 배열의 중간 값을 가져온다. 2. 중간 값과 검색 값을 비교한다. - 중간 값이 검색 값과 같다면 종료한다. (mid = key) - 중간 값보다 검색 값이 크다면 중간 값 기준 오른쪽 구간을 탐색한다.(right = mid-1) - 중간 값보다 검색 값이 작다면 중간 값 기준 왼쪽 구간을 탐색한다.(left = mid+1) 3. 값을 찾거.. 2024. 5. 17. [네트워크] 컴퓨터네트워크 및 인터넷 역사 네트워크의 구성 요소1. network edge 보통의 사용자들, 서버들은 가장자리(edge)에 위치한다. 웹브라우저들이 가장자리에 있다. 2. network core 사용자들을 연결시켜주는 특수한 역할을 하는 컴퓨터들.(라우터) 서로 연결되어있는 라우터들의 집합체이다. 3. access networks 장치들을 연결시켜주는 링크들. 즉, 네트워크에 접속하는 네트워크이다. 호스트가 네트워크 코어에 접속하는데 도움을 주는 중간 단계 네트워크이다. 유선(랜선), 무선(와이파이) 등. 프로토콜프로토콜이란 서로 다른 개체가 의사소통을 하기 위해 일정한 룰이 필요한데, 그 룰을 프로토콜이라고 한다. 의사소통을 위해 정해진 규칙. 패킷 스위칭패킷 스위칭(Packet swit.. 2024. 5. 17. [알고리즘] 정렬 알고리즘 정리 - JAVA 개요어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 문제이다. 데이터를 정렬해야 하는 이유는 탐색을 위해서이다. 컴퓨터는 이론상 무한 개의 데이터를 다룰 수 있어야 한다. 탐색할 대상 데이터가 정렬되어있지 않다면 순차 탐색 이외에 다른 알고리즘을 사용할 수 없지만 데이터가 정렬되어 있다면 이진 탐색이라는 강력한 알고리즘을 사용할 수 있다. 대표적인 정렬의 종류로 버블정렬, 퀵정렬, 삽입정렬 등이 있다. 버블정렬버블정렬은 거의 모든 상황에서 최악의 성능을 보여준다. 단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다. 시간복잡도는 O(n²). 버블정렬은 다음과 같은 순서로 작동한다.1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교2. 현재 원소가 다음 원소보다 크면.. 2024. 5. 17. [알고리즘] 에라토스테네스의 체 - JAVA 내용에라토스테네스의 체는 소수를 찾는 방법 중 하나이다. 1. 2부터 자기 자신을 제외한 2의 배수를 모두 지운다. 2. 남아있는 수 중 3은 소수이므로 3을 제외한 3의 배수를 모두 지운다. 3. 남아있는 수 중 5는 소수이므로 5를 제외한 5의 배수를 모두 지운다. 4. 위의 과정을 반복한다. 코드// N까지의 소수를 구하기 위한 배열boolean[] prime = new boolean[N + 1];// 소수를 false라고 하자// 0과 1은 소수가 아니므로 trueprime[0] = prime[1] = true;// 2부터 자신의 배수를 지운다for (int i = 2; i * i 2024. 5. 11. 이전 1 다음 반응형
