이재문

문제: 

[BOJ 30897] 0으로 만들기 

알고리즘 : 애드혹, 누적합

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

풀이

예제 입력은 도움이 되지 않으니 입력 조건에 맞는 작은 입력을 만들어 봅시다

10

1 4 2 2 4 1 3 1 4 2

예제 입력이 이렇다고 가정하면 사실 본질은 여기서 +-를 통해 0이 되는 연속 되는 수열이 있냐는 문제로 바꿀 수 있는데

저 예제의 경우 

1*4*(2-2)*4*... 이렇게 하면 0을 곱하니까 무조건 0이 되기 때문이죠

하지만 일일이 전부 더하거나 빼면서 0이 되는게 있나 확인하면 O(N**2 ∗ 2**N) 걸릴거 같네요

여기서 A의 범위가 10000인데 N이 30000개인게 도움을 주는데

누적합으로 계속해서 더해나가면서 누적합이 적용된 앞리스트 인자가 +면 뒤에 인자에 -로 연산해주시면 누적합 배열이

1 -3 -1 1 -3 -2 1 ... 이런식으로 나오는데

이 범위가 [-10000, 10000]이 되게 됩니다

저 범위안에 모든 값들이 한번씩만 나온다고 하면 2만 1개이고

여기서 N의 갯수가 무조건 3만개 이상이므로 무조건 겹쳐서 나오는 값이 존재하는데

누적합 알고리즘 공식이 수열 A의 누적합 배열 S의 i+1부터 j까지의 누적합은 Sj-Si이고

Si == Sj가 되면 i+1부터 j까지의 합은 0입니다.

따라서 같은 값을 가지는 index 하나는 무조건 있으니 그것을 두개 찾아서 괄호 안에 본래의 연산을 해주고 나머지는 *로 묶으면 됩니다.

코드

import sys

input=sys.stdin.readline

n = int(input())

l = list(map(int, input().split()))
flag = True
s = l[0]
d = {l[0]:0}
for i in range(1, n):
    if s > 0:
        s -= l[i]
        try:
            x1 = d[s]
            x2 = i
            break
        except:
            d[s] = i
    elif s < 0:
        s += l[i]
        try:
            x1 = d[s]
            x2 = i
            break
        except:
            d[s] = i
    elif s == 0:
        flag = False
        x1 = i
        break
    
print('YES')
if flag:
    if s > 0:
        s *= -1
    for i in range(x1):
        print(f'{l[i]}*', end='')

    print(f'{l[x1]}*(',end='')
    for i in range(x1+1, x2+1):
        if s > 0:
            s -= l[i]
            print(f'-{l[i]}', end='')
        else:
            s += l[i]
            if i == x1+1:
                print(l[i], end ='')
            else:
                print(f'+{l[i]}', end='')
    if x2+1 == n:
        print(')')
    else:
        print(')*', end='')

        for i in range(x2+1,n-1):
            print(f'{l[i]}*', end='')
        print(l[n-1])
else:
    s = l[0]
    print(f'({l[0]}', end='')
    for i in range(1, x1):
        if s > 0:
            s -= l[i]
            print(f'-{l[i]}', end='')
        else:
            s += l[i]
            if i == x1+1:
                print(l[i], end ='')
            else:
                print(f'+{l[i]}', end='')
    print(')' ,end = '')
    for i in range(x1, n):
        print(f'*{l[i]}', end='')

코드 엄청 못 짰는데 암튼 이런식으로 하면 될듯하네요

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

난이도: P4

유형 : DP, 수학, 에라토스테네스의 체(내가 푼 방식) / 수학

일반적으로 보여주는 점화식으로 DP를 이용해 풀면 되는데

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())

arr = [True for i in range(N+1)]

primes = []
def prime(N):
    for i in range(2, N+1):
        if arr[i] == True:
            primes.append(i)
            for j in range(i + i, N+1, i):
                arr[j] = False

prime(N)
dp = [1 for i in range(N+1)]

for i in range(len(primes)):
    for j in range(i, len(primes)):
        if primes[i]+primes[j]+1 > N:
            break
        if arr[primes[i]+primes[j]+1] == True:
            dp[primes[i]+primes[j]+1] = max(dp[primes[i]+primes[j]+1], dp[primes[i]]+dp[primes[j]]+1)
   

