초이의 끄적끄적

프로그래머스 스택/큐

# 다리를 지나는 트럭 (Level2)

• 앞 쪽에 위치한 트럭이 우선적으로 다리를 건너야 하기 때문에 FIFO 구조
• 리스트의 pop(0)은 0(n)의 시간복잡도를 가지고 deque의 popleft()는 O(1)의 시간복잡도를 가지기 때문에 deque사용한다
• 1초가 지날때마다 현재 다리에 있는 트럭의 무게와 다음으로 올라갈 트럭의 무게의 합이 최대 하중을 넘는지 확인한다
• 하중을 넘지 않는다면 다음 트럭을 올리고
• 그렇지 않다면 0을 더해 다리를 왼쪽으로 밀어낸다

- 첫번째 풀이(실패)

• Point. 하나의 테스트케이스에서 시간초과가 났다 -> sum이 O(n)이라 시간초과 발생

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_q = deque(truck_weights)
    q = deque([0] * bridge_length)
    
    while q:
        time += 1
        q.popleft()
        if truck_q:
            if sum(q) + truck_q[0] <= weight:
                q.append(truck_q.popleft())
            else:
                q.append(0)
    
    return time

- 두번째 풀이 (성공) -> sum대신 다리의 무게를 따로 관리해준다

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_q = deque(truck_weights)
    q = deque([0] * bridge_length)
    t_weight = 0 # 현재 다리의 무게
    
    while q:
        time += 1
        # 나갈 트럭이 있다면 그 무게를 빼준다
        if q[0] != 0: t_weight -= q[0]
        q.popleft()
        if truck_q:
            # 다리의 무게와 대기하는 트럭의 크기가 weight값을 넘지 않으면 더해준다
            if t_weight + truck_q[0] <= weight:
                t_weight += truck_q[0]
                q.append(truck_q.popleft())
            else:
                q.append(0)

    return time

* 시간복잡도를 생각하는 습관을 길러야겠다

wiki.python.org/moin/TimeComplexity

방어 맛집으로 유명한 남해바다마차 👍

방어는 철이 지나 오늘은 🐟참돔🐟 을 먹으러 갔습니다!!

마지막 테이블로 들어가 겨우 먹은 회... 휴... 다행... 또 가리비 먹을뻔.... 근데 가리비도 맛나... 츄륩

( 매장이 좁고 다들 오래 드시기 때문에 일찍 가는걸 추천드려요 👍 )

메뉴판은 아래와 같습니다

메뉴는 제철 해산물에 따라 수시로 바뀝니다 ( 현재 4월! )

저희는 참돔과 우니, 캐비어를 시켰어요

( 진짜 우니는 꼭 드셔보세요 제가 먹었던 우니 중 최고급입니다!! 👍 )

미역국과 간장, 초, 막장, 초장

막장에 회 먹으면 넘 맛있어요

짜란..... 영롱... 그 자체...

마지막 테이블이라고 회도 우니도 많이 주셨어요...♥

완전 두툼하고... 맛있는 참돔... ♥

이 집은 우니가 진짜 최고에요👍

안먹으면 후회합니다ㅠㅠ

여기서 우니먹기 시작해서.... 다른 곳 우니는 비려서 못먹어요.... 엉엉...

기본인 회에 와사비 간장 조합

김 + 우니 + 캐비어 + 와사비 + 초 + 간장

 회 + 우니 + 캐비어 + 와사비 + 초 + 간장

마지막으로 돔 머리구이를 주셨어요

역시 어두육미....👍

돈만 많으면... 정말 매일 가고싶은 횟집ㅠㅠㅠ

비싼데 맛없으면 맞아야되지만

맛있으면 비싸도되....

우니먹으러 또 가야지...

남해바다마차 위치 :

프로그래머스 스택/큐

# 프린터

- 나의 풀이

• 순서를 표시할 deque와 순서에 해당하는 중요도값을 저장한 dic값을 만들어줌
• 맨 앞 대기목록의 중요도와 나머지 중요도를 비교해 중요도가 가장 높으면 출력을 아니면 뒤로 빼준다 -> deque를 써야하는 이유 앞뒤로 빠져야되니까

