알고리즘 (최대, 최소값 찾기)
실습 1 ) 최대값찾기
- 코드업문제
- 9개의 서로 다른 자연수가 주어질 때, 이들 중 최대값을 찾고 그 최대값이 몇 번째 수인지를 구하는 프로그램을 작성하시오.
- 예를 들어, 서로 다른 9개의 자연수
3, 29, 38, 12, 57, 74, 40, 85, 61
이 주어지면 이들 중 최대값은 85이고, 이 값은 8번째 수이다.
public class Max {
public int[] getMax(int arr[]){
int maxIdx = 0;
int maxValue = arr[0];
// O(n)의 for loop문
for (int i = 0; i < arr.length; i++) {
if (arr[i] > maxValue) {
maxValue = arr[i];
maxIdx = i;
}
}
return new int[]{maxValue, maxIdx};
}
public static void main(String[] args) {
int[] arr = new int[]{3, 29, 38, 12, 57, 74, 40, 85, 61};
Max max = new Max();
System.out.println(Arrays.toString(max.getMax((arr))));
// 출력값 : [85, 7]
}
}빅 오 표기법(Big-O)이란?
- 알고리즘의 복잡도를 판단하는 척도로 공간복잡도와 시간복잡도가 있는데, 빅오 표기법은 시간복잡도를 다룬다.
- 시간복잡도는 알고리즘 내 정의, 단순계산, 비교 등과 같은 '단위 연산'의 횟수와 관련이 있다.
- 빅 오 표기를 할 때는 가장 최악의 경우를 가정한다.
실습 2 ) 다차원배열 + 최대값 찾기
- 코드업문제
- <그림 1>과 같이 9×9 격자판에 쓰여진 81개의 자연수가 주어질 때, 이들 중 최대값을 찾고 그 최대값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오.
- 예를 들어, 다음과 같이 81개의 수가 주어지면 이들 중 최대값은 90이고, 이 값은 5행 7열에 위치한다.
🔽 code
public class MaxInMatrix {
public static void main(String[] args) {
int[][] arr = new int[][]{
{113,23,85,34,17,74,25,52,65},
{10,7,39,42,88,52,14,72,63},
{87,42,18,78,53,45,18,84,53},
{34,28,64,85,12,16,75,36,55},
{21,77,45,35,28,75,90,76,1},
{25,87,65,15,28,11,37,28,74},
{65,27,75,41,7,89,78,64,39},
{47,47,70,45,23,65,3,41,44},
{87,13,82,38,31,12,29,29,80}
};
int maxValue = arr[0][0];
int [] maxIdx = {0,0}; // i,j
// 9*9 루프를 돌린다. O(n^2)
for (int i = 0; i < 9; i++) {
for (int j =0; j < 9; j++) {
if ( arr[i][j] > maxValue ) {
maxValue = arr[i][j];
maxIdx[0] = i;
maxIdx[1] = j;
}
}
}
System.out.println(maxValue);
System.out.println(Arrays.toString(maxIdx));다차원배열
위와 같은 격자판을 표현하기 위해, 다차원배열 생성 시 이중 for문을 사용하는데 코드를 짜기 전 표를 만들어 보고 순회 방향 등을 생각해 봐야한다.
// 9*9 루프를 돌린다. O(n^2)
for (int i = 0; i < 9; i++) {
for (int j =0; j < 9; j++) {
if ( arr[i][j] > maxValue ) {
maxValue = arr[i][j];
maxIdx[0] = i;
maxIdx[1] = j;
}위 코드에서 arr[i][j]는 배열을 가로순회 하겠다는 의미이며 arr[j][i]로 바꿔쓴다면 배열을 세로 순회 하게 된다.
즉 for문내의 제어변수를 통해 가로/세로 순회를 생각해볼 수 있다.
데이터가공 관련 단축키 꿀팁
alt + J : 지정한 텍스트와 같은 텍스트를 찾아 동시에 여러 개를 지정하는 기능
Home, End : alt+J상태에서 줄 맨 처음으로, 줄 맨 마지막으로
alt + 1 : project explorer로 이동하기
alt +insert : project explorer 에 커서를 두고 누르면 class 생성, 코드 화면에선 생성자/getter/setter 등을 생성함
shift + 위아래 방향키 : 멀티 마우스 커서
-> Ctrl + shift + G : 하나씩 취소하기
Ctrl + G : 같은 단어 찾기
실습 3 ) 최대/최소값 같이 구하기 (Template Callback design pattern)
이전 최대값 찾기 코드에서 getMax 메서드 안의 if문 안 조건식의 부등호 방향만 반대로한 메서드 getMin을 만들어 추가할 수도 있다. 하지만 통째로 메서드를 copy해서 두개로 잡아주는 것은 기술낭비 이기 때문에 다형성을 이용해서 리팩토링을 해본다.
1. getMax메서드 내부의 조건문 변경
public int[] getMax(int arr[]) {
int maxValue = arr[0];
for (int i = 0; i < arr.length; i++) {
// if문을 실행할지 결정하는 boolean isSth
boolean isSth = arr[i] > maxValue;
if (isSth) {
maxValue = arr[i];
}
}
return maxValue;
}if문 내부에 있던 최대/최소값 부등호 방향에 따른 조건식의 차이를isSth변수를 만들어 줌으로써 간단하게 차이를 둘 수 있게 할 것이다.- 또한
isSth를boolean형식으로 만들어 수를 비교해서 그 조건이 만족할때만 max값에 담길 수 있도록 할 수 있다.
2. Polymorphism을 활용한 인터페이스 추가
interface Compare {
boolean doSomething(int valueA, int valueB);
}private int getMaxOrMin(int[] arr, Compare compare) { // compare 부분: callback
// loop 구성
int targetValue = arr[0];
for (int i = 0; i < arr.length; i++) {
boolean isSth = compare.doSomething(arr[i], targetValue);
// max인 경우 arr[i] > targetValue
// min인 경우 arr[i] < targetValue
if (isSth) {
targetValue = arr[i];
}
}
return targetValue;
}getMaxOrMin 의 매개변수로 Max와 Min의 차이점인 부분을 표현하기 위해 인터페이스 Compare 를 사용한다. (이 과정을 Callback 이라 한다.)
compare.doSomething 에 arr[i] 와 targetValue 를 넘겨주어 값을 비교하도록 한다.
이 때 max값을 리턴하는 메서드와 min값을 리턴하는 메서드를 만든다.
3. max , min 메서드 구현
public int max(int[] arr){
return getMaxOrMin(arr, new Compare() {
@Override
public boolean doSomething(int valueA, int valueB) {
return valueA > valueB;
}
});
}max 메서드는 getMaxOrMin 을 리턴한다.
이 때 getMaxOrMin 의 매개변수인 Compare 를 내부 클래스로 선언한다.
내부 클래스로 선언함으로써 Compare 인터페이스의 doSomething 메서드를 구현한다.
max 메서드의 경우 새로운 값 arr[i] 가 더 큰 경우 true 를 리턴하게 한다.
public int min(int[] arr){
Compare cp = new Compare() {
@Override
public boolean doSomething(int valueA, int valueB) {
return valueA < valueB;
}
};
return getMaxOrMin(arr, cp);
}내부 클래스를 다음과 같이 선언할 수 있다.
min 메서드의 경우 새로운 값 arr[i] 가 더 큰 경우 false 를 리턴하게 한다.
4. main 메서드에서의 선언
public static void main(String[] args) {
int[] arr = new int[]{3, 29, 38, 12, 57, 74, 40, 85, 61};
MaxAndMin maxAndMin = new MaxAndMin();
int maxResult = maxAndMin.max(arr);
int minResult = maxAndMin.min(arr);
System.out.println(maxResult);
System.out.println(minResult);
}
}- Template Callback패턴
SQL
병원 정보 제공 앱을 만들기 위한 백엔드 서버를 만든다고 가정하고, 전국병원에 대한 정보를 가진 data를 '공공데이터' 포탈에서 다운받아 분석해보았다.
DB 설계
요구사항 분석 -> 개념적 설계 -> 논리적 설계 -> 물리적 설계
(1) 요구 사항분석
- 병원분류명이 총 몇가지 인지?
- 병원분류별로 몇개씩 있는지? ex) 의원:x개 치과병원:y개 한방병원:z개 …
- 병원 분류가 몇가지 인지?
- 서울의 구별로 각 병원이 몇개 있는지 ex) 서울시 금천구 의원, 한방병원, 치과병원, .. 이 각 몇개인지?
- 구별로 병원이 가장 많은 구는?
- 이비인후과(0), 외과(1), 내과(2), 소아과(3), 피부과(4), 성형외과(5) 는 각 몇개인지(category)
(2) 개념적설계
- 사용자의 요구사항 분석 후, 데이터베이스에 대한 추상적인 형태를 설계
- 데이터와 데이터 간의 관계를 ERD(Entity Relationship Diagram)로 표현
(3) 논리적 설계
- 개발에 사용할 DBMS가 처리할 수 있는 데이터베이스의 논리적 구조를 설계
- ERD를 관계 데이터 모델의 릴레이션(테이블) 스키마로 변환
(4) 물리적설계
- 필요한 인덱스의 구조나 내부 저장 구조 등에 대한 물리적인 구조를 설계
- create Table
SQL 통해서 DB 제어
1개의 ROW (Record) Insert 하기
INSERT INTO `likelion-db`.`seoul_hospital`
(`id`,
`address`,
`district`,
`category`,
`emergency_room`,
`name`,
`subdivision`)
VALUES
('A1120837',
'서울특별시 금천구 벚꽃로 286 삼성리더스타워 111~114호 (가산동)',
'서울특별시 금천구',
'C',
2,
'가산기대찬의원',
null);
파일로 insert 하기
💻 일반파일
- 파일에 sql문 작성 (.sql로 저장)
- workbensh에서 .sql 스크립트 불러오기
💻 JAVA 파일
1. LineReader 클래스
package com.lion;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class LineReader {
List<String> readLines(String filename) throws IOException {
List<String> result = new ArrayList<>(); // 한줄씩을 모두 모은 List
String str; // readLine() 을 통해서 한줄씩 담을 변수
BufferedReader br = new BufferedReader(new FileReader(filename));
// loop
while ((str = br.readLine()) != null){ // 다음 줄이 없을때까지 str에 한줄씩 담고
// result 리스트에 str을 바로 add한다.
result.add(str);
}
return result;
}
public static void main(String[] args) throws IOException {
String filename = "C:\\Users\\sj980\\Downloads\\seoul hospital.csv";
LineReader lr = new LineReader();
List<String> lines = lr.readLines(filename);
System.out.println(lines.size()); // 잘 불러와졌는지 라인수로 확인
}
}
🔼 List<String>을 반환하는 readlines()
🔽 다형성을 이용해 다양한 타입을 반환할 수 있게 parser 추가
참고링크