print(dp[-1])

이런식으로 풀면 시간 초과가 날 것이다.

300만까지의 소수의 갯수가 잘은 모르지만 10^5 정도 됐던거 같은데 저 방정식은 O(K^2) K = 소수의 갯수 정도 될것이니

시간이 너무 많이 걸린다..

해결 방법

• 사실 모든 primes의 값을 탐색 할 필요가 없는게 간단한 정수의 법칙을 보면 저런식으로 나눠지는 숫자의 max값은 대부분 서로의 차이가 적은 값들이다 
• 예를 들면 4를 최대한 많이 탐색하려면 1,3 이런것보다 2,2로 나누는 것이 많이 나듯..
• 그래서 인접한 몇개만 뽑았다.. 
• 인덱스는 자율적으로 i~i+100까지 더했는데 N의 범위가 더 커지면 더 늘려야 될 수 도 있고 모든 3000000이하에서 전부 돌아갈지는 좀 의문이긴 해서 좋은 코드는 아니라고 본다..

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())

arr = [True for i in range(N+1)]

primes = []
def prime(N):
    for i in range(2, N+1):
        if arr[i] == True:
            primes.append(i)
            for j in range(i + i, N+1, i):
                arr[j] = False

prime(N)
dp = [1 for i in range(N+1)]

for i in range(len(primes)):
    for j in range(i,len(primes)):
        if primes[i]+primes[j]+1 > N:
            break
        if arr[primes[i]+primes[j]+1] == True:
            dp[primes[i]+primes[j]+1] = max(dp[primes[i]+primes[j]+1], dp[primes[i]]+dp[primes[j]]+1)
            break
   

print(dp[-1])

이 방법 말고

답을 보면 100B이내의 아주 간단한 방법이 있던데..

증명도 아직 나는 모르겠고,, 사실 그보다.. 그 수식을 찾아낸 사람이야 그런데 이글 보고 푸는데 그런거 보면,, 실력에 도움이 안될거 같아서,,,,,,,,,, 올리지는 않는다..

유형 : 그리디?, 수학

난이도 : P4 

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

• 문제를 이해하고 있다는 가정하에 대충 1~20까지의 수를 적어서 보면

• 여기서 몇개의 점을 찍어보자
  • N = 4일때 2x + 2의 값이 배제되므로 역으로 돌려 4개면 (4-2) // 2인 수 즉 1의 해당 식의 값이 배제 되므로 1보다 작은 수들은 전부 배제가 된다 가정하면 되는데 그래서 N(4) - ((N-2) // 2)(1)를 해주면 답이 3이 나온다
  • N = 8도 마찬가지이다  N(8) - ((N-2) // 2)(3) = 5
  • 다만 알아 차렸겟지만 N = 10이면 4가 이미 배제가 되어서 10은 포함이 된다는건데 그것을 보상하기 위해 4부터 다시 반복하면서 해당식을 더해준다
  • N = 10에서 또한 모두를 보상해서 더해줫기에 N = 22에서는 또한 다시 배제가 되어야 하게 된다
• 말을 좀 어렵게 써봤는데 오히려 코드로 보면 간단하다
• 코드 예시

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())

ans = N

flag = False
while N >= 3:
    N -= 2
    N //= 2
    if flag == False:
        ans -= N
    else: ans += N
    flag = not flag

print(ans)

• 어려울때는 그냥 직접 돌아가는걸 체크해보는게 나은듯하다

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

유형 : 투포인터 (이분탐색도 가능하다는데 아직 잘..)

난이도 : G3 (G4가 더 맞다 생각이 든다)

전형적인 투포인터 문제입니다

투포인터 알고리즘을 모르시면 두 용액 문제 및 알고리즘을 보고 오시면 될거 같네요

두 용액 문제에서 하나가 더 늘었으므로 하나를 빼줘서 계산하시면 됩니다.

네 용액이면...좀 골때리겠네..

import sys

input = sys.stdin.readline

n = int(input())

nums = list(map(int, input().split()))

