3820. [Professional] 2일차 - 롤러코스터

새로운 정렬방법에 놀래서 나중에 활용하려고 올림.

sort시 key를 비교방식으로 한다. c++이랑 java에는 있던데 파이썬은 삭제됐더만..

https://python.flowdas.com/library/functools.html

https://python.flowdas.com/howto/sorting.html#sortinghowto

https://python.flowdas.com/library/functools.html#functools.cmp_to_key

주의할 점은 functools.cmp_to_key(func)의 리턴을 True나 False가 아닌 양수,0,음수로 받는다는 것. 두 비교 결과를 통해 제일 작은 건 맨 앞에, 큰 건 뒤로 오름차순 정렬은 같다.

import sys
import itertools
import functools
sys.stdin = open("sample_input.txt", "r")

def compare_rail(x,y):
    com1 = y[0]*(x[0]+x[1]) + y[1]
    com2 = x[0]*(y[0]+y[1]) + x[1]
    print(x,y,com1,com2,com1-com2)
    return com1-com2

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N = int(input())
    rail = [0] * (N)
    for i in range(N):
        a,b = map(int, input().split())
        rail[i] = (a,b)

    # rail.sort(key=lambda x:x[1]-x[0])
    cmp = functools.cmp_to_key(compare_rail)
    print(rail)
    rail.sort(key=cmp)
    print(rail)
    v = 1
    # vc = list(itertools.permutations(rail,r=5))
    # print(vc)
    for a,b in rail:
        v = ((a*v) + b) % 1000000007
        print(v)
    # v=1
    # for r in vc:
    #     v = 1
    #     print(r)
    #     for a, b in r:
    #         v = (a * v) + b
    #         print(v)
    # print(v % 1000000007)

    print("#{}".format(test_case),v % 1000000007)
    # ///////////////////////////////////////////////////////////////////////////////////

3814. [Professional] 평등주의

이번에도 parametric search 방법을 써서 풀어낸다. 이런곳에서도 쓰일수 있다는 느낌을 가지고 싶어서 작성.

솔직히 상식적으로 (2 ≤ N ≤ 100000, 1 ≤ K ≤ 109) 의 범위를 가지고 있는데, 정석대로 한다면 범위 K가 10억이라 도저히 안될 것 같았다. 그러니까 for i in range(k) 같은 것은 못쓴다. 100000까지는 무리없이 되기 때문에 N 크기만큼 for문을 써야 한다고 생각했다.

그럼 N만큼만 해서 어떻게 정답을 알아낼 수 있는가? 어떻하긴 계속 순회시키면서 정답을 때려 맞추는 수밖에..

여기서 주의할 테크닉은 양쪽과 비교한 크기이기 때문에 →쪽으로 순회와 ← 쪽으로 순회를 하는데 한번에 for문으로 넣었더니 의도대로 안되서 맘 편하게 for문을 2개 썻다. 어떻게 이게 문제인지 알아냈냐면 리스트 내의 원소 순서가 반전이 되도 결과는 똑같아야 되는데 결과가 다르게 나와서 눈치챘다.

이런식으로 주어진 테스트케이스로는 되는데 제출하면 안되는 경우가 너무 많다. 그래서 왜 틀렸나 점검하고 싶어도 스스로 만들어가며 점검해야 한다. 쉐도우복싱하는 느낌이다.. 

import sys

sys.stdin = open("sample_input.txt", "r")

def isAvailable(a,c,k):
    count = 0
    for i in range(len(a)-1):
        if a[i+1] - a[i] > c:
            count += a[i+1] - (a[i] + c)
            a[i+1] = a[i] + c
        # print(a,i,c,count,k)
        if count > k:
            return False
    for i in range(len(a)-1,0,-1):
        if a[i-1] - a[i] > c:
            count += a[i-1] - (a[i] + c)
            a[i-1] = a[i] + c
        # print(a, i, c, count, k)
        if count > k:
            return False
    return True

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    s = 0
    e = max(A)-min(A)
    while s < e:
        c = (s+e) // 2
        if isAvailable(A[:],c,K):
            e = c
        else:
            s = c + 1

    print("#{}".format(test_case),s)
    # ///////////////////////////////////////////////////////////////////////////////////