from collections import deque
def solution(priorities, location):
    answer = 0
    queue = deque(i for i in range(len(priorities)))
    dic = {}
    
    for i in range(len(priorities)):
        dic[i] = priorities[i]
    
    while queue:
        tmp = queue.popleft()
        dic_value = list(dic.values())
        if dic[tmp] == max(dic_value):
            del dic[tmp]
            answer+=1
            if tmp == location:
                break
        else:
            queue.append(tmp)
        
    return answer

+ (GOOD) 풀이

• deque에 중요도와 순서를 함께 저장함

from collections import deque
def solution(priorities, location):
    answer = 0
    # v : 중요도 , i : 순서
    queue = deque((v,i) for i,v in enumerate(priorities))
    
    while queue:
        item = queue.popleft()
        if item[0] < max(queue)[0]:
            queue.append(item)
        else:
            answer+=1
            if item[1] == location:
                break
        
    return answer

# 자연수 뒤집어 배열로 만들기

def solution(n):
    answer = []
    for i in str(n):
        answer.append(int(i))
    answer.reverse()
    return answer
    #return list(map(int, reversed(str(n))))

# 나누어 떨어지는 숫자 배열

def solution(arr, divisor):
    answer = []
    for i in arr:
        if i%divisor == 0:
            answer.append(i)
    
    if len(answer) == 0:
        answer = [-1]
    else:
        answer.sort()
    return answer

Q. SQL과 NoSQL의 차이점은 무엇인가요?

 -> SQL은 테이블 구조를 갖고, 스키마를 준수하며, 수직적 확장만 가능하지만, NoSQL은 Document구조로서 테이블을 유연하게 변경할 수 있으며, 수직적, 수평적 확장이 모두 가능합니다. 대표적인 SQL은 MySQL이 존재하고 NoSQL은 MongoDB가 존재합니다.

 -> 꼬리 질문

• SQL과 NoSQ의 장점은 무엇인가요?
• SQL과 NoSQL의 단점은 무엇인가요?
• SQL과 NoSQL 중에 어떤 것이 더 좋나요?
• 수직적, 수평적 확장이 무엇인가요?

더 자세히 알아보자.

SQL ( 관계형 데이터베이스 )

• SQL(Structured Query Language : 구조화된 쿼리 언어)
• 관계형 데이터베이스 관리 시스템(RDBMS)에서 데이터를 저장, 수정, 삭제 및 검색할 수 있습니다.
• 데이터는 정해진 데이터 스키마에 따라 테이블에 저장됩니다.
• 데이터는 관계를 통해서 여러 테이블에 분산됩니다.
• 수직적 확장만 지원

NoSQL ( 비관계형 데이터베이스 )

• 스키마도 없고, 관계도 없습니다.
• 레코드를 문서(documnets)라고 부르고 JSON 데이터와 비슷한 형태를 가지고 있습니다.
• 수직적, 수평적 확장 가능

+ NoSQL에는 조인이라는 개념이 존재하지 않는다. 그러면 조인하고 싶을 때 NoSQL은 어떻게 할까?

-> 컬렉션을 통해 데이터를 복제하여 각 컬렉션 일부분에 속하는 데이터를 산출하도록 합니다. 하지만 이러면 데이터가 중복되어 서로 영향을 줄 위험이 있습니다. 따라서 조인을 잘 사용하지 않고 자주 변경되지 않는 데이터일 때 NoSQL을 사용하면 효율적입니다.

수직적(Vertical) vs 수평적(Horizontal) 확장(Scaling) -> 데이터베이스의 서버의 확장성

• 수직적(Vertical) 확장 : 데이터베이스 서버의 성능 향상 ex) CPU 업그레이드
• 수평적(Horizontal) 확장 : 더 많은 서버가 추가되고 데이터베이스가 전체적으로 분산됨 (하나의 데이터베이스에서 작동하지만 여러 호스트에서 작동)

Q. SQL과 NoSQL의 장점

• SQL 장점
  • 명확하게 정의된 스키마, 데이터 무결성 보장
  • 관계는 각 데이터를 중복없이 한 번만 저장
