Slow but steady wins the race

문제

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

풀이

1. 한 노드 기준에서 각 정점까지 거리를 구하기
2. 가장 먼 길이에 해당하는 노드 찾기
3. 2번의 노드를 기준으로 거리 구하는 과정을 한번 더 반복하면 됨

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def dfs(idx,v):
    for n_idx, n_val in tree[idx]:
        if visited[n_idx] == -1:
            visited[n_idx] = v+n_val
            dfs(n_idx,v+n_val)

n = int(input())
tree = {}
for i in range(1,n+1):
    tree[i] = []
for _ in range(n-1):
    a,b,c = map(int, input().split())
    tree[a].append([b,c])
    tree[b].append([a,c])


visited = [-1]*(n+1)
visited[1] =0
dfs(1,0)
last_node = visited.index(max(visited))
visited = [-1] * (n + 1)
visited[last_node] = 0
dfs(last_node,0)
print(max(visited))

가장 긴 증가하는 부분 수열의 '길이'을 구하는 방법은

1. DP(Dynamic Programming) - 동적 계획법

2. Binary Search - 이분 탐색

으로,, 이전 게시글 참고하기 : https://bskwak.tistory.com/259 

이번 게시물은 '길이'가 아닌 가장 긴 증가하는 부분 수열(LIS) 자체를 구하는 방법이다.

풀이 방법을 간단하게 설명하면,

1. dp를 통해 LIS 길이 구하기

2. 역추적하여 배열 구하고 뒤집으면 구할 수 있음

관련 문제 : 

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

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

dp = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i]>arr[j]:
            dp[i] = max(dp[i],dp[j]+1)
            
max_len = max(dp)
idx = dp.index(max_len)

res = []
while idx>=0:
    if dp[idx] == max_len:
        res.append(arr[idx])
        max_len -=1
    idx -=1

res.reverse()
print(*res)

max_len : 가장 긴 증가하는 부분 수열의 길이 

idx : max_len에 해당하는 위치 

res : 가장 긴 증가하는 부분 수열을 담을 배열

 arr = [10, 20, 10, 30, 20, 50] 일때, 

dp =[1, 2, 1, 3, 2, 4]

max_len = 4 이고, idx = 5 (초기값)

반복문을 하나씩 실행하면, 아래와 같이 추가된다. 즉, idx 4->3->2->1 에 해당하는 값을 추가하면 된다..

[50]
[50, 30]
[50, 30, 20]
[50, 30, 20, 10]

문제는,, 이렇게 풀면 14003 문제처럼 n의 범위가 커졌을 때, 시간 초과가 난다..

관련 문제 : https://www.acmicpc.net/problem/14003

위에서 dp 구하는 부분을 이분탐색을 통해 구하면 된다!

import sys
input = sys.stdin.readline

def bs(arr,target):
    left, right = 0, len(arr)-1
    while left<= right:
        mid = (left+right)//2
        if arr[mid]<target:
            left = mid+1
        else:
            right = mid-1
    return left

n = int(input())
arr = list(map(int, input().split()))
INF = int(1e10)

check = [0]*n
inc_arr = [INF]*n

for i, x in enumerate(arr):
    idx = bs(inc_arr,x)
    inc_arr[idx] = x
    check[i] = idx

max_len = max(check)
idx = check.index(max_len)

res = []
while idx>=0:
    if check[idx] == max_len:
        res.append(arr[idx])
        max_len -=1
        # print(res)
    idx -=1

res.reverse()
print(len(res))
print(*res)

가장 긴 증가하는 부분 수열(LIS) 풀이 방법

부분 수열 : 임의의 수열이 주어질 때, 몇 개의 수를 제거하여 만든 수열
부분 수열 중 가장 긴 증가하는 부분 수열을 구하는 방법은 2가지가 있다.

1. DP(Dynamic Programming) - 동적 계획법

2. Binary Search - 이분 탐색

1. 동적 계획법을 사용한 풀이 (백준 11053)

문제 : https://www.acmicpc.net/problem/11053

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

dp = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i]>arr[j]:
            dp[i] = max(dp[i],dp[j]+1)

print(max(dp))

dp: arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

현재 위치(i)의 원소 vs 이전에 있는 원소(j)

- 작다면 증가하는 부분 수열이 될 수 있기 때문에 dp값 설정

- dp값 : 현재 위치의 이전 숫자 중 최대 dp 값 + 1 (현재 값 추가하므로)

이렇게 dp를 통해 문제를 풀면 시간복잡도는 O(N^2)..

2. 이분 탐색을 사용한 풀이 (백준 12015)

해당 문제에서, n의 범위가 늘어났기 때문에 dp로 풀면 당연히 시간초과가 난다..!
따라서 이분탐색으로 풀이해야 한다..

import sys
input = sys.stdin.readline

def bs(arr,target):
    left, right = 0, len(arr)-1
    while left<= right:
        mid = (left+right)//2
        if arr[mid]<target:
            left = mid+1
        else:
            right = mid-1
    return left


