• Sequel이란 언어의 시초
• 표준 질의어로 채택되어 널리 쓰이는 관계형 질의언어
• 관계대수나 관계해석은 확실한 이론적 배경을 제공하나 상용으로 쓰이기에는 어렵고 적절 X → SQL 사용

SQL 의 구성 : DDL & DML

DDL(데이터 정의(Definition) 언어)

• 데이터 저장 구조를 명시
• 테이블 스키마의 생성, 기본키 외래키 설정,정의, 수정, 삭제

DML(데이터 조작(Manipulation) 언어)

• 사용자가 데이터를 접근하고 조작할 수 있게 하는 언어
• 레코드의 검색, 삽입, 삭제, 수정

DDL (데이터 정의 언어)

테이블 생성

create table department
(
    dept_id     varchar2(10),
    dept_name   varchar2(20) not null,
    office      varchar2(20),
    constraint pk_department primary key(dept_id)
);

//constraint pk_department primary key(dept_id)
//제약조건을 지정.
//이 테이블의 **기본 키(primary key)**는 dept_id 컬럼.
//pk_department라는 제약조건 이름을 부여함.
//나중에 이 제약조건을 수정하거나 삭제할 때 이 이름을 사용 가능.

create table student
(
    stu_id       varchar2(10),
    resident_id  varchar2(14) not null,
    name         varchar2(10) not null,
    year         int,
    address      varchar2(10),
    dept_id      varchar2(10),
    constraint pk_student primary key(stu_id),
    constraint fk_student foreign key(dept_id) references department(dept_id)
);

// constraint fk_student foreign key(dept_id) references department(dept_id)
- dept_id는 외래 키(foreign key).
- 외래 키는 다른 테이블의 기본 키를 참조함.
- 여기서는 department 테이블의 dept_id를 참조.
- 즉, student 테이블의 dept_id 값은 반드시 department 테이블에 존재하는 값이어야 함.
- 제약조건 이름: fk_student

테이블 삭제

drop table <테이블 이름>

• 다른 테이블에서 외래키로 참조되는 경우 삭제할 수 없음

테이블 수정

// 필드 추가
alter table <테이블 이름> add <추가할 필드>
alter table student add age int

// 필드 삭제
alter table <테이블 이름> drop column <삭제할 필드>
alter table student drop column age

표준 SQL과 오라클의 데이터 타입

DML (데이터 조작 언어)

레코드 삽입

insert into department(dept_it, dept_name, office)
values('920', '컴퓨터공학과', '201호')

insert into department 
values ('923', '산업공학과', '207호')

• 필드 이름을 명령문에 나열할 경우, 테이블 생성할 때 지정한 순서와 달라도 됨

레코드 수정

• 모든 레코드에 대한 수정 적용시 where 절 생략 가능

update <테이블 이름> set <수정 내역> where <조건> 

// student 테이블의 모든 학생들의 학년을 하나씩 증가
update student set year = year + 1 

update professor set 지위 ='교수', number = '923' where name = '고희석'

레코드 삭제

• where절에 지정된 조건을 만족하는 레코드들 삭제
• where 절 생략 시 모든 레코드 삭제
• 모든 레코드들이 삭제되어도 테이블은 삭제 X
• 외래키로 사용되는 필드에 대해 데이터를 삽입할 때

delete from <테이블 이름> where <조건>

delete from professor where name='김태석'

레코드 검색

select <필드리스트>
from <테이블리스트>
where <조건>

//중복된 레코드를 제거 -> distinct
select distinct address from student

//select 절에 필드이름 외 산술식이나 상수 사용 가능
select name, 2012-year_emp
from professor

//컴퓨터공학과 3학년 학생들의 학번 검색
select student.stu_id
from student, department
where student.dept_id = department.dept_id and
            student.year = 3 and
            department.dept_name='컴퓨터공학과'

COMMIT

• 대부분의 DBMS는 명령어를 실행하면 변경 결과를 즉시 데이터베이스에 반영하지 않고 가지고 있다가 COMMIT 명령을 내리면 그때 영구적으로 데이터베이스에 반영
• 취소 불가능
• COMMIT 전에는 ROLLBACK으로 작업 취소가능
• set autocommit on → 자동 커밋

집계함수

• count, sum, avg, max, min
• select절과 having절에서만 가능
• sum, avg는 숫자형 데이터 타입을 갖는 필드에서만 가능

COUNT

• NULL 은 계산에서 제외
• 단, count * → 레코드 수 계산

count(distinct<필드이름>) // 서로 구별되는 값의 개수

ORDER BY

• 정렬
• SELECT문 맨 마지막에
• asc, desc

SELECT name, student_id
from student
where year=3 or year=4
order by name,stu_id // 학심 이름으로 오름차순 정렬, 같은 이름은 stu_id로 정렬

GROUP BY

• select 절에 집계함수가 사용될 경우 다른 필드는 select 절에 사용할 수가 없음
• ⇒ GROUP BY 사용해야함 !!
• Null속성도 그룹화

select ename, max(sal) from emp // ⚠️에러발생 

// 부서별 최고 금여
select deptno, max(sal) from emp group by deptno

//deptno별 레코드 개수 출력
select deptno, count(*)
from student
group by deptno 

select dname, count(*), avg(sal), max(sal), min(sal)
from emp e, delt d
where e.deptno = d.deptno
group by dname

Having

• 그룹에 대한 조건 명시
• group 에 대한 조건은 where 절에 사용할 수 없음 ! → having 절 이용

select dept_name, count(*), avg(2012-year_emp), max(2012-year_emp)
from professor p, department d
where d.dept_id = p.dept_id and avg(2012-year_emp)>=10 //⚠️에러발생 
group by dept_name

//올바른 표현식
select dept_name, count(*), avg(2012-year_emp), max(2012-year_emp)
from professor p, department d
where d.dept_id = p.dept_id 
group by dept_name
having avg(2012-year_emp)>=10

💡SQL 실행 순서

from → where → group by → having → select → distinct → order by → rownum

where, having, group by 절을 모두 함께 사용할 경우

1. where 절에 명시된 조건을 만족하는 레코드들 검색
2. group by 절에 명시된 필드값이 서로 일치하는 레코드들끼리 그룹지어 집계함수 적용
3. 집계함수 적용한 결과들 중 having절을 만족하는 결과만 출력

Like 연산자

• 문자열에 대해서는 일부분만 일치하는 경우를 찾아야할 때 사용
• = 대신 like 연산자 사용

//student 테이블에서 김씨 성을 가진 학생들을 찾아라
select * from student where name like '김%'

재명명 연산

• <원래 이름> as < 새로운 이름>
• as 생략 가능
• Oracle에서 컬럼(속성) 은 as 사용가능, 테이블 별칭은 as키워드 사용X
• 실제 테이블 이름이 수정되거나 필드 이름이 바뀌는 것은 X
• 질의를 처리하는 과정 동안만 일시적

// ♦️ 테이블 재명명
student 테이블과 department 테이블을 조인하여 학생들의 이름과 소속 학과 이름 검색
select s.name, d.dept_name
from student s, department d
where s.dept_id = d.dept_id

// ♦️ 필드의 재명명
student name 이름, position 직위, 2012-year_emp 재직연수 from professor

NULL 처리

• is null, is not null
• 산술 표현식(+, - ,* ,/)의 결과는 입력값중 하나라도 null인 경우 null
• 그룹함수(sum, avg, min, max)는 NULL 무시
• count는 일반적으로 NULL이 아닌 값을 세지만, COUNT(*) 는 NULL 상관없이 전체 행의 수를 리턴

SELECT stu_id
FROM takes
WHERE grade <> 'A+'; // 👉🏻<> : 오라클에서의 같지 않다

-> grade 의 필드 값이 널인 레코드에 대해서는 질의 결과에 포함 X

Inner Join

• 일반 조인(equi-join)과 의미가 동일

//형식
select <컬럼명>
from <테이블1> (inner) join <테이블2>
         on table1.컬렴명 = table2.컬럼명

select <컬럼명>
from <테이블1> (inner) join <테이블2>
       using 같은 컬럼명

Natural Join(자연조인)

• 두 테이블 간의 동일한 이름을 갖는 모든 칼럼들에 대해 equi(=) join
• 두 테이블에 동일한 이름의 컬럼이 있을 때만 동작 !

select name, stu_id, dept_name
from student natural join department

Outer Join

select title, credit, year, semester
from course left outer join class
using (course_id)

select title, credit, year, semester
from course left outer join class
on (course.course_id = class.course_id)

