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

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>