3813. [Professional] 1일차 - 그래도 수명이 절반이 되어서는

원래 정직하게 찾으면 N^3 정도는 나올 것 같은데 거꾸로 정답을 가정하고 찾아가는 방법을 써서 NlogN으로 줄었다고 한다.

다른 사이트들을 보고 참고했다. 특히 코드는 그대로 따라함.

# https://ggodong.tistory.com/90
# https://herong.tistory.com/entry/SWEA-3813-%EA%B7%B8%EB%9E%98%EB%8F%84-%EC%88%98%EB%AA%85%EC%9D%B4-%EC%A0%88%EB%B0%98%EC%9D%B4-%EB%90%98%EC%96%B4%EC%84%9C%EB%8A%94

일단 주어진 배열에서 "이 값이면 정답일까?" 하고 배열에서 최소값과 최대값의 중간값을 가정하고 풀어나간다. (위 스크린샷에선 확인해볼라고 임시로 0~20으로 지정함.)

만약 임시로 잡은 중간값이 정답이라면 이거보다 더 작은값도 정답일 확률이 있으므로 end값을 반으로 줄이고 실험. 

중간값이 정답이 아니라면 중간값보다는 더 커야 하므로 start를 중간값+1로 지정하고 계산. 

이런식으로 거꾸로 역추적하는 방식을 쓰는데 이게 parametric search 인 것 같다.

코드의 count 어쩌구는 문제 조건을 참조.

솔직히 꼼수 같다. 그래도 정답만 찾으면 그만이니..

import sys

sys.stdin = open("sample_input.txt", "r")

# https://ggodong.tistory.com/90
# https://herong.tistory.com/entry/SWEA-3813-%EA%B7%B8%EB%9E%98%EB%8F%84-%EC%88%98%EB%AA%85%EC%9D%B4-%EC%A0%88%EB%B0%98%EC%9D%B4-%EB%90%98%EC%96%B4%EC%84%9C%EB%8A%94

def isAvailable(p):
    now = 1
    cont = 0
    for i in range(1,lenS+1):
        # print("i,now,cont,p,S[i]",i,now,cont,p,S[i])
        if S[i] <= p:
            cont += 1
        else:
            cont = 0
        if cont == K[now]:
            cont = 0
            now += 1
            if now > lenK:
                break
    return now > lenK

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    lenS,lenK = map(int, input().split())
    S = list(map(int, input().split()))
    K = list(map(int, input().split()))
    S.insert(0,0)
    K.insert(0, 0)
    print(S,K)

    s = min(S)
    e = max(S)
    while s<e:
        m = (s+e) // 2
        print("s,m,e",s,m,e)
        if (isAvailable(m)):
            e = m
        else:
            s = m + 1
    print(s)

    print("#{}".format(test_case),s)
    # ///////////////////////////////////////////////////////////////////////////////////

5286. [파이썬 SW 문제해결 최적화] 5일차 - 그래프 색칠하기 (트리 탐색 정리)

트리 탐색을 하는 김에 재귀 깊이 우선 탐색, 스택을 이용한 깊이 우선 탐색과 너비 우선 탐색 코드를 다 해보고 정리해봤다.

import sys
from collections import deque

sys.stdin = open("sample_input.txt", "r")

def color_tree(n):
    global result

    Q = deque()
    Q.append((1,[0] * (N + 1)))
    while Q:
        n, c = Q.pop()
        if n == N+1:
            # print("possible")
            result = 1
            return

        cn = [0] * (N+1)
        for t in range(1, N+1):
            if WM[n][t] == 0: continue
            else: cn[t] = c[t]
        for m in range(1,M+1):
            if m in cn: continue
            c[n] = m
            # print(n, m, c[:])
            Q.append((n+1,c[:]))

    # if n == N+1:
    #     print("possible")
    #     result = 1
    #     return
    #
    # cn = [0] * (N+1)
    # for t in range(1, N+1):
    #     if WM[n][t] == 0: continue
    #     else: cn[t] = C[t]
    #
    # for m in range(1,M+1):
    #     if m in cn: continue
    #     C[n] = m
    #     print(n, m, C)
    #     color_tree(n+1)
    #     C[n] = 0
    # return

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, E, M = map(int, input().split())
    WM = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(E):
        f, s = map(int, input().split())
        WM[f][s], WM[s][f] = 1, 1

    C = [0] * (N + 1)
    result = 0
    color_tree(1)

    print("#{}".format(test_case),result)
    # ///////////////////////////////////////////////////////////////////////////////////

