• 여러 개의 데이터가 존재할 경우 구간의 합을 구하는데 사용하는 자료구조
• 트리 종류 중에 하나이고 이진 트리의 형태이며 특정 구간의 합을 가장 빠르게 구할 수 있다. O(logN)

참고 사항 파이썬 배열 생성 시간 비교

import time
start = time.time()  # 시작 시간 저장
print('-------')
print('arr = [0 for i in range(n)] 시간')
for i in range(100):
    arr= [0 for i in range(1000000)]
print("time :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간
print('-------')
start = time.time()  # 시작 시간 저장
print('arr = [0] * 1000000 시간')
for i in range(100):
    arr= [0] * 1000000
print("time :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

반복문으로 배열 생성과 [0] X n 으로 시간 차이가 궁금해서 한번 비교를 해보았는데 시간 비교를 해보니 10배 이상 차이가 난다.. 배열 초기화를 할 경우에는 [0] X N 으로 하자!!

구현 과정

arr = [1,2,3,4,5,6,7,8,9,10]
tree = [0] * (len(arr) *4)

tree 의 크기를 할당 할때에는 배열의 개수가 N 일때는 N보다 큰 가장 가까운 N의 제곱수를 구할 뒤 그것의 2배를 하여 세그먼트 트리의 크기를 만들어야 한다 편하게 구하기 위해서 N에 4를 곱한 크기만큼 생성을 해두면 편하다. 이미지 참고 ![] (https://velog.velcdn.com/images%2Fkimdukbae%2Fpost%2Fa228321e-2e5d-4310-b57c-7b6c87aec291%2Fimage.png) 이런식으로 배열이 초기화가 된다.

# 세그먼트 트리의 초기화
# start : 배열의 시작 index , end : 배열의 마지막 index
# 시작 node는 1부터 시작
def init(node,start,end):
    if start==end:
        tree[node] = arr[start]
        return tree[node]
    mid = (start+end) //2
    tree[index] = init(node*2,start,mid) + init(node*2+1,mid+1,end)
    return tree[index]

구간 합을 구하는 함수

원하고자 하는 구간에 들어왔을 경우에만 더해서 return 을 해주면 된다

# left , right : 구간 합을 구하고자 하는 범위
def subsum(node,start,end,left,right):
    # 범위 밖에 있는 경우
    if left > end or right < start:
        return 0
    # 범위안에 들어갈 경우
    if left <= start and right >= end:
        return tree[node]
    # 범위를 나눠서 더해줌
    mid = (start+end)//2
    c_left = subsum(node*2,start,mid,left,right)
    c_right = subsum(node*2+1,mid+1,end,left,right)
    return c_left+c_right

특정 원소의 값을 수정하는 함수

# 범위안에 들어가면 변경하면 된다.
def update(node,start,end,left,right,index,value):
    if index < start or index > end:
        return
    # 범위 안에 있으면 변경
    tree[node] += value
    if start==end:
        return
    mid = (start+end) // 2
    update(node*2,start,mid,index,value)
    update(node*2,mid+1,end,index,value)

Json 포맷을 이용하여 사용자에 대한 속성을 저장하는 Claim기반 WebToken 인증에 필요한 정보들을 암호화시킨 토큰 이다. JWT 기반 인증은 JWT Token ( Access Token) 을 HTTP 헤더에 실어 서버가 클라이언트를 식별하는 방식이다.

서버 기반 인증 시스템

서버의 세션을 사용하여 사용자 인증을 하는 방식 ( 데이터베이스나 램 ) 에서 사용자의 인증정보를 관리 클라이언트의 상태를 계쏙 유지해놓고 사용하므로 사용자가 증가함에 따라 성능문제가 일어날 수 있다.

토큰 기반 인증 시스템

인증받은 사용자에게 토큰을 발급 , 로그인이 필요한 작업일 경우에는 헤더에 토큰을 같이 보내 인증받은 사용자인지 확인을 한다. 서버 기반 인증 시스템과는 다르게 상태를 유지하지 않으므로 Stateless한 특징이 있다.

JWT 구조

XXXXXX.YYYYYY.ZZZZZZ
Header , Payload , Signature

Header

알고리즘 형식

{
 "alg" : "HS256",
 "typ" : "JWT" 
}

📺 alg : 서명 암호화 알고리즘 📺 typ : 토큰 유형

Payload

토큰에서 사용할 정보의 조각들인 Claim이 담겨있음

{
    "name" : "slbin",
    "age" : "25"
}

Key-value 형식으로 이루어진 한 쌍의 정보를 Claim이라고 칭한다.

페이로드에는 *Registed Claims * *Public claims * *Private claims * 세 가지로 나누어짐

Registed claims : 미리 정의된 클레임

iss(issuer 발행자) exp(expireation time 만료 시간) sub(subject 제목) iat(issued At 발행 시간) jti(JWI ID) 등이 있고 필수는 아니다.

Public claims : 사용자가 정의할 수 있는 클레임

공개용 정보 전달을 위해 사용이 된다.

private claims : 당사자들 간에 정보를 공유하기 위한 클레임

외부에 공개되도 상관이 없지만 해당 유저를 특정할 수 있는 정보들을 담는다.

Signature

헤더의 인코딩 값과 정보의 인코딩 값을 합친 후 비밀키로 해쉬를 하여 생성

JWT를 이용한 인증과정

1)

사용자가 로그인 인증을 요청

2)

서버에서 Header , Payload , Signature를 정의 한다 암호화를 하여 JWT를 생성하고 클라이언트에게 발급을 한다.

3)