nums.sort()
min_mix = 20e9+1

if nums[0] > 0:
    ans = nums[0:3]
elif nums[-1] < 0:
    ans = nums[-3:]
else:
    for i in range(len(nums)-2):
        liqud = nums.pop(0)
        n -= 1
        start, end = 0, n-1
        
        while start < end:
            temp = liqud + nums[start] + nums[end]
            
            if abs(temp) < min_mix:
                ans = [liqud, nums[start], nums[end]]
            min_mix = min(abs(temp), min_mix)
            if temp > 0:
                end -= 1
            elif temp == 0:
                break
            else:
                start += 1

print(*ans)

제건 파이썬으로 안돌아갑니다 시간 초과라 ㅠㅠ..

pypy3로 돌렸고..

아마 더 좋은 코드는 널렸을거에요

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

유형 : Greedy

난이도 : P5

제일 첫번째로 알아야 하는건 가장 큰 수를 만드려면 자릿수가 최대가 되어야 합니다

두번째는 가장 큰 수가 앞에 오면 되는거죠

인접한 수가 있으면 안되니까 가장 많은 수가 카운트들이 남은 블럭보다 홀수일때 //2 짝수일때 /2 -1 개만큼만 있어도 됩니다

예를들어 1이 4개고 2가 3개 3이 1개면

처음에는 8개에 최대는 4개니까 가장 큰수를 넣어줍시다

3

그다음은 7개에 최대는 4개니까 가장 많은수를 넣어줘야 해요

31

그 다음은 6개의 최대는 3개니까 가장 큰수를 넣어주면 되고요

312

이런식으로 반복하면

3121212

이게 가장 큰 수입니다

마지막으로 이렇게 넣다보면 

4 1 2 0 0 0 0 0 0 0

202010

이것이 사실

0202010 이렇게 들어가게 되어서

반드시 인트값으로 변환을 시켜 맨 앞 0을 삭제 시켜주면 된다고 봅니다

import sys

input = sys.stdin.readline

nums = [*map(int, input().split())]
nums.reverse()

ans = []

cur_n = -1

while sum(nums) > 0:
    max_cnt = max(nums)
    sum_cnt = sum(nums)
    if sum_cnt // 2 < max_cnt:
        temp = 9 - nums.index(max_cnt)
        if cur_n != temp:
            ans.append(temp)
            nums[nums.index(max_cnt)] -= 1
            cur_n = temp
        else:
            if max_cnt == sum_cnt:
                break
            else:
                for j in range(len(nums)):
                    if nums[j] != 0:
                        if cur_n != 9 - j:
                            ans.append(9 - j)
                            nums[j] -= 1
                            cur_n = 9 - j
                            break
                
    else:
        for j in range(len(nums)):
            if nums[j] != 0:
                if cur_n != 9 - j:
                    ans.append(9 - j)
                    nums[j] -= 1
                    cur_n = 9 - j
                    break
str_ans = ''

for i in ans:
    str_ans += str(i)

print(int(str_ans))

더러울 순 있는데 

데이트 하러 가는 날이라 ㅠㅠ 대충 맞는 코드 올립니다.

참고하시고 모두 코테 화이팅입니다

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

유형 - DFS

난이도 - G5

import sys

input = sys.stdin.readline

dot, case = map(int, input().split())

def dfs(start, end, cost):
    if start == end:
        print(cost)
    visited[start] = True
    for next_node, next_cost in graph[start]:
        if visited[next_node] != True:
            dfs(next_node, end, cost + next_cost)
    

graph = [[] for _ in range(dot + 1)]

for i in range(dot - 1):
    dot1, dot2, cost = map(int, input().split())
    graph[dot1].append([dot2, cost])
    graph[dot2].append([dot1, cost])

for j in range(case):
    start, end = map(int, input().split())
    visited = [False for _ in range(dot + 1)]
    dfs(start, end, 0)

DFS의 가장 기본적인 유형으로 

기초를 다지기에 가장 적합한 문제라고 생각된다

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

유형 : DFS/ BFS

난이도: G3

import sys

input = sys.stdin.readline

n, m, x = map(int, input().split())

