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..
문제를 효율적으로 해결하는 것은 무엇일까? 똑같은 문제를 해결해도 빠르게 해결하는 것이 중요하다. 같은 입력을 제공했을 때, 어느 프로그램이 더 빠른가? 내 프로그램은 얼마나 빠를까? 라는 의문을 가지고 나오게 된 것이 시간 복잡도이다. 프로그램이 대략적으로 몇 개의 명령을 수행하는가? public class Main { public static void main(String[] args) { int a =1, b= 5; int sum = a+b; System.out.println(sum); } } 위와 같은 코드는 a, b를 선언하고 sum 에다 a+b 값을 넣어주고 출력해주는 코드이다. 위는 대략 3번이 실행되는 데 이것은 O(3)이라고 한다. O는 Big-O를 나타내고 읽을 때는 빅-오 또는 오더라..
완전 탐색 문제입니다. 핵심 우선 세로 길이가 4인 블록을 넣을 수 있는지를 확인해야 한다. 가능하다면, 블록을 넣고 그때의 점수를 찾고, 다시 블록을 지우는 것이 핵심이다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int c = sc.nextInt(); //가로 int r = sc.nextInt(); //세로 //값넣기 int[][] arr = new int[r + 1][c + 1]; for (int i = 1; i
오늘은 완전 탐색 알고리즘에 대해 알아보자 완전탐색 알고리즘이란? 완전탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. 즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미한다. 이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부른다. 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 영어로 brute는 "짐승 같은, 난폭한"이라는 뜻이고, brute-force는 "난폭한 힘, 폭력"이라는 뜻이다. 오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식하다고 생각할 수도 있겠지만, 항상 정확도 100%를 보장한다는 점에서 암호 해독법 중 가장 확실하고 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해..
2주 차에서 다룰 내용은 다음과 같다. 1. Computer Architecture 고정 소수점/ 부동 소수점 패리티 비트/ 해밍 코드 ARM 프로세서 2. Java 고유 락 문자열 클래스 Garbage Collection Primitive type & Reference type Computer Architecture 컴퓨터에서 실수를 표현하는 방법은 고정 소수점과 부동 소수점 두 가지 방식이 존재한다. 고정 소수점/ 부동 소수점 고정 소수점(Fixed Point)이란? 소수점이 찍힐 위치를 미리 정해놓고 소수를 표현하는 방식이다. (정수 + 소수) ex) -6.12345 -> 부호(-)와 정수부(6), 소수부(0.12345) 3가지 요소가 필요함 장점: 실수를 정수부와 표현하여 단순하다. 단점: 표현의..
Docker를 사용하는 이유? 1. 운영 표준화 작은 컨테이너식 어플을 사용하면 손쉽게 배포하고, 문제를 파악하고, 수정을 위해 롤백이 가능하다. 2. 원활하게 이전 Docker 기반 어플을 로컬 개발 시스템에서 AWS의 프로덕션 배포로 원활하게 이전할 수 있다. 3. 빠른 코드 전달, 비용 절감 Docker를 쓰면 코드를 더 빨리 전달하고, 라소스 사용률을 높여 비용을 절감할 수 있다. 개발 환경: mac m1 애플 실리콘 , 완성된 스프링 부트 프로젝트(java11, jdk16으로 진행) 1. Homebrew로 Docker 설치하기(터미널 사용) Homebrew란 터미널에서 명령을 실행하는 것만으로, 패키지 설치 및 제거가 용이하게 할 수 있는 Mac 용 패키지 관리 도구이다. Homebrew설치 /..
완전 탐색 관련 문제입니다. 핵심 문제에서 좌표로 주어진 자리를 우리는 배열을 이용해서 표현해야 한다. 즉 좌표를 x축으로 대칭시킨 모습이 배열과 같다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int width = sc.nextInt(); // 공연장의 가로길이 int height = sc.nextInt(); // 공연장의 세로길이 int order = sc.nextInt(); // 대기순서 int x = 0, y = -1; boolean down = true, up = false, right = false, lef..