클라이언트는 서버로부터 받은 JWT 로컬스토리지에 저장 API를 요청할때 헤더에 토큰을 담아서 보낸다.

4)

서버에서 발행한 토큰이랑 일치하면 인증을 해준다. 인증이 통과되었으면 페이로드에 들어있는 유저의 정보들을 클라이언트에 돌려준다.

5)

액세스 토큰의 시간이 만료되었으면 클라이언트는 리프래시 토큰을 이용해서 서버로 부터 새로운 액세스 토큰을 발급 받는다.

Access Token , Refresh Token

실질적으로 로그인이 필요한 기능을 사용할때는 Access Token을 헤더에 담아서 보내고 Access Token을 발급 받기위한 토큰이 Refresh Token 이다.

마무리

Access Token만을 사용했었는데 Refresh Token까지 사용하려니 어지럽다.

https://taenami.tistory.com/69 여기 있는 babel까지 하면 된다.

적용이 안된이유는 styled-componenet보다 먼저 html 코드들이 불러와져서 그렇다.

pages/_app.tsx 에서

import '../styles/globals.css';
import theme from '../styles/globals'
import { ThemeProvider } from 'styled-components';
import GlobalStyle from '../styles/globals';

function MyApp({ Component, pageProps }) {
  return (
  <ThemeProvider theme={GlobalStyle}>
    <Component {...pageProps} theme={theme}/>
    </ThemeProvider>
    )
}

export default MyApp;

import { ThemeProvider } from 'styled-components';
import GlobalStyle from '../styles/globals';

두개를 import 해주고

  <ThemeProvider theme={GlobalStyle}>
    <Component {...pageProps} theme={theme}/>
  </ThemeProvider>

Thmeprovider 로 감싸서 theme을 전역으로 내려줘야한다.

🧭 플로이드 와샬

용도 : 각 정점간 최단경로를 구할 때

• 공간 복잡도 : v^2
• 시간 복잡도 " v^3

장단점

• 소스가 더 간결함
• 간선 수가 많으면 다익스트라 알고리즘보다 빠를 수 있음
• 시작점으로부터 각 정점까지 최단거리만 구할때에 보통 다익스트라가 압도적으로 빠름
• 그래프에 음의 가중치 간선이 있으면 다익스트라 알고리즘은 사용불가 But 플로이드 알고리즘은 사용 가능함

🧭 다익스트라

용도 : 시작점으로 부터 나머지 정점까지 최단거리를 구할시에 사용

• 공간 복잡도 : v^2 , V+E(인접리스트)
• 시간 복잡도 " v^2(인접행렬) 우선순위큐 VlogV

🖥 사용시기

• 정점간 최단경로를 모두 구해야함 간선이 매우 많으면 플로이드 알고리즘 간선이 작을시 다익스트라
• 시작점으로부터 나머지 정점만 최단거리를 구할때에는 다익스트라를 사용
• 시간에 영향을 안받을경우 플로이드를 사용함
• 음의 가중치가 존재하면 플로이드와샬을 사용함