select title, credit, year, semester
from course, class
where course.course_id = class.course_id (+) //left outer join

select title, credit, year, semester
from course, class
where course.course_id (+) = class.course_id //right outer join

• where 절에서 기준이 되는 테이블 반대 테이블 조건 컬럼 뒤에 (+)를 붙힘
  • Left outer : 오른쪽
  • Right outer : 왼쪽
• full outer join : 양쪽 테이블에서 서로 일치하는 레코드가 없을 경우, 해당 레코드들도 결과 테이블에 포함시키며 나머지 필드에 대해서는 모두 NULL삽입

카티션 프로덕트

• FROM 테이블1,테이블2
• FROM 테이블1 CROSS JOIN 테이블2

무결성

• Intefrity constraints (무결성 제약 조건)
• not null, unique,…

UNIQUE

• 기본키와 UNIQUE 모두 특정 속성에 중복된 값이 저장되는 것을 방지
• 차이점은 기본키 : NULL 값 X , UNIQUE : NULL 값 가능
• 기본키 = NOT NULL + UNIQUE

create table univ (
univ_name varchar(20),
tel char(12),
UNIQUE(univ_name)

String operation

• concat() : 문자열 연결
  • 오라클에서는 오직 두개의 인수만 가능
• || : concat 연산자
  • select name || ‘,’ || dept_name → name,dept_name 출력
• upper(), lower() : 대문자, 소문자로 변환
• length() : 문자열 길이
• substr(문자열, 1, 5) : 1부터 5번째 글자의 문자열 추출

• 정렬시켜야할 대상은 레코드(record) —> 행에 해당
• 레코드는 필드(field) 로 구성 —> 열에 해당
• 키필드로 레코드와 레코드를 구분

• 모든 경우에 최적의 정렬 알고리즘은 X

  → 각 응용분야에 적합한 정렬 방법을 사용해야 함

  구분 요소

  • 레코드 수
  • 레코드 크기
  • Key의 특성(문자, 정수, 실수 등)
  • 메모리 내부/외부 정렬
    • 내부정렬: 모든 데이터가 주기억장치에 저장
    • 외부정렬: 외부기억장치에 대부분의 데이터 일부만 내

정렬 알고리즘 평가 기준

• key 값 비교 횟수의 많고 적음
• data의 이동 횟수의 많고 적음

**이동횟수와 비교 횟수는 비례하지 않음(하나는 적고 하나는 클 수 있다)

단순하지만 비효율적(O(n^2))

• 삽입,선택,버블 정렬

복잡하지만 효율적(O(nlogn))

• 퀵, 히프, 합병, 기수

정렬 알고리즘의 안정성→ 동일한 키 값을 갖는 레코드들이 정렬 후에도 바뀌지 않음(삽입, 버블, 합병 정렬)

: 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘

→ 제자리정렬

• (n-1)번 인덱스의 값은 정렬할 필요 없음

• (n-2)번 인덱스 까지만 교환(정렬)하면 됨

• 비교횟수 = n(n-1)/2 = O(n^2)

  : 외부 for문: n-1 , 내부 for문: i+1

• 이동횟수 = 3(n-1) = O(n)

• 전체적인 시간복잡도: O(n^2)

• 안정성 만족X

📌삽입정렬

• 필요할때에만 위치를 바꿈

• 앞에있는 원소들이 이미 정렬이 되어있다고 가정

• 최선의 경우 O(n) : 이미 정렬이 되어있는 경우→ 가장 효율

  • 비교: n-1 번

• 최악의 경우 O(n^2): 역순으로 정렬되어있는 경우

  • 모든 단계에서 앞에 놓인 자료 전부 이동
  • 비교 = n(n-1)/2 = O(n^2)
  • 이동 = n(n-1)/2 + 2(n-1) = O(n^2)

• 시간복잡도 O(n^2)

• 안정된 정렬방법

📌버블정렬

• 효율성이 가장 떨어짐
• 뒤에서부터 정렬됨(선택정렬과 반대)
• 바로 옆에있는 값과 비교하여 정렬

• 비교횟수 (최상, 평균, 최악 모두 일정) : O(n^2)
• 이동 횟수
  • 최악의 경우(역순으로 정렬): 비교횟수 *3 → temp,i,j 3번 교환
  • 최선의 경우(이미 정렬): 0
  • 평균: O(n^2)
• 이동연산은 비교연산보다 더 많은 시간이 소요

📌쉘정렬

• 삽입정렬을 보완한 정렬
• 불연속적인 부분 리스트에서 멀리 떨어진 자료 이동으로 보다 적은 위치교환
• 부분 리스트가 5→3→1 로 갈수록 점진적으로 정렬된 상태가 되므로 삽입정렬 속도 증가
• 시간복잡도
  • 최악의 경우 O(n^2)
  • 평균 O(n^1.5)

📌합병정렬

• 분할 → 정복 → 결합
  • 분할: 리스트를 두개의 균등한 크기로 분할, 하나가 될때까지 계속 분할 4→2→1
  • 정복: 부분 배열을 정렬
  • 결합: 정렬된 부분배열을 하나의 배열에 통합

분할

합병 및 정렬

왼쪽(2,3,4,7)이 i 오른쪽(1,9,11,15)이 j 라 해보자

먼저 2와 1을 비교해 1이 더 작으므로 1을 정렬한다

그리고 j+1 을 하여 9와 2를 비교한다. 2가 더 작으므로 2를 정렬

i+1을 하여 3과 9를 비교… 이런 식

• 비교횟수
  • 크기가 n인 리스트를 정확히 균등분배하므로 log(n) 개의 패스
  • 각 패스에서 리스트의 모든 레코드를 n개 비교하므로 n번의 비교연산
• 이동횟수
  • 레코드의 이동이 각 패스에서 2n번 발생하므로 전체 레코드의 이동은 2n*log(n)번 발생
  • 레코드를 연결리스트로 구성하여 합병 정렬할 경우 효율적
• 최적, 평균, 최악의 경우 큰 차이 없이 O(n*log(n))의 시간복잡도
• 안정적이며 데이터의 초기분산 순서에 영향을 덜 받음

📌퀵정렬

• 평균적으로 가장 빠른 정렬
• 비균등 분할
• 재귀호출

pivot 값보다 큰 값을 low 가 찾고 pivot 값보다 작은 값을 high가 찾는다 → 교환

만약 low 값이 더 작고 high 값이 더 클 시 엇갈린 것 → low 값과 pivot 값을 바꿈

• 시간복잡도 n*log(n)

📌기수정렬

: 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘

• 레코드를 비교하지 않고 정렬 수행 ( 대부분의 정렬방법은 레코드를 비교)
• 시간복잡도 : O(dn) (n: 데이터의 개수, d : 데이터들의 최대 자리수, 대부분 d<10 이하)
• 자리수가 고정되어 있는 안정적인 정렬

ex) 두자리수의 기수정렬

: 일의 자리수 오름차순으로 정렬 → 데이터 정렬 완료 → 다시 십의 자리수로 오름차순으로 정렬

💡 알고리즘별 시간복잡도

정점(node) 와 그 정점을 연결하는 간선( edge)로 이루어진 자료구조

그래프 탐색의 종류 2가지 : DFS, BFS

💡깊이 우선 탐색(DFS)

📌 개념

• 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대깊이 까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색하는 알고리즘

• 완전 탐색 기법 중 하나

• 완전 탐색 기법

  • 특징
    • 재귀함수로 구현
    • 스택 자료구조 이용

📌 특징

• 모든 노드를 방문하고자 하는 경우 이 방법을 사용
• 너비 우선 탐색 보다 더 간결함
• 검색 속도는 너비 우선 탐색에 비해 느리다

📌 DFS 템플릿 코드

static Set<String> visited = new HashSet<>();

static void dfs(Map<String, List<String>> graph, String current) {
    // *---------------------------------------*
        // 그래프를 방문하며 처리해야할 일을 여기서 한다
        // (예시)
      // if (current == value) {
        //     << 현재 노드가 특정 값을 만족할 때 해야할 일 >>
        //     return current;
        // }
    // *---------------------------------------*
    visited.add(current);
    for (String v : graph.get(current)) {
        if (!visited.contains(v)) {
            dfs(graph, v);
        }
    }
}

💡너비 우선 탐색(BFS)

• 완전 탐색 기법
• 시작 노드에서 인접한 노드를 먼저 탐색하고, 그 다음 인접한 노드를 탐색하는 알고리즘

📌 특징

• 완전 탐색 기법
• 큐 자료구조 이용
• 최단 경로를 찾을 때 유용