재귀를 이용한 깊이 우선 탐색의 경우 잘 작동했다. 단지 이 문제의 경우에는 가능한 경우의 수를 한가지만 찾으면 되기 때문에 이미 가능한 걸 알았는데도 더 찾는건 낭비인 것 같았다. 그래서 큐에 쌓는 방식을 생각하기로 했다. 또 개인적으로 재귀를 싫어하기도 한다.

Q를 만들고 쌓게 한 뒤 뒤에서부터 pop하면 깊이 우선 탐색이 되지만 사실 재귀랑 방식이 다르게 작동한다. 한번 따져 보자.

만약 이진 트리라면 깊이 h의 경우 h+1인 왼쪽 자식과 오른쪽 자식으로 들어간다. 재귀의 경우 왼쪽이 가능한 경우 바로 호다닥 자식으로 들어가 진행하는 반면 Q 스택 방식은 일단 왼쪽 자식, 오른쪽 자식을 둘 다 스택에 넣고 왼쪽자식으로 들어간다. 이런식으로 조금 다른 것 같다.

재귀는 함수가 쌓여있어서 return을 해도 계속 쌓여있던 함수가 실행되는 반면 이 스택방식은 while문을 이용하기 때문에 return 하자마자 묻지도 따지지도 않고 바로 함수를 끝내는 모습이다.

만약 경우의 수를 더 찾더라도 계속 찾고 싶으면 return 대신 continue 등을 통해 Q가 빌 때 까지 반복하면 그만이다.

Q를 popleft로 바꾸면 너비 우선 탐색이 된다.

또 스택을 이용할 때 주로 tuple을 이용해서 정보를 넘긴다. 근데 튜플 안에서 리스트를 넘겨서 저장하면 후에 그 리스트가 변경될 시 안의 내용도 같이 변경된다는 것을 알았다. 만약

A = [1,2,3]

Q.append((A))

로 저장하면 처음 Q 안에는

Q : [([1,2,3])]

로 되어있지만 만약

A[2] = 5

Q.append((A))

를 실행하면

Q: [([1,2,3]),([1,2,5])]

가 아니라

Q: [([1,2,5]),([1,2,5])]

로 되어 기존에 저장되었던 A의 리스트도 바뀐다. 이는 리스트 값을 저장할 때 파이썬도 주소값으로 저장해서 그런 것 같다. 그래서 위 코드를 잘 보면 append 할 시 그냥

Q.append((n+1,c))

가 아니라

Q.append((n+1,c[:]))

로 리스트 뒤에 [:]를 붙여 통채로 복사해서 넣으라는 표시를 추가했다.

5260. [파이썬 SW 문제해결 최적화] 3일차 - 부분 집합의 합

이미 부분집합에 포함된 원소의 합들 S와 포함안된 원소의 합들 R을 이용하여 한계치를 만들어 쓸떼없는 계산을 줄이는 것이다.

위 그림에서 왼쪽으로 가면 포함, 오른쪽으로 가면 미포함이다.

S가 기준점 K를 넘을 경우, 그 트리부분은 진행하지 않는다. 뭘 더하든 K 이상이기 때문이다.

또 R가 기준점 K보다 작을 경우, 그 트리 부분은 진행하지 않는다. R은 전체원소의 합에서 후보원소에서 제외한 만큼 빼는 것으로, R을 넘는 S의 합이 나올 수가 없다.

앞으로 남아있는 모든 원소를 더해도 K는 되지 못할 것이므로..

import sys

sys.stdin = open("sample_input.txt", "r")