🧭 다익스트라 예제

최단경로 백준

import sys
import heapq

input = sys.stdin.readline
INF = 1e9


def dijkstra(start):
    heap = []
    heapq.heappush(heap, (0, start))  # 가중치 , 간선
    distance[start] = 0
    while heap:
        cost, index = heapq.heappop(heap)
        if distance[index] < cost:
            continue
        # 목적지까지 거리가 현재 인덱스의 cost보다 작을 경우에는
        # 굳이 다음걸 확인할 필요가 없다.
        for next, c in arr[index]:
            if distance[next] > cost + c:
            # 목적지 next인덱스의 가중치보다 현재 인덱스의 가중치 + (현재인덱스에서 목적지 간선의 가중치)가
            # 더 작을경우에 가중치를 업데이트 시켜준다
                distance[next] = cost + c
                # 가중치 업데이트
                heapq.heappush(heap, [cost + c, next])


n, m = map(int, input().split())
start = int(input())
arr = [[] for i in range(n + 1)]
distance = [INF for i in range(n + 1)]
for i in range(m):
    u, v, w = map(int, input().split())
    # u에서 v로 가는 가중치는 w이다.
    arr[u].append([v, w])
dijkstra(start)
for i in range(1, n + 1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

SVG 기반 아이콘을 활성화 시키기 위한 기본패키지 설치

npm i @fortawesome/fontawesome-svg-core

Font Awesome 아이콘에 대한 패키지 설치 Solid , Regular , Brands 3개의 카테고리가 무료임

npm i @fortawesome/free-solid-svg-icons @fortawesome/free-regular-svg-icons @fortawesome/free-brands-svg-icons

마지막으로 Font Awesome을 컴포넌트 형태로 사용할 수 있도록 해주는 패키지 설치

npm i @fortawesome/react-fontawesome

사용법

icon props안에 이름을 넣으면 사요이 가능하다

import React from "react";
import { faCamera } from "@fortawesome/free-solid-svg-icons";
import { FontAwesomeIcon } from "@fortawesome/react-fontawesome";
<FontAwesomeIcon icon={faCamera} />

크기를 늘리고 싶으면 size ="2x"를 넣으면 된다

<FontAwesomeIcon icon={faCamera} size = "2x" />

액션 (Action)

상태에 변화가 필요할 때 액션이라는 것을 발생 시킴 이것은 하나의 객체로 표현됨 액션 객체는 다음 형식으로 이루어짐

{
    type : "TOGGLE_VALUE"
}

type필드는 필수로 있어야한다. 그외의 값은 개발자 마음대로..

{
    type : "CHG_INPUT"
    data: {
        id:0,
        text:"텍스트"
    }
}

액션 생성함수 (Action Creator)

액션 생성함수는 액션을 만드는 함수 파라미터를 받아와서 액션 객체 형태로 만들어준다

export function add(data){
     return{
       type:"ADD",
      data
    } ;
}
// arrow function 으로도 가능함
export const chginp= text =>({
  type:"CHG_INP",
  text
});

액션 생성함수를 만드는 이유 ? 나중에 컴포넌트에서 더 쉽게 액션을 발생시키기 위함 그래서 함수 앞에 export 키워드를 붙여서 다른 파일에서 불러와서 사용함

리듀서 (Reducer)

리듀서는 변화를 일으키는 함수이다. 두가지의 파라미터를 받아온다.

function reducer(state,action){
      // 여기에 업데이트 로직은 만든다.
     return alterState; 
}

function counter(state, action) {
  switch (action.type) {
    case 'INCREASE':
      return state + 1;
    case 'DECREASE':
      return state - 1;
    default:
      return state;
  }
}
// 위와 같이 리듀서를 작성해준다.

리덕스를 사용 할 때에는 보통 여러개를 만들고 이것들을 합쳐서 루트 리듀서 (Root Reducer)를 만들 수 있다. 루트 리듀서 안의 작은 리듀서는 서브 리듀서라고 부른다.

스토어 (Store)

리덕스는 한 어플리케이션당 하나의 스토어를 만든다. 스토어 안에는 현재 앱 상태 , 리듀서 , 추가적인 내장 함수들이 있다.

디스패치 (dispatch)

디스패치는 스토어의 내장 함수 중 하나 액션을 발생 시키는 것 이라고 이해. dispatch에는 action을 파라미터로 전달한다.

입력 , 출력

50점 solution

import sys

input = sys.stdin.readline

name = input().strip()
n = int(input())
for i in range(n):
    a = input().split()
    sum = 0
    for j in range(int(a[1]), int(a[2]) + 1):
        if name[j] == a[0]:
            sum += 1
    print(sum)

그냥 무식하게 2중 반복문을 사용함 20 * 20 * 20 시간 복잡도로 충분히 가능한 시간인줄 알았는데 50점이 나왔다

100점 soltuion

import sys

input = sys.stdin.readline

name = input().strip()
n = int(input())
arr = [[0 for i in range(26)] for i in range(len(name))]
arr[0][ord(name[0]) - 97] = 1
for i in range(1, len(name)):
    arr[i][ord(name[i]) - 97] = 1
    for j in range(26):
        arr[i][j] += arr[i - 1][j]
for i in range(n):
    a = input().split()
    if int(a[1]) > 0:
        res = arr[int(
            a[2])][ord(a[0]) - 97] - arr[int(a[1]) - 1][ord(a[0]) - 97]
    else:
        res = arr[int(a[2])][ord(a[0]) - 97]
    print(res)

#26개

설명

누적합 풀이로 소문자 az까지 총 26개 * name의 길이 로 2차원 배열을 생성 az를 아스키코드로 변환 한 뒤에 -97을 하면 0~25까지 된다

그리고 arr[i][j] += arr[i-1][j] + 현재i번째 위치에 알파벳 아스키코드-97 을 해서 0번째 부터 끝까지 누적으로 몇개 나왔는지 전부 2차원 배열안에 넣는다. 그래서 ij번째 까지 알파벳이 몇개 나왔는지 확인하려면 arr[i][askii] - ar[j-1][askii] ij번째 까지 나온 알파벳askii의 개수를 알 수 있다.

예외처리

0~i번재 까지라면 arr[i][askii] - 0 을 해줘야한다.

// 원시타입
const num: number = 123;
const str: string = 'string';
const tru: boolean = true;
let assdf : any = 'asdf';
// 원시값
const nul: null = null;
const undef: undefined = undefined;

기본적으로 원시타입 , nul , undefined 도 사용이 가능하다.

배열

const arr : number[] = [12,3,4,1];
const stringarr : Array<string> = ['asd','asdf']

배열의 선언은 두가지 방식으로 할 수 있다. 타입[] , Array< type >

객체

// interface
interface MyInfo {
  nickname: string;
  age: number;
}

interface MyAccountInfo extends MyInfo {
  id: string;
  password: string;
}

인터페이스를 사용해서 하는법 extends에 의존하게 된다.

// type
type MyInfo = {
  nickname: string;
  age: number;
};

type MyAccountInfo = {
  id: string;
  password: string;
} & MyInfo;

&연산자로 확장이 가능함

funtion abc(a:number|string){
    ...
}

식으로 | 연산자로 타입을 여러개 지정할 수 있다.

let b : (a:number,b:number) => number
// 람다식을 사용할 때에 이런식으로 타입을 지정해줄수도있음
b = (c,d) => {
    return 1234
}
console.log(b(123,12345))
const a = (a : number , b : any) : void =>{
    console.log(1234)
}
// void는 리턴값이 없음
// 람다식을 사용할때는 이런식으로 사용이 가능함

이런식으로 람다식도 사용이 가능하다.

컴퓨터 전역에 설치하기 위해서

sudo npm i -g typescript

를 실행 그리고 tsc -v 를 쳐서 설치가 와료되었는지 확인

TypeSciprt 실행

우선 tsc 명령어로 js로 바꿀수있는데 tsc test.ts 이렇게 실행을하면 js로 바꿔준다.

하지만 우리는 편하게 사용을 하고싶다.

ts-node로 바로 컴파일

npm i -g ts-node 를 터미널에 실행 그리고 ts-node test.ts를 할게되면 바로 실행이 된다.

create-react-app 으로 리액트 폴더를 생성후

npm install typescript @types/node @types/react @types/react-dom @types/jest

패키지를 설치를 해준다

그리고

npx typescript --init

를 실행해주면 tsconfig.json 파일이 생성되면서 js를 타입스크립트로 바꿔주게된다.

처음 설정

js 파일을들을 ts,tsx로 바꿔주면 실행이 되지 않을것이다. 그 경우 https://pythonq.com/so/reactjs/95106 여기 사이트대로 tsconfig.json을 수정하고 tsx,ts 파일들 최상단에

import React from 'react';

선언을 해주면 된다.

타입스크립트를 설치 할 때 에러가 뜨면 권한을 sudo로 줘서

sudo npm install -g typescript

로 설치하면 전역에 설치가 된다.

입력 , 출력

solution

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
for i in range(n):
    a = input().strip()
    m = int(input())
    flag = 1
    arr = input().strip()
    dq = deque(arr[1:-1].split(','))
    if m == 0:
        dq = deque()
    R = 0
    for i in range(len(a)):
        if a[i] == 'R':
            R += 1
        elif a[i] == 'D':
            if len(dq) == 0:
                print('error')
                flag = 0
                break
            else:
                if R % 2 == 0:
                    dq.popleft()
                else:
                    dq.pop()

    if flag == 0:
        continue
    else:
        if R % 2 == 0:
            print('[' + ",".join(dq) + ']')
        else:
            dq.reverse()
            print('[' + ",".join(dq) + ']')

설명

키포인트

1. 입력 배열의 파싱 , 0번째 인덱스와 마지막 인덱스를 제외하면 [1,2,3,4] = > 1,2,3,4 로 만들어지므로 arr[1:-1] 로 하면 1,2,3,4 라는 문자열이 만들어진다. 여기서 split(',') 하면 ['1','2','3','4'] 가 만들어진다.
2. R을 할 시에는 배열을 reverse 해준다. 하지만 n번의 연산이 필요하다. R의 최대 횟수 100,000 , 배열의 최대 크기 100 , 테스트케이스 100개 100 * 100,000 * 100 = 1,000,000,000 1억번의 시간이 대략 소요가 된다. 시간초과가 날수도 있기때문에 R을 짝수번 했을경우에는 배열을 reverse시키지 않아도 괜찮다. 그래서 R이 나왔을 경우에는 카운트를 해줘서 D가 나왔을때 R이 짝수일경우에는 popleft , 홀수일경우에는 pop 을 해주고 마지막에 R이 홀수일 경우에 배열을 reverse해서 출력해주면 된다.

예외처리

배열의 크기가 0인 경우에 D(삭제)를 실행할 경우 error메세지를 출력한다. 데크의 크기가 0 인경우에 D를 실행할 경우 , 입력 배열의 개수가 0 인 경우 두가지 경우를 생각하면 된다.

입력 , 출력

solution

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
arr = [[] for i in range(n + 1)]
res = 0


def dfs(idx, cost):
    global res
    for i, c in arr[idx]:
        if visited[i] == 0:
            visited[i] = cost + c
            dfs(i, c + cost)


for i in range(n):
    cur = list(map(int, input().split()))
    i = 1
    while 1:
        if cur[i] == -1:
            break
        arr[cur[0]].append((cur[i], cur[i + 1]))
        i += 2
visited = [0 for i in range(n + 1)]
dfs(1, 0)
visited[1] = 0
res = 0
idx = 0
for i in range(2, n + 1):
    if res < visited[i]:
        res = visited[i]
        idx = i
visited = [0 for i in range(n + 1)]
dfs(idx, 0)
visited[idx] = 0
print(max(visited))

설명

1. 특정 노드를 선택해서 가장 먼 거리에 있는 노드(B)를 찾는다.
2. 찾은 노드(B) 에서 dfs로 가장 먼 거리에 있는 노드의 거리가 트리의 지름이된다.

해당 알고리즘의 증명 트리의 지름 증명

트리의 지름을 구하는 방법만 알면 dfs를 두번 돌리면 풀리는 간단한 문제

입력 , 출력

solution

import sys

input = sys.stdin.readline


def find(a):
    if a == parent[a]:  # 자신이 루트노드면 자신을 반환
        return a
    parent[a] = find(parent[a])  # 루트노드를 찾음
    # 메모이제이션과 비슷한 아이디어
    # a의 부모를 find(parent[a])로 바꿔줌
    return parent[a]


def union(a, b):
    a = find(a)
    b = find(b)
    # a , b의 루트노드를 찾아줌
    if b < a:
        parent[a] = b
    else:
        parent[b] = a


n = int(input())
m = int(input())
arr = []
parent = [i for i in range(n + 1)]
res = 0
for i in range(m):
    a, b, c = map(int, input().split())
    arr.append((
        c,
        a,
        b,
    ))

arr.sort(key=lambda x: x[0])
for dis, a, b in arr:
    if find(a) != find(b):  # 루트가 같으면 할 필요가 없음
        union(a, b)
        res += dis
print(res)

설명

최소스패닝 트리를 구현만 하면 풀리는 문제이다 처음에 parent 배열을 만든 뒤에 자기 자신을 조상으로 만든다. 그리고 (a,b) = 연결된 노드 , c = 간선의 가중치 간선의 가중치를 기준으로 입력받은 배열로 정렬해준다.

최소 스패닝트리

사이클 없이 최소한의 가중치로 연결을 하는 것 이다. find로 루트 노드를 찾는다 find 함수에서 자신이 루트노드 일 경우에는 자신을 return해준다 union 함수에서 받은 간선 두개의 루트 노드를 뽑아준다 처음 union에 들어가기 전에 find로 루트노드를 먼저 찾아서 같지 않다면 연결을 해준다 여기서는 노드 (a,b) 중에 노드 번호가 작은것을 루트노드로 지정을 해준다. 여기서 배열을 가중치를 기준으로 정렬을 했기 때문에 최소한의 가중치로 연결이 된다. 그래서 연결에 성공하면 res에 가중치를 계속 더해주면 결과값이 나온다.

입력 , 출력

solution

import heapq
import sys

input = sys.stdin.readline

n = int(input())
heap = []
for i in range(n):
    arr = list(map(int, input().split()))
    for j in range(n):
        if len(heap) == n:
            a = heapq.heappop(heap)
            if a < arr[j]:
                heapq.heappush(heap, arr[j])
            else:
                heapq.heappush(heap, a)
        else:
            heapq.heappush(heap, arr[j])
print(heapq.heappop(heap))

설명

시행착오

1번 메모리 초과

import heapq
import sys

input = sys.stdin.readline

n = int(input())
heap = []
for i in range(n):
    arr = list(map(int, input().split()))
    for j in range(n):
        heapq.heappush(heap, (-arr[j], arr[j]))
for i in range(n):
    a = heapq.heappop(heap)[1]
print(a)

틀린이유

최대힙으로 만들어서 n번째를 출력하는 방식으로 구현을 함 하지만 메모리초과..

why??

n은 최대 1500 처음 반복문 에서 nlogn(n = 1500* 1500 =2250000) 4500000log(1500)≈14292410.665750567

두번째 nlogn (n = 1500) 1500log(1500)≈4764.136888584

으로 반복횟수로만은 충분한 시간이라고 생각했다. 그래서 굳이 두번째 반복문을 사용할 필요가 없어서

2번 메모리 초과

import heapq
import sys

input = sys.stdin.readline

n = int(input())
heap = []
for i in range(n):
    arr = list(map(int, input().split()))
    for j in range(n):
        heap.append(arr[j])
heap.sort()
print(heap[n * n - n])

이렇게 풀리면 골드 문제가 아니였겠지.. 또 메모리 초과.. 시간의 문제가 아니라 배열이 너무 커서 메모리초과가 난듯 했다. 배열의 최대 크기가 2250000 이라서

그래서 배열의 크기를 줄일 수 있는 방법은 n번째 큰 수를 찾기 위해서는 우선순위큐 , 최소힙으로 크기를 n으로 고정 해서 첫번째 인덱스를 출력하면 n 번째 큰 수 이기 때문에 heap의 크기가 n일 경우에는 pop을 하여서 비교 한 뒤 입력받은 크기가 pop한 수보다 클 경우에는 입력받은 숫자를 heap에 넣고 아닐경우에는 다시 pop한 숫자를 넣는 방식으로 heap의 크기를 n으로 고정하는 풀이를 선택했다.

후기

틀린 이유를 시간복잡도만 생각해서 틀렸었다. 맨날 시간복잡도만 생각했는데 공간복잡도도 생각해봐야 하는 계기가 되었다.

입력 , 출력

solution

import sys

input = sys.stdin.readline


def bisearch(start, end):
    global s1, s2, res
    while start <= end:
        if abs(arr[start] + arr[end]) < res:
            s1 = arr[start]
            s2 = arr[end]
            res = abs(arr[start] + arr[end])
        if arr[start] + arr[end] < 0:
            start += 1
        else:
            end -= 1


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
res = 2e+9 + 1
s1 = 0
s2 = 0
bisearch(0, n - 1)
print(s1, s2)

설명

키포인트

1. 이분탐색 , 투포인터를 사용해서 풀이
2. mid값으로 하지 않고 left , right만 사용함
3. 두 값을 더했을 경우 0보다 작은경우

마이너스 + 마이너스
마이너스 (절대값이 더 큼) + 플러스
위 두가지 경우가 있다.
이럴 경우에는 배열을 정렬했기때문에
왼쪽 인덱스를 1씩 더해주면 된다.

4. 0보다 같거나 큰경우는 오른쪽 포인터에 인덱스를 1씩 더해준다.
5. 두가지 포인터를 더했을때 절댓값이 기존에 저장된 정보보다 작을 경우에는 res에 값을 갱신해준다.

입력 , 출력

solution

import sys

sys.setrecursionlimit(10**5)
iuput = sys.stdin.readline


def dfs(a, b):
    global res
    sum = 0
    rcur = b
    sarr = []
    for i in arr[a]:
        cur = dfs(i[0], i[1])
        sarr.append(cur)
        rcur = max(b + cur, rcur)  # 밑에서 올라온것 중에 가장 높은값을 저장
    # 자식노드가 2개 이상일 경우도 있으니 반복문을 돌려 2개를 연결했을때 가장 큰 값을 지름으로 사용
    for i in range(len(sarr) - 1):
        for j in range(i + 1, len(sarr)):
            sum = max(sum, sarr[i] + sarr[j])
    res = max(res, sum, rcur) # sum을 다 합쳐도 일자로 한 것이 더 길 경우를 생각해서 rcur도 같이 넣어서 계산

    return rcur


n = int(input())
arr = [[] for i in range(n + 1)]
res = 0
for i in range(n - 1):
    a, b, c = map(int, input().split())
    arr[a].append([b, c])
dfs(1, 0)
print(res)

설명

키포인트

1. 이진트리가 아니다 자식 노드가 2개 이상일 경우도 생각해야함
2. 일자로 길이를 했을경우가 자식노드 두개를 연결했을 경우 보다 더 길 수도 있다.

DFS를 할 때 a -> b노드 의 가중치를 인자로 넣어준다. 다음 b의 자식노드를 돌아서 가장 긴 값을 받은 가중치 인자랑 더해서 return을 해준다. 만약 리프노드일 경우에는 받은 간선의 가중치 값만 return을 하게 된다. 그리고 자식노드가 2개 이상일 경우 두개를 이을 수 있는 모든 경우의 수를 반복문으로 확인하여 가장 높은값을 계산한다. 그리고 res에 저장된 값 보다 클경우 res값을 갱신해준다. res의 값을 갱신해줄때 자식노드 2개를 이은것 보다 ( 가중치 b의 값 + 자식노드중 가장 긴 가중치 ) 도 같이 max함수에 넣어줘서 🔥🔥🔥🔥 [ res에 저장된값 , 자식노드 2개를 이은 값 , ( 가중치 인자 b의 값 + 자식노드중 가장 긴 가중치 ) ]
이 3개를 비교하여 res의 값을 갱신을 해준다.

후기

내가 이겼다.

입력 , 출력

solution

import sys
from collections import deque

input = sys.stdin.readline

Max = 100001
n, m = map(int, input().split())
dq = deque()
dq.append(n)
dis = [-1 for _ in range(Max)]
dis[n] = 0
res = 0
if n == m:
    res = 1
while dq:
    a = dq.popleft()
    if a * 2 < Max:
        if dis[a * 2] == -1:
            dq.append(a * 2)
            dis[a * 2] = dis[a] + 1
        elif dis[a * 2] == dis[a] + 1:
            dq.append(a * 2)
        if a * 2 == m and dis[a] + 1 == dis[m]:
            res += 1
    if a + 1 < Max:
        if dis[a + 1] == -1:
            dq.append(a + 1)
            dis[a + 1] = dis[a] + 1
        elif dis[a + 1] == dis[a] + 1:
            dq.append(a + 1)
        if a + 1 == m and dis[a] + 1 == dis[m]:
            res += 1
    if a - 1 >= 0:
        if dis[a - 1] == -1:
            dq.append(a - 1)
            dis[a - 1] = dis[a] + 1
        elif dis[a - 1] == dis[a] + 1:
            dq.append(a - 1)
        if a - 1 == m and dis[a] + 1 == dis[m]:
            res += 1
print(dis[m])
print(res)

설명

키포인트

1. (예외처리) n == k 일 경우에는 res 0 , 1 이 출력되어야함
2. 방문처리 , EX) 10이란 숫자에 방문횟수가 1번 이상일수도 있다.