📌 BFS 템플릿 코드

public static void makeGraph() {
    graph.put(0, Arrays.asList(1, 3, 6));
    graph.put(1, Arrays.asList(0, 3));
    graph.put(2, Arrays.asList(3));
    graph.put(3, Arrays.asList(0, 1, 2, 7));
    graph.put(4, Arrays.asList(5));
    graph.put(5, Arrays.asList(4, 6, 7));
    graph.put(6, Arrays.asList(0, 5));
    graph.put(7, Arrays.asList(3, 5));
}

Set<String> bfs(Map<String, List<String>> graph, String start) {
    Set<String> visited = new HashSet<>();
    visited.add(start);
    Queue<String> queue = new ArrayDeque<>();
    queue.add(start);

    while (!queue.isEmpty()) {
        String current = queue.remove();
            // *---------------------------------------*
                // 그래프를 방문하며 처리해야할 일을 여기서 한다
                // (예시)
              // if (current == value) {
                //     << 현재 노드가 특정 값을 만족할 때 해야할 일 >>
                //     return current;
                // }
            // *---------------------------------------*
        for (String v : graph.get(current)) {
            if (!visited.contains(v)) {
                visited.add(v);
                queue.add(v);
            }
        }
    }
    return visited;
}

💡이진탐색(Binary Search)

📌 개념

• ‘정렬된 배열’에서 ‘특정 값’을 찾는 알고리즘
• ‘탐색 범위를 절반씩 줄여’나가기 때문에 선형탐색에 비해 빠른 속도를 보장
• 하지만 ‘배열이 정렬되어 있어야 한다는 조건’이 필요하기 때문에 배열이 정렬되어 있지 않은 경우에는 정렬 작업이 필요

📌 특징

• 반드시 정렬되어 있는 상태에서만 사용 가능
• 배열 또는 이진트리를 이용해 구현 가능
• 시간복잡도 Olog(n)

📌 이진탐색트리란?

• 이진 탐색을 위한 이진트리
• 왼쪽 서브트리 < 루트
• 오른쪽 서브트리 > 루트

📌 반복을 이용한 이진탐색 구현 ★★

int binarySearch2(int key, int low, int high) {
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if(key == arr[mid]) {
            return mid;
        } else if(key < arr[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1; // 탐색 실패 
}

📌 순환호출을 이용한 이진탐색 구현

int binarySearch1(int key, int low, int high) {
    int mid;

    if(low <= high) {
        mid = (low + high) / 2;

        if(key == arr[mid]) { // 탐색 성공 
            return mid;
        } else if(key < arr[mid]) {
            // 왼쪽 부분 arr[0]부터 arr[mid-1]에서의 탐색 
            return binarySearch1(key ,low, mid-1);  
        } else {
            // 오른쪽 부분 - arr[mid+1]부터 arr[high]에서의 탐색 
            return binarySearch1(key, mid+1, high); 
        }
    }

    return -1; // 탐색 실패 
}

• 1978년 :로렌스 J. 엘리슨(현 회장)이 관계형 DBMS인 오라클 첫 번째 버전(Version 1)을 개발
• 1979년 : 회사명을 RSI(Relational Software Inc.)로 바꾸고 첫 번째 상용 DBMS인 오라클 두 번째 버전(Version 2)을 개발
• 1983년 : 회사 이름을 지금의 오라클로 바꾸고 C언어로 개발된 오라클 세 번째 버전(Version3)을 출시
• 1999년 : 오라클 8i 출시 (i는 인터넷의 약자)
• 2011년 : 오라클 11g 출시
• 현재 : 오라클 21c (최신)

오라클의 특징

• 네트워크 환경 지원
• 다양한 운영체제 지원
• 대용량 데이터 처리 지원
• 여러 사용자의 동시 접속 지원
• 신뢰성 높은 보안 기능 지원
• 오류 및 장애에 대한 대비책 지원

SQL*Plus 기본 명령어

SQL*Plus 접속 및 종료

화면 및 출력 관리

테이블 목록 조회

자동 커밋 설정

//SQL*Plus 실행
sqlplus/nolog
sqlplus/nolog
//시스템 관리자인 sys 계정으로 접속
connect sys as sysdba
connect sys as sysdba
//둘이 합쳐서 이렇게도 가능
sqlplus sys as sysdba
sqlplus sys as sysdba
//현재 데이터베이스에 존재하는 모든 사용자 계정 정보를 조회
select * from all_users;

//기본적 생성 명령
create user <사용자 계정> identified by <비밀번호>;
create user C##Yujin identified by 1234
//계정 잠금 해제
alter user <사용자 계정> account unlock;
alter user C#Yujin account unlock
//로그인 및 자원 사용 권한 부여
grant connect,resource to <사용자계정>
grant connect, resource to 
//새로운 사용자계정으로 로그인
connect <사용자 계정>

• 물리적 혹은 추상적으로 존재하는 현실세계를 단순화 하고 정형화 된 형태로 표현 하는 하나의 방식 또는 규범
• 실제 데이터가 갖는 특성을 살리면서, 목적에 맞게 관심 있는 정보만 단순화 하여 표현하는 방식
  • 데이터에 대한 조작이 가능해야 함

릴레이션(Relation)

관계형 데이터 모델(relation data model)

• 테이블 형식을 이용하여 데이터를 정의하고 설명
• 실세계의 데이터를 누구나 직관적으로 이해할 수 있는 간단한 방식
• 테이블을 릴레이션(relation)이라 부름
• 수학적으로 두개 이상의 집합으로부터 각 집합을 구성하는 원소들의 순서쌍에 대한 집합 의미

도메인(domain)

• 각 필드에 입력 가능한 값들의 범위
• 각 필드가 가질 수 있는 모든 값들의 집합
• 원자값(더이상 분리 X)이여야함

널(null)

• 특정 필드에 대한 값을 알지 못하거나 아직 정해지지 않아 입력하지 못한 경우의 필드의 값
• 0이나 공백 문자와 다름

테이블 스키마와 테이블 인스턴스

테이블 스키마

• 테이블 정의에 따라 만들어진 데이터 구조
• ex) 신입생(학번, 주민등록번호, 이름, 주소)

차수(degree)

• 테이블 스키마에 정의된 필드 수
  • 차수 1 : 단항 테이블
  • 차수 2 : 이항 테이블
  • 차수 n : n항 테이블

테이블 인스턴스

• 테이블 스키마에 현실 세계의 데이터를 레코드로 저장한 형태
• 스키마는 한번 정의하면 거의 변함이 없지만, 인스턴스는 수시로 바뀔 수 있음

기수(cardinality)

• 테이블 인스턴스의 레코드 수

테이블 특성

• 중복된 레코드가 존재하지 않음
  • 테이블 인스턴스는 레코드들의 “집합” 이다
• 레코드 간의 순서는 의미 X
• 레코드 내에서 필드의 순서는 의미 X
• 모든 필드는 원자값을 가짐

키(key)

💡 키는 왜 필요한가? 레코드간의 순서가 의미가 없으므로 레코드를 구분하기 위해 각 레코드의 값을 이용함

• 필드들의 일부로 각 레코드들을 유일하게 식별해낼 수 있는 식별자
• 일반적으로 하나의 필드를 지정, 여럿도 가능 (복합키)
• 관계형 데이터 모델에서 특정 레코드를 구별하거나 탐색하기 위한 유일한 방법

수퍼키(super key)

• 아무런 제약 조건 없이 레코드들을 식별할 수 있는 필드의 집합
• (주민등록번호) (주민등록번호, 학번) (주민등록번호, 이름) 등등,,,
  • 전체 테이블의 속성(필드)를 모두 합한 것도 하나의 수퍼키

후보키(candidate key)

• 최소한의 필드만 구성된 키
• (학번) (주민등록번호)

기본키(primary key)

• 후보키 중에서 식별자 하나로 정의한 하나의 키
• 되도록 하나의 필드로 구성된 후보키를 선정하는 것이 유리
• (학번)
• NULL 허용 X, 동일한 값 X

외래키(foreign key)

• 서로 관련이 있는 테이블 사이에서 데이터 일관성을 보장하는 수단
• 한 테이블(R1)의 필드가 다른 테이블(R2)의 기본키(PK) 또는 유니크 키를 참조할 때 외래키(FK)라고 함.
• 외래키로 지정이 되면 기본키 또는 유니크 키를 참조하게 됨
• 참조되는 테이블에서 사용중인 기본키를 삭제 혹은 변경 할 수 없음
• 기본키에 없는 값은 외래키로 입력할 수 없음

조건

1. 외래키(FK)의 필드들은 참조되는 테이블의 기본키(PK)와 같은 데이터형(도메인)이어야 함.
2. 외래키(FK)의 값은:
   • 참조되는 테이블(R2)의 기본키(PK) 값 중 하나와 일치하거나,
   • NULL일 수 있음 (값이 아직 없거나, 모를 때).

외래키의 역할

• 데이터 무결성을 보장:
  • 외래키 필드에 기본키에 없는 값은 입력할 수 없음.
  • 외래키로 참조된 기본키는 삭제하거나 변경할 수 없음.
• 데이터베이스의 테이블 간 관계를 정의.

관계형 데이터베이스

💡관계형 데이터베이스란?

관계형 데이터 모델에 기반하여 하나 이상의 테이블로 실세계를 표현한 데이터베이스

• 실세계를 관계형 데이터 모델이라는 추상적인 도구를 이용하여 표현한 것
• 테이블들을 컴퓨터의 기억 장치에 어떠한 방법으로 저장할 것인가에 대한 물리적 구조까지 정의한 것은 XX

관계형 데이터베이스가 하나 이상의 테이블로 구성되어 있을 때

• 데이터베이스 스키마
  • 테이블 스키마의 집합
• 데이터베이스 인스턴스
  • 테이블 스키마들에 대한 테이블 인스턴스의 집

개체(entity)

• 현실 세계에서 조직을 운영하는데 꼭 필요한 사람이나 사물과 같이 구별되는 모든것
• 저장할 가치가 있는 중요 데이터를 가지고 있는 사람이나 사물, 개념, 사건 등등
• 다른 개체와 구별되는 이름을 가지고 있고, 각 개체만의 고유한 특성이나 상태, 즉 속성을 하나 이상 가지고 있음

속성(attribute)

• 개체가 가지고 있는 고유한 속성
• 의미 있는 데이터의 가장 작은 논리적 단위

관계(relationship)

• 개체와 개체가 맺고 있는 의미 있는 연관성

키(key)

• 각 테이블의 레코드(행)을 유일하게 식별하는 장치
• 기본키, 외래키 등

데이터 모델화

데이터 모델화란?

• 현실 세계에 존재하는 데이터를 컴퓨터 세계의 데이터베이스로 옮기는 변환 과정
• 데이터베이스 설계의 핵심 과정 (현실세계 → 추상화 → 모델화)
• 추상화는 복잡한 자료들이나 모듈 시스템으로부터 핵심적인 개념 또는 기능을 간추려낸것

데이터 관리 시스템

파일 시스템

• 데이터를 파일로 관리하기 위해 파일을 생성, 삭제, 수정, 검색하는 기능을 제공하는 소프트웨어

• 응용프로그램마다 필요한 데이터를 별도의 파일로 관리

파일 시스템의 단점

• 또 다른 응용프로그램에서 별도의 파일을 관리해야함
• 만약 하나의 파일로 통합할 때 문제 ⇒ 데이터 통합 - 데이터 베이스 시스템

관계 데이터 모델

• 테이블(table) : 하나의 개체에 대한 데이터를 2차원 테이블 구조로 저장한 것.
  • table = Relation(릴레이션)
• 속성(attribute) : 테이블의 열(column).
  • attribute = column = 필드 = 속성
• 투플(tuple) : 테이블의 행(row)
  • tuple = row = 레코드

key(키)

• 각 릴레이션(테이블)의 튜플(행)을 유일하게 식별하는 속성, 또한 릴레이션 간의 연결고리

기본키(primary key)

데이터 베이스 설계자에 의해 선택된 대표로 삼는 키

릴레이션의 특성을 반영하여 하나 선택

• 릴레이션 내 튜플을 식별할 수 있는 고유한 값을 가져야 한
• 동일한 값이 중복되어 저장될 수 X
• NULL 값은 허용 X

• 데이터를 필요에 따라 모아놓은 것
• 조직이나 개인이 사용하는 조작 가능한 저장된 데이터 모임

데이터 베이스의 특징

• 데이터베이스에는 특정 조식에 대한 정보가 포함
• 데이터베이스는 매우 클 수 있음
• 우리 삶의 모든 측면에 영향을 미친

데이터 VS 정보 VS 지식

데이터

• 실세계의 실체를 묘사하는 값
• 정형화되고 기록할 만한 가치가 있다고 판단되는 어떤 현상이나 사건에 대한 묘사
• 삼성전자 주가 : 7500,…

정보

• 데이터는 사실들 그 자체에 대한 일차적인 표현
• ⇒ 사실들과 이들로부터 유도될 수 있는 유추된 사실들
• 삼성전자 주가는 최근 3일간 하락중이다..(데이터를 분석하여 의미를 부여)

지식

• 데이터와 정보에 비해 좀 더 상위 수준의 개념
• 수동적이고 정적인 데이터나 정보에 비해 이들을 처리하는 “방법” 이나 어떤 근거에 의한 판단을 내리는데 필요한 분석과 판단에 대한 “법칙”등을 포함
• 과거 데이터와 비교해보면 특정 패턴이 반복되는 경향이 있다

현실세계 -추출→ 데이터 -처리→정보-추론→지식

데이터베이스의 정의

• 관련된 데이터의 모임 또는 집합
• 정형화 하고 조작 가능한 (처리하기 용이한) 컴퓨터에 저장된 데이터의 모임
• 특정 목적을 위해 계산, 저장, 검색, 정렬 등의 “데이터 처리” 작업을 수행
• 관계형 데이터는 모든 것을 테이블로 저장

→ 데이터 베이스란 어떤 특정 조직의 응용 시스템에 사용되는 조작 가능한 저장 데이터의 모습

일시적 데이터

• 해당 프로세스가 실행되는 동안만 일시적으로 존재 ex) 프로그램의 변수

