문제 : 백준 9465: 스티커

• 2*n 행렬의 스티커가 있고, 스티커는 0~100사이 정수값을 가짐
• 한 스티커를 선택하면 해당 스티커와 인접한 좌우상하의 스티커는 사용할 수 없음
• 최대 점수가 되는 스티커 조합의 점수를 결과로 출력
• 1 <= n <= 100,000

접근 방법

• n이 10만까지의 값을 가지므로 n^2의 시간복잡도는 불가 -> 이중 for문이 있으면 안되겠다.
• 스티커의 모든 점수는 양수이기에 스티커를 선택할 수 있다면 선택하는게 무조건 좋다.
• 2*n 이라고 할때 2 *(n-1)의 결과값을 이용할 수 있을까?
  • [0][n]을 선택하는 경우, [0][n-1] 스티커는 사용 불가, [1][n-1] 스티커 사용 가능
  • 또는 [*][n-1] 스티커는 선택하지 않고, [1][n-2] 스티커 사용 가능
  • 두 값을 비교하여 최대값을 선택하면 됨.

📌제출코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int T;

    cin >> T;

    for (int t=0; t<T; t++){
        int n;
        cin >> n;

        int arr[2][100001] = {0,};
        int dp[2][100001] = {0, };
        int result = 0;

        for (int i = 1; i <= n; i++){
            cin >> arr[0][i];
        }
        for (int i = 1; i <= n; i++){
            cin >> arr[1][i];
        }

        if (n == 1){
            result = max(arr[0][1], arr[1][1]);
            cout << result << '\n';
            continue;
        }
        if (n == 2){
            result = max(arr[0][1]+arr[1][2], arr[1][1]+arr[0][2]);
            cout << result << '\n';
            continue;
        }

        dp[0][1] = arr[0][1];
        dp[1][1] = arr[1][1];
        dp[0][2] = arr[0][2] + arr[1][1];
        dp[1][2] = arr[1][2] + arr[0][1];


        if (n >= 3){
            for (int i = 3; i <= n; i++){
                dp[0][i] = arr[0][i] + max(dp[1][i-1], dp[1][i-2]);
                dp[1][i] = arr[1][i] + max(dp[0][i-1], dp[0][i-2]);
            }
            result = max(dp[0][n], dp[1][n]);
            cout << result << '\n';
        }
    }
    return 0;
}

관계형 데이터베이스

데이터를 어떤 목적에 따라 가공하여 유용한 정보로 변환 이러한 데이터를 일정한 체계에 따라 통합하여 디스크나 메모리에 저장한 것을 데이터베이스라고 함. 응용 프로그램에 종속적이지 않도록 미들웨어 형태로 만든 것.

데이터베이스를 구축하고 관리할 수 있는 기능을 제공하는 시스템 소프트웨어를 데이터베이스 관리 시스템(DBMS)라고 함

관계형 데이터베이스

2차원 구조의 행과 열로 구성된 테이블 형태

• 연산을 수학적으로 최적화할 수 있음

• SQL(Structured Query Language)라는 공통의 질의언어를 정의하여 정보를 다룰 수 있음

• table

• 스키마 = 칼럼헤더

• column = 필드(속성) = attribute

• row = 레코드 = tuple

SQL(Structured Query Language)

수학적 이론을 바탕으로 원하는 결과 ㅈ데이터를 추출할때 사용하는 명령문 데이터베이스의 구조를 정의하고, 데디터를 조작하고, 데이터를 정의할 수 있는 절차적(How) + 비절차적(What) 언어

• DDL (데이터 정의언어)

• 데이터의 구조(스키마)를 정의하는 명령어

• create, alter, drop, rename, truncate

• DDL 명령어는 오라클에서는 커밋이 자동으로 수행되어 롤백 불가하고, SQL서버에서는 자동커밋모드를 끄거나 명시적 트랜잭션을 선언하는 경우 롤백 가능

• DML (데이터 조작 언어)

• 데이터 조회, 입력, 수정, 삭제

• 커밋 전에 롤백이 가능

• selet, insert, update, delete, merge

SELECT문

특정 열을 조회할 수 있음

F W G H S O → 해당 순서로 처리됨

• select [칼럼] from [테이블]
• 테이블 뒤에 별명은 공백으로, 속성 뒤에 별명은 as로
• 산술 연산자 : ( ), *, /, %, +, -
• Null과 산술연산 결과는 Null. 0으로 나누는 경우는 오류
• 합성 연산자 : ||
• 문자열을 연결하 때 사용

함수

• lower(문자열) / upper(문자열) : 소문자로/대문자로

• chr(ASCII코드값) : 아스키코드에 해당하는 문자로 반환

• trim(?방향, ?제거할 문자, 문자열): 문자열에서 공백 또는 특정 문자열 제거

• 방향은 leading, tailing, both가 있음. both가 기본값

• 제거할 문자는 공백이 기본값

• ltrim, rtrim : 왼쪽/오른쪽 끝에서 trim

• substr(문자열, 시작점, ?길이) : 시작점에서 길이만큼 문자열 반환

• length(문자열) : 문자열 길이 반환

• replace(문자열, 변경 대상, ?변경 후) : 특정 문자열을 찾아 변경

• abs(숫자) : 절대값 반환

• mod(숫자1, 숫자2) : 1을 2로 나눈 나머지

• round(숫자, ?소수점 정수) : 반올림

• trunc(숫자, ?소수점 정수) : 버림

• sign(숫자) : 양수는 1, 음수는 -1, 0은 0

• ceil(숫자) : 크거나 같은 최소 정수

• floor(숫자) : 작거나 같은 최소 정수

• sysdate : 오늘 날짜를 날짜형으로 반환

• extract(avg from 날짜) : 날짜의 특정 부분 추출

• avg = year/month/day/hour/minute/second

• to_number, to_char, to_date : 형변환

• 암시적 형변환도 있으나 성능 저하나 에러를 가져올 수 있어 명시적 형변환이 좋음

• nvl(avg1, avg2) : (avg1 != Null) ? avg1 : avg2

• nullif(avg1, avg2) : (avg1 == avg2) ? Null : avg1

• coalsce(list…) : 인자를 순서대로 평가하여 Null이 아닌 첫번째 인자 반환

• case when [칼럼] = 값1 then 값A … (else 값N) end case [칼럼] when 값1 then 값A … (else 값N) end : 칼럼이 특정 값을 가지면 이를 새 값으로 대체하여 반환

WHERE절

select, update, delete에 사용 가능. insert에는 사용 불가 from 절에서 정의한 별명 사용 가능.

where [조건식]

• 단일행 비교 연산자 : =, <, <=, >, >=, is null

• 다중행 비교 연산자

• in : 리스트 중 동일한 값이 하나라도 있으면 참

• exists : 서브쿼리의 결과가 한 건이라도 있으면 참

• all : 모두 참이면 참

• any : 하나라도 참이면 참

• 단일행 부정 비교연산자 : !=,^=, <>, is not null

• 다중행 부정 비교연산자

• not in : 리스트 중 동일한 값이 하나도 없으면 참

• not exists : 서브쿼리의 결과가 한 건도 없으면 참

• between A and B : A보다 크거나 같고 B보다 작거나 같으면 참

• like : 패턴 문자열 검색. %는 0개 이상의 문자, _는 1개의 문자를 의미함

• not between A and B : A보다 작거나 B보다 크면 참

• not like : 패턴과 매칭되는 것이 하나도 없으면 참

• and, or, not

GROUP BY, HAVING절

group by를 통해 데이터를 그룹핑 할 수 있음

그룹핑한 다음에 해당 그룹에 대해 집계함수를 사용하여 통계값을 구할 수 있음

• count, sum, avg, min, max
• 중첩된 집계함수의 경우 결과는 1건이 됨
• avg(*)는 불가

having으로 필터링할 조건을 명시할 수 있음. 그룹핑 후에 수행됨. (where절은 집계함수를 사용할 수 없음)

ORDER BY절

칼럼을 조회할 때 정렬을 수행함