예외처리만 잘 해주면 BFS만 하면 정답이 나오는 것 같다.

입력 , 출력

solution

import sys
from collections import deque

input = sys.stdin.readline

Max = 100001
n, m = map(int, input().split())
dq = deque()
dq.append(n)
dis = [-1 for _ in range(Max)]
dis[n] = 0
while dq:
    a = dq.popleft()
    if a == m:
        break
    if a * 2 < Max and dis[a * 2] == -1:
        dq.appendleft(a * 2)
        dis[a * 2] = dis[a]
    if a + 1 < Max and dis[a + 1] == -1:
        dq.append(a + 1)
        dis[a + 1] = dis[a] + 1
    if a - 1 >= 0 and dis[a - 1] == -1:
        dq.append(a - 1)
        dis[a - 1] = dis[a] + 1
print(dis[m])

설명

키포인트

1. 현재 위치에서 *2 로 이동하는것은 비용이 0 이다.
2. 1번에 의해서 큐에 제일 앞에 넣어줘서 *2로 이동할 수 있는 모든경우의 수 를 dis(거리)에 저장을 해준다.
3. 그 이후에 + 1 , -1 거리를 이동하는 경우를 넣어준다.

제일 중요한건 *2로 이동하는 가중치가 0 이기 때문에 체크를 할 경우에 큐에 가장 앞에 넣어주는게 제일 중요한 키포인트