영구적 데이터

• 어떤 프로세스의 생명주기에 종속적이지 않고 스스로 존재
• 비휘발성 매체에 저장
• 데이터베이스는 일반적으로 지속적인 데이터 모임 을 말함

DBMS : 데이터베이스 관리 시스템

컴퓨터에 저장되는 데이터베이스를 관리해주는 소프트웨어 시스템

• 데이터베이스 전문 관리 소프트웨어 (오라클 등)
• 많은 사람들끼리 공유 가능, 많은 데이터를 빠르고 쉽게 관리 가능
• 파일시스템으로는 다양한 사람들이 공유 X, 다량의 데이터 처리가 어려움 → DBMS의 필요성

DBMS가 제공하는 기능

• 정보를 표현할 수 있는 틀 = 데이터 모델
• 데이터 공유 기능
  • 데이터 중복의 제거 : 데이터를 공유함으로써 비효율성과 일관성(consistency) 문제를 제거

💡데이터 중복성 및 비일관성(불일치)

• 데이터 중복성 : 동일 한 데이터가 여러 파일에 중복 저장 ⇒ 저장공간 낭비, 접근 비용 증가
• 데이터 비일관성 : 동일한 데이터의 사본이 서로 다른 값을 저장, 불일치

• 동시성 문제 방지
  • DBMS는 하나의 단위 프로그램이 일을 마칠 때 까지 해당 데이터를 독점하도록 하여 동시성을 막음
• 데이터 무결성 유지
  • 무결성 : 데이터베이스 내의 데이터가 얼마나 정확한가
    • 데이터에 오류가 없어야함
• 데이터 독립성
  • 응용 프로그램과 데이터 간의 독립성
    • 응용프로그램은 데이터가 디스크에 구체적으로 어떻게 저장되어 있는지 몰라도 됨
  • 데이터에 종속적
    • 데이터의 구조와 저장형태를 바꾸려 하면 그 데이터를 사용하는 모든 응용프로그램을 바꿔야 함 →DBMS 사용으로 해결
• 원자성(쪼갤 수 없는 성질)
  • 과정 전체가 수행되던지 어떤 것 도 수행되면 안됨
• 효율적인 자원관리
• 데이터 보안성과 안정성 유지
  • 데이터를 소유한 사람이나 허가한 사람만 접근 가능

데이터 공유로 일어날 수 있는 문제

• 중복성
  • 동일한 데이터가 여러 파일에 중복 저장 → 저장공간 낭비, 접근 비용이 늘어남
• 비일관성
  • 동일한 데이터의 여러 사본이 서로 다른 값을 저장, 불일치
