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

nums = [-2,1,-3,4,-1,2,1,-5,4]

이 배열에서 가장 큰 합을 가진 부분 배열은 [4,-1,2,1], 최대합은 6이다

어떻게 구해야 할까?

# Brute Force

카데인 알고리즘이 생각나지 않는다면 Brute Force 접근법으로 풀어야한다!

Brute-Force란, 모든 경우의 수를 다 구해본 후에 max값을 찾는것

풀이를 간략하게라도 적어보자면,,

1. nums의 index 0부터 시작해서 nums[0]과 함께할수있는(?) 모든 부분합을 구한다.

2. nums[0]의 가능한 모든 부분합 중 가장 큰 값을 변수/리스트/..에 저장

3. 나머지 index 1부터 n-1까지 '1','2' 반복

4. 그러면 리스트던지, 변수던지, 각 인덱스에 해당하는 큰 값들이 모아짐

5. 그 중에서 가장 큰 값을 출력하면 됨

이 방식은 풀이만 봐도 정말 비효율적이다..

배열의 크기가 작으면 물론 금방 풀리겠지만, 커지면 커질수록 '1-2'번 반복횟수가 많아지므로, 시간 복잡도는 O(n^2)가 된다

따라서 나는 "카데인 알고리즘"으로 접근했다

#카데인 알고리즘

예시로 들어 설명하면

nums=[-2,-1,5,-3]

일단 가볍게 아래와 같은 아이디어?로 시작한다

1. (자기자신 vs 자기자신+이전값) 들 중 큰값들만 선정

따라서 -2일땐 -2, -1일땐 -1, 5일땐 5, -3일땐 2

2. 1번 중 가장 큰 값 -> 5

이때, 조금만 더 생각해보면

어짜피 같은 값을 더해주니까 굳이 모든 값을 비교해볼 필요가 없다..

따라서,

1.  max(자기자신 vs 자기자신+이전값 중 가장 큰 값)

따라서 -2일땐 -2, -1일땐 -1, 5일땐 5, -3일땐 2

2. 1번 중 가장 큰 값 -> 5

"이전 값"을 사용하는 것이 가장 큰 핵심 포인트다!

여기서 나는 1번에 배열을 생성하여 저장하지 않고,

max(자기자신 vs 자기자신+이전값 중 가장 큰 값) = localMax 값과 이전 max값을 비교하여 globalMax 변수에 큰 값을 저장해서 풀었다..

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        localMax = nums[0]
        globalMax = nums[0]
        for i in range(1,len(nums)):
            localMax = max(nums[i],localMax+nums[i])
            globalMax = max(localMax,globalMax)
        return globalMax

배열 순회를 한번만 하므로, 카데인 알고리즘의 시간복잡도는 O(n)이다.

1. JAVA 풀이

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int[] answer = new int[nums.length];
        int len = nums.length;
        
        if (nums.length %2 != 0)
            len = nums.length+1;
        
        for(int i=0;i< len/2; i++){
            answer[i*2] = nums[len/2-i-1];
        }
        
        for(int i=0; i< nums.length/2; i++){
            answer[i*2+1] = nums[nums.length-i-1];
        }

        for(int i=0;i<nums.length; i++){
            nums[i] = answer[i];
        }
    }
}

Java는 새로운 배열을 만들어 풀면 어렵지 않게 풀 수 있었다

nums를 정렬한 다음 짝수, 홀수 index에 역순으로 대입해주면 된다!

2. python 풀이

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
  
        nums.sort()
        half = len(nums)//2 if len(nums)%2==0 else len(nums)//2+1
        nums[::2],nums[1::2] = nums[:half][::-1],nums[half:][::-1]

pop()을 사용하면서 풀고 싶었지만,, 아무리 생각해도 비효율적인 것 같아서 이것저것 시도해보다가,, 결국 다른사람 풀이와 동일한 풀이가.. 독창적인 풀이를 하고 싶었지만.. 실패

# nums = [3,2,6,4,5,1,0] 라 가정할때

1. 오름차순 정렬

# nums = [0,1,2,3,4,5,6]

2. half는 "nums길이의 반 값"인데, 홀수일 경우는 1을 더하도록 설정한다.

** "/"가 아닌 "//"를 써야함 -> "/"의 경우 홀수 일 경우, 소수점이 생기므로 다음 코드를 실행할 때 문제 발생

# len(nums)의 값은 7이므로 half의 값은 4가 된다

3. 짝수자리에 0~(half-1) index까지의 값을 역순으로 차례로 대입(변경), 홀수 자리에 half~끝 index까지의 값을 역순으로 차례로 대입(변경)

** 따로 코드를 분리해서 작성하면, 짝수 먼저 실행, 홀수 이후 실행으로 되므로 원하는 결과값이 나오지 않는다! 

    따라서 "동시 실행"이 가능하도록 코드 작성

참고로, 짝수의 경우를 예로 들면,,

nums[::2]= nums[:half][::-1]

참고로 [::2]는 2칸씩 띄어 읽는다는 의미!  따라서, nums[::2] 는 [0,2,4,6] 

nums[:half] 는 처음부터 (half-1)index까지의 값을 뜻하고

[::-1]은 그 값을 역순 처리한다는 뜻이다

그림으로 해당 풀이를 보면,,

1. 루시와 엘라 찾기

동물 보호소에 들어온 동물 중 이름이 Lucy, Ella, Pickle, Rogan, Sabrina, Mitty인 동물의 아이디와 이름, 성별 및 중성화 여부를 조회하는 SQL 문을 작성해주세요.이때 결과는 아이디 순으로 조회해주세요.

SELECT ANIMAL_ID, NAME, SEX_UPON_INTAKE
FROM ANIMAL_INS
WHERE NAME IN ('Lucy','Ella','Pickle','Rogan','Sabrina','Mitty')
ORDER BY ANIMAL_ID

2. 이름에 el이 들어가는 동물 찾기

보호소에 돌아가신 할머니가 기르던 개를 찾는 사람이 찾아왔습니다. 이 사람이 말하길 할머니가 기르던 개는 이름에 'el'이 들어간다고 합니다. 동물 보호소에 들어온 동물 이름 중, 이름에 "EL"이 들어가는 개의 아이디와 이름을 조회하는 SQL문을 작성해주세요. 이때 결과는 이름 순으로 조회해주세요. 단, 이름의 대소문자는 구분하지 않습니다.

SELECT ANIMAL_ID, NAME
FROM ANIMAL_INS
WHERE ANIMAL_TYPE = "Dog" AND NAME LIKE "%EL%"
ORDER BY NAME

"EL"이 들어가는 개의 아이디와 이름 조회

따라서, 조건문은 1. 개 2. 이름에 "EL"이 들어가야 함

1. ANIMAL_TYPE = "Dog"

2. NAME LIKE "%EL%"

* 특정 문자가 포함되어 있음 -> LIKE 와 '%' 사용

(1) LIKE "%EL" : EL로 끝나는 단어

(2) LIKE "EL%" : EL로 시작하는 단어

(3) LIKE "%EL%" : "EL"을 포함하는 단어