입력 , 출력

solution

def bi_search(start, end):
    global res
    mid = 0
    while start <= end:
        mid = (start + end) // 2
        temp = 0
        for i in range(1, n + 1):
            temp += min(n, mid // i)
            # mid // i 를 하는 이유?
            # 해당행에서 mid보다 작은 수를 구하는 방법은
            # mid / i 를 하면 해당 행에서 mid보다 작은 수의 개수를 찾을 수 있음
            # 하지만 3*3에서 행에 최대 개수는 3인데
            # 6/1 을 할 경우에는 6개가 나와서
            # mid / i 의 값이n의 값보다 커질경우
            # 최대개수인 n을 삽입하는것임
        if temp >= m:
            # mid보다 작은수의 개수가 m이랑 같거나 크면
            # 더 작아져야하기 때문에 end값을 낮춰줌
            res = mid
            end = mid - 1
        else:
            start = mid + 1


n = int(input())
m = int(input())
arr = []
res = 0
bi_search(1, m)
print(res)

설명

키포인트

1. k번째 수는 최대 k값을 가짐
2. k번째의 수 보다 작은 수의 개수를 찾음
3. mid의 값보다 작은 수의 개수는 EX) 3 * 3 에서 7보다 작은 수의 개수는 11 ~ 13 = 3개 = min(n,7/1) = 3 21 ~ 23 = 3개 = min(n,7/2) = 3 31 ~ 32 = 2개 = min(n,7/3) = 2 즉 min(n,mid/i)를 n번 하면 mid의 값보다 작거나 같은수의 개수를 찾을수 있음

나머지 설명은 주석