척척석사의 코딩기록

import math
from collections import defaultdict
#에라토스테네스 체 응용
num = [i for i in range (0,100001)]
num[0] = 1
prime = []
for i in range (2,int(math.sqrt(100001))+ 1):
    if num[i] == i:
        for j in range (i,100001,i):
            if num[j] == j:
                num[j] = i

N = int(input())
for i in range (0,N):
    x = int(input()) #소인수분해 되는 숫자
    d = defaultdict(int)
    while num[x] != 1:
        d[num[x]] += 1
        x //= num[x]
    d_key = list(d.keys())
    for j in range (0,len((d_key))):
        print(d_key[j], d[d_key[j]])

에라토스테네스 체의 응용으로 간단하게 풀 수 있습니다.

def f(n):
    length = len(n)
    if len(n) == 1:
        if n == "9":
            return 11
        else:
            return int(n) + 1
    k = length // 2
    if length % 2 == 0:
        num = int(n[:k] + n[::-1][k:])
        if num > int(n):
            return int(num)
        else:
            number = str(int(n[:k]) + 1)
            if len(number) > k:
                num = number[:-1] + number[::-1]
            else:
                num = number + number[::-1]
            return int(num)
    else:
        num = int(n[:k+1] + n[::-1][k+1:])
        if num > int(n):
            return int(num)
        else:
            number = str(int(n[:k+1]) + 1)
            if len(number) > k + 1:
                number = str(int(number) // 10)
                num = number + number[::-1]
                return int(num)
            else:
                num = number[:-1]+ number[::-1]
                return int(num)
N = input()
print(f(N))

어렵지는 않았던 것 같다 !

문제 조건이 상당히 유했어서, 이런 방식의 접근으로서도 괜찮았던 것 같다.

수열 갯수가 1000개로 제한이 되어있었기 때문에, O(n^2) 정도의 시간복잡도로도 풀렸다.

실제로 이 경우에는 총 연산횟수가 n(n-1)/2회가 되겠다.

N = int(input())
A = list(map(int,input().split()))
dp = [0 for _ in range (0,N)]
dp[0] = A[0]
answer = 0
for i in range (1,N):
    dp[i] = A[i]
    for j in range (0,i):
        if A[j] < A[i]:
            dp[i] = max(dp[j] + A[i], dp[i])
print(max(dp))

요즘은 논문이랑 학회 준비에 상당히 바쁜데, 얼른 잘 끝났으면 좋겠다.

취직도 그렇고 (._.

from collections import deque
import sys
input =  sys.stdin.readline
N = int(input())
graph = [[] for _ in range (0,N+1)]
for i in range (0,N-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = []
visited = [False for _ in range (0,N)]
for i in range (0,len(graph[1])):  
    deq = deque()
    deq.appendleft(graph[1][i])
    visited[0] = True
    visited[graph[1][i]-1] = True
    cnt = 1
    while deq:
        x =  deq.popleft()
        visited[x-1] = True
        cnt += 1
        for y in graph[x]:
            if visited[y-1] == False:
                deq.appendleft(y)
                visited[y-1] = True
    ans.append(cnt) 
if len(graph[1]) == 1:
    print(1)
else:
    n = len(graph[1])-1
    ans.sort()
    answer = 0
    for i in range (0,n):
        answer += ans[i]
    print(answer - n + 1)

D치고는 굉장히 간단했던 문제로서, 

현재 가장 많은 득표수를 취하고 있는 사람들이 누구인지 묻는 문제입니다.

N,M = map(int,input().split())
A = list(map(int,input().split()))
vote = [0 for _ in range (0,N+1)]
vote[A[0]] += 1
print(A[0])
t = A[0]
for i in range (1,M):
    vote[A[i]] += 1
    if vote[A[i]] > vote[t]:
        print(A[i])
        t = A[i]
    elif vote[A[i]] == vote[t]:
        t = min(A[i],t)
        print(t)
    else:
        print(t)

소스 코드도 어렵지 않았습니다. 

아이디어는, 새롭게 투표되는 후보의 표가 "이전에 가장 많았던 후보의 표" 보다 많은지? 적은지를 묻는 상황입니다.

혹시 두명의 표가 같아지게 된다면, 더 숫자가 낮은 사람이 당선된다 하는 점에 주의 해주면 되겠습니다.

먼저 N명이 입후보 하였으므로 길이 N+1의 리스트를 생성해줍니다. (첫번째 element는 생각하지 않는 것으로 합니다)

첫번째로 투표되는 인원을 출력해주고, 인원의 투표수를 1 높여줍니다.

그 뒤, 반복문을 통해 "이전 최대 득표"인 후보와 현재 새롭게 투표된 사람을 비교해줍니다.

이전 최대 득표가 새롭게 득표된 사람의 표보다 많다면, 기존의 값을 그대로 출력해주면 될 것이고

혹시 같다면 더 번호가 낮은 사람을 취하기 위해 min을 사용해주고, 출력해줍니다

남은 경우는 새롭게 득표한 사람이 최다득표가 되는 경우였기 때문에, 이때는 최다 득표 인원을 그 인원으로 바꿔줄 필요가 있겠습니다.

D치고는 간단한 문제였습니다.

주어진 문자열에서 ABC가 나온다면 그것을 지워나가는 문제가 되겠습니다.

import sys
input = sys.stdin.readline
S = input().rstrip()
n = len(S)
result = []
if n >= 3:
    for s in S:
        result.append(s)
        if result[-3:] == ["A","B","C"]:
            result.pop(-1)
            result.pop(-1)
            result.pop(-1)
    u = "".join(t for t in result)
    print(u)
else:
    for s in S:
        result.append(s)
    u = "".join(t for t in result)
    print(u)

정말 안 떠올라서 마지막에 겨우겨우 붙잡고 풀었네요 ....

문제는, 주어진 문자열의 부분문자열에 대해서 같은 알파벳이 연달아 두번 나오는 횟수는 몇번인가? 라는 문제입니다.

누적합에 대한 내용이 되겠습니다.

import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
S = input().rstrip()
result = [0]
cnt = 0
for i in range (1,len(S)):
    if S[i] == S[i-1]:
        cnt += 1
        result.append(cnt)
    else:
        result.append(cnt)
for i in range (0,Q):
    l,r = map(int,input().split())
    print(result[r-1] - result[l-1])

생각보다 되게 단순한거였는데 너무 복잡하게 생각해버려서 아쉬웠네요.

from collections import deque
def solution(people, limit):
    people.sort()
    deq = deque()
    for i in range (0,len(people)):
        deq.append(people[i])
    cnt = 0
    while len(deq) > 1:
        a = deq.popleft()
        b = deq.pop()
        if a + b <= limit:
            cnt += 1
        else:
            deq.appendleft(a)
            cnt += 1
    if len(deq) == 1:
        cnt += 1
    return cnt

덱을 사용하여 풀면 되겠다. 

알고리즘은 그리디 알고리즘.

덧붙여 한번 시간초과 뜨면서 한 방법이 있는데, 재귀 2번 돌리는걸로 했더니 효율성에서 개박살났더라 ...

결론적으로 아이디어는, 덱을 크기순으로 정렬해서 생성해준 뒤에,

덱의 길이가 1이상이 될때까지 반복 (1개가 남았을 경우에, while문 내에서 2개를 뽑아내지 못하기 때문)

만약 왼쪽에서 뽑은 값 (최소) 와 오른쪽에서 뽑은 값 (최대)가 limit 이하라면, 이 두개를 뽑아내면 되겠다.

여기서 중요했던 것이, 왜 이렇게 뽑는가? 였는데, 아래와 같다.

아마 많은 사람들을 태울 수 있다고 했다면 다른 방법으로 풀어야하지 않았나 싶기도하다.

혹은 while 안에 while을 하나 더 넣어야할 것 같다. 

from collections import deque
A = list(map(int,input().split()))
deq = deque()
for i in range (0,len(A)):
    deq.append(A[i])
N = len(deq)
limit = int(input())
num = 0
cnt = 0
while True:
    if deq == deque():
        break
    weight = deq.pop()
    num += 1
    while weight <= limit:
        if deq == deque():
            break
        a = deq.popleft()
        if a + weight > limit:
            deq.appendleft(a)
            break
        else:
            weight += a
            num += 1
        if num == N:
            break
    cnt += 1
print(cnt)

이런 느낌? 

Test case는 50 50 70 80 80, limit : 180으로 했는데 2로 맞게 나왔다 (80,50,50), (80,70)

토요일에 코딩테스트가 있는데 힘내서 보고 와야겠다.