오늘은 이진 탐색에 대해 정리해보려 한다. 영어로는 Binary Search라고 한다. 이진 탐색은 정렬되어 있는 숫자들 중에서 특정 숫자를 찾는다. -값들 중에 절반을 기준으로 원하는 값을 찾는다. -절반을 나눈 값을 기준으로 원하는 값이 있는 쪽에서 다시 절반을 나눈다. 즉 이진 탐색은 숫자를 절반씩 지워나가면서 찾는다. 따라서 시간 복잡도는 O(log n)이 된다. 여기서 의문점이 들 수 있다. 정렬해야 하면 O(log n)이 아니라 결국 O(n log n) 아닌가요? -> yes 따라서 이미 배열이 정렬되어 있다면 Binary Search가 효율적이다. 또는 숫자 찾기를 엄청 많이 해야 하는 경우에는 오히려 정렬을 한 뒤에 Binary Search를 하는 것이 좋다. 이제 이진 탐색을 구현해보자...
우선 함수에 대해 알아보자 함수란 값을 입력받아 특정 연산을 수행하여 결과를 반환하는 것이다. 다음은 재귀 함수에 대해 알아보자 자기 자신을 부르는 함수 대표적인 예시는 팩토리얼이다. import java.util.Scanner; public class Main2 { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n =sc.nextInt(); System.out.println(getFactorial(n)); } public static int getFactorial(int n){ if (n==0)return 1; else return n*factory(n-1); } } 위 코드를 보면 계속해서 자기 자신을 ..
3주 차에서 다룰 내용은 다음과 같다. 1. Network OSI 7 계층 TCP 3 way handshake&4 way handshake TCP/IP 흐름 제어&혼잡 제어 UDP 2. Java Error&Exception Stream API Record Network OSI 7 계층 OSI 7 계층이란? OSI계층은 네트워크에서 통신이 일어나는 과정을 7단계로 나눈 것을 말한다. 7 계층은 왜 나눌까? 통신이 일어나는 과정을 단계별로 알 수 있고, 특정한 곳에 이상이 생기면 그 단계만 수정할 수 있기 때문이다. 1. 물리 계층(Physical): 단지 데이터 전기적인 신호로 변환해서 주고받는 기능을 진행하는 공간 즉, 데이터를 전송하는 역할만 진행한다. 2. 데이터 링크 계층(Data Link): 물리..
https://school.programmers.co.kr/learn/courses/30/lessons/17681 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 핵심 2개의 배열의 값을 2진수로 바꾸어, 각 배열의 값이 둘 중 1개라도 1이면 새로운 배열에 # 아니면 공백을 추가해준다. 정답 코드, 처음 풀이 public class Solution { public String[] solution(int n, int[] arr1, int[] arr2) { String[] answer = new String[n]; for (int i =0;i
https://school.programmers.co.kr/learn/courses/30/lessons/12915 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 문자열 내 마음대로 정렬하기 문제 링크입니다. 핵심 이 문제에서 핵심은 정렬을 하는데, 문자열에서 원하는 index의 문자를 비교하여 정렬해야 한다. 정답 코드 import java.util.*; class Solution { public String[] solution(String[] strings, int n) { String[] answer = {}; List list = new..
https://www.acmicpc.net/problem/2204 2204번: 도비의 난독증 테스트 꿍은 도비에게 영어단어들을 제시한 후 어떤 단어가 대소문자를 구분하지 않고 사전순으로 가장 앞서는지 맞추면 양말을 주어 자유를 얻게해준다고 하였다. 하지만 인성이 좋지 않은 꿍은 사실 www.acmicpc.net 2204번 도비의 난독증 테스트 문제 링크입니다. 핵심 HashMap을 사용하여 기존의 문자열을 저장해주고, 전부 소문자로 바꾼다. 정답 코드 import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scann..
재귀 함수 문제입니다. 핵심 숫자가 작아지는 형태로 나타나야 한다. 재귀 함수를 만들 때, 매개변수로 값의 합과 인덱스 위치를 나타내는 값을 사용한다. 정답 코드 import java.util.Scanner; public class Main { static int[] result; static int n; static int count; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); result = new int[n]; division(0,0); System.out.println(count); } //현재까지 구한 합이 mysum //index번째 숫자를 결정할 차례 result[..
String관련 문제입니다. 핵심 문자가 연속해서 나오는지 확인해야 한다. 1번만 나올 경우 1은 생략한다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); String str = sc.nextLine()+" "; StringBuilder sb = new StringBuilder(); int count = 1; for (int i=0;i
더 빠르게 정렬할 수는 없을까? 기존의 정렬의 시간 복잡도는 O(n^2) 걸리지만 오늘 배울 합병 정렬과 퀵 정렬은 시간 복잡도가 O(n log n)이 걸리게 된다. 두 정렬은 모두 재귀를 사용하게 된다. 재귀 함수 디자인의 과정 1. 작성하려는 함수의 역할을 말로 명확하게 정의한다. 2. 함수가 기저 조건에서 제대로 동작하게 작성한다. 3. 함수가 제대로 동작한다고 가정하고 함수를 완성한다. 4. 함수를 완성한 후, 기저 조건으로 수렴함을 보인다. 합병 정렬 배열을 절반으로 나누어 각각을 정렬한 후, 합친다. T(n) = n개의 숫자를 합병 정렬할 때의 시간 복잡도 1. 왼쪽 합병 정렬 = T(n/2) 2. 오른쪽 합병 정렬. = T(n/2) 3. 합친다. = O(n) 점화식 = T(n) =2*T(n/..
수학에서 에라토스테네스의 체는 소수를 찾는 방법이 다. 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2. 2는 소수이므로 자기 자신을 제외한 모든 배수를 지운다. 3. 남아있는 수 중에 가장 작은 수인 소수 3을 제외하고 다시 3의 모든 배수를 지운다. 4. 다음은 남아있는 소수 5를 제외하고 5의 배수를 모두 지운다. 5. 이것을 반복한다. 핵심 위 문제를 풀기 위해 앞서 살펴본 에라토스테네스의 체 알고리즘을 사용한다. 정답 코드 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.i..