• 동시성
  • 프로세스가 동시에 같은 데이터 작업을 하려할 때 → 하나의 단위 프로그램이 일을 마칠 때 까지 독점하도록 하는 방법으로 문제를 해결
• 데이터 접근의 어려움
  • 파일 포멧의 다름, 데이터가 분산되어 관리 → 데이터 고립 발생 (검색의 어려움)

파일과 데이터 베이스

파일시스템

• 운영체제의 중요한 부분으로 데이터나 프로그램을 디스크에 읽고 쓸 수 있도록 해주는 프로그램

• 프로그램에서 다루는 데이터를 직접 하나의 파일에 저장하여 관리하는 경우 문제점

  • 프로그램 이외의 방법으로도 데이터 조작 가능

  • 프로그램과 데이터 형식이 묶여 있음

  • 동시 접근의 문제

  • 보안 문제

  • 장애 복구 문제

    ⇒ DBMS는 데이터베이스를 다루는 데 있어서 필요한 공통의 기능들을 제공하는 소프트웨어 시스템

파일시스템을 이용하는 DBMS

• 파일 시스템 : 기본적인 저장 기능만 제공
• DBMS : 데이터 관리에 필요한 다양한 기능 제공

파일시스템을 이용하는 DBMS

• 파일시스템 : 기본적인 저장 기능만

• DBMS : 데이터베이스 관리에 필요한 다양한 기능

• 최종 사용자

  • end user, general user
  • 응용프로그램이 제공하는 사용자 인터페이스 이용, 업무 처리
  • 숙련된 최종 사용자는 응용프로그램을 이용하지 않고 DBMS에서 직접 사용

• 응용프로그램 개발자

  • application programmer
  • DBMS를 이용한 응용프로그램을 개발하는 사람

• 데이터베이스 관리자

  • DataBase Administrator (DBA)
  • DBMS 및 이와 관련된 하드웨어, 소프트웨어를 중앙에서 관리 감독하는 사람

• DBMS 개발자

  • DBMS developer
  • DBMS를 구성하는 모듈들을 설계, 구현

https://www.acmicpc.net/problem/15889

문제 이해

• 전우 N명이 수직선 상에 일렬로 서 있고, 욱제는 항상 pos[0] = 0에 위치함
• 각 전우는 자신의 사거리 범위 내 전우에게 수류탄을 던질 수 있음
• 수류탄이 마지막 전우(인덱스 N-1)까지 전달되면 성공, 중간에 멈추면 실패

문제 풀이 방법

그리디 + 스위핑 알고리즘

• 왼쪽부터 오른쪽으로 전우들을 순회하면서
• 현재까지 도달 가능한 최대 거리(maxReach)를 갱신
• 다음 전우가 maxReach보다 멀리 있으면 → 수류탄 떨어짐 → 실패

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] pos = new int[N];           // 위치 배열
        int[] range = new int[N - 1];     // 사거리 배열

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            pos[i] = Integer.parseInt(st.nextToken());
        }

        if (N > 1) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N - 1; i++) {
                range[i] = Integer.parseInt(st.nextToken());
            }
        }

        int maxReach = 0; // 현재까지 도달 가능한 가장 먼 위치
        int i = 0;        // 지금 탐색할 사람의 인덱스

        for (; i < N - 1 && pos[i] <= maxReach; i++) {
            int reach = pos[i] + range[i];     // 이 전우가 던질 수 있는 거리
            maxReach = Math.max(maxReach, reach); // 최대 도달 위치 갱신

            // 다음 전우가 pos[]에 정렬되어 있으므로 i만 증가
        }

        // 마지막 전우의 위치가 maxReach 이하라면 도달 가능
        if (pos[N - 1] <= maxReach) {
            System.out.println("권병장님, 중대장님이 찾으십니다");
        } else {
            System.out.println("엄마 나 전역 늦어질 것 같아");
        }
    }
}

코드 설명

int N = Integer.parseInt(br.readLine());
int[] pos = new int[N];
int[] range = new int[N - 1]; // 마지막 전우는 던지지 않음

• pos[i]: i번째 전우의 위치
• range[i]: i번째 전우가 수류탄을 던질 수 있는 거리
• N-1명까지만 사거리를 입력받는 이유는 마지막 전우는 ****던지지 않기 때문

for (int i = 0; i < N - 1 && pos[i] <= maxReach; i++) {

• i번째 전우의 위치가 maxReach보다 작거나 같아야만 도달 가능
• 만약 pos[i] > maxReach가 되먄, 수류탄 전달 불가 → break

int reach = pos[i] + range[i];

• i번째 전우가 수류탄을 던질 수 있는 최대 거리 계산

if (pos[N - 1] <= maxReach)
    System.out.println("권병장님, 중대장님이 찾으십니다");
else
    System.out.println("엄마 나 전역 늦어질 것 같아");

• 마지막 전우의 위치pos[N-1]가 현재까지의 maxReach보다 작거나 같으면 도달 가능
• 그 외의 경우는 전달 도중 수류탄이 바닥에 떨어진 것……

시간복잡도 : O(N)

https://www.acmicpc.net/problem/16969

문제 이해

• 차량 번호판 형식이 문자열로 주어짐 (c, d)
  • c: 알파벳 자리 → 가능한 경우의 수: 26개 (a~z)
  • d: 숫자 자리 → 가능한 경우의 수: 10개 (0~9)
• 같은 종류의 자리가 연속될 경우, 이전 값과 중복되면 안됨
  • 만약에 cc 가 나오면, 두 번째 c는 첫 번째와 다른 문자여야 하므로 경우의 수: 26 × 25
• 출력: 결과를 1,000,000,009로 나눈 나머지

문제 풀이 방법

• 현재 자리가 이전 문자와 같으면
  • 가능한 경우의 수는 중복 제거
    • d면 10 → 9가지 (앞 숫자와 다르게)
    • c면 26 → 25가지
• 이전 자리와 다르면
  • 중복 고려 X → 전체 가능성
    • d → 10가지, c → 26가지
• 결과는 매번 곱셈으로 누적 후 나누기

코드

import java.util.Scanner; 

public class Main {
    static final int MOD = 1_000_000_009; 

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); 
        String pattern = sc.nextLine(); 

        long result = 1; 

        // 번호판 형식의 각 자리를 순회
        for (int i = 0; i < pattern.length(); i++) {
            char current = pattern.charAt(i); // 현재 자리

            int choices = 0; // 현재 자리에 가능한 경우의 수

            // 현재 자리가 문자 자리일 경우
            if (current == 'c') {
                choices = 26; // 알파벳 26가지 가능
            } 
            // 현재 자리가 숫자 자리일 경우
            else if (current == 'd') {
                choices = 10; // 숫자 10가지 가능
            }

            // 이전 문자와 현재 문자가 같으면 중복 제거
            if (i > 0 && pattern.charAt(i) == pattern.charAt(i - 1)) {
                choices -= 1; // 같은 종류 연속 시 중복 제거 
            }

            // 가능한 경우의 수를 누적 계산, 나누기
            result = (result * choices) % MOD;
        }

        System.out.println(result);
    }
}

https://www.acmicpc.net/problem/16969

문제 이해

• 차량 번호판 형식이 문자열로 주어짐 (c, d)
  • c: 알파벳 자리 → 가능한 경우의 수: 26개 (a~z)
  • d: 숫자 자리 → 가능한 경우의 수: 10개 (0~9)
• 같은 종류의 자리가 연속될 경우, 이전 값과 중복되면 안됨
  • 만약에 cc 가 나오면, 두 번째 c는 첫 번째와 다른 문자여야 하므로 경우의 수: 26 × 25
• 출력: 결과를 1,000,000,009로 나눈 나머지

문제 풀이 방법

• 현재 자리가 이전 문자와 같으면
  • 가능한 경우의 수는 중복 제거
    • d면 10 → 9가지 (앞 숫자와 다르게)
    • c면 26 → 25가지
• 이전 자리와 다르면
  • 중복 고려 X → 전체 가능성
    • d → 10가지, c → 26가지
• 결과는 매번 곱셈으로 누적 후 나누기

코드

import java.util.Scanner; 

