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

def solution(genres, plays):
    # key: 장르 , value: (곡의 index, play수)인 딕셔너리
    genere_dic = {}
    for i, g in enumerate(genres) : 
        if g not in genere_dic : genere_dic[g] = [(i, plays[i])] #index, play수
        else : genere_dic[g].append((i, plays[i])) #index, play수
            
    # 각 키 내에서 조건 2, 조건 3에 따라 정렬
    for genre, values in genere_dic.items():
        genere_dic[genre] = sorted(values, key=lambda x: (x[1], -x[0]), reverse=True)
        
    # 조건 1에 따라 키 정렬
    sorted_genere = sorted(genere_dic.items(), key=lambda x: sum(v[1] for v in x[1]), reverse=True)
    sorted_genere = dict(sorted_genere)
    
    # 결과 list로 정리 
    res = []
    for key, val in sorted_genere.items() : 
        if len(val) < 2 : 
            res.append(val[0][0])
        else : 
            res.append(val[0][0])
            res.append(val[1][0])
        
    return res

questions

• activation function을 쓰는 이유는?

## reference
https://github.com/boost-devs/ai-tech-interview/tree/main

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

import sys

n = int(sys.stdin.readline().strip()) #n = int(input())

dic = {}
for _ in range(n) :
    word = sys.stdin.readline().strip() #word = input()
    l = len(word)
    if l in dic :   dic[l].append(word) # 이미 딕셔너리에 존재할 경우
    else :          dic[l] = [word] # 딕셔너리에 해당 길이인 단어가 없을 경우

key_list = sorted(list(dic.keys())) # 길이 순 정렬
for key in key_list:
    for w in sorted(list(set(dic[key]))):  # 같은 길이인 단어들 중 중복 제거 후, 정렬
        print(w)

간단한 string 문제이기 때문에 속도를 높이기 위해 노력했다

dictionary 사용 / key 기준 정렬로 전체 단어들 정렬 피했다. 

그 결과 pypy 제출 답안중에서는 괜찮은 속도인 것 같다

그래도 더 괜찮은 코드가 있을것같은데 잔디 채우고싶어서 술먹고꾸역꾸역 푼거라서 내일...찾아봐야지....

Introduction

DB와 DBMS

• 데이터베이스(DB, database)는 서로 연관 있는 데이터의 모임을 의미한다.
  일반적으로 우리가 관심 있는 데이터베이스는 컴퓨터에 저장되어 있는 데이터이며, 또한 데이터 용량이 방대하며 이차 저장 장치인 하드디스크(HDD, hard disk drive) 또는 SSD(solid state drive)에 저장되는 데이터이다.

• 컴퓨터에 데이터베이스가 저장되어 있으면, 이를 관리하는 소프트웨어가 필요하며 우리는 이를 데이터베이스 관리 시스템(DBMS, database management system) 이라 한다.

용어정리

• DB : collection of data
• DBMS : Database Management System
• DBS : Database System
• 여기에선 INTErchangeably 하게 쓴다!

Advantages of DBMSs

• Data abstraction
• Easy accessing data
  • 접근위한 언어 제공 / UI 제공
• Data redundancy (중복), inconsistency(불일치) 제어 용이
• IC(Intergrity constraint : 제약조건) 유지 용이
  • 데이터 무결성 제약조건은 데이터가 만족하여야 하는 조건
  • EX) “학생의 학점 데이터는 최소값 0.0 최대값 4.5 내의 실수 값이어야 한다”
• Atomicity of updates (데이터 원자성)
  • all :전부 잘 업데이트하거나
  • nothing : 오류있으면 아예 업데이트하지않거나
  • 데이터 갱신 시에 갱신 연산이 부분적으로 데이터베이스에 반영되질 않음
• 다수 사용자의 동시성 제어
• Data security
• Data backup and recovery

1.2 Data Abstraction and Data Mdoel

Schemas & Instance

Abstraction

전산학에서 추상화는 어떤 사물에 대한 세세한 개체(instance)로부터 중요한 개념을 분리하는 프로세스를 의미하며, 구현상에서만 관련 있는 사항이나 문제 해결에 중요하지 않은 사항을 제거하여 사람들이 문제 핵심 속성에만 집중하여 문제를 해결하게 한다

데이터 추상화 레벨

• physical level
  • 물리적으로 어떻게 저장되는가
• logical level
  • 논리적으로 db와 db가 어떤 관계를 가지고 있는지
• view level
  • 어떤 유저가 이 db에 관련되어있고, 볼 수 있으며, 숨겨야하는지

뷰 레벨(사용자에게 오직 관심있는 데이터만을 추상화) -> 로지컬 -> 물리적 레벨(실제 데이터 레코드가 어떻게 저장되는지 기술)

Data Independence

• 가급적 abstraction level들 간 독립되도록 헤야한다
• physical data independence
  • 논리적 스키마 변화없이 물리적 스키마를 변화할 수 있는 기능
• logicla data independence
  • 뷰 스키마 변화없이 논리적 스키마 변화 할 수 있는지

Data Model

• data model은 데이터, 관계성, 의미, 제약조건등을 기술하는 명세(specification) 혹은 개념적 도구(oconceptual tool) => 데이터 추상화를 지원하는 도구

  이름	설명
  Relatinal	우리가 아는 테이블형식
  Object-relational	relational 방식에 객체지향 요소를 부분적 도입
  XML	Extensible Markup Language. 문서 교환을 위한 표준 기술