order by 칼럼 (ASC/ DESC)

• 기본은 오름차순으로 정렬

조인

두 테이블을 하나로 병합하는 것

• 두 테이블 간 PK와 FK의 연관성에 의해 성립하거나

• 연관성이 없더라도 논리적인 값들의 연관만으로도 조인을 성립할 수 있음

• 조인은 O(N^2)의 시간복잡도를 가짐

• equi join

• 칼럼값이 정확하게 일치할때 성립 where절 조건이 등식인 경우

• non equi join

• where 절 조건이 등식이 아닌 부등식인 경우

• 3개 이상의 테이블을 조인하는 경우 n개의 테이블에 대해서 n-1개의 조인이 발생

• outer join

• 조건에 맞는 행만 병합된 것을 inner join이라고 함

• 조건에 맞지 않는 행까지 병합한 것을 outer join이라고 함 (left outer join, right outer join, full outer join)

표준 조인

DBSM 별 SQL문을 따로 사용하는 불편을 줄이기 위해 표준 문법(ANSI SQL) 사용.

표준 조인에서는 기준조건은 where절이 아닌 on절을 사용하여 from에 조인 종류를 명시함.

• from [t.name] (join) [t.name] on 조건;

• inner join : 교집합 개념. (null이 없도록 조인) 기준이 되는 키에 따른 칼럼값이 존재하는 것만 병합

• outer join : 합집합 개념

  • left outer join : 왼쪽 테이블의 모든 행을 포함시키면서 조일
  • right outer join : 오른쪽 테이블의 모든 행을 포함시키면서 조인
  • full outer join : 왼쪽과 오른쪽의 모든 행을 포함시키면서 조인

• natural join : 같은 이름의 칼럼에 대해서는 동일한 칼럼값을 가진 행만 병합되는 조인 SQL server는 지원 안함. on 절을 사용할 수 없음.

• cross join : 왼쪽 테이블의 각 행에 대해 오른쪽 테이블 모든 행의 대응을 조합하여 결과 출력 M*N개의 행이 생성됨 (모든 경우의 수) where절 없이 from절에 테이블을 나열하면 cross join이 됨

1. 정규화

• 데이터베이스 이상현상 (Anomaly) : 데이터를 입력, 수정, 삭제하는 과정에서 일관성이 깨지는 경우
  • 삽입이상
  • 데이터 삽입 시 의도하지 않은 정보까지 삽입
  • 갱신이상
  • 중복 저장된 데이터 중 하나만 갱신
  • 삭제이상
  • 데이터 삭제 시 의도하지 않은 정보까지 삭제

⇒ 이러한 문제를 방지하기 위해 중복을 최소화하며 테이블을 잘 조직된 상태로 분해하는 과정을 정규화라고 함

제1정규형

모든 속성이 하나의 속성값을 가지는 상태 (atomic values) (속성의 원자성 확보)

제2정규형

주식별자가 복합식별자인 경우, 일반속성이 주식별자의 일부에만 종속성을 가질 때(→ 부분 함수종속성), 이를 제거한 상태

(ex)

(함수종속성)

[관서번호, 납부자번호] → {직급명, 통신번호} [관서번호] → {관서명, 관서등록일자}

(테이블)

관서번호, 납부자번호 | 관서명, 관서등록일자, 직급명, 통신번호

⇒ 2차 정규화를 하면

관서번호 | 관서명, 관서등록일자 납부자번호, 관서번호 | 직급명, 통신번호

제3정규형

주식별자가 아닌 일반 속성간 함수종속성이 존재 (→ 이행함수종속성), 이를 제거한 상태

a→ b, b→c 이면 a→c 관계가 성립 제3정규화의 수행 결과 분리된 엔터티들은 서로 비식별자 관계임

2. 관계와 조인의 이해

정규화로 테이블이 분해된 상황에서는 조회 시 조인 발생이 많아지면서 성능이 떨어질 수 있음 데이터 정합성과 조회성능 간 트레이드 오프 관계가 성립

성능 데이터 모델링

1. 데이터 모델링 시 정규화를 정확하게 수행
2. 데이터베이스 용량산저을 수행
3. 발생되는 트랜잭션의 유형 파악
4. 용량과 트랜잭션의 유형에 따라 반정규화 수행
5. 이력모델의 조정, PK/FK 조정, 슈퍼타입/서브타입 조정 등을 수행
6. 성능관점에서 데이터 모델을 검증

테이블의 반정규화

데이터의 조회성능이 중요한 경우 반정규화가 필요

데이터의 중복을 허용하거나 데이터를 그룹핑하여 조회성능을 높임

반정규화 수행 절차

1. 반정규화 대상 조사 : 범위처리 빈도수 조사, 통계성 프로세스 조사, 테이블 조인 개수 등
2. 다른 방법 검토 : 뷰 테이블 생성, 인덱스 조정, 클러스터링 적용, 응용 애플리케이션에서의 처리 등 대안 검토
3. 반정규화 적용

1. 테이블 병합

발생빈도가 높아서 아예 하나로 합치는 것

※ 슈퍼타입/서브타입 관계 테이블 병합

2. 테이블 분할

• 수직분할 : 한 테이블에 너무 많은 칼럼이 존재하는 경우. 특정 속성에만 접근이 빈번한 경우.
• 수평분할 : 속성값에 따라 구분하여 조회하는 경우. 스키마는 원래 테이블과 동일.

3. 테이블 추가

• 중복 테이블 추가 : 다른 업무에 있는 테이블과 동일한 구조의 테이블을 추가하여 원격 조인을 제거
• 통계 테이블 추가 : 통계값 연산을 미리 계산하여 저장하는 테이블 추가
• 이력 테이블 추가 : 변경 이력 등 이력 데이터 관리를 위한 테이블 추가
• 부분 테이블 추가 : 디스크 I/O를 줄이기 위한 방법으로 특별히 자주 사용하는 속성만 모아서 추가

칼럼의 반정규화

1. 중복 칼럼 추가 : 조인을 감소시키기 위해 자주 사용하는 칼럼을 추가
2. 파생 칼럼 추가 : 트랜잭션 처리 시 계산에 의한 부하를 줄이기 위해 계산값을 별도의 칼럼으로 추가
3. 이력 테이블 칼럼 추가 : 이력 테이블에 조회 조건에 해당하는 기능성 칼럼 추가
4. PK에 의한 칼럼 추가 : PK를 파싱해서 추가적인 내용을 조회하는 경우 이를 일반속성으로 추가
5. 응용 시스템 오작동을 위한 칼럼 추가 : 이전 데이터를 임시적으로 중복하여 보관하는 기법 (백업 데이터)

관계의 반정규화

여러 관계를 거쳐 다수의 조인을 통해 처리가 가능하지만 중복된 관계를 추가로 맺음

3. 트랜잭션의 이해

All or Nothing 작업이 완전하게 처리되거나 전혀 처리되지 않아야 함. 중간에 미완결된 상태로 중단되어서는 안됨

트랜잭션 관련 명령

• commit - 작업을 정상처리 완료 후에 DB 반영
• rollback - 작업 취소하고 이전상태로
• savepoint - 부분 작업 취소를 위한 저장점 지정

트랜잭션 특성

데이터를 읽고 쓸 때 한번에 수행되어야하는 논리적 작업단위

• 원자성
• all or nothing
• 일관성
• 트랜잭션 이전에 오류가 없다면 트랜잭션 이후에도 오류 없음
• 고립성
• 독립적으로 수행되어 다른 트랜잭션이 간섭하거나 영향을 미치지 않음
• 영속성
• 트랜잭션의 결과는 데이터베이스에 영구적으로 저장

트랜잭션 격리수준이 낮을때는

• dirty read
• non-repeatable read
• phantom read 문제가 생길 수 있음

4. NULL

값이 입력되지 않은 상태. 값이 없는 상태 0과 공백과 문자열 “NULL”과 다른 상태임

5. 본직식별자 & 인조식별자

본질식별자 : 업무에 존재하는 원래 식별자