public class Main {
    static final int MOD = 1_000_000_009; 

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); 
        String pattern = sc.nextLine(); 

        long result = 1; 

        // 번호판 형식의 각 자리를 순회
        for (int i = 0; i < pattern.length(); i++) {
            char current = pattern.charAt(i); // 현재 자리

            int choices = 0; // 현재 자리에 가능한 경우의 수

            // 현재 자리가 문자 자리일 경우
            if (current == 'c') {
                choices = 26; // 알파벳 26가지 가능
            } 
            // 현재 자리가 숫자 자리일 경우
            else if (current == 'd') {
                choices = 10; // 숫자 10가지 가능
            }

            // 이전 문자와 현재 문자가 같으면 중복 제거
            if (i > 0 && pattern.charAt(i) == pattern.charAt(i - 1)) {
                choices -= 1; // 같은 종류 연속 시 중복 제거 
            }

            // 가능한 경우의 수를 누적 계산, 나누기
            result = (result * choices) % MOD;
        }

        System.out.println(result);
    }
}

https://www.acmicpc.net/problem/32403

문제 이해

• 전구 주기가 t라면 t, 2t, 3t,... 시점에 반짝임
• 모든 전구가 T초 시점에 동시에 반짝이어야 함 → 즉, 모든 전구의 주기가 T의 약수여야 함
• 전구 하나의 주기는 1초씩만 증가 or 감소 가능 (단, 1초 아래로는 감소 불가)
• 최소 조작 횟수를 구해야 함

문제 풀이 방법

• T의 약수를 모두 구함
• 각 전구마다 가장 가까운 T의 약수로 바꾸는 비용(조작 횟수)를 계산
• 전체 조합에서 최소 조작 횟수를 선택
• 모든 전구 : 가장 가까운 T의 약수로 바꾸는 최소 횟수 → min(abs(현재 주기 - 약수))

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();   // 전구 개수
        int T = sc.nextInt();   // 목표 시점

        int[] bulbs = new int[N];
        for (int i = 0; i < N; i++) {
            bulbs[i] = sc.nextInt();
        }

        // T의 약수 구하기
        ArrayList<Integer> divisors = new ArrayList<>();
        for (int i = 1; i <= T; i++) {
            if (T % i == 0) {
                divisors.add(i);
            }
        }

        // 최소 조작 횟수 구하기
        int result = 0;
        for (int bulb : bulbs) { // bulbs : 현재 전구의 원래 주기 값
            // 한 전구에 대해 최소로 변경해야하는 회수를 저장하는 변수
            int minChange = Integer.MAX_VALUE; 
            for (int divisor : divisors) {
                // 현재 전구 주기와 약수 간의 절댓값 차이를 구함 -> 두 값의 차 = 조작 회수
                int diff = Math.abs(bulb - divisor); 
                minChange = Math.min(minChange, diff); // 최소값으로 갱신
            }
            result += minChange; // 모든 전구에 대해 반복 -> 전체 최소 변경 횟수 계산
        }

        System.out.println(result);
    }
}

민겸이는 1 빼기를 할 수 있는 능력을 가지고 있다. 1 빼기란, 다음의 두 연산 중 하나를 골라 수행하는 것이다.

1. 가지고 있는 수에서 1을 뺀다.
2. 가지고 있는 수에 있는 1을 하나 지운다. 지우고 난 뒤 좌우의 수들을 순서대로 다시 합쳐 하나의 수로 만든다. 이때 맨 앞의 연속되는 0은 지워진다.

민겸이가 최초로 가지고 있는 정수가 하나 주어질 때, 이 수를 0으로 만들기 위해 최소 몇 번의 1 빼기가 필요한지 구해보자.

입력

민겸이가 가지고 있는 정수 N이 주어진다.

출력

민겸이가 해당 수를 0으로 만들기 위해서 최소 몇 번의 1 빼기가 필요한지 출력한다.

문제 이해

민겸이는 두 가지 방법으로 숫자를 줄일 수 있다.

1. 현재 숫자에서 1을 뺀다
2. 숫자 안에 있는 ‘1’을 하나 지운다.
3. 지운 뒤 남은 숫자들은 이어 붙이고, 맨 앞의 연속된 0은 모두 제거

민겸이가 가진 숫자 N이 주어질 때,

이 숫자를 0으로 만들기 위한 최소 연산 횟수를 구하는 문제

문제풀이 방법

• N이 0이 될 때까지 반복
• 현재 숫자에 '1'이 포함되어 있으면 → '1' 하나 제거
• 그렇지 않으면 → N = N - 1
• 연산 횟수를 1 증가
• N = 0이 되면 연산 횟수를 출력

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int count = 0;

        while (N != 0) {
            String strN = String.valueOf(N); // 문자열로 변환
            if (strN.contains("1")) { // 1 포함시
                // '1'을 하나 제거
                int index = strN.indexOf('1'); // 가장 맨 앞의 1의 위치를 찾음
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < strN.length(); i++) {
                    if (i != index) sb.append(strN.charAt(i)); // 해당 위치 문자열을 빼고 붙임
                }
                String resultStr = sb.toString().replaceFirst("^0+", ""); // 앞쪽 0 제거
                N = resultStr.isEmpty() ? 0 : Integer.parseInt(resultStr);
            } else {
                N--; // '1'이 없으면 -1
            }
            count++;
        }

        System.out.println(count);
    }
}

코드 설명

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int count = 0;

• 사용자로부터 N을 입력 받음
• 연산 횟수를 카운트하기 위해 count를 0으로 초기화