def allPartSum(i,K,S,R):
    global result
    if i == 0:
        if S == K:
            result += 1
        return
    if S > K: return
    if R < K: return
    allPartSum(i - 1, K, S + jiphap[i], R)
    allPartSum(i - 1, K, S,R - jiphap[i])


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, K = map(int, input().split())
    jiphap = list(range(N+1))
    S = 0
    allsum = sum(jiphap)
    result = 0
    allPartSum(N,K,0,allsum)
    print("#{}".format(test_case),result)
    # ///////////////////////////////////////////////////////////////////////////////////

5255. [파이썬 SW 문제해결 최적화] 2일차 - 타일 붙이기

내가 이런 문제만 보면 머리가 나쁘다는 걸 느낀다. 이해하기가 힘들다.

일단 감각적으로 풀었는데 막상 답이 되자 당황했었다.

우선 쉽게 풀어보기 위해 재귀방법을 이용해 풀었었다. 그 뒤 동적계획법으로 리스트에 저장해서 [0]에서 [n]까지 올라가면서 구하는 방식으로 해결했다.

내가 당황했던 부분은 inputbox(n-3) + 2*inputbox(n-2) + inputbox(n-1) 수식에서 왜 (n-2)에 *3이 아닌 *2를 해야 하느냐 였다.

그림을 그리고 나서야 이해할 수 있었다. 2칸을 차지하는 부분 b(n-2)에서 ll, --, ㅁ 이렇게 각각 3개가 있는데 왜 *3이 아니고 *2인가?

이것은 1칸을 차지하는 부분 b(n-1) 에서 차지할 때 l 로 차지하는데 이것이 2칸을 차지하는 부분 b(n-2)의 ll과 중복되기 때문.

그래서 --과 ㅁ만 남아 *2를 한다.

import sys

sys.stdin = open("sample_input.txt", "r")

def inputbox(n):
    if n <= 3:
        return BoxResultList[n]

    for i in range(4,n+1):
        if BoxResultList[i] != -1: continue
        BoxResultList[i] = BoxResultList[i-1] + 2*BoxResultList[i-2] + BoxResultList[i-3]
    return BoxResultList[n]

    if n <= 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 3
    elif n == 3:
        return 6
    else:
        return inputbox(n-3) + 2*inputbox(n-2) + inputbox(n-1)


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N = int(input())
    BoxResultList = [-1] * (N+1)
    BoxResultList[0] = 0
    BoxResultList[1] = 1
    BoxResultList[2] = 3
    BoxResultList[3] = 6
    result = inputbox(N)
    # print(result)
    # print(BoxResultList)

    print("#{}".format(test_case),result)

    # ///////////////////////////////////////////////////////////////////////////////////

업로드

https://github.com/sglee487/SW-Expert-Academy

5254. [파이썬 SW 문제해결 최적화] 1일차 - 부분 문자열

시발 뭐 이딴게 다있냐

이 문제와는 별개로 몇 군데를 찾아보니 접미어배열 자체가 유용한 듯 하다.

강의와 외부 코드를 참고해서 작성했다.

일단 set을 이용해서 꼼수 비슷하게 정답 하나 만들어놓고, 접미어 배열와 LCP배열 만들어 놓은거를 이용해서 푼 것과 비교해서 작성했다.

for i 문을 통해 A[i][1] 의 string을 보는데 A[i][1] 의 string도 앞에서부터 끊어 읽으면 set에서의 부분문자열을 읽는 것과 비슷해진다.

단지 이렇게 끊어 읽기만 하면 i의 뒤를 읽을 때 중복해서 읽는 문제가 생긴다.

가령 abac를 보면 처음엔 A[0][1]을 봐서 'abac'를 'a', 'ab', 'aba', 'abac'로 다 읽었다 치자.

그 뒤엔 A[1][1]을 보고 'ac'를 'a', 'ac'로 읽지만 이미 'a'는 중복이므로 이를 빼고 읽어야 한다.

하지만 이미 LCP를 통해 앞의 문자와 얼마나 중복되는 가를 이미 파악했다. 그래서 중복되는 만큼 더 건너뛰어서 시작하기 위해 LCP의 값을 이용한다.

import sys