n = int(input())
arr = list(map(int, input().split()))
dp = [arr[0]]
for i in range(n):
    if arr[i] > dp[-1]:
        dp.append(arr[i])
    else:
        idx = bs(dp,arr[i])
        dp[idx] = arr[i]

print(len(dp))

dp : 가장 긴 증가하는 부분 수열을 저장하는 배열

현재 위치(i)의 원소 vs 이전 원소들

1. 현재 위치 원소가 더 크면 dp에 추가 (dp[-1]은 이전 원소들의 최댓값)

2. 더 작거나 같으면,, 이분 탐색을 통해 dp에 특정 값이 들어갈 위치를 찾고 arr[i]로 바꿔주기

3. dp의 길이 == 가장 긴 증가하는 부분 수열의 길이

cf) bisect 라이브러리를 사용해도 되지만, 나는 bisect 라이브러리 없이 구현하여 사용하였다.

이때 시간 복잡도는..? O(NlogN)이다

가장 긴 증가하는 부분 수열 자체를 구하는 방법은???

https://bskwak.tistory.com/260

문자열 → 숫자 : parseInt(문자열변수, 10)

var str_n = "12";
var int_n = parseInt(str_n, 10);

숫자 → 문자열  : 숫자변수.toString()

var n = 10
var str_n = n.toString();

문자열 길이 : 문자열변수.length

console.log(str_n.length)

문자열 → 배열 : [...문자열변수]

my_string = '12345;
console.log([...my_string]);

배열 뒤집기 : 배열.reverse()

num_list=[1,2,3];
num_list.reverse();

배열 자르기 : 배열.slice(시작,끝)

const arr = ['a', 'b', 'c', 'd'];

const arr1 = arr.slice(1, 3); 	// [ 'b', 'c' ]
const arr2 = arr.slice(1); 	 // ['b', 'c', 'd']
const arr3 = arr.slice(-3, -1); // ['b', 'c']

올림 : Math.ceil(숫자) / 내림 : Math.floor(숫자) / 반올림 : Math.round(숫자)

var ceil_n = Math.ceil(1.222); // 2
var floor_n = Math.floor(1.222); // 1
var round_n = Math.round(1.222); // 1

소수점 반올림 : 숫자.toFixed(원하는소수점이하자리수) , 숫자.toPrecision(유효자릿수)

var fixed_n1 = 1.5.toFixed(1); // 1.5
var fixed_n2 = 1.77.toFixed(1); // 1.8

var precision_n1 = 1.5.toPrecision(2); // 1.5
var precision_n2 = 1.777.toPrecision(2); // 1.8

• toFixed의 경우, 원본 숫자의 소수점 이하 길이가 'digit'보다 길면 숫자를 반올림, 짧으면 뒤를 0으로 채워서 return
• toPrecision의 경우, 원본 숫자의 자릿수보다 작으면 반올림한 값 리턴

정수 판별 : Number.isInteger(숫자)

console.log(Number.isInteger(12.3)) // false

숫자의 root값 구하기 : Math.sqrt(숫자)

var n = Math.sqrt(4)

숫자의 제곱값 구하기 : Math.pow(숫자, 제곱수)

Math.pow(7, 2);    	// 49
Math.pow(2, 10);   	// 1024
Math.pow(4, 0.5);  	// 2 (square root of 4)

// 제곱수가 음수일 때,
Math.pow(7, -2);   	// 0.02040816326530612 (1/49)
Math.pow(8, -1/3); 	// 0.5

// 숫자가 음수일 때,
Math.pow(-7, 2);   	// 49 
Math.pow(-7, 3);   	// -343

배열 속 원하는 값 찾기 : indexOf, includes

• indexOf : 찾은 값의 첫번째 원소의 위치 반환 (없으면 -1)
• includes : 존재 여부 반환(true/false)

var arr = [1,2,3,4,5,1,2,3]
arr.indexOf(3) // 2
arr.indexOf(6) // -1 (없으므로)

arr.includes(5) // true
arr.includes(6) // false

여러가지 데이터 중 원하는 데이터 뽑기 : filter

var arr = [3,6,10,0,9,'str']

var res = arr.filter((value)=>value<10);

시도 1

deque로 풀 수 있을 것이라 생각했다..

[value, idx ] (value: 현재까지 값, idx : 현재 위치) 를 deque에 추가
하나씩 꺼내어 idx+1 번째의 값을 value에 더하고 m으로 나눈 나머지가 0인지 아닌지 체크

당연하게 시간초과..

시도 2 (정답)

list = [1,4], m으로 나눈 나머지 r 이라고 할 때, 다음과 같이 식을 작성할 수 있다

tmp1 = list[0] * m + r
tmp2 = list[1] * m + r

r의 값이 동일하다면,
tmp2 - tmp 1 = m * (list[1] - list[0])

이말은 즉,, 나머지가 같으면? m으로 나누어 떨어진다는 의미와 같다.
만약, list가 누적합 리스트라면, list[1] - list[0] 은 구간합을 의미한다.