• NoSQL 장점
  • 스키마가 없기 때문에 유연함. 언제든지 저장된 데이터를 조정하고 새로운 필드를 추가 가능
  • 데이터는 애플리케이션이 필요로 하는 형식으로 저장됨. 데이터를 읽어오는 속도가 빨라짐
  • 수직 및 수평 확장이 가능하므로 애플리케이션에서 발생시키는 모든 읽기/쓰기 요청을 처리 가능

Q. SQL과 NoSQL의 단점

• SQL 단점
  • 상대적으로 덜 유연함. 데이터 스키마를 사전에 계획하고 알려야 함. (수정이 번거롭거나 불가능할 수 있음)
  • 관계를 맺고 있기 때문에, JOIN문이 많은 복잡한 쿼리가 만들어질 수 있음
  • 수평적 확장이 어렵고, 대체로 수직적 확장만 가능함
• NoSQL 단점
  • 유연성 때문에 데이터 구조 결정을 하지 못하고 미루게 될 수 있음
  • 데이터 중복은 여러 컬렉션과 문서가 여러 개의 레코드가 변경된 경우 업데이트해야 함.
  • 데이터가 여러 컬렉션에 중복되어 있기 때문에, 수정 시 모든 컬렉션에서 수행해야 함 (SQL은 중복된 데이터가 없기 때문에 한 번만 수행하면 됨.)

Q. SQL과 NoSQL 중에 어떤것이 더 좋나요?

-> 어떤 데이터를 다루는지에 따라 선택해야 합니다.

• SQL의 경우 관계를 맺고 데이터가 자주 변경되는 애플리케이션의 경우, 변경될 여지가 없고, 명확한 스키마가 사용자와 데이터에게 중요한 경우에 사용하는 것이 좋습니다.
• NoSQL의 경우 정확한 데이터 구조를 알 수 없거나 변경/확장될 수 있는 경우, 읽기(read) 처리를 자주 하지만, 데이터를 자주 변경(update) 하지 않는 경우, 데이터를 수평적으로 확장해야 하는 경우(즉, 막대한 양의 데이터를 다뤄야 하는 경우)에 사용하는 것이 좋습니다.

조인이란

• 두 개 이상의 테이블이나 데이터베이스를 연결하여 데이터를 검색하는 방법

JOIN 종류

• 내부 조인( INNER JOIN ) : 교집합
• 교차 조인 ( CROSS JOIN - CARTESIN PRODUCT, 카디션 곱 ) : 곱집합, 두 개 이상의 테이블에 대해 연결 가능한 행을 모두 결합
• 외부 조인 ( OUTER JOIN ) : 두 개 이상의 테이블 조인 시 한쪽 테이블의 행에 대해 다른쪽 테이블에 일치하는 행이 없더라도 다른쪽 테이블의 행을 NULL로 하여 행을 Return 하는 것
  • 완전 외부 조인 ( FULL OUTER JOIN ) : 합집합
  • 왼쪽 ( LEFT OUTER JOIN )
  • 오른쪽 ( RIGHT OUTER JOIN )
• 셀프 조인 ( SELF JOIN ) : 자기자신과 자기자신을 조인하는 것

 + 등가 조인( EQUI JOIN ) , 비등가 조인 ( NON-EQUI JOIN )

Q. JOIN에 대하여 설명해 보세요

-> JOIN은 두 개 이상의 테이블이나 데이터베이스를 연결하여 데이터를 검색하는 방법으로 크게 INNER JOIN, CROSS JOIN, OUTER JOIN, SELF JOIN 이 있습니다.

+ SQL JOIN 문제 

2021.03.11 - [알고리즘/SQL] - 프로그래머스 SQL 고득점 Kit 풀이 - JOIN

키(Key)란 

• 데이터베이스에서 검색, 정렬 시 다른 튜플들과 구별할 수 있는 기준이 되는 Attribute(속성)입니다.

+ 튜플(Tuple) : 릴레이션을 구성하는 각각의 행, 속성의 모임으로 구성된다.

1. 후보키 (Candidate Key)
   • Tuple을 유일하게 식별하기 위해 사용하는 속성들의 부분집합 (기본키로 사용할 수 있는 속성들)
   • 모든 릴레이션은 반드시 하나 이상의 후보키를 가져야 한다.
   • 유일성과 최소성 만족
     • 유일성 : Key로 하나의 Tuple을 유일하게 식별할 수 있음
     • 최소성 : 꼭 필요한 속성으로만 구성
   • ex) 학번이나 주민번호