String strN = String.valueOf(N);
if (strN.contains("1")) {

• 현재 숫자 N을 문자열로 바꿔서 1이 포함되어 있는지 확인
• 1이 있으면 1 제거 , 없으면 -1

int index = strN.indexOf('1');
StringBuilder sb = new StringBuilder();
for (int i = 0; i < strN.length(); i++) {
    if (i != index) sb.append(strN.charAt(i));
}

• 가장 앞쪽의 1 위치인 index를 첮음

• 그 위치의 문자를 제외하고 나머지 문자들은 StringBuilder로 다시 이어붙임

  → 1을 하나 지운 숫자가 완성됨

String resultStr = sb.toString().replaceFirst("^0+", "");

• 어떻게 0으로 시작하면 지우지 고민하다가 정규표현식을 사용해도 된다는 걸 보고…
• 정규표현식 사용
• ^0+ → 문자열 처음부터 연속된 0 제거
• StringBuilder 객체인 sb를 toString()으로 문자열로 바꿈

N = resultStr.isEmpty() ? 0 : Integer.parseInt(resultStr);

• 만약 모든 숫자가 지워져서 빈 문자열이면 N = 0
• 아니면 문자열을 숫자로 변환해서 N에 저장

else {
    N--;
}

• '1'이 아예 없으면 -1 연산만 가능
• N--으로 1을 빼줌

https://www.acmicpc.net/problem/1138

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

문제이해

• 사람 N명 (키 = 1 ~ N, 중복 없음)
• 키 1인 사람부터 N인 사람까지, 본인보다 키 큰 사람이 왼쪽에 몇 명 있었는지 기억

이 기억 정보를 바탕으로 정확한 줄 서기 순서를 구하는 문제

문제 풀이 방법

1. 사람 수 N을 입력 받고, 각 사람이 기억하는 값(왼쪽 큰 사람 수)을 배열에 저장
2. 키 1부터 N까지 반복하면서, 그 사람이 기억하는 값(왼쪽 큰 사람 수)에 해당하는 위치에 ArrayList에 삽입
   1. 키가 작은 사람부터 넣어야 왼쪽에 이미 들어가 있는 키 큰 사람의 수를 판단할 수있음

💡 키가 작은 사람부터 넣어야하는 이유

키가 작은 사람 입장에서 자신보다 키가 큰 사람의 수를 기억하고 있음

큰 사람은 작은 사람에게는 영향이 없기 때문에

큰 사람 부터 자리배치를 하면 작은 사람이 들어와도 큰 사람의 위치가 변하지 않는 문제 발생….→ 이래서 처음에 에러남

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 사람 수 입력
        int[] arr = new int[N]; // 왼쪽에 키 큰 사람 수 정보 저장 배열

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt(); // 배열 초기화
        }

        ArrayList<Integer> line = new ArrayList<>(); // 최종 줄 배열

        // 키가 작은 사람부터 (1 ~ N) 넣는다.
        for (int height = N; height >= 1; height--) {
            // arr[height-1] : 이 사람보다 큰 사람이 왼쪽에 몇 명 있었는지
            line.add(arr[height - 1], height);
        }

       for (int person : line) {
            System.out.print(person + " ");
        }
    }
}```

https://leetcode.com/problems/permutation-sequence/description/

문제 해결 방식

1. 각 자리마다 가능한 순열의 범위는 남은 숫자들로 만들 수 있는 순열의 수로 정해짐
2. 현재 선택한 숫자로 만들 수 있는 순열 범위에 k가 속하지 않으면 다음 범위라는 뜻
3. 그 범위를 넘어가기 위해 k에서 그 범위(팩토리얼 값)를 빼줌
4. k가 범위 내에 속할 때까지 반복
5. k가 현재 범위에 속하면, 그 숫자가 확정되고, 해당 숫자를 사용된 것으로 표시
6. 확정된 숫자는 순열의 일부로 추가되고, 남은 숫자들로 다시 위 과정을 반복해 나머지 자리를 결정

Test Case 예시

예를 들어, n=4일 때 [1, 2, 3, 4]의 숫자로 만들 수 있는 모든 순열을 생각해 봅시다. 총 4! = 24개의 순열이 존재합니다.

첫 번째 자리 선택

첫 번째 자리에는 1, 2, 3, 4 중 하나가 올 수 있고, 첫 번째 숫자를 정하면 그 뒤로 나머지 3자리에 대해 3! = 6개의 순열이 나옵니다.

즉:

• 첫 번째 자리가 1일 때 나오는 순열: 1xxxx → 총 6개 (1 ~ 6번째 순열)
• 첫 번째 자리가 2일 때 나오는 순열: 2xxxx → 총 6개 (7 ~ 12번째 순열)
• 첫 번째 자리가 3일 때 나오는 순열: 3xxxx → 총 6개 (13 ~ 18번째 순열)
• 첫 번째 자리가 4일 때 나오는 순열: 4xxxx → 총 6개 (19 ~ 24번째 순열)

이제 예를 들어, k=9번째 순열을 구한다고 해봅시다.

1. 첫 번째 자리가 1이면, 순열은 1xxxx에서 나오는데 이는 1~6번째 순열에 해당하므로, k=9는 그 범위에 포함되지 않습니다. 그래서 첫 번째 자리는 1이 아니고, 우리는 그 범위를 넘어가야 하므로 k=9 - 6 = 3으로 갱신합니다.
2. 첫 번째 자리가 2이면, 순열은 2xxxx에서 나오는데 이는 7~12번째 순열입니다. 여기서 k=3은 해당 범위에 포함되므로, 첫 번째 자리는 2가 됩니다.

이 과정을 통해 첫 번째 자리를 결정한 것입니다.

두 번째 자리 선택

이제 첫 번째 자리가 2로 결정됐고, 나머지 자리의 숫자는 [1, 3, 4]입니다. 이제 두 번째 자리를 정해야 합니다.

남은 3자리에서 가능한 순열의 개수는 2! = 2입니다. 즉:

• 두 번째 자리가 1일 때 나오는 순열: 21xxx → 총 2개 (7~8번째 순열)
• 두 번째 자리가 3일 때 나오는 순열: 23xxx → 총 2개 (9~10번째 순열)

현재 k=3이므로, 두 번째 자리는 1이 아닌 3이 됩니다. 따라서 k=3 - 2 = 1로 갱신됩니다.

나의 코드

class Solution {
    public String getPermutation(int n, int k) {
        String ans = "";
        boolean[] vis = new boolean[n + 1];  // 숫자 사용 여부

        // n개의 숫자를 사용하여 순열을 구성
        for (int i = 0; i < n; ++i) {
            int fact = 1;  // 현재 자리에서 고려할 남은 자리수에 대한 팩토리얼을 계산

            // 남은 자리에 대한 팩토리얼 계산
            for (int j = 1; j < n - i; ++j) {
                fact *= j;
            }

            // 1부터 n까지의 숫자 중에서 순열을 선택
            for (int j = 1; j <= n; ++j) {
                // j가 아직 사용되지 않았다면
                if (!vis[j]) {
                    // 현재 자리의 팩토리얼보다 k가 크다면, 해당 순열 조합은 현재 범위를 넘어가므로 넘겨줌
                    if (k > fact) {
                        k -= fact;  // 해당 범위를 넘어갔으므로 k에서 팩토리얼 값을 빼줌
                    } else {
                        // 현재 자리에 j를 넣음
                        ans += j;  
                        vis[j] = true;  
                        break;  // 현재 자리에 숫자를 채웠으므로 다음 자리로 이동
                    }
                }
            }
        }
        return ans;  // 최종적으로 완성된 순열 반환
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/92334

문제 설명

신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.

• 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
  • 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
  • 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.
• k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.
  • 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다.

다음은 전체 유저 목록이 ["muzi", "frodo", "apeach", "neo"]이고, k = 2(즉, 2번 이상 신고당하면 이용 정지)인 경우의 예시입니다.

각 유저별로 신고당한 횟수는 다음과 같습니다.

위 예시에서는 2번 이상 신고당한 "frodo"와 "neo"의 게시판 이용이 정지됩니다. 이때, 각 유저별로 신고한 아이디와 정지된 아이디를 정리하면 다음과 같습니다.

따라서 "muzi"는 처리 결과 메일을 2회, "frodo"와 "apeach"는 각각 처리 결과 메일을 1회 받게 됩니다.

이용자의 ID가 담긴 문자열 배열 id_list, 각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report, 정지 기준이 되는 신고 횟수 k가 매개변수로 주어질 때, 각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 2 ≤ id_list의 길이 ≤ 1,000
  • 1 ≤ id_list의 원소 길이 ≤ 10
  • id_list의 원소는 이용자의 id를 나타내는 문자열이며 알파벳 소문자로만 이루어져 있습니다.
  • id_list에는 같은 아이디가 중복해서 들어있지 않습니다.
• 1 ≤ report의 길이 ≤ 200,000
  • 3 ≤ report의 원소 길이 ≤ 21
  • report의 원소는 "이용자id 신고한id"형태의 문자열입니다.
  • 예를 들어 "muzi frodo"의 경우 "muzi"가 "frodo"를 신고했다는 의미입니다.
  • id는 알파벳 소문자로만 이루어져 있습니다.
  • 이용자id와 신고한id는 공백(스페이스)하나로 구분되어 있습니다.
  • 자기 자신을 신고하는 경우는 없습니다.
• 1 ≤ k ≤ 200, k는 자연수입니다.
• return 하는 배열은 id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

"ryan"이 "con"을 4번 신고했으나, 주어진 조건에 따라 한 유저가 같은 유저를 여러 번 신고한 경우는 신고 횟수 1회로 처리합니다. 따라서 "con"은 1회 신고당했습니다. 3번 이상 신고당한 이용자는 없으며, "con"과 "ryan"은 결과 메일을 받지 않습니다. 따라서 [0, 0]을 return 합니다.

접근 방식

1. 신고자와 신고당한 사람 간의 관계, 사용자의 인덱스와 이름을 각각 HashMap 을 사용해 저장
2. report 배열을 반복하여 각 신고 정보를 처리, → 신고한 사람(a)과 신고당한 사람(b)
3. reportMap에 b(신고당한 사람)를 키로 하는 HashSet을 생성하거나 가져오고, 신고한 사람 a를 이 집합에 추가
4. 동일한 신고자가 여러 번 신고하는 경우에도 중복 제거하여 한 번만 추가.
5. reportMap 에서 신고당한 사람의 신고 수가 k 이상일 경우, 그 사람을 신고한 모든 사람에 대해 메일 수를 증가시킴

나의 코드

import java.util.*;

public class Solution {
    public static int[] solution(String[] id_list, String[] report, int k) {

        int len = id_list.length; // id_list의 길이
        HashMap<String, Integer> indexMap = new HashMap<>(); // 유저 이름과 인덱스를 저장
        HashMap<String, HashSet<String>> reportMap = new HashMap<>(); // 신고당한 사람과 신고한 사람들 저장
        int[] mailCountArr = new int[len]; // 메일 전송 개수를 저장하는 배열

        // 유저별 인덱스 설정
        for (int i = 0; i < len; i++) {
            indexMap.put(id_list[i], i); // 유저 이름을 키로 하고 인덱스를 값으로 저장
        }

        // 신고 정보 저장
        for (int i = 0; i < report.length; i++) {
            String a = report[i].split(" ")[0]; // 신고한 사람
            String b = report[i].split(" ")[1]; // 신고당한 사람

            // 신고당한 사람을 key로 하는 HashSet을 가져오거나, 없으면 새로 생성하여 초기화
            reportMap.put(b, reportMap.getOrDefault(b, new HashSet<>())); 
            reportMap.get(b).add(a); // 신고한 사람을 해당 신고당한 사람의 HashSet에 추가, 중복제거
        }

        // 메일 전송 대상 선별
        for (String stopName : reportMap.keySet()) {
            if (reportMap.get(stopName).size() >= k) { // 신고당한 사람이 k번 이상 신고받았을 경우
                for (String name : reportMap.get(stopName)) {
                    mailCountArr[indexMap.get(name)]++; // 신고한 사람의 메일 전송 개수를 증가
                }
            }
        }

        return mailCountArr; 
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/49994

접근 방식

1. 좌표계를 11x11 크기로 설정, 중앙인 (5,5)에서 시작
2. 각 명령어를 순서대로 처리하면서 새로운 좌표 (nr, nc)를 계산
3. 계산된 좌표가 보드 범위를 벗어나지 않는지 확인한 후, 유효한 범위 내에 있을 때만 이동을 수행
4. 이동하려는 좌표가 이전에 방문한 적이 없는 경로인지를 확인
5. 경로는 양방향이므로, 반대방향에서 오는 경우도 방문 처리
   1. 위 ↔ 아래, 왼↔오
      1. 짝수 방향 (U와 D)는 2 - d 2- 0 = 2, 2 - 2 = 0
      2. 홀수 방향 (L과 R)은 4 - d 4 - 1 = 3, 4 - 3 = 1
6. 새로운 경로일 경우, answer 값을 증가시키고, 방문 기록을 남김

나의 코드

class Solution {

    static int dr[] = {-1, 0, 1, 0};  // 행(row) 이동 방향
    static int dc[] = {0, -1, 0, 1};  // 열(column) 이동 방향

    public int solution(String dirs) {
        int answer = 0; 
        int map[][] = new int[11][11]; 
        boolean visit[][][] = new boolean[11][11][4]; // 방문 여부 [행][열][방향]

        // 시작 좌표 (5, 5)
        int r = 5; 
        int c = 5;

        for (int i = 0; i < dirs.length(); i++) {
            // 처리할 명령어를 하나씩 가져옴
            char cc = dirs.charAt(i);

            int d = 0; // 이동 방향을 저장할 변수
            if (cc == 'U') // 위
                d = 0;
            if (cc == 'L') // 왼쪽
                d = 1;
            if (cc == 'D') // 아래
                d = 2;
            if (cc == 'R') // 오른쪽
                d = 3;

            // 새로운 좌표
            int nr = r + dr[d];
            int nc = c + dc[d];

            // 범위 밖으로 나가면
            if (nr < 0 || nc < 0 || nr >= 11 || nc >= 11)
                continue;

            // 방문하지 않았다면
            if (!visit[nr][nc][d]) {
                // 방문처리
                visit[nr][nc][d] = true;

                // 반대 방향에도 방문처리
                // 짝수라면 -> 위 아래, 홀수라면 -> 왼 오
                d = (d % 2 == 0) ? 2 - d : 4 - d;
                visit[r][c][d] = true;

                // 새로운 경로, answer 증가
                answer++;
            }

            // 좌표 갱신
            r = nr;
            c = nc;
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42578

접근 방식

1. 의상의 종류별로 HashMap을 사용해 각 종류의 의상 수를 저장
2. 의상 종류가 처음 등장할 경우 1(아무것도 입지 않는 경우 포함)을 기본값으로 설정
3. 그 이후 등장할 때마다 1씩 더함

<의상 조합>
각 의상 종류마다 의상 수 + 1 (해당 종류의 의상을 입지 않는 경우 포함)을 곱함

4. 모든 종류에 대해 곱을 구한 후 1을 뺌 -> 아무것도 입지 X

map.getOrDefault

특정 키에 해당하는 값을 가져오되, 해당 키가 맵에 존재하지 않을 경우 기본값을 반환

map.getOrDefault(Object key, V defaultValue)

• key: 찾고자 하는 키.
• defaultValue: 만약 맵에 해당 키가 없을 경우 반환할 기본값.

동작 방식

1. map.get(key)를 호출해서 해당 키가 존재하면 그 값을 반환
2. 만약 해당 키가 맵에 없으면 기본값(defaultValue)를 반환

나의 코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> map = new HashMap<>();

        // 옷의 종류별로 카운트
        for(int i = 0; i < clothes.length; i++){
            // map에 옷의 종류를 키로 저장, 기본값은 1 (착용하지 않는 경우 포함)
            map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 1) + 1);
        }

        // 모든 의상 종류의 조합을 계산
        for(Integer value : map.values())  {
            answer *= value;
        }

        // 아무것도 입지 않는 경우를 제외해야 하므로 -1
        return answer - 1;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/84512

접근 방식

1. 가능한 모든 조합을 만들어 저장
2. 재귀적으로 반복
3. 모음 조합은 최대 5자리까지, 깊이가 5 이면 재귀 중단
4. 각 생성된 문자열은 리스트에 추가
5. word와 비교하여 몇번재에 위치하는지 찾음

나의 코드

import java.util.*;

class Solution {

    // 모음 배열
    String[] vowels = {"A", "E", "I", "O", "U"};
    // 모든 가능한 조합을 저장할 리스트
    ArrayList<String> list = new ArrayList<>();

    public int solution(String word) {
        int answer = 0;

        // 재귀함수를 이용해 모든 조합을 찾음
        findWord("", word, 0);

        // list에서 해당 단어의 인덱스를 찾아 반환
        for(int i=0; i<list.size(); i++){
            if(word.equals(list.get(i))){
                answer = i;
            }
        }

        return answer;
    }

    // 재귀적으로 단어 조합을 생성하는 함수
    void findWord(String str, String target, int depth){
        // 현재 생성된 단어를 리스트에 추가
        list.add(str);

        // 단어 길이가 5글자에 도달하면 더 이상 재귀하지 않음
        if(depth == 5) return;

        // 모음 배열을 돌며 재귀적으로 단어를 생성
        for(int i=0; i<vowels.length; i++){
            findWord(str + vowels[i], target, depth+1);
        }
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12953

My Solution

• 배열의 첫 번째 원소부터 순차적으로 두 수씩 계산하여 최소공배수를 구함
• 두 수의 최소공배수는 arr[i+1] = (arr[i] * arr[i+1]) / getGCD(arr[i], arr[i+1])로 구함
• 마지막 계산된 값이 배열의 모든 원소의 최소공배수
• getGCD 함수는 유클리드 호제법을 사용하여 두 수의 최대공약수를 재귀적으로 구함

나의 코드

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        Arrays.sort(arr); // 배열을 오름차순 정렬

        // 반복문을 통해 배열의 최소공배수를 구함
        for (int i = 0; i < arr.length - 1; i++) {
            // 두 수의 최대공약수 구하기
            int gcd = getGCD(arr[i+1], arr[i]);
            // 두 수의 최소공배수를 계산
            arr[i+1] = (arr[i] * arr[i+1]) / gcd;
        }

        // 최종적으로 계산된 최소공배수를 반환
        return arr[arr.length - 1];
    }

    // 유클리드 호제법을 사용하여 최대공약수(GCD) 구하는 함수
    public static int getGCD(int n1, int n2) {
        if (n1 % n2 == 0) {
            return n2;
        }
        return getGCD(n2, n1 % n2);
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42842

접근 방법

• 카펫의 전체 크기는 갈색 격자와 노란색 격자를 합친 수.
• 가로와 세로 길이를 구할 때, 가로 ≥ 세로 조건을 만족해야 함
• 테두리를 갈색으로 둘러싸고 내부를 노란색으로 채운 형태이므로, 전체 격자 수 - 테두리가 노란색 격자의 수와 일치해야 함
• 가능한 가로, 세로 길이 조합 중에서 위 조건을 만족하는 값을 찾아 반환

나의 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        // 답을 저장할 배열, answer[0]은 가로(width), answer[1]은 세로(height)
        int[] answer = new int[2];

        // i는 카펫의 세로 길이, 최소 3부터 시작 (최소 크기의 카펫은 3x3)
        for(int i = 3; i < brown + yellow; i++) {
            // 가로 길이 width는 전체 타일 수(brown + yellow)를 i로 나눈 몫
            int width = (brown + yellow) / i; 

            // 가로 길이는 세로 길이보다 크거나 같아야 하므로 이 조건을 확인
            if (width >= i) {
                // 테두리를 제외한 내부 영역의 크기가 노란색 타일 수와 같은지 확인
                // 즉, 카펫의 테두리(갈색 타일)를 제외한 내부가 정확히 노란색 타일로 채워졌는지 확인
                if ((i - 2) * (width - 2) == yellow) {
                    // 조건을 만족하면 answer 배열에 가로와 세로 값을 저장
                    answer[0] = width; // 가로
                    answer[1] = i;     // 세로
                    break;
                }
            }
        }
        return answer;
    }
}