인조식별자 : 원래 존재하지는 않지만 업무가 복잡하여 인위적으로 만든 식별자

읹조식별자를 주식별자로추가하는 경우 추가적인 연산없이 시퀀스나 키 제약조건 등을 통해 주식별자를 생성할 수 있어 편의성이 향상됨.

반면 데이터 중복이 발생하고 별도의 인덱스 생성 등이 필요하다는 단점있음.

1. 모델링

모델링

: 현실세계를 대상의로 일종의 모델(모형)을 만드는 것. 약속된 표기법에 따라 도식화 해야 함. 업무의 흐름을 가시화하고 명세화하기 위함(업무 형상화) 또한 모델링은 추상화를 기본으로 함 필요한 수준에서 데이터를 추상화하여 단순명료하게 표현하는 것이 중요

• 데이터 모델링 : 정보시스템을 구축하기 위해 데이터베이스를 설계하는 것

  특징

• 추상화 : 대상의 주요 특징을 추출하여 일정한 형식으로 표현
• 단순화 : 현실세계를 그대로 표현하지 않고 단순하게 표현
• 명확화 : 모델링 결과를 보는 사람이 같은 해석을 할 수 있도록 모홈함이 없게 기술

따라서 데이터 모델링이란 일정한 표기법을 사용하여 대상이 되는 데이터를 추상화, 단순화, 명확화하여 표현하는 것

유의사항

• 중복 최소화 : 같은 정보 중복하여 저장하지 않음
• 비유연성 최소화 : 데이터 정의와 데이터 사용 프로세스 분리
• 비일관성 최소화 : 연관관계를 명확하게 정의하여 데이터가 일관성있게 유지되어야 함

모델링 관점

• 데이터 관점 : 데이터에 집중. 정적분석, 구조분석 등을 기반으로 함
• 프로세스 관점 : 업무 흐름에 집중. 동적분석, 도메인분석 등을 기반으로 함
• 데이터와 프로세스의 상관 관점 : 데이터와 프로세스가 서로 어떻게 관계를 맺고 영향을 주고받는지. CRUD 분석을 기반으로 함

모델링 단계

• 개념적 데이터 모델링 : 가장 높은 추상화 레벨. 업무와 개념 중심으로 포괄적인 수준에서 모델링. 엔터티와 속성 도출(EA 수립)
• 논리적 데이터 모델링 : 데이터 모델의 키, 속성, 관계 등을 표현. 서로 다른 DBMS에 적용 가능한 수준의 추상화 단계. 중복 데이터 최소화, 식별자 도출 및 관계 정의.
• 물리적 데이터 모델링 : 특정 DBMS에 맞추어 구현. 가장 낮은 수준의 추상화 레벨. 테이블, 인덱스, 함수 등을 생성.

ANSI-SPARC 3단계 스키마 구조

데이터 독립성을 보장하기 위한 설계방법

• 외부 스키마 : 사용자 관점. 사용자 또는 애블리케이션(응용 프로그래머)이 바라보는 데이터베이스 스키마 정의. 다중 사용자 뷰

• 개념 스키마 : 설계자 관점. 몯느 사용자가 바라보는 데이터베이스 스키마를 통합. 통합된 뷰

• 내부 스키마 : 개발자 관점(DBMS의 SQL문을 작성하는). 디스크나 메모리 상의 물리적, 실질적 저장구조. 물리적 뷰

  논리적 데이터 독립성 : 외부 스키마와 개념 스키마 간의 독립성 물리적 데이터 독립성 : 개념 스키마와 내부 스키마 간의 독립성

ERD (Entity Relationship Diagram)

데이터 모델링에 대한 문서화 방법 (여러가지 표기법이 있지만 해당 책에서는 IE 표기법 사용)

• 엔터티 : 박스로 표현. 엔터티 이름은 박스 상단에 표시.
• 속성 : 박스 안에 리스트로 표현. 주식별자와 일반 속성은 칸막이로 구분
• 관계 : 박스를 연결한 선으로 표현. 식별자 관계는 실선, 비식별자 관계는 점선.
• 카디널리티 : O은 0, 세로 실선은 1, 까치발 모양은 다수(2 이상)를 의미.

작성순서

엔터티 도출 - 엔터티 배치(중요한 엔터티는 왼쪽 상단) - 관계 설정 - 관계명 기술 - 참여도 기술 - 필수,선택 여부 기술

2. 엔터티 (Entity)

엔터티

데이터베이스 구성요소 중 독립적으로 식별 가능한 객체 속성이라는 하위요소를 가짐

특징

• 업무에 필요로 하고 관리하고자 하는 정보
• 유일한 식별자 가짐
• 영속적으로 존재하는 인스턴스가 두 개 이상인 집합
• 하위요소로 반드시 속성을 가짐
• 다른 엔터티와 한 개 이상의 관계를 가짐(통계성 엔터티나 코드성 엔터티의 경우 관계 생략)

분류

(발생시점/상속관계에 따라)

• 기본 엔터티 : 고유한 주식별자를 가지는 독립적으로 생성되는 엔터티
• 중심 엔터티 : 주식별자를 상속받아 생성되어 업무의 중심 역할을 하는 엔터티
• 행위 엔터티 : 두 개 이상의 엔터티를 상속받아 생성되는 엔터티

(물리적 형태 여부에 따라)

• 유형 엔터티 : 물리적 형태가 존재
• 개념 엔터티 : 개념적으로 정의
• 사건 엔터티 : 업무 수행중 발생하는 행위나 이벤트

교차 엔터티 : M:N 관계를 해소하기 위해 만들어진 엔터티

3. 속성 (Attribute)

속성

엔터티에 대해 자세하고 구체적인 정보를 나타내는 엔터티의 하위요소 속성은 자신이 가질 수 있는 속성값의 집합이라고 할 수 있음

하나의 엔터티 인스턴스에서 각각의 속성은 한 개의 속성값만을 가져야 함 만약 하나 이상의 속성값을 가지는 경우에 1차 정규화를 수행하여 한 개의 속성값만 갖도록 해야 함.

• 한 개의 엔터티는 두 개 이상의 인스턴스를 가짐
• 한 개의 엔터티는 두 개 이상의 속성을 가짐
• 한 개의 속성은 한 개의 속성값만 가짐

분류

(속성의 특성에 따라)

• 기본 속성 : 엔터티가 본래 가지고 있어야 하는 속성
• 설계 속성 : 본래 가지는 속성은 아니지만 설계 시 필요하다고 판단되어 도출된 속성
• 파생 속성 : 다른 속성으로부터 계산되거나 특정 규칙에 따라 변형되어 만들어진 속성

(구성방식에 따라)

• PK(Primary Key, 기본키) 속성 : 엔터티에서 인스턴스를 유일하게 식별할 수 있는 속성
• FK(Foreign Key, 외래키) 속성 : 관계를 통해 다른 엔터티의 속성을 가져와 포함시킨 속성
• 일반 속성 : PK나 FK가 아닌 나머지 일반 속성

도메인

속성이 가질 수 있는 값의 범위(값의 데이터 타입과 크기)를 정의한 것

4. 관계

관계

엔터티 간 맺고 있는 연관성 존재적 관계와 행위적 관계로 나눌 수 있으나 EDR에서는 둘을 구분하지 않음

• 존재적 관계 : 일종의 소속관계. 존재 자체로 서로 연관성을 갖는 관계
• 행위적 관계 : 특정 행위나 이벤트를 일으킬 경우에 연관성이 발생하는 관계

연관관계 : 존재 자체로 연관성을 가짐 의존관계 : 특정 행위를 할 때만 연관성을 가짐

표기법

• 관계명 (Membership) : 관계의 이름
• 관계차수 (Cardinality) : 관계를 맺는 엔터티 인스턴스의 차수. 1:1, 1:M, M:N
• 관계선택사양 (Optionalty) : 필수적 관계인지 선택적 관계인지 (null 가능 여부) 선택적 관계인 경우 까치발 기호에 O을 붙임

5. 식별자

식별자