Database Design

• ER model (Entity Relationship model)

- entity와 relation으로 포함함
- ER diagram으로 직관적으로 파악가능
- ER 나오면 관계형으로 갈껀지 객체형으로 갈껀지 결정 가능
- Normalization Theory : 내가 만든 스키마가 좋은지 안좋은지 판단 가능한 이론

1.3 Database System

DBMS 의 component

• query processor(질의어 처리기) : 질의어 처리, 권한 부여 및 철회, 인증 등 기능
• stoarage manager(저장 관리) : 데이터베이스 서버의 하단부분을 의미하며, 데이터 저장, 검색뿐만 아니라 화일 구조, 색인, 트랜잭션 관리 등의 업무를 담당

Data dictionary

• =data directory
• meta data를 저장중
• ex) schema, intergrity constraints, authorization, statiscal data ...

Transaction Management

• Concurrency control manager (동시성 제어 기능)
  • 사용자가 db를 저장해서 수정/검색/삭제등을 할때 DBMS에 전달
  • DBSM에서는 transaction 형태로 변환하여 사용.
  • 이럴때 여러개의 transaction을 control하는게 concurrency control manager
  • consistency를 보장한다
• Recovery manager(복구 기능)
  • 중간에 failure 발생하거나, 전기나갔을대 복구

Database Users

• Naive user
  • 주어진 사용자 UI이용 + 주어진 절차 이용
  • 보통 사용자
• DB administrator (DBA)
  • 스키마 정의, 저장 구조 및 접근 방법 정의, 스키마 및 물리 구조 변경, 데이터베이스 접근 권한 관리, 제약 조건 관리, 시스템 성능 관리 등
• 그외 : Application programmers, DB designer, DB analysist,

Database System Architercture

• 데이터 위치에 의거하여 분류
  • Centralized
  • Distributed
  • Client-server
  • Parallel(multi-processor) : 컴퓨터 병렬처리 기술을 DB시스템에 적용한 경우

DB system의 역사

• 1950s & 1960s
  • magnetic tapes, pucned card는 sequqential하게 밖에 읽지 못하지만
  • hard disk 는 바로 접근이 가능해서 DB의 본격적 등장
• 1970s
  • E.Codd가 최초의 관계형 DB 모델 제안
• 1980s
  • 상업적으로 관계형 DB 모델 사용 시작
  • 관계지향 DB 등장
• 1990s
  • data-mining
  • data warehouse -> decision making에 활용
  • web commerce 등장
• 2000s
  • XML 등장
• 2010s
  • Big data
  • NO SQL

• 수강일시 : 2021년 3학년 2학기
• 교수님 : 박동주 교수님
• 교재 : Database Systems Concepts/A. Silberschats, H. Korth, S./McGraw Hill
  

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

1. BFS문제인데 DP로 생각했다.
2. 우선순위큐를 활용한 BFS라 신기했다. 

처음 풀때 

이런식으로 하나씩 쓰다보면서 규칙을 발견해보려고 했다. 

짝수인경우) X_i = min( X_i/2 , X_i-1 + 1) 

홀수인경우) X_i = X_i-1 + 1 

이라는 점화식을 세웠다. 

subin, target = map(int, input().split())

d = [-1] * 100002
d[subin] = 0
d[subin+1] = 1
for i in range(subin+2, target+1) : 
    if i%2 == 0 and d[i//2] != -1: 
        d[i] = min(d[i//2], d[i-1]+1)
    else :
        d[i] = d[i-1] + 1

print(d[target])

근데 

하하하!

로그 찍어보니까 

이렇게 나왔다. 최적값을 제대로 못 구하고 있음을 알 수 있다. 

두배수로 점프하는게 가장 적은 값인데, 이걸 한번 배열 전체에 기록을 하고, 또 이걸기반으로 또 배열 전체를 기록을 하는 식으로 진행해야 최적값을 제대로 구할 수 있음을 알게 됐다. (나는 배열 전체를 한번만 검색하는 식으로 만들어서,, 최적값이 나올 수 가 없었다.) 

그래서 검색하니까 DP가 아니라 BFS 더라 .. ^^

오해해서 미안했다..

이렇게 우선순위 큐를 돌리면 빠르게 최적값을 찾아낼 수 있다!!

이런식의 우선순위큐를 활용한 BFS도 있군아 재밌다

최종 코드

from collections import deque 

def bfs() :
    graph = [-1] * 100001
    graph[subin] = 0
    que = deque([subin])

    while que :
        target = que.popleft()
        
        # 동생 위치에 도달시(정답발견)
        if target == sister :
            return graph[target]
        
        for i in (target+1, target-1, target*2) : # 세가지 방법을 순서대로 진행
            # 이동하는 곳이 범위내이며 / 한번도 방문하지 않았으면
            if 0<=i<=100000 and graph[i] == -1 :
                # 순간이동인경우
                if i == target*2 :
                    graph[i] = graph[target]
                    que.appendleft(i) # 순간이동이니까 먼저 탐색
                else :
                    graph[i] = graph[target] + 1
                    que.append(i)

subin, sister = map(int, input().split())
print(bfs())

굿!