2. 기본키 (Primary Key) = 주 키, 프라이머리 키, PK
   • 후보키 중 선택한 주키(Main Key)
   • Null 값을 가질 수 없음 (개체 무결성의 첫 번째 조건)
   • 동일한 값이 중복될 수 없음 (개체 무결성의 두 번째 조건)
   • ex) 학번이나 주민번호
3. 대체키 (Alternate Key) = 보조키
   • 후보키 중 기본키를 제외한 나머지 키
   • ex) 학번을 기본키로 정의하면 주민번호는 대체키가 된다
4. 슈퍼키 (Super Key)
   • 유일성은 만족하지만, 최소성은 만족하지 못하는 키 -> 뭉쳤을 경우 유일성이 생기고, 흩어지지만 몇몇 속성들은 독단적으로 유일성 있는 키로 사용할 수 없음
   • ex) 학번 + 주민번호 + 성명으로 슈퍼키 구성 -> 성명은 단독적으로 사용 못함
5. 외래키 (Foreign Key)
   • 참조되는 릴레이션의 기본키와 대응되어 릴레이션 간에 참조 관계를 표현하는 중요한 도구이다
   • 외래키로 지정 시 참조 테이블의 기본키에 없는 값은 입력할 수 없다 (참조 무결성 조건)

# 시저 암호

def solution(s, n):
    answer = ''
    alpa = 'abcdefghijklmnopqrstuvwxyz'
    Alpa = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    for i in s:
        if i in alpa:
            answer += alpa[(alpa.index(i)+n)%26]
        elif i in Alpa:
            answer += Alpa[(Alpa.index(i)+n)%26]
        else:
            answer += " "
            
    return answer

# 콜라츠 추측

def solution(num):
    answer = 0
    while num!=1:
        if num % 2 == 0:
            num = num//2
        else:
            num = num*3 +1
        answer+=1
        if answer == 500:
            answer =-1
            break
        
    return answer

# 하샤드 수

def solution(x):
    answer = True
    x_sum = sum(int(i) for i in str(x))
        
    if x % x_sum != 0:
        answer = False

    return answer

# 제일 작은 수 제거하기

def solution(arr):
    answer = []
    arr.remove(min(arr))
    if len(arr)==0:
        answer = [-1]
    else:
        answer = arr
    return answer

# x만큼 간격이 있는 n개의 숫자

def solution(x, n):
    answer = []
    for i in range(1,n+1):
        answer.append(x*i)
    return answer

# 평균 구하기

def solution(arr):
    return sum(arr)/len(arr)

# 짝수와 홀수

def solution(num):
    answer = ''
    if num%2 == 0:
        answer = "Even"
    else:
        answer =  "Odd"
    return answer

# 핸드폰 번호 가리기

def solution(phone_number):
    return '*'*(len(phone_number)-4)+ phone_number[-4:]

# 직사각형 별찍기

a, b = map(int, input().strip().split(' '))
for i in range(b):
    print('*'*a)

프로그래머스 - 깊이/너비 우선 탐색(DFS/BFS)

# 여행경로 (Level 3)

• Point . dic로 그래프 만들고 DFS로 풀기

from collections import defaultdict
def solution(tickets):
    # 특정 티켓의 인접 리스트를 구하는 함수
    def init_graph():
        routes = defaultdict(list)
        for key, value in tickets:
            routes[key].append(value)
        return routes

    # 스택을 사용한 DFS
    def dfs():
        stack = ["ICN"] # 첫시작은 ICN
        path = []  # 가려고하는 경로를 저장하는 변수
        while stack:  # stack이 비어있을 때까지
            top = stack[-1]
            # 특정 공항에서 출발하는 표가 없다면 또는 있지만 티켓을 다 써버린 경우
            if top not in routes or len(routes[top]) == 0:
                path.append(stack.pop())
            else:
                stack.append(routes[top].pop(0))
        return path[::-1]

    routes = init_graph() # 그래프로 만들기
    for r in routes: # 알파벳순 정렬
        routes[r].sort() 
    answer = dfs() # 경로 구하기
    
    return answer