엔터티 인스턴스를 유일하게 구별하는 속성 해당 인스턴스의 대표 속성

주식별자

해당 엔터티 인스턴스를 유일하게 구별해주는 식별자로 PK에 있는 속성 유일성, 최소성, 불변성, 존재성을 만족해야 함.

• 유일성 : 인스턴스를 유일하게 구별
• 최소성 : 유일성을 보장하면서 최소 개수의 속성
• 불변성 : 최초 부여된 값이 변경되지 않고 유지
• 존재성 : 반드시 값을 가져야 함 (null 안됨)

분류

(대표성 여부)

• 주식별자
• 보조식별자 : 해당 엔터티를 유일하게 구별할 수 있는 식별자이기는 하나 대표성을 가지지 못함. 다른 엔터티와 참조관계 연결 불가

후보키 : 유일성과 최소성을 만족하는 속성. 주식별자와 보조식별자를 포함

(스스로 생성 여부)

• 내부식별자 : 엔터티 내부에서 스스로 만들어지는 식별자
• 외부식별자 : 관계를 통해 다른 엔터티로부터 받아오는 식별자(FK)

(속성의 수)

• 단일식별자 : 식별자를 구성하는 속성이 하나
• 복합식별자 : 식별자를 구성하는 속성이 둘 이상

(대체 여부)

• 본질식별자 : 업무에 존재하는 본래의 식별자 (원조식별자)
• 인조식별자 : 업무에 존재하지 않으나 원조식별자가 너무 복잡하여 인위적으로 만든 식별자 (대리식별자)

(비)식별자 관계

식별자 관계

• 강한 연결 관계
• 부모 엔터티의 식별자가 자식 엔터티의 주식별자 구정에 포함
• ERD 상에서 실선으로 표현
• 부모 엔터티 인스턴스와 자식 엔터티 인스턴스가 같은 생명주기를 가지는 경우 적합

비식별자 관계

• 약한 연결 관계
• 부모 엔터티의 식별자가 자식 엔터티의 일반 속성이 됨
• ERD 상에서 점선으로 표현
• 부모 엔터티 인스턴스와 자식 엔터티 인스턴스가 다른 생명주기를 가지는 경우 적합
• 부모 엔터티 인스턴스에 참조값이 없어도 자식 엔터티 인스턴스가 생성될 수 있을 때 고려

문제: 백준 11724(연결요소의 개수) 이 문제를 통해 그래프 탐색 알고리즘의 대표적인 두 가지 방법인 DFS와 BFS에 대해 설명하고자 한다. 문제는 3가지 방법으로 해결하였다.

1. DFS - 재귀함수 활용
2. DFS - 스택 활용
3. BFS - 큐 활용

🐣DFS (Depth-First Search, 깊이 우선 탐색)

시작 노드에서 가능한 깊게 들어간 뒤, 더이상 갈 수 없으면 다시 돌아와 다른 경로를 탐색하는 방식이다.

• 스택이나 재귀함수를 통해 구현
• 어떤 노드를 방문했는지 반드시 검사해야 함
• 모든 경로를 완전 탐색할 때 유리

위의 방법으로 그래프를 탐색하는 것을 깊이우선탐색이라고 한다. 종료 후 방문한 노드를 확인하면 1 -> 2 -> 3 -> 4 -> 6 -> 5 순서가 된다. 6에서 5를 방문할 때에는 4 -> 3 -> 2 순서로 올라가면 인접한 노드가 있는지 탐색한다. 이러한 진행을 백트래킹(backtracking)이라고 한다.

DFS 구현방법 (재귀 기반)

1. 시작노드 방문(visit 표시)
2. 인접한 노드 방문 2-1. 인접한(방문 가능한) 노드가 없으면 종료. 이전 노드로 돌아감. 2-2. 인접한(방문 가능한) 노드가 있으면 방문(visit 표시, 재귀 호출)
3. 시작노드로 돌아갈 때까지(또는 스택이 모두 빌 때까지) 2번 단계를 반복
4. visit이 표시되지 않은 정점부터 다시 DFS 진행

📌재귀함수를 이용한 DFS 코드

void DFS(int root){
    visited[root] = true; // (1단계) root노드 방문 기록.

    // (2단계)
    for(int i = 0 ; i < nodes[root].size(); i++){ 
        int next = nodes[root][i];
        if (!visited[next]) { // (2-2단계) 인접한 노드 방문을 위한 재귀함수 호출
            DFS(next);
        } // (3단계) 방문할 노드가 없으면 dfs 종료
    }
}

int main() {
  ...  
  // (4단계) 방문하지 않은 노드에서 DFS 진행
  for (int i = 1; i <= n; i++){
      if(!visited[i]) {
          count++;
          DFS(i);
      }
  }

}

📌Stack을 이용한 DFS 코드

스택으로 구현할 때에는 LIFO(Last-in First-out)의 구조로 인해, 같은 깊이 중에서 탐색하고 싶은 정점을 역순으로 넣어야 원하는 탐색 순서를 얻을 수 있다.

위와 같은 탐색 경로를 스택에 저장하는 경우에 1번을 방문하여 인접한 2, 3, 4를 스택에 넣을 때 순서대로 넣으면 (stack) : 1 - 2 - 3 - 4 순서로 들어있어 top()으로 확인한 값이 2가 아닌 4가 된다. 그래서 i = 0부터 순서대로 그래프를 탐색하고 싶다면 인접한 노드를 역순으로 넣어야 top()으로 2를 확인할 수 있다. (stack) : 1 - 4 - 3 - 2

for (int i = 1; i <= n; i++){
    if(!visited[i]) {
          count++;
          visited[i] = true; // (1단계) 시작 노드 방문 표시
          vertex.push(i);

          while(!vertex.empty()){ // (3단계)스택이 빌 때까지 반복
              int current = vertex.top();
              vertex.pop();

            // (2단계) current 노드와 연결된 노드를 스택에 역순으로 저장
              for (int j = nodes[current].size() - 1; j >= 0; j--){
                  int next = nodes[current][j];
                  if(!visited[next]) {
                      visited[next] = true;
                      vertex.push(next);
                  }
            }    
        }
    }
  }

🐣BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 시작 노드에서 인접한 노드를 모두 방문하고 다음 깊이의 노드를 탐색하는 방식이다. (같은 깊이를 먼저 탐색함)

• 큐를 이용하여 구현
• 어떤 노드를 방문했는지 반드시 검사해야 함
• 같은 깊이를 먼저 탐색하기에 최단 거리 탐색에 유리

BFS 구현 방법

1. 시작 노드 방문 (visit 표시)
2. 인접한 노드 탐색 2-1. 인접한(방문 가능한) 노드가 없으면 큐를 pop() 하여 다음 노드 탐색 2-2. 인접한(방문 가능한) 노드가 있으면 큐에 넣음 (visit 표시)
3. 큐가 소진될 때까지 2단계 반복

📌Queue를 이용한 BFS 코드

큐는 FIFO(First-in First-out)이기에 같은 깊이의 노드를 넓게 탐색할 수 있다.

for (int i = 1; i <= n; i++){
      if(!visited[i]) {
          count++;
          visited[i] = true; // (1단계) 시작 노드 방문 표시
          vertex.push(i);

          while(!vertex.empty()){ // (3단계) 큐가 빌 때까지 반복
              int current = vertex.front();
              vertex.pop();

            // (2단계) current 노드와 연결된 노드를 큐에 저장
              for (int j = 0; j < nodes[current].size(); j++){
                  int next = nodes[current][j];
                  if(!visited[next]) {
                      visited[next] = true;
                      vertex.push(next);
                  }
            }
        }
    }
 }

문제 : LeetCode 349. Intersection of Two Arrays

📌제출코드

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        set<int> n1(nums1.begin(), nums1.end());
        set<int> n2(nums2.begin(), nums2.end());

        for (auto& n : n2) {
            if (n1.find(n) != n1.end()) {
                result.push_back(n);
            }
        }
        return result;
    }
};

📌오늘의 회고

19, 20일차 코딩테스트 문제는 풀지 못했다. 현생이 바빴지만 반성합니다.