# http://cd4761.blogspot.com/2017/02/trie-1.html
# http://cd4761.blogspot.com/2017/03/trie-2.html
# https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/
# http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=221028710658
# https://swexpertacademy.com/main/talk/solvingTalk/boardCommuView.do?searchCondition=COMMU_DETAIL-COMMU_TITLE-NICK_NAME_TAG&commuId=AXAuybMapTADFAXq&searchKeyword=5254&orderBy=DATE_DESC&pageSize=10&pageIndex=1&&&&&&


def LongestCommonPrefix(a,b):
    i=0
    while i < min(len(a),len(b)):
        if a[i] != b[i]: break
        i += 1
    return i

sys.stdin = open("sample_input2.txt", "r")

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    # 그냥 배열로 하니까 안됨.
    # 진짜 접미어 트리 배열 써야 하는 듯..

    inp = input().split()
    n = int(inp[0])
    s = inp[1]

    print(s)
    print("n :",n)
    # 그냥 배열로 하니까 안됨.
    # 진짜 접미어 트리 배열 써야 하는 듯..
    sps = set()
    for i in range(len(s)):
        for j in range(len(s),i,-1):
            sps.add(s[i:j])
    sp = sorted(list(sps))
    print(sp)

    A = [[0] * 2 for _ in range(len(s))]
    for i in range(len(s)):
        A[i][0] = i
        A[i][1] = s[i:]
    # print(A)
    A = sorted(A,key=lambda a:a[1])
    print(A)
    LCP = [0] * len(A)
    LCP[0] = 0
    for i in range(1,len(A)):
        LCP[i] = LongestCommonPrefix(A[i-1][1],A[i][1])
    print(LCP)

    resultc = ''
    resultl = 0
    for i in range(len(A)):
        suffix_index = A[i][0]
        curstr = A[i][1]
        if n > len(curstr):
            n += LCP[i] - len(curstr)
        else:
            resultc = curstr[0]
            resultl = len(curstr[:(n+LCP[i])])
            break

    print("#{}".format(test_case),resultc,resultl)

    # ///////////////////////////////////////////////////////////////////////////////////

5250. [파이썬 SW 문제해결 구현] 7일차 - 최소 비용

다익스트라 알고리즘에 익숙해지기 위해 씀.

최소 거리부터 집합 S에 합치는 방식이다.

import sys

sys.stdin = open("sample_input.txt", "r")

def printmatrix(matrix):
    for i in matrix:
        print(i)
# https://hongsj36.github.io/2020/02/02/Ad_GraphMST/
def Dijkstra_custom(tera):
    # 원래 visited 리스트 만들어서 append 했었는데 역시 실행시간에 문제가 발생.
    # 나도 고정배열 써야지
    visited = [[False]*N for _ in range(N)]
    # d = [[1000] * N for _ in range(N)]
    d = [[float('inf')] * N for _ in range(N)]
    # Q = []
    Q = set()
    d[0][0] = 0
    # Q.append((0,0))
    Q.add((0,0))
    while True:
        # 최소 거리부터 집합 S에 합치는 다익스트라 알고리즘임.
        y,x = 0,0
        # minfuel = 1000000
        minfuel = float('inf')
        for r, c in Q:
            if d[r][c] < minfuel and not visited[r][c]:
                minfuel = d[r][c]
                y,x = r,c

        visited[y][x] = True
        Q.remove((y,x))
        if y == N-1 and x == N-1:
            return d[N-1][N-1]
        for i in range(4):
            new_y, new_x = y + dy[i], x + dx[i]
            if 0<=new_y tera[y][x]:
                    fuel = d[y][x] + tera[new_y][new_x] - tera[y][x] + 1
                else:
                    fuel = d[y][x] + 1
                if fuel < d[new_y][new_x]:
                    d[new_y][new_x] = fuel
                    Q.add((new_y,new_x))



T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N = int(input())

    tera = [list(map(int, input().split())) for _ in range(N)]

    #왼,아래,오,위
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]

    result = Dijkstra_custom(tera)

    print("#{}".format(test_case),result)

    # ///////////////////////////////////////////////////////////////////////////////////