따라서,,
나머지 같은 것 중에서 2개씩 뽑는 경우의 수와 같다 (단,, 나머지가 0일 때는 단독 가능하므로 추가로 더해줘야 함)

문제의 예시로 살펴보면
A = [1,2,3,1,2] 일 때, 누적합은 1, 3, 6, 7, 9 다
누적합의 나머지를 각각 계산하면? 1, 0, 0, 1, 0 이다.
나머지 list는 [3, 2, 0] ( 나머지 0은 3개, 1은 2개, 2는 0개)

nC2 = n*(n-1)//2 ( n 개 중 2개를 뽑는 경우의 수)이므로, 아래 식과 같이 각각에 대해 2개씩 뽑는 경우의 수를 계산하여 더한다.

for i in range(m):
    res+= r_list[i]*(r_list[i]-1)//2

++ 잊지말고 나머지가 0개일 경우, 단독 가능하므로 더해주기

전체 코드

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
alist = list(map(int, input().split()))

r_list = [0]*m
prefix_sum = 0
for a in alist:
    prefix_sum += a
    r_list[prefix_sum%m]+=1

res = r_list[0]
for i in range(m):
    res+= r_list[i]*(r_list[i]-1) // 2
print(res)

문제링크

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

여러 프로젝트를 진행하면서, 내가 왜 Typescript를 쓸까? Typescript를 쓰면서 얻게 되는 이점은 이런거였구나.. 등 많은 생각을 했다

내가 제일 크게 느꼈던 Typescript의 장점은..

일반적으로 말하는 타입스크립트의 장점을 떠나서, 백엔드의 DTO(Data Transfer Objects)를 type으로 정의해두면 정말 편리했다.

1. 백엔드로 부터 받는 데이터 구조를 type으로 정의하면 프론트에서 데이터를 처리할 때 발생할 수 있는 타입 관련 오류를 방지할 수 있었다.

• 예를 들면, price이 string인지 number인지에 따른 오류를 사전 방지할 수 있음..!

2. 백엔드에서 데이터 구조에 변경 사항이 있을때, 쉽게 반영할 수 있어 편리했다.

그리고 자동 완성 이것도 정말.. Typescript를 놓을 수 없는 이유 중에 하나다.
type을 정의해 놓아서 변수나 함수 입력할 때 자동 완성되는 게 좋다. 오타도 줄일 수 있고..

일반적인 내용

Typescript의 특징

1. 컴파일 언어, 정적 타입 언어

• 자바스크립트는 동적 타입의 인터프리터 언어로 런타임에서 오류를 발견할 수 있
• 타입스크립트는 정적 타입의 컴파일 언어이며 타입스크립트 컴파일러 또는 바벨(Babel)을 통해 자바스크립트 코드로 변환됨
• 오류를 코드 작성 단계에서 발견할 수 있으며, 실행 속도가 빠르지만, 타입을 지정해야 하는 번거로움과 컴파일 시간이 필요

2. 자바스크립트 슈퍼셋(Superset)

• 타입스크립트 : 자바스크립트 기본 문법에 타입스크립트의 문법을 추가한 언어
• 자바스크립트에 추가된 문법을 포함하는 언어로, 유효한 자바스크립트 코드는 타입스크립트로 변환 가능

3. 객체 지향 프로그래밍 지원

• ES6(ECMAScript 6)에서 새롭게 사용된 문법을 포함
• 클래스, 인터페이스, 상속, 모듈 등의 객체 지향 프로그래밍 패턴을 제공

Typescript 장점

1. 오류를 잡아내기 쉬움

• 컴파일 과정에서 오류를 발견하기 때문에, 런타임 전에 문제점을 잡아낼 수 있음
• 자바스크립트는 실행 시점에서만 오류를 발견

2. 협업에 도움이 됨

• 코드의 가독성 : 타입 지정은 주석처럼 작동하여, 다른 개발자들이 코드를 쉽게 이해하고 파악할 수 있게 도와줌

3. 자바스크립트 호환

• 자바스크립트와 100% 호환됨
• 프론트엔드 및 백엔드에서 자바스크립트를 사용하는 모든 곳에서 사용 가능

const [profileImg, setProfileImg] = useState<string>("");

  useEffect(() => {
    setMounted(true);
    if (isLogin && userInformation) {
      setProfileImg(userInformation.gender === "MAN" ? "/manIcon.png" : "/womanIcon.png");
    }
  }, [isLogin]);
  
  
  

<Image src={profileImg} alt="man" width={20} height={20} style={{ border: "1px solid black", borderRadius: "50%" }}></Image>

 Image is missing required "src" property:

=> 에러가 뜨는 이유? 위 코드에서 profileImg가 없을수도 있어서!

src={변수} 이면, 변수에 값이 없는 경우도 고려해주어야한다. 

해결

{profileImg && <Image src={profileImg} alt="man" width={20} height={20} style={{ border: "1px solid black", borderRadius: "50%" }}></Image>