문제 : 백준 1181 : 단어정렬

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다.

• 중복 제거
• 길이 순 정렬
• 사전순 정렬 (같은 길이일 때)

📌제출코드

#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

int main() {
    int n;
    string str;
    map<string, int> strMap;
    map<int, vector<string>> intStrMV;

    cin >> n;
    for (int i = 0; i < n ; i++) {
        cin >> str;
        strMap.insert({str, str.length()});
    }
    for (auto s : strMap) {
        intStrMV[s.second].push_back(s.first);
    }
    for (auto& im : intStrMV) {
        for(auto& strv : im.second) {
            cout << strv << endl;
        }
    }
    return 0;    
}

📌문제 해결

1. 중복제거 C++에서 map과 set은 중복된 key를 자동으로 제거하고, key값을 오름차순으로 정렬하는 특성을 가지고 있다. 이러한 특성을 활용하면 문제가 요구하는 두가지 조건을 자연스럽게 만족할 수 있다, (1) 중복된 단어는 하나만 남긴다. (2) 길이가 같으면 사전순으로 정렬한다. 또한, 기본 조건인 길이가 짧은 순으로 정렬을 처리하기 위해, 사용자의 입력을 받을 때 각 문자열의 길이 정보를 함께 저장할 수 있는 map<string, int>를 사용하였다. set을 통해 문자열만 저장하고 나중에 .length()를 길이를 계산할 수도 있지만 이후 과정을 고려하여 문자열과 길이를 함께 저장할 수 있는 map을 선택하였다.

2. 길이순 + 사전순 정렬 map<string, int>에서 이미 사전순으로 자동 정렬되고 value에는 문자열 길이가 저장되어 있으므로, 이를 기반으로 다시 문자열 길이를 기준으로 정렬하면 문제의 조건을 모두 충족할 수 있다. 이를 위해 map<int,vector<string>> 형태를 사용하여, 문자열 길이(int)를 key로 하고 해당 길이에 속하는 문자열들을 vector로 체이닝하여 저장하였다. 이 구조에서 map의 특성에 따라 길이는 자동으로 오름차순 정렬되며, 각 vector<string>안에는 이미 사전순으로 정렬된 문자열들이 있게 된다. 이를 이중for문으로 순회하면 문제의 모든 요구조건을 만족한 출력이 가능하다.

📌오늘의 회고

자료구조의 기본 특성을 알고 있어야 문제 해결 방향을 잡기 쉽다.

문제 : 백준 25757 : 임스와 함께하는 미니게임 유형 : 문자열, 해시테이블

임스가 미니게임을 같이할 사람을 찾고 있습니다.

플레이할 미니게임으로는 윷놀이 $Y$, 같은 그림 찾기 $F$, 원카드 $O$가 있습니다. 각각 2, 3, 4 명이서 플레이하는 게임이며 인원수가 부족하면 게임을 시작할 수 없습니다.

사람들이 임스와 같이 플레이하기를 신청한 횟수 $N$과 임스가 플레이할 게임의 종류가 주어질 때, 최대 몇 번이나 임스와 함께 게임을 플레이할 수 있는지 구하시오.

1) 첫 줄에 총 신청 횟수 N과 진행할 게임이 주어진다 2) N명의 사람 이름이 주어진다. 이때 이름이 동일하면 동일한 사람이다. 2-1) 동일한 이름이 들어오는 것은 무시해도 된다. 3) 한 사람은 한 번만 게임을 할 수 있다. 3-1) 임스는 모든 게임에 참여하므로 실제 필요한 인원은 게임별로 1, 2, 3명이다.

📌제출코드

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int main() {
    int n;
    char game;

    cin >> n >> game;
    string user;
    unordered_set<string> userSet;

    for (int i = 0; i < n; i++) {
        cin >> user;
        userSet.insert(user);        
    }
    int count = userSet.size();
    if (game == 'Y') {
        cout << count << endl;
        return 0;
    }
    if (game == 'F') {
        cout << count/2 << endl;
        return 0;
    }
    if (game == 'O') {
        cout << count/3 << endl;
        return 0;
    }
    return 0;
}

📌문제 해결

1. 중복되는 인물 처리 동일한 이름은 동일한 사람으로 간주되므로 중복되는 인물은 무시하고 전체 인원 수만 계산하면 된다. 각 이름이 가지는 특별한 의미는 없기 때문에 map이 아닌 set으로 인물을 저장하고 탐색하였다. unordered_set은 중복된 값을 자동으로 무시하기 때문에 이 문제에 적합하며, 최총 인원수는 .size()를 통해 간편하게 확인할 수 있다.

📌오늘의 회고

해시 테이블 활용이 익숙해지고 있는 것 같다.

문제 : LeetCode 187. Repeated DNA Sequences 유형 : 문자열, 비트맵, 해시테이블

1) string에서 반복되는 substring 찾기 2) substring의 길이가 10으로 고정되어있기에 길이가 11이상인 string부터 확인하면 된다 3) substring을 잘라내여 <string, int> 해시맵에 저장하고 동일한 substring이 있는 경우 int값을 +1 한다

📌제출코드

1. substring 이용

   class Solution {
    string subStr;
    unordered_map<string, int> strMap;
   public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> result;
        int len = s.length();
        if (len < 11) 
            return result;
   
        for (int i = 0; i <= len-10; i++) {
            subStr = s.substr(i, 10);
            auto key = strMap.find(subStr);
            if (key != strMap.end()) {
               key->second++;
                continue;
            } 
            strMap.insert({subStr, 0});    
        }
        for (auto& k : strMap) {
            if (k.second > 0)
                result.push_back(k.first);
        }
        return result;
    }
   };

2. 2비트 인코딩을 이용한 슬라이딩 비트마스크 + 해시맵

   class Solution {
    unordered_map<char, int> charToBit = {
        {'A', 0b00}, {'C', 0b01}, {'G', 0b10}, {'T', 0b11}
    };
    unordered_map<int, int> bitMap;
    vector<string> result;
   

public: vector findRepeatedDnaSequences(string s) { int len = s.length(); if (len <= 10) return result; int bit = 0;

    for (int i = 0; i < 10 ; i++) {
        bit = bit << 2 | charToBit[s[i]];
    }
    bitMap.insert({bit, 0});
    int mask = (1 << 20) - 1;
    for (int i = 1; i < len - 9; i++) {
        bit = (bit << 2 | charToBit[s[i + 9]]) & mask;

        auto b = bitMap.find(bit);
        if (b != bitMap.end()) {
            b->second++;
            if (b->second == 1 ) result.push_back(s.substr(i, 10));
            continue;
        }
        bitMap.insert({bit, 0});
    }
    return result;
}  

};

### 📌문제 해결
비트연산이 익숙치 않아서 개념을 한번 정리하고 구현하였다.
2비트 인코딩을 이용한 해시맵 방식이 시간효율성 면에서 훨씬 뛰어났다.

**비트 인코딩과 마스킹**

DNA는 'A', 'C', 'G', 'T' 4개의 문자로 되어있어 각각을 2비트 이진수로 표현할 수 있다. 이를 위해

unordered_map<char, int> charToBit = { {'A', 0b00}, {'C', 0b01}, {'G', 0b10}, {'T', 0b11} };

해시맵을 사용해 각 문자를 대응되는 비트값으로 매핑한다.
문제에서는 중복된 10글자 DNA 시퀀스를 찾는 것이 목표이며, 각 글자를 2비트로 표현하면 총 20비트이기에 10글자를 int(32비트)에 담을 수 있다. 이를 비트 연산을 통해 순차적으로 인코딩한다.

bit = (bit << 2) | 다음_비트;

하지만 비트 인코딩을 반복하다 보면 20비트를 초과한 상위 비트가 남게 될 수 있기에 항상 최근 10글자만 유지하기 위해 마스킹을 적용한다.

int mask = (1 << 20) - 1; //하위 20비트가 1인 카스트 bit = (bit << 2 | 다음_비트) & mask;

