D+50 -모델링,알고리즘.재귀함수,정렬알고리즘.선택정렬,삽입정렬,버블정렬,합병정렬,수학알고리즘.소수,최대공약수,최소공배수,스프링부트.라이브러리확인,가져오기,jsp라이브러리 추가하기
학원 일기
모델링
모델링이란 DB설계를 의미한다. 건축같은경우 설계도, 청사진 등을 만드는 것이다.
DB모델링 툴
주로 er-win을 사용한다. 하지만 비싸서 이번 시간엔 무료툴인 ERDCloud를 사용할 것이다.
ERDCloud
ERDCloud에서 로그인 후 사용하면된다.
새로운 테이블 만들기
1번을 누르면 새로운 엔티티가 만들어진다. 여기서 "!"를 클릭하면 다음과같은 이름을 적는 창이 뜨는데 논리이름은 보통 한글을 적고 물리이름은 보통 영어로 적는다.
여기서 "!"는 정보를 입력하는 창은 띄워주고,쓰레기통은 행삭제를 시켜준다.
"+"버튼은 행 추가인데 파란색은 일반 행, 노란색은 기본 키이다.
테이블 정보 입력
테이블 정보를 입력하는 곳으로 "!"를 누르면 나온다. 여기 입력해야하는 정보에는
- 테이블이름 : 논리이름에는 한글 물리이름에는 영어
- 타입 : 숫자나, 문자, 날짜 타입과 길이수
- NULL 허용 : NULL이 들어가도 되는지 안 되는지를 정해주는 것이다. 기본키는 CHECK하면 안된다.
- 기본값 : DEFAULT값으로 NULL이들어올 때 반환할 값을 적어주는 곳
- 코멘트 : 말그대로 코멘트를 적어주는 곳. 보통 논리이름과 같은 이름을 음
이 있다.
엔티티
부서 정보 테이블의 엔티티를 만들었다. 엔티티는 행이 컬럼의 정보이므로 행이 컬럼의 갯수와 같아야한다.
관계설정
참조키(외래키 FK)로 관계설정을 해야한다. 사원들은 기본적으로 부서에 소속이 되어있다. 부서와 사원을 연결해주는 공통된 컬럼을 참조키라고 하고 이건 부서번호가 된다.
부모의 값이 아닌 다른 값이 자식테이블에 들어오면 참조키가 이것을 못들어오게 막아주는 역할을한다.
관계의 종류
- 1대1 관계 : 모든 사람은 하나의 휴대폰만을 가지고 있다고 하면 이것은 1대1관계이다.
- 1대 N관계 : 부서와 사원 테이블이있다. 부서에는 4건이있고 사원은 14명이 있다고 하면 한 부서에는 여러명의 사원이 있다. 사원 입장에서는 한 부서에만 소속이 되니까 부서는 N이고 사원은 1관계이다.
-N대 N관계 : 회원과 권한의 관계에서, 한명의 회원은 여러 권한을 가질 수 있고, 하나의 권한도 여러 회원을 가질수 있기에 이것은 N대 N관계이다.
N대 N관계 DB에서 만들기
N대 N관계는 DB에서 만들수 없기에 변형이 필요하다. 1대 N관계 테이블을 만들고 매핑테이블을 하나 만들어서 이것을 다시 N대 1관계로 만든다. 도식을 보자면 다음과 같다
1:N - 매핑테이블 - N:1
식별관계와 비식별관계
-
식별관계 : 부모 테이블의 기본키 또는 유니크 키를 자식 테이블이 자신의 기본키로 사용하는 관계.
-
비 식별관계 : 모 테이블의 기본키 또는 유니크 키를 자신의 기본키로 사용하지 않고, 외래 키로 사용하는 관계
ERD에서 관계 설정하는 법
몇대 몇의 관계인지를 설정 해줄수 있다. 아이콘에 마우스를 가져다 대면 몇대 몇인지를 알 수있다.
관계를 설정해주었고 부서테이블의 기본키를 사원테이블에서는 외래키로 사용하기에 비식별관계로 맺어주었다.
모델링시 주의할점
정규화
테이블에 중복된 데이터를 없게 만드는 것으로 깔끔한 설계 및 중복된 데이터 제거로 용량절약과 성능이 향상된다.
하지만 정규화를 하면 테이블이 여러개로 쪼개져서 JOIN을 많이 하게 된다. 그렇게 되면 오히려 속도가 느려지는 역효과가 생길 수 있다.
정규화의 3단계
제 1 정규화
컬럼에는 오직한개의 값만 들어가게 설계해야한다.
만약 과목이라는 컬럼에 수학과 영어가 동시에 들어갈 수 없다는 것이다.
예시) 아래 설계가 있음 : 잘못된 것을 고치시요
수정 전 :
# 이름 | 나이 | 수강과목
# 홍길동 | 20 | C, C++ => 제 1 정규화 위반
# 장길산 | 21 | JAVA
# 수정 후 :
# 이름 | 나이 | 수강과목
# 홍길동 | 20 | C
# 홍길동 | 20 | C++
# 장길산 | 21 | JAVA위의 수정 전 테이블에서 홍길동의 수강 과목이 두개인데 하나의 값에 들어가있다. 이것을 나누어 2개의 행으로 만들어주어야한다.
제 2 정규화
컬럼에서 중복되는 값을 최대한 없애는 것이다.
수정 전 :
# 이름 | 나이 | 수강과목
# 홍길동 | 20 | C
# 홍길동 | 20 | C++
# 장길산 | 21 | JAVA
# => 위에 데이터 중복을 제거하는 방향으로 테이블 쪼개기
수정 후 :
# A 테이블 :
# 이름 | 나이
# 홍길동 | 20
# 장길산 | 21
# B 테이블 :
# 이름 | 수강과목
# 홍길동 | C
# 홍길동 | C++
# 장길산 | JAVA
두컬럼 이상 겹치는 값이 있을때 테이블을 두개로 쪼개서 중복을 줄일 수있다. 필수는 아니다.
제 3 정규화
만약 하나의 컬럼이 다른 컬럼을 참고하여 값을 결정할때, 이 테이블을 두 테이블로 쪼갤 수 잇다.
수정 전 :
# 학생 코드 | 학생이름 | Street | City | State | Zip(우편번호)
# 0001 | 홍길동 | 2 | 보스턴 | 캘리포니아 | 607001
# => Zip(우편번호) : Street, City, State 정보를 가지고 우편번호를 만듬
수정 후 :
# A 테이블
# 학생 코드 | 학생이름 | Zip(우편번호)
# 0001 | 홍길동 | 607001
# B 테이블
# Zip(우편번호) | Street | City | State
# 607001 | 2 | 보스턴 | 캘리포니아Street, City, State 정보를 가지고 우편번호를 만드므로 이것들을 떼어내어 따로 하나의 테이블을 만들 수 있다.
알고리즘
재귀함수
함수자신을 계속 호출하는 함수를 재귀 함수 또는 순환 함수라고 한다.
자기자신을 너무많이 호출하면 성능이 매우 나빠지거나 스택 오버플로우 에러가 발생할 수 있으므로항상 그 이전에 답을 곧장 반환하는 조건문을 최소 1개 포함해야한다.
함수의 형태
함수의 형태는 자신을 return값으로 가지는 것이다. 다음의 함수를 보자.
public static int reSum(int n){
if(n == 1) return 1;
return reSum(n-1)+n;
// return에 자신을 넣으면 재귀함수가 되나보네,
// i)3을 넣으면 3더하고3-1인 2가 함수로들어가서 i과정을 다시 시작한다.
// ii) 그럼다시 2를 더하고 2-1인 1을 함수에 넣어 reSum함수를 실행하고
// ii)마지막에 1이 들어왔으니 끝이난다.
}-
자신의 return값으로 가지고 함수가 끝나면 자신을 다시 실행시켜반복을 시킨다. 위의 함수에서도 을 넣으면 3더하고3-1인 2가 함수로들어가서 i과정을 다시 시작한다. 그럼다시 2를 더하고 2-1인 1을 함수에 넣어 reSum함수를 실행하고 마지막에 1이 들어왔으니 끝이난다.
-
여기서 중요한 점은 마지막에 끝나는 지점을 잘 지정해주어야한다는 것이다. 아니면 무한 루프가 걸리게 된다. 위의 함수에서는 1부터 n까지 수를 더하는 것이므로 마지막에 n == 1일때 return이 되게 만드는 것이다.
-
그리고 1씩 빼는 것도 모든 수를 다 더해야하기 때문에 1씩 제거하는 것이다.
public static void main(String[] args) {
System.out.println(reSum(10));
}함수를 실행하면 
값이 잘 나온다.
DER을 이용해서 설계를 더 쉽고 정확하게 할 수 있게 된다. 물론 테이블을 생성하는 것도 더 쉬워 모델링을 해보는것이 더 쉬워진다. 프로젝트 전에 이것을 해서 데이터 베이스를 설계해봐야겠다.
정렬 알고리즘
선택정렬
구현 간단, 성능 낮음 : 시간복잡도 (n^2)
선택정렬
(1) 주어진 배열에서 최소값을 찾는다
(2) 그값을 맨앞의 값과 교환한다.
(3) 맨 처음 위치를 뺀 나머지 배열을 (1) ~ (2) 를 반복한다.
2) 삽입정렬
손안의 카드를 정렬하는 방법과 유사하다
새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입하는 방법
(1) 2번째 숫자를 첫번째 숫자와 비교해서 작으면 그 숫자 앞에 끼워넣음
(2) 3번째 숫자를 이전 배열과 하나씩 비교해서 작으면 그 숫자 앞에 끼워넣음
(3) ... 배열의 끝까지 (1) ~ (2) 를 반복한다.
3) 버블정렬
인접한 2개의 숫자를 비교하여 크기가 정렬되지 않으면 오름차순 정렬하면서 배열의 끝까지 이동시키는 알고리즘
(1) 배열의 인접한 숫자를 비교하여 작은수를 앞으로 교환한다.
(2) 위와 같은 방식을 모두 진행하면 가장 큰수가 제일 뒤로 가게된다.(최대값이 가장 맨뒤에 있음)
(3) (1) ~ (2) 과정을 배열이 오름차순으로 정렬될때까지 계속 반복한다.
구현 복잡, 성능 높음 : NLogN, (몇번 재귀호출하는가? LogN), (몇번 비교/교환하는가? N)
1) 합병정렬
1개의 리스트를 2개의 균등한 크기로 분할하고 분할된 리스트를 정렬한다음, 2개의 정렬된 부분을 합쳐서 전체가 정렬되게 하는 방법
주로 배열보다 링크드 리스트를 사용한다.(휠신빠름)
(1) 입력 리스트를 같은 크기의 2개의 부분 배열로 분할한다.
(2) 부분 리스트을를 정렬한다. 부분 리스트의 크기가 충분히 작지 않으면 순환 호출을(재귀호출) 이용해서 다시 정렬한다.
(3) 정렬된 부분리스트들을 하나씩 합병한다.
퀵정렬
합병정렬을 개량한 방법, 자바에서 구현되어 있으면 Arrays.sort 가 퀵정렬 좀더 향상시킨 듀얼피봇 퀵정렬임
장점 : 가장 빠른 알고리즘임
단점 : 만약 정렬되어 있으면 성능이 대폭 낮아짐
삽입 + 합병정렬 = 타임정렬
속도가 빠름
결론 : 코딩 테스트 정렬문제를 풀때 Arrays.sort 또는 Collecitons.sort 2개 중에 1개를 선택해서 해결할것 : 상황에 따라 시간초과가 발생할 수 있음
수학 알고리즘
최대 공약수 및 최소 공배수 구하기
- 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
=> a % b = r
=> b % r = r'
...
=> r'%r'' = 0 => r'' 최대공약수임
- 최소공배수 : a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다
- 예제) 8, 4 의 최대공약수, 최소공배수 구하기
- 일반 풀이 :
예) 8 4 최대공약수 :
- 8 : 1, 2, 4, 8
- 4 : 1, 2, 4
- 최대공약수 : 4
- 8 : 8, 16, 32 ...
- 4 : 4, 8, 12 ...
- 최소공배수 : 8 - 유클리드 호제법 풀이 :
예) a%b = 0 이면 b 가 최대공약수
- 8 4 최대공약수 : 8 % 4 = 0 => 나누는값 4 : 최대공약수
예) a*b/최대공약수
- 32 / 4 = 8 (최소공배수)
public class Main {
public static int gcd(int a, int b) { //유클리드 호제법으로 최대공약수를 구함
int r = a % b; // 최초 1번 나머지 구하기
while(r > 0) { //mod가 0이 될 때 b의 값이 최대 공약수
a = b; // 나머지 구하기
b = r; // 다시 계산하기 위해 a 를 b 의 값으로 수정함
r = a % b; // 다시 계산하기 위해 b 를 r 의 값으로 수정함 (2nd 반복문이 실행되면 재계산된 값이 계산됨)
}
return b;// r이 0일때 b는 최대공약수
}
public static void main(String[] args) {
int gcdVal = gcd(8, 4); // 최대공약수
int lcmVal = (a * b) / gcdVal; // 최소공배수
System.out.println(gcdVal + " " + lcmVal);
}
}소수 구하기 알고리즘
- 2) 2 ~ n 까지 숫자중 대량의 수들에 대해 소수를 빠르게 판별하는 알고리즘
(1) 1~ n 까지 저장된 이차원 배열을 생성함
(2) 2의배수 지움 : 단, 자기자신은 제외하고 지움 (배수들은 제일 작은수를 최소 1개 약수로 가지므로 소수가 아님)
(3) 3의배수 지움 : 단, 자기자신은 제외하고 지움 (배수들은 제일 작은수를 최소 1개 약수로 가지므로 소수가 아님)
(4) 순차적으로 증가시키면서 n의 배수를 지움. : 단, 자기자신 및 이미 지워진 수는 제외함
(5) 남은 숫자가 소수임 : 배열의 남은 숫자를 모두 지움
public class Main {
public static void main(String[] args) throws IOException {
// 알고리즘 :
// 0) 소수 : 1, 자기자신 이외의 수로 나누어 떨어지지 않으면 소수임
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] str = bufferedReader.readLine().split(" "); // 3 16
int start = Integer.parseInt(str[0]); // 3
int end = Integer.parseInt(str[1]); // 16
StringBuilder stringBuilder = new StringBuilder();
int[] arr = new int[1000001];
// 배열 초기화
for (int i = 2; i <= 1000000; i++) {
arr[i] = i; // 2 ~ 1000000 까지 배열에 값 넣기, arr[0] == arr[1] == 0 (소수 아님으로 넣기)
}
// 에라토스테네스의 체 배열 만들기
for (int i = 2; i <= 1000000; i++) {
for(int j = 2*i; j <= 1000000; j += i) { // 반복시 (2~1000000)배수만 반복하기
// i에 2를 곱하는 이유는 어차피 i가 소수가 아니라면 앞의 코드에서 걸러졌을 것이기 때문에 2를 곱하는 것이다.
//그리고 i씩 증가시키는 이유는 i의 배수들을 제거하기 위함이다.
if(arr[j] == 0) continue; 이미 0이면 밑의 코드를 실행안 해도 되니 성능을 증가시켜준다.
if(j % i == 0) arr[j] = 0; // 배수는 소수 아님 : 0 저장(소수 아님 표시)
}
}
for (int i = start; i <= end; i++) {
// 소수 아니면 0 맞으면 0보다 큼 : 큰수는 stringBuilder 에 저장해 둔다.
if(arr[i] > 0) stringBuilder.append(i + "\n");
}
System.out.println(stringBuilder);
}
}Spring boot
시작
인강에서는 spring사이트에서 설정을 했는데 여기서는 spring initializr을 이용해서 설정한다.
여기서 group은 우리가 속한 소속을 나타내는데 웹 주소뒤에 나오는 이름이 이것이다. 회사이름이나 회사에서 정해주는 것을 하면된다.
packging은 실행하는 프로그램이 web이면 war, exe프로그램이면 jar를 하면된다.
라이브러리 가져오기
이 세개를 기본적으로 가져오고 다른 것은 차차 필요하면 가져오기로 한다.
- dev tool은 데이터가 변경되면 자동으로 실행이 되는 것을 말한다. 원래는 서버를 껐다 켜야하는데 이걸 자동으로 해주는 기능이다.
- lombok은 어노테이션의 일종으로 편리한 기능들이 많다.
- spring web은 우리가 웹 프로그밍을 하기 때문에 이걸 꼭 넣어주어야한다.
라이브러리 확인
위 경로로 가져온 라이브러리를 확인 할 수 있다. 우리가 가져온 라이브러리를 볼 수 있다. 여기서 tomcat은 자바 프로그램을 웹부라우저에서 돌아가게 해준다. 자바 언어를 해석해서 웹브라우저에 뜨게 해준다. was의 일종이고 spring boot에는 기본적으로 내장되어있다.
JSP라이브러리 추가하기
// jsp 라이브러리 추가
implementation 'org.apache.tomcat.embed:tomcat-embed-jasper' // 추가
implementation 'javax.servlet:jstl' // 추가위의 라이브러리를 추가하면 jsp를 사용할 수 있다.
jsp란
https://lordofkangs.tistory.com/34 링크를 참고하자. 대략 html을 확장한 것이라 보면된다. 자바를 기반으로 하는 것이지만, 최근에는 자바언어 사용을 지양하려한다. 그래서 html언어를 이용해서 자동으로 java언어로 바뀌는 기능을 가진다.
위와 같은 경로를 만들면 jsp파일이 생기고, jsp는 다음과 같이 생겼다.
한글설정
외국 ide라서 한글지원이 잘 안된다. 그래서 이것을 utf-8로 맞춰줘여한다.
- 경로 : settings - editor - file encodings
이것들을 그림과 같이 설정하면된다.