low = [[] for _ in range(n+1)]
high = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

for i in range(m):
    h, l = map(int, input().split())
    low[h].append(l)
    high[l].append(h)

def dfs(lst, cur):
    cnt = 1
    visited[cur] = 1
    
    for n_node in lst[cur]:
        if visited[n_node] == 0:
            cnt += dfs(lst, n_node)
    return cnt

top, bot = 1, n

top += dfs(high, x) - 1
bot -= dfs(low, x) - 1

print(top, bot)

자기보다 높은 등수 낮은 등수 구해서 높은 놈은 최대에서 더해주고 낮은 등수는 최소에서 빼주면 된다

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

나의 풀이

이런식으로 접근을 해보았다.

num, num2 = map(int, input().split())

result = []

for j in range(num2,101):
    if j % 2 == 0:
        if num % j == j/2 and num/j + 0.5 - (j//2) >= 0:
            for k in range (0, j):
                result.append(int(num/j + 0.5 - (j//2) + k))
            break
    else:
        if num % j == 0 and num/j-(j//2) >= 0:
            for k in range (0, j):
                result.append(int(num/j-(j//2) + k))
            break
if len(result) == 0:
    result.append(-1)
        
print(*result)

메모리 시간은 각각 이렇게 나왔는데 더 단축 시킨 다른 풀이를 보기로 했다

다른 풀이

대게 이런식으로 미리 나누는 수열의 합들을 뺀다음에 나눠서 0이 되면 나누는 수의 갯수가 홀수 짝수 나눌 필요가 없게 되는것을 배웠다
https://www.acmicpc.net/source/12598433

다른 분의 코드라 직접 올리지는 않고 링크로 남겨 두겠다.
저분은 메모리와 시간이 이런식으로 찍히는데 표본이 적어 큰 차이인지는 잘 모르겠네

문제 링크 : https://www.acmicpc.net/problem/5430

 
문제 보고 1분이면 만드는 느낌은 감이 왔다
계속적으로 뒤집으면 무조건 타임에러 날꺼니까 앞뒤로 빼고 나중에 뒤집으면 끝나겠지..
사실 그게 맞고 오픈북으로 힌트 보고 푼 이유는
아직 초보라 그런지.. 입력값 받는 법도 까다롭게 느껴지고 
코테와 별계로 emtpy list 일때 처리가 미흡했던거 같다..
 
소스코드

from collections import deque

n = int(input())
for i in range(n):
    func_ac = input()
    k = int(input())
    list_file = input()[1:-1].split(',')
    
    queue = deque(list_file)
    
    if k == 0:
        queue = []
    
    reverse = False
    
    for j in func_ac:
        if j == "R":
            reverse = not reverse
        elif j == "D":
            if len(queue) == 0:
                print("error")
                break
            else :
                if reverse == False :
                    queue.popleft()
                else :
                    queue.pop()
    else:
        if reverse == True:
            queue.reverse()
        print("[" + ",".join(queue) + "]")

.소요시간 = 20분 + 오픈북 10분 가량
 

• 2개 이하로 다른 비트

 
문제는 이러함
입출력을 보면 알겠지만.. 연속해서 111이 나올때만 문제라는거
000는 1만 더하면 되고 001도 1만 더하면 되지만 이 이상부터는 111이 연속으로 나오면 문제가 생기는건데
패턴을 잘 보면 알겠지만 최소값은 101111 이런식이면 오른쪽에서부터 0이되기전 가장 마지막 1값만 한칸 쉬프트 해줘서 110111 이런식으로 나오는게 제일 최소로 만들 수 있는건데
저렇게 하는게 알고리즘 연습을 잘 안해서 잘 모르겠다;;
그래서 그냥 생각 나는대로 2로 몇번 나눴는지 세서 2의 n-1 제곱 해서 더해줬다...
 

너무 늦게 코테 준비를 시작한거 같다..
정말 메모리 관리 시간관리 로직 짜기 뭐 하나 되는게 아직은 없는거 같다..
가장 댓글 많은 글 보니까 내가 처음 생각한 대로 3줄 이내로 써놨더라 멋있다,,
 
소요시간 : 20~30min..