``` &mask를 통해 하위 20비트에만 유지하고, 상위비트를 제거하여 bit 변ㅅ는 항상 최근 10글자의 정보만 담게 된다.

📌오늘의 회고

문제를 푸는 것은 어렵지 않았지만 구현 코드의 시간효율이 좋지 않았다. 비트맵을 이용하여 다시 풀 예정이다.

+) 2비트 인코딩을 통한 문제 해결 코드 업로드 완료

문제 : 백준 2358 (https://www.acmicpc.net/problem/2358) 유형 : 정렬, 해시테이블

평면에 n개의 점이 있다. 그중 두 개 이상의 점을 지나면서 x축 또는 y축에 평행한 직선이 몇 개인지 알아내는 프로그램을 작성하시오.

입력 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 주어진다. 같은 좌표가 여러 번 주어질 수 있으며, 그런 경우 서로 다른 점으로 간주한다. 좌표는 절댓값이 231보다 작은 정수이다.

1) x축 또는 y축에 평행하려면 y좌표가 동일한 두 점이거나 x좌표가 동일한 두점이면 된다. 2) n이 (1 ≤ n ≤ 100,000) 이므로 시간복잡도에 신경을 써보자.

📌제출코드

#include <iostream>
#include <unordered_map>

using namespace std;


int main() {
    int n, x, y;
    unordered_map<int, int> xCount, yCount;    

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        xCount[x]++;
        yCount[y]++;
    }

    int result = 0;
    for (auto& p : xCount) {
        if (p.second > 1) result++;
    }
    for (auto& p : yCount) {
        if (p.second > 1) result++;
    }

    cout << result << endl;

    return 0;     
}

📌문제 해결

문제의 기본적인 해결 방법은 동일한 x, y좌표가 몇번 들어오는지 카운트 하여 2번 이상인 경우 하나의 평행선을 만들 수 있다. => 좌표값을 key로 하는 해시맵에 등장 횟수를 카운트 하여 저장한다.

1. '같은 좌표는 서로 다른 점으로 간주한다' 의 해석 가장 많은 시간을 고민하게 했던 부분이다. 우선 나의 해석은 (1) 같은 좌표는 서로 다른 점으로 카운트 한다. (2) 서로 다른 두 점으로 평행선을 만들 수 있다. (3) 그러므로 x좌표와 y좌표의 개수를 카운트 할때 해당 key값에 완전히 동일한 좌표의 점만 들어온 경우에는 평행선을 만들 수 없고, 다른 점이 있어야 평행선을 만들 수 있다. 위의 내용을 표현하기 위해서 count를 저장하는 맵뿐 아니라 해당 좌표의 점이 중복되는 점인지 다른 점인지를 확인하는 추가적인 자료구조(적절한 자료구조를 생각하지 못함)이 필요했다. 몇 시간을 고민하는데 원하는 구현이 어려워 문제를 구글링했더니 입력이 같은 두 점으로도 직선을 만들 수 있다는 것을 알게되었다. 그럼 (2)에 대한 고려없이 (1)만 고려하여 카운트를 하면 되기에 구현을 빠르게 마쳤다. 문제 해석의 애매함으로 고민을 많이 했지만 여러가지 구현 방법을 고민했던 시간이 의미있었다..

2. 시간복잡도 해시맵을 이용하여 탐색과 삽입에 평균 O(1)의 시간복잡도가 되도록 구현하였다. 최종 코드의 시간복잡도는 평균 O(n)이다.

📌오늘의 회고

원하는 구현을 위해 자료구조 공부가 더 필요함을 느꼈다.

• map은 내부적으로 균형이진트리 구조로 구성됨
• 각 노드에 <key, value> 쌍을 저장
• 중복 key를 허용하지 않음
• key가 자동으로 정렬됨 (key가 비교 연산 가능해야 함)
• 탐색, 삽입, 삭제에 O(log n) 소요

2. unordered_map (hash map)

• unordered_map은 해시 테이블 기반의 구조
• map과 마찬가지로 <key, value> 쌍을 저장함
• 하지만 key를 정렬하는 것이 아닌 해시 함수를 통한 해시값을 기반으로 저장
• 동일한 해시값을 가지는 경우(충돌)을 처리할 방법이 필요함 (ex. 2차해시함수, 체이닝)
• 탐색, 삽입, 삭제는 평균 O(1), 최악의 경우 O(n)소요

3. 활용

헤더 & 선언

#include <map>
#include <unordered_map>

map<string, int> m;
unordered_map<string, int> um;

데이터 삽입

m.insert({"Tom", 100});
um.insert({"Alice", 300});

m["Tom"] = 100;
um["Alice"] = 300;

데이터 찾기

auto it = m.find(key);
// key가 존재하면 해당 iterator 반환. 없으면 m.end() 반환

데이터 접근 (범위 기반 for문)

for (auto& it : m) {
    cout << "key: " << it.first << " value: " << it.second << endl;
}

데이터 삭제

1. 특정 위치 삭제 (iterator)

   m.erase(m.begin()+1);

2. key값으로 삭제

   m.erase(key);

3. 모든 요소 삭제

   m.erase(m.begin(), m.end()); // 범위 삭제
   m.clear(); // 전체 삭제

비어있는지 확인

m.empty(); // 비어있으면 true 반환. 아니면 false

문제 : LeetCode 706. Design HashMap (https://leetcode.com/problems/design-hashmap/description/)

해시맵을 이용하여 <key, value>를 put, get, remove하는 함수를 구현하라.

1) 해시맵에 대한 이해 C++ map, unordered_map 정리

제출코드

#include <vector>
#define SIZE 10000
class MyHashMap {
private:
    vector<vector<pair<int, int>>> hv;
    int hashKey;

public:
    MyHashMap() : hv(SIZE) {

    }

    void put(int key, int value) {
        hashKey = key%SIZE;
        if (hv[hashKey].empty()) {
            hv[hashKey].push_back({key, value});
            return;
        }
        for(auto& k : hv[hashKey]) {
            if (k.first == key) {
                k.second = value;
                return;
            }
        }
        hv[hashKey].push_back({key, value});
        return;
    }

    int get(int key) {
        hashKey = key%SIZE;
        if (hv[hashKey].empty()) return -1;
        for (auto& k : hv[hashKey]) {
            if (k.first == key) return k.second;
        }
        return -1;
    }

    void remove(int key) {
        hashKey = key%SIZE;
        if (hv[hashKey].empty()) return;
        for (auto it = hv[hashKey].begin(); it != hv[hashKey].end(); it++) {
           if (it->first == key) {
            hv[hashKey].erase(it);
            return;
           }
        }
        return;

    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

문제 해결

1. 해시맵 이해 처음에는 해시맵에 대한 이해 없이 <key, value> 쌍을 단순히 벡터에 저장하고 선형 탐색으로 구현하였다. 기능 구현에는 성공했지만 해시맵의 핵심인 해시 함수를 활용하지 못했기 때문에, 이후 해시 함수를 적용한 방식으로 문제를 다시 해결하였다.
2. 해시 함수 및 충돌 관리 충돌 해결 방법으로는 이중 해시보다는 구현이 간단한 체이닝 방식을 선택하였고, 2차원 벡터를 이용해 구조를 설계하였다. 연결 리스트와 벡터 중 고민한 끝에 탐색 속도가 더 빠른 벡터를 사용해 구현하였다.

오늘의 회고

함수 기능뿐 아니라 요구하는 구조에 맞게 구현하도록 하자.

문제 : LeetCode 2283. Check if Number Has Equal Digit Count and Digit Value (https://leetcode.com/problems/check-if-number-has-equal-digit-count-and-digit-value/description/) 유형 : 문자열/해시

1) 입력된 문자열에서 각 숫자가 몇번 나왔는지 카운트 한다 2) 카운트한 값과 입력된 문자열을 비교한다

제출코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    bool digitCount(string num) {
        vector<int> numCount(10, 0);
        string numTrue;
        int n = num.length();

        for (int i = 0; i < n; i++) {
            int m = (int)num[i] - '0';
            numCount[m]++;
        }
        for (int i = 0; i < n; i++) {
            numTrue += (char)(numCount[i] + '0');
        }
        if (numTrue == num)
            return true;
        else
            return false;
    }
};

문제해결

시간복잡도 : O(n) 문자형과 정수형을 섞어서 코드를 작성할 때 실수하지 않도록 주의 하기

오늘의 회고

매일 꾸준히 공부하기

문제 : 백준 3986 (https://www.acmicpc.net/problem/3986) 유형 : stack

A, B로 이루어진 문자열을 N개 입력받는다. 문자열에서 A는 A끼리, B는 B끼리 선을 이어 서로 겹치지 않으면 좋은 단어로 판단한다. 좋은 단어의 개수를 출력한다.

1) strng을 이용해 문자열 입력 받기 2) 겹치지 않고 선이 그어지려면 문자열의 중심 부분부터 짝꿍이 만들어져야 한다 3) 짝꿍이 있는 문자는 문자열에서 무시해도 된다

-> 단어를 stack으로 받아서 이전 문자와 동일한지 비교하여 짝꿍을 찾는다

제출코드

#include <iostream>
#include <string>
#include <stack>


using namespace std;

int main() {
    int n, count = 0;
    string str;
    stack<char> s;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> str;
        if (str.length()%2 == 1) continue;

        for (char c : str) {
            if (!s.empty() && s.top() == c)
                s.pop();
            else s.push(c);
        }
        if (s.empty()) count++;
        while(!s.empty()) s.pop();
    }
    cout << count << endl;
    return 0;
}

문제 해결

1. 처음 구현시에는 A와 B를 구분하여 스택을 만들어 두개의 스택 상태를 매번 확인하여 문자열을 검사하였다. 구현 중에 단순히 짝꿍을 찾아주면 되는 문제인데 너무 복잡하게 로직을 짜고 있다는게 느껴져서 처음부터 다시 구현했다. 이전에 구현했던 계산기 괄호 입력과 동일한 문제라는 것을 깨닫고 하나의 stack으로 상태와 top()을 확인하여 짝꿍을 확인할 수 있었다.
2. range-based for loop (범위 기반 for 루프) c++ 11부터 도입된 범위 기반 for 루프를 통해 좀 더 간단하게 모든 요소를 확인할 수 있다.

오늘의 회고

시간 내로 문제를 해결해보자.

stack은 LIFO(Last-in, first-out) 데이터 구조이다. 순서대로 a, b, c, d의 입력이 들어온다면 데이터를 꺼낼 때는 d, c, b, a 순서로 마지막 들어온 데이터부터 접근할 수 있다.

queue는 FIFO(First-in, first-out) 데이터 구조이다. 순서대로 a, b, c, d의 입력이 들어온다면 데이터를 꺼낼 때도 a, b, c, d 순서로 접근할 수 있다.

C++ 함수 정리

stack

#include <stack>

std::stack<type> s;

• empty() bool 타입. stack이 비어있는지 판단. 비어있으면 true, 비어있지 않으면 false 반환.
• pop() stack의 맨 위에 있는 요소를 제거함. return 값 없음.
• push() stack의 맨 위에 요소를 추가함. return 값 없음.
• size() stack의 현재 길이를 반환.
• top() stack의 맨 위의 요소에 대한 참조를 반환.

queue

#include <queue>

std::queue<type> q;

• empty() bool 타입. queue가 비어있는지 판단. 비어있으면 true, 비어있지 않으면 false 반환.
• pop() queue의 첫 번째 요소를 제거함. return 값 없음.
• push() queue의 뒤에 요소를 추가함. return 값 없음.
• size() queue의 현재 길이를 반환.
• front() queue의 첫 번째 요소에 대한 참조를 반환.
• back() queue의 마지막 요소 반환. 가장 최근에 추가된 요소의 참조 반환.

문제 : LeetCode 70. Climbing Stairs (https://leetcode.com/problems/climbing-stairs/description/)

1) 1칸과 2칸의 조합으로 n칸을 올라야 함 2) n칸 오르는 방법 : (n-1)칸을 오르고 + 1칸 오르기 : (n-2)칸을 오르고 + 2칸 오르기 3) n=1 -> 1, n=2 -> 2

제출코드

class Solution {
public:
    int climbStairs(int n) {
        int result = 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        int s1 = 1, s2 = 2, s3;
        for (int i = 2; i < n ; i++) {
            s3 = s1 + s2;
            s1 = s2;
            s2 = s3;
        }
        return s2;
    }
};

문제 해결

1. 재귀함수 시간복잡도 문제 처음에는 f(n) = f(n-1) + f(n-2) 형태의 단순 재귀함수로 문제를 구현하였다. 그러나 이 방식은 동일한 계산을 반복적으로 수행하게 되어 시간복잡도가 O(2ⁿ)으로 매우 비효율적이다. 이를 해결하기 위해 재귀 호출 대신 변수를 사용하여 값을 직접 저장하고 누적하는 방식으로 중복 계산을 방지하였다. n = 1, n = 2일 때의 base case를 기준으로, n > 2인 경우에는 반복문을 통해 직접 값을 더해가며 계산하였다. 이 방식은 반복문을 한 번만 수행하므로 시간복잡도는 O(n)으로 효율적이다.

오늘의 회고

시간복잡도를 고려하여 구현하기.

문제 : LeetCode 232. Implement Queue using Stacks (https://leetcode.com/problems/implement-queue-using-stacks/submissions/1599103736/) LeetCode 225. Implement Stack using Queues (https://leetcode.com/problems/implement-stack-using-queues/description/)

1. stack과 queue에 대한 이해 필요 자료구조 stack, queue

제출코드

#include <stack>

class MyQueue {
private:
stack<int> s_main;
stack<int> s_sub;

public:
    MyQueue() {

    }

    void push(int x) {
        s_main.push(x);
    }

    int pop() {
        while (s_main.size() > 1) {
            s_sub.push(s_main.top());
            s_main.pop();
        }
        int result = s_main.top();
        s_main.pop();
        while(!s_sub.empty()) {
            s_main.push(s_sub.top());
            s_sub.pop();
        }

        return result;
    }

    int peek() {
        while (s_main.size() > 1) {
            s_sub.push(s_main.top());
            s_main.pop();
        }
        int result = s_main.top();

        while(!s_sub.empty()) {
            s_main.push(s_sub.top());
            s_sub.pop();
        }

        return result;
    }

    bool empty() {
        return s_main.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

#include <queue>

class MyStack {
private:
    queue<int> q1;
    queue<int> q2;

public:
    MyStack() {

    }

    void push(int x) {
        q1.push(x);
    }

    int pop() {
        while(q1.size()>1) {
            q2.push(q1.front());
            q1.pop();
        }
        int result = q1.front();
        q1.pop();
        while(!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
        }
        return result;

    }

    int top() {
        while(q1.size()>1) {
            q2.push(q1.front());
            q1.pop();
        }
        int result = q1.front();
        q2.push(result);
        q1.pop();
        while(!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
        }
        return result;
    }

    bool empty() {
        return q1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

오늘의 회고

쉬는 기간동안 배운 것들을 많이 까먹었다. 더 많은 공부가 필요할 것 같다.

문제 : 백준 31458 (https://www.acmicpc.net/problem/31458) 분류 : 문자열 구현

T개의 문자열을 입력받는다. 문자열은 공백이 없는 "!!n!!" 형태로 받아 두가지 규칙(팩토리얼, 논리반전)을 적용하여 출력한다. 정수 n 에는 0 또는 1이 들어간다. 정수 앞/뒤로 '!'가 붙을 수 있다. 각 자리에 0~30개의 !가 붙을 수 있다.

1) 수식의 개수 T를 입력받음 2) 문자열에서 정수 앞 !, 정수, 정수 뒤 !를 구분 3) 정수 뒤 !는 bool형태로 확인하여 판단 4) 정수 앞 !는 홀수/짝수개인지 판단 5) 결과 출력

제출코드

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n, num, front, len;
    bool answer, check_num, back;
    string str;

    cin >> n;
    cin.ignore();

    for (int i = 0; i < n; i++) {
        check_num = false;
        back = false;
        front = 0;

        getline(cin, str);
        len = str.length();

        for (int j = len ; j > 0; j--) {
            if (str[j-1] == '0' || str[j-1] == '1') {
                check_num = true;
                num = str[j-1] - '0';
                continue;
            }
            if (check_num == false) back = true;
            else front++;

        }

        if (back == true) answer = 1;
        else answer = num;

        if (front%2 == 0) cout << answer << endl;
        else cout << !answer << endl;    
    }
    return 0;
}

문제 해결

1. 문자열에서의 정수 string으로 문자열을 받아 중간에 써있는 정수도 char형태라는 것을 까먹었다.

if(str[j-1] == 0 || str[j-1] == 1) 처음에는 정수 0과 1로 조건을 설정해 해당 if문을 건너뛰었다. 코드를 검토하는 과정에서 이를 깨닫고 if(str[j-1] == '0' || str[j-1] == '1') num = str[j-1] - '0'; 으로 수정하였다.

오늘의 회고

구현에만 초점을 두고 빠르게 하려고 하니 기초적인 부분에서 문제가 생긴다. 지금은 실력 상승보다느 머릿속 깊은 곳에 있는 내용을 하나씩 꺼내서 정리하는 수준이다. 앞으로 열심히 해야지..! 화이팅!

문제접근

문제 : 백준 10820 (https://www.acmicpc.net/problem/10820) 유형 : 문자열 구현

n (1 <= n <= 100)줄의 문자열을 받아 각 문자열에 대해 소문자, 대문자, 숫자, 공백의 개수를 구분하여 출력.

1) 공백을 포함한 문자열을 입력받기에 cin이 아닌 getline을 이용. 1-1) 몇 줄의 문자열이 입력될지 모르기에 while문으로 루프를 돌리고 break 조건을 생각함. 2) string으로 문자열을 받아 앞에서부터 하나씩 접근하여 문자를 구분. 3) low_c, up_c, num, space 변수에 개수 저장 4) 결과 출력

제출코드

#include <iostream>
#include <string>
#include <vector>
#include <cctype>

using namespace std;

int main() {
    string str;
    vector<int> low_v, up_v, num_v, space_v;

    char c;
    int count=0;
    int low_c, up_c, num, space; 


    while(1){
        getline(cin, str);
        if (cin.eof()) break;
        low_c = 0;
        up_c = 0;
        num = 0;
        space = 0;

        count++;
        for (int i=0;;i++) {
            c = str[i];
            if (islower(c) != 0) low_c++;
            else if(isupper(c) != 0) up_c++;
            else if (isdigit(c) != 0) num++;
            else if (isspace(c) != 0) space++;
            else break;
        }
        low_v.push_back(low_c);
        up_v.push_back(up_c);
        num_v.push_back(num);
        space_v.push_back(space);


    }
    for (int i =0; i < count; i++) {
        cout << low_v[i] << " " << up_v[i] << " " << num_v[i] << " " << space_v[i] << endl;
    }

    return 0;
}

구현과정 문제 해결

1. 입력 종료 시점(?)의 문제

처음 구현할 당시에는 while문 루프 상황에서 break포인트로 getline(cin, str); if(str.empry()) break; 로 구현하였다.

이렇게 구현하면 생기는 문제는 (1) 사용자 입력이 '\n'로 끝난 후에 한번 더 엔터를 입력해야 된다. (2) (이건 회고하는 과정에서 생각한건데) 말그대로 빈 문자열을 무시하게 된다. 라는 두가지 문제가 생긴다. 백준에서 제공하는 입력 예시에서 모든 문장의 마지막이 '\n'로 끝나기에 무엇으로 break 조건을 설정할지 고민했다.

결론은 질문게시판을 통해 EOF로 문자열의 종료를 알려주는 방법으로 구현하였다. EOF를 알고있었지만 파일과 문자열을 동일 선상에서 생각하고 있지 않아서 (크기를 알지 못한 채) 연속으로 입력되는 문자열을 처리하는 다른 방법이 있을거라 생각하느라 시간이 많이 지체되고 헤맸다. 이번 경험으로 알게 되었으니 이게 코딩테스트 스터디의 좋은점이 아닐까싶다. 알던 것도 더 열심히 생각하고 고민하게 된다.

최종적으로는 if(cin.eof()) break; 로 구현하였다. 참고로 cin.eof()는 eof일 때 true(1)을 반환하고 나머지 상황에는 false를 반환한다. 콘솔에서 eof를 나타내고 싶다면 'Ctrl+x'를 통해 입력할 수 있다.

2. 입출력 방식 이건 문제는 아니지만 구현하다보니 억울했던 부분이다. 백준 예시입력과 예시출력이 여러줄로 묶여있어서 입력을 모두 받은 후에 한번에 출력을 해야된다고 이해했다.

그래서 개수를 저장한 변수 값들을 바로 출력하지 않고 한 번 더 저장할 공간이 필요했다. 이는 vector를 통해 각 문자별 벡터를 만들어 첫번째 문자열부터 개수를 하나씩 저장하여 while문이 종료된 후에 for문으로 순서대로 돌며 출력하게 하였다. 다른 사람들의 결과를 보니 (입력-출력)을 함께 반복시켜도 문제가 없더라... 굳이 vector까지 사용을 안해도 됐었는데 아쉽다.

오늘의 회고

아직 모르는 내용과 함수가 많다. 초반에는 문제를 푸는 것과 다른 사람들의 답안을 보면서 비교하며 공부하는 것이 도움될 것 같다.

문제 접근

문제 : 백준 1032 (https://www.acmicpc.net/problem/1032) 분류 : 문자열

n개의 파일 이름을 입력받아 1)모두 동일한 문자는 그대로 출력 2)다른 문자는 '?'로 출력하여 파일 이름의 패턴을 분석.

접근방법

1) 문자열 처리를 위해 string 헤더 사용 2) 중첩 for문을 이용해 string arr에 입력된 파일 이름을 자리별로 비교하여 출력 string에 추가함. 2-1) [0]->[len]까지 반복하며(첫번째 for문) 2-2) 각 파일이름을 직전 파일이름과 비교 (두번째 for문) 2-3) 문제(직전 파일 이름과 다른 경우) 검출 -> answer += '?' 문제 없음 -> 해당 문자를 answer에 추가

제출 코드

#include <iostream>
#include <string>
using namespace std;


int main() {
    int n, len;
    string file_name[51];

    cin >> n;

    for (int i =0; i <n; i++) {
        cin >> file_name[i];
    }

    len = file_name[0].length();    

    if(n == 1) {
        cout << file_name[0];
        return 0;    
    }

    string answer;
    for(int i=0;i<len;i++) {
        for(int j=1;j<n;j++) {        
            if(file_name[j-1].at(i) == file_name[j].at(i)) {
                if (j == n-1) 
                    answer += file_name[j].at(i);
            }
            else {
                answer +='?';
                break;
            }
        }
    }

    cout << answer << endl;

    return 0;
}

오늘의 회고

오랜만에 문제를 풀려고 하니 손도 굳고 어리도 굳어서... 시간이 오래걸렸다. 혼자서 문제를 풀때는 타임어택의 부담이 크지 않았는데 99클럽으로 문제를 풀면서 타임어택의 부담감으로 최종 코드가 난잡해졌다. 아직 라이브러리 활용이나 기본적인 알고리즘 지식이 부족하지만 부족해서 스터디를 하는거니 열심히 해보겠습니다.

** 다른 분들의 TIL을 보니 더 많은 분석과 회고를 작성하셨네요... 앞으로의 과정에서 발전하는 모습을 보이겠습니다.

99클럽 코테스터디 목표

• c++과 파이썬으로 비기너 문제 100% 풀기
• TIL 70% 이상 작성
• 미들러 문제 50% 이상 풀기
• 자료구조 및 알고리즘 심화 공부