스택쌓기

📌 FACTS

카페에 앉아 backjoon 문제 풀이 했음

3일차 면접 스터디 진행 했음

backjoon 문제 풀이함 ->14889번 풀이했음

(오늘 풀이한것) [https://thread-ounce-2af.notion.site/14889-b1d6154035da438db97bb06731acfd90]

백트래킹과 순열을 사용하면 쉽게 풀리는 문제였다.

n명의 사람이 주어지면 n번쨰 사람은 nij의 능력치를 가지는데 n00 의 경우 (0,0) 에 잇는 수치만큼 value를 가져간다.

공평한 팀 구성을 위해 게임을 하는 player 들은 항상 짝수로 주어지고 각 player들은 다른 player(n)번째 선수와 팀이 되엇을때 마다 player가 가지는 value값이 전부 다르다

i/j	0	1	2	3
0	0	2	6	8
1	3	0	6	8
2	4	2	0	8
3	8	2	6	0

이라는 데이터가 들어오면

진영 분배를 위해 A팀과B팀으로 나누기 위한 연산을 수행한다 i ) N//2

팀을 나눳을떄 1번 3번 과 0번과 2번이 팀이 되었다고 가정하자

ii) A =s13+ s31 이때 중복값이 존재하면 안되기 떄문에 중복을 제거 해준 후 연산하자 다음과 똑같이 B팀도 연산을 거친후 팀간의 능력치 값을 비교하고 다음 분기로 넘어간다 2번과 1번이 팀이되고 3번과 0번 처럼 분기를 쪼개어 연산을 지속해준다

from itertools import combinations as c

n = int(input())
array = [i for i in range(n)]
matrix = []
for _ in range(n):
    matrix.append((list((map(int, input().split())))))
result = int(1e9)
for r1 in c(array, n // 2):  # n/2 만큼
    start, link = 0, 0
    r2 = list(set(array) - set(r1))  # 중복제거
    for r in c(r1, 2):
        start += matrix[r[0]][r[1]]
        start += matrix[r[1]][r[0]]
    for r in c(r2, 2):
        link += matrix[r[0]][r[1]]
        link += matrix[r[1]][r[0]]
    result = min(result, abs(start - link))  # 횟수는 무조건 정수

print(result)

면접 스터디

면접 스터디에서는 BFS와DFS 그리고 JWT와 OAuth의 차이점에 대해 논의햇다.

알고리즘중 가장 많이 다루어봣고 가장 실생활과 가깝다고 느껴지는 알고리즘이다. 백트래킹과 유사하지만 그래프로 접근하여 단순하게 이해 할 수 잇었다.

DFS와 BFS 는 깊이와 넓이로 나뉘는데 상위 개념으로는 우선탐색이 있다.

미로를 탐색할 때 한 방향으로 갈 수 없을때 까지 계속 가다가 갈 수 없는 길에 도착 한다면, 가장 가까운 분기점으로 돌아가 돌아온 곳을 제외한 방향으로 다시 탐색을 시작하는 방법이고, 미로를 탐색 할 때 분기점이 발생하거나 인접한 길을 이동하는 방식이다

BFS는 구현이 DFS에 비해 복잡 하지만 검색속도가 빠른 장점이 있고 반대로 DFS는 구현이 쉽지만 검색 속도는 느리다. DFS의 경우 자기 자신을 호출하는 순환 알고리즘의 형태로 전위순회를 포함한 다른 형태의 트리순회는 모두 DFS의 한종류이다

BFS의 경우 큐라는 자료구조를 사용하고, 인접한 정점을 모두 저장하고 순서대로 방문하기 떄문에 스택으로는 구현이 어렵다, 또한 인접한 node를 발견과 동시에 방문이 이루어진다.

JWT와 OAuth의 차이

우선은 jwt와 oauth는 비교 대상이 될 수 없다고 생각한다.. jwt는 사과라면 oauth는 상자기 떄문인데 전문적인 단어로는 jwt는 token의 한 종류이고, oauth는 framewrok이기 떄문인데..

질문의 의도는 모르겠으나 가장 가까운 비교를 하자면

-> Oauth에서 나오는 OAuth bearer token과 단순한 jwt 토큰의 차이는 무엇인가? 가 연상된다.

OAuth 토큰은 어떤 사용자의 정보와 중요한 정보가 들어있지 않고 무작위, 랜덤의 문자열이 들어가있는데 JWT Token 같은 경우네는 유의미한 정보와 데이터들이 암호화 되어 있다.

JWT token의 단점으로는 명확한 정보를 가진 상태로 이 정보들을 db에서 사용자 정보 조작을 한 후 token을 직접 바뀐 내용들을 update 할 수 없다.

토큰을 이용해 데이터를 송/출력 할 경우 담을 데이터가 커진다면 트래픽 크기에 영향을 미치는 단점이 있다.

데이터베이스에서 인덱스를 사용하는 이유?, 장단점은 무엇인가?

 a. 인덱스란 무엇인가부터 접근해보자.
    i. 인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기위한 labelling이라고 생각한다.
        b.인덱스의 구조
            대표적으로 해시 테이블을 가장 많이 사용하고 빠른 데이터 검색이 필요할 떄 해시테이블 구조를 기용한다, 하지만 부등호 연산이 자주 사용되는 db의 경우 검색을 위해서 B-tree 또는 B+tree를 사용한다
        c. B-Tree?
            데이터베이스오 파일 시스템에서 널리 사용되는 트리로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리를 말한다.
        d. B+Tree?
            자식 노드가 2개 이상인 B-tree를 개선 시킨 구조로, 리프노드만 인덱스와 함께 데이터를 가지고 있고, 나머지 노드들은 데이터를 찾기 위한 인덱스값만을 보유한다.
                -> 리프 노드들은 링크드리스트로 구현되어 있다.
                -> 데이터 노드 크기는 인덱스 노드 크기와 같지 않아도 된다.

=> 사용하는 이유
    -> 책 내용 중 어느 부분을 표시하여 다음에 책을 펼 쳤을때 해당하는 부분을 찾기 위해서 marking을 하는 행위
    -> 만약 사용하지 않는 경우 ?
    책을 펼친 후 모든 책의 페이지를 검사해서 찾는 부분을 찾아야한다
    
=> 장/단점
    -> 테이블을 조회하는 속도와 그에 따른 성능을 향상 시킬 수 있다.
    -> 전반적인 시스템의 부하를 줄인다
    ---> full scan을 수행하거나 search를 수행 당하는 데이터들이 많을떄 부하를 줄일 수 있다.
    ->>단점 
    -> 인덱스를 관리하기 위해 db의 약 10%에 해당하는 저장공간을 소모해야한다.
    -> 인덱스를 관리하기 위한 추가 작업이 필요하다
    -> 인덱스를 잘 못 사용하는 경우 오히려 성능이 더 저하되는 역효과 발생
    EX) Create,Delete,Update가 빈번하게 일어나는 경우!

- 규모가 작은 테이블
- INSERT/UPDATE/DELETE가 빈번하지 않은 컬럼
- JOIN/WHERE ORDER BY 처럼 연관관계에 자주 이용되는 컬럼
- 데이터 중복도가 낮은 컬럼

[] 설날 맛있는거 많이 먹기
[] 연휴 잘 쉬고 backjoon 하루 3문제 이상풀기
[] 오늘 학습한 내용들 개발 블로그에 잘 정리하기
[] 이력서 다듬기
[] 카카오 2차 이력서 1500자 쓰기(경력사항)
[] 다음 면접스터디를 위해 로그인 로직에 대해 아는것 서술해놓기