Coding 공부

def get_divide_list(num):
    result = []
    for i in range(1,int(num**0.5)+1):
        if not num%i:
            result.extend([i,num//i])

    result = list(set(result))
    result.remove(1)
    return result

N = int(input())

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

X = int(input())


X_list = get_divide_list(X)

answer = 0
cnt = 0
for num in arr:
    for x_num in X_list:
        if not num%x_num:
            break
    else:
        answer += num
        cnt += 1

print(answer/cnt)

이 문제 또한, 소수를 구하면 된다. 약수를 구할때, 구하고자하는 수의 sqrt만

탐색을 해주면 좀 더 빠르게 할 수 있다는 점을 생각하고 풀면 편한다.

만약 1을 제외한 약수들을 구한뒤, 약수로 나뉘면, 멈추는 방식으로 해서, 평균을 구했다.

사실 python 유저라면 gcd 라이브러리를 쓰는게 편하다!

아니면 gcd를 구현해도 된다.

import sys
input = sys.stdin.readline
def get_prim_number(input_Num):
    last_num = input_Num
    visited = [False for _ in range(last_num+1)]
    visited[0] = True
    visited[1] = True

    result = []
    for num in range(2,last_num+1):
        if not visited[num]:
            result.append(num)
            for new_num in range(2*num,last_num+1,num):
                visited[new_num] = True
    return result
N = int(input())

arr = list(map(int,input().split()))
result = []
max_num = max(arr)
prim_set = get_prim_number(max_num)
for val in arr:
    if val in prim_set:
        result.append(val)

if len(result)>0:
    answer = 1
    result = set(result)
    for prim in result:
        answer*=prim
    print(answer)
else:
    print(-1)

이 문제는 소수를 구하고, 소수가 있으면, SET에 추가를 해주고,

전부 판별을 한 뒤에, 

아무것도 없으면 -1 을,

그리고 최소공배수를 출력해주면 된다.

이 문제에서 많이 틀렸던 이유는

중복되는 소수가 온다는걸 깜빡했었다.

즉 2 2 3 5 7 이라하면, 전체를 그냥 곱하기만 하면, 420이 된다.

그러나 실제 최소공배수는 210이므로,

이러한 점을 주의하기만 하면 되는 문제였다.

import sys

input = sys.stdin.readline

N,M = map(int,input().split())

arr = list(map(int,input().split()))
cnt = [0]*(N+1)
for _ in range(M):
    command,x,y = map(int,input().split())
    x -= 1
    if command == 1:
        arr[x] = y
    elif command == 2:
        y -= 1
        for ind in range(x,y+1):
            arr[ind] = (arr[ind]+1)%2
    elif command == 3:
        y-=1
        for ind in range(x,y+1):
            arr[ind] = 0
    else:
        y -= 1
        for ind in range(x,y+1):
            arr[ind] = 1
print(*arr)

이 문제는 문제에 주어진 조건대로 배열의 상태를 바꿔주면 되는 문제였다. 

전체 배열의 크기가 4000이고, 최대 명령이 4000이라,

최악의 경우라 해도 1600만번밖에 안되므로, 문제에 주어진 조건대로 돌리면 되는 문제이다.

import sys
from collections import deque
input = sys.stdin.readline

def calc(i,input_list,flag):
    if i == 1:
        input_list.rotate(2)
    elif i == 2:
        input_list.reverse()
        input_list.rotate(2)
    elif i == 3:
        a,b = input_list.popleft(),input_list.popleft()
        input_list.insert(1,a)
        input_list.insert(3,b)
    elif i == 4:
        a = input_list.popleft()
        input_list.rotate(1)
        b = input_list.pop()
        input_list.rotate(1)
        input_list.append(a)
        input_list.append(b)
    elif flag and i ==6:
        a = input_list.popleft()
        input_list.rotate(1)
        b = input_list.pop()
        input_list.rotate(1)
        input_list.append(a)
        input_list.append(b)
    elif flag and i == 5:
        a,b = input_list.popleft(),input_list.popleft()
        input_list.insert(1,a)
        input_list.insert(3,b)
        



N,M,R = map(int,input().split())
half_N = N//2
half_M = M//2
arr = [list(map(int,input().split())) for _ in range(N)]

arr_divide = {}
for i in range(4):
    temp = []
    quo = i//2
    mod = i%2
    start_x = quo*(N//2)
    end_x = (quo+1)*(N//2)
    start_y = mod*(M//2)
    end_y = (mod+1)*(M//2)
    for x in range(start_x,end_x):
        tmp = []
        for y in range(start_y,end_y):
            tmp.append(arr[x][y])
        temp.append(tmp)
    arr_divide[i+1] = temp
command_cnt = [0 for _ in range(7)]

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

small_list = deque([1,2,3,4])


mini_rotate = deque([0,1,2,3])

for i in command_list:
    calc(i,small_list,True)
    calc(i,mini_rotate,False)
position = [[0,0],[0,M//2-1],[N//2-1,0],[N//2-1,M//2-1]]
one,two,three = mini_rotate.popleft(),mini_rotate.popleft(),mini_rotate.popleft()
for i in range(4):
    origin = position[one]
    left_origin = position[two]
    bottom_origin = position[three]
    if origin[0] == left_origin[0] and origin[1] == bottom_origin[1] :
        if origin[1] > left_origin[1]:
            dy = -1
        else:
            dy = 1
        if origin[0] > bottom_origin[0]:
            dx = -1
        else:
            dx = 1
        temp = []
        for x in range(abs(bottom_origin[0]-origin[0])+1):
            tmp = []
            for y in range(abs(origin[1] - left_origin[1])+1):
                tmp.append(arr_divide[i+1][origin[0]+x*dx][origin[1]+y*dy])
            temp.append(tmp)
        arr_divide[i+1] = temp
    else:
        if origin[0] > left_origin[0]:
            dy = -1
        else:
            dy = 1
        
        if origin[1] > bottom_origin[1]:
            dx = -1
        else:
            dx = 1
        temp = []

        for x in range(abs(bottom_origin[1]-origin[1])+1):
            tmp = []
            for y in range(abs(left_origin[0]-origin[0])+1):
                tmp.append(arr_divide[i+1][origin[0]+dy*y][origin[1]+dx*x])

            temp.append(tmp)
        arr_divide[i+1] = temp

last_N= len(arr_divide[1])*2
last_M = len(arr_divide[1][0])*2

result = [[0 for _ in range(last_M)] for _ in range(last_N)]
for i in range(4):
    idx = small_list.popleft()
    quo = i//2
    mod = i%2
    start_x = quo*(last_N//2)
    start_y = mod*(last_M//2)
    my_array = arr_divide[idx]
    for x in range(last_N//2):
        for y in range(last_M//2):
            result[start_x+x][start_y+y] = my_array[x][y]


for x in range(last_N):
    for y in range(last_M):
        print(result[x][y],end=' ')
    print()

    

배열 돌리기 시리즈의 5번째이다.

이 배열돌리기는 전체를 돌리면 무조건 시간초과가 날수밖에 없다.

왜냐하면 최대 100*100의 행렬이 오는데 그걸 200만번 수행을 하면 터질수 밖에 없다.

그렇다 면 이 문제를 해결하는 방법은 다음과 같다.

이 문제에서 행렬을 크게 4부위로 나눌수 있다.

처음 배열을 다음과 같이 4등분을 해주자(문제에서는 1 2/ 3 4 가 아니라, 1 2 / 4 3 형태이지만, 그냥 편하대로 하면 된다.)

그러면 1번 돌리기는 다음과 같이 표현할 수 있다.

위 아래의 배열이 바뀌고, 그리고 그안의 있는 값도 상하반전이 된 것을 알 수 있다.

2번 돌리기는

좌우 반전이 되고, 그리기 도구에서 안의 숫자를 좌우반전을 하는게 없어서 표현 못했지만, 그 안에 있는 작은 배열들도 좌우 반전이 되어야한다.

3번 돌리기는

오른쪽으로 90도 돌면서 그 안의 있는 값들도 90도로 돌리면 된다.

4번 돌리기는 왼쪽으로 90도로 돌리고, 그 안의 배열들도 같이 왼쪽으로 90도를 돌리면 된다.

5번 돌리기는 3번돌리기와 똑같이 전체 배열의 이동은 같지만, 안의 배열이 돌아가지 않는 모습이다.

그리고 6번 돌리기는 4번돌리기와 전체배열의 이동은 같지만 안의 배열이 돌아가지 않는 모습이다.

이렇게 4등분을 해보면 우리는 알 수 있는 사실이 있다.

전체 배열을 전부 돌릴필요가 없다는 것이다.

1~6번 돌리기를 간략하게 표현할 수 있는 2*2 배열을 돌리기만 하면 된 다는 것을 알 수 있다.

그러면 그 안에 있는 배열들이 돌아가는 것은 어떻게 표현하느냐이다.

 위와 같이 한 배열이 있다고 하면, 우리는 네 꼭지점의 위치를 알면 전체 배열이 어떻게 모양이 변한지 알 수 있다.

이러한 특성을 이용해서 

mini_rotate에는 각 꼭지점의 위치를 표현한 (0,1,2,3)을 상황에 맞게 돌려주면서, 작은 배열에서 1~4번 돌리기에 해당될때 어떻게 회전되는지를 표현해주었다.

그리고 small_list는 전체 배열을 4등분을 해서, 각 등분된 배열을 1,2,3,4로 매칭시키고, 1~6번 돌리기에 맞게 회전을 시켜 주었다.

mini_rotate를 돌릴때 주의 해야할 것은 나는 행을 x  열을 y로 표현하는 편이다. 돌리다 보면

행과 열이 뒤바뀌어서 행이 dy 열로 이동하는 것이 dx로 뒤바뀔때가 있을 것이다.

그러면 이걸 어떻게 구분할 것이냐,

위의 변수명을 잘못 선언했지만 다음과 같다.

원본 배열에서 (0,0) 이 부분을 origin이라 하겠다.

그리고 (0,M//2) 이부분을 right_origin(코드에서는 left_origin) 이라 부르겠다.

그리고 (N//2,0) 이 부분을 bottom_origin이라 부르겠다.

그러면 우리가 전부 회전을 하고 난뒤에 바뀐 위치에 있는 origin, right_origin, bottom_origin이 있을것이다.

그러면 행과 열이 뒤바뀌었는지 아는 방법은 다음과 같다.

origin의 x좌표와 right_origin의 x좌표가 같고, orign과 bottom_origin의 y좌표가 동일하다면,

우리는 평소에 알던 x,y의 형태로 가면 될것이다.

이 dx,dy가 +인지 -인지는 대소로 구분하면 된다.

이렇지 않을 경우엔 행과 열이 바뀐 90도나 270도로 회전한 모습일것이므로, dy와 dx를 변경해서 구해주면 된다.

이렇게 배열들을 전부 회전 시킨다음

mini_rotate의 순서에 맞게, 전체 배열에 넣어주면 문제를 해결 할 수 있다.

이 문제는 원본배열을 4등분을 해서 축약해서 돌릴수 있느냐, 그리고 그 안의 작은 배열도 네꼭지점으로 나누어서 돌릴 수 있느냐를 물어본 문제 같다.

또한 이렇게 회전을 했을때, dx,dy와 배열을 복사할때의 위치를 어떻게 찾을지 구현을 하는데 어려운점이 많았다.

이 문제에서 시간이 가장 오래 걸렸던 것은, dx,dy의 방향이 바뀔때를 찾는 것이었다.

그리고 위의 6가지 유형에 맞게, deque를 rotate,pop,insert,popleft를 해야할지 고민했던게 오래걸렸다.

단순해 보이지만, 여러가지 고민을 하게 만들어주었던 문제였다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)
def root_dfs(node):
    if visited[node]:
        return
    visited[node] = True
    child_list = []
    for next_node in tree[node]:
        if not visited[next_node]:
            child_list.append(next_node)

    if len(child_list)==2:
        return [node,0]
    elif len(child_list) == 1:
        return_value = root_dfs(child_list[0])
        return_value[1] += tree[node][child_list[0]]
        return return_value
    else:
        return [node,0]

def leef_dfs(node):
    if visited[node]:
        return
    visited[node] = True
    child_list = []
    for next_node in tree[node]:
        if not visited[next_node]:
            child_list.append(next_node)
    
    if len(child_list)==0:
        return 0
    else:
        result = 0
        for child_node in child_list:
            result = max(result,leef_dfs(child_node)+tree[node][child_node])
        return result
N,R = map(int,input().split())
tree = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,b = map(int,input().split())
    tree[x][y] = b
    tree[y][x] = b


visited = [False for _ in range(N+1)]

root_node_info = root_dfs(R)
visited[root_node_info[0]] = False
leef_dis = leef_dfs(root_node_info[0])
print(root_node_info[1],leef_dis)

2개의 DFS로 나눠서 최초엔 풀었다.

첫번째 풀이는 두개로 나뉘어서 DFS를 했다.

첫 DFS는 기가노드를 찾는것이다. 기가노드를 찾으면 그때의 길이를 저장해놓는다.

그리고 기가노드에서 부터 리프노드까지 최대 길이를 찾아내는 방식으로 해서 구했다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(300000)
def root_dfs(node,dis):
    if visited[node]:
        return
    visited[node] = True
    count = 0
    nexts = -1
    distance = 0
    for next_node in tree[node]:
        if not visited[next_node]:
            count += 1
            nexts = next_node
            distance += tree[node][next_node]
    if count == 1:
        return root_dfs(nexts,dis+distance)
    else:
        return [node,dis]

def leaf_dfs(node,dis):
    global leef_dis
    visited[node] = True
    count = 0
    for next_node in tree[node]:
        if not visited[next_node]:
            leaf_dfs(next_node,dis+tree[node][next_node])
            count += 1
    if not count:
        leef_dis = max(leef_dis,dis)


N,R = map(int,input().split())
tree = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,b = map(int,input().split())
    tree[x][y] = b
    tree[y][x] = b


visited = [False for _ in range(N+1)]
root_dis = root_dfs(R,0)
leef_dis = 0
leaf_dfs(root_dis[0],0)
print(root_dis[1],leef_dis)

두번째 풀이는 좀더 깔끔한 풀이이다.

count를 별도로 세주어서 기가노드인지 리프노드인지 구분을 해주었다.

기가노드가 아닐때에는 재귀를 해주면서 distance를 더해주고, 만약 기가노드일때는 재귀를 머추고, 기가노드의 위치와

지금까지 누적된 거리를 반환해준다.

leaf_dfs도 비슷한 과정을 겪는다.

leaf_dfs를 계속 재귀를 통해 가면서 leaf_node에 도착하면 현재까지 누적된 값과 최대값과 비교를 해서 더 큰 값을 넣어주면 된다.

N = int(input())

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

arr.sort()
min_value = 0
if len(arr)%2:
    min_value = arr.pop()
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
else:
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
print(min_value)

정렬을 해주고, 가장 첫번째값과 가장끈값을 더한값의 최소값을 출력해주면 된다.

import sys

input = sys.stdin.readline
def dfs(node,flag,*args):
    stack = [(node,0)]
    distance_list = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    visited[node] = True
    if not flag:
        visited[args[0]] = True
    while stack:
        node,distance = stack.pop()
        distance_list[node] = distance

        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append((next_node,distance+graph[node][next_node]))
    
    temp = []

    for i in range(1,N+1):
        temp.append((distance_list[i],i))
    temp.sort(key=lambda x :-x[0])
    if flag:
        return_value = temp[0][1]
    else:
        return_value = temp[0][0]
    return return_value


N = int(input())
graph = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay

first_point = dfs(1,True)
second_point = dfs(first_point,True)

first_value = dfs(first_point,False,second_point)
second_value = dfs(second_point,False,first_point)

print(max(first_value,second_value))

 이 문제는 트리의 지름을 구하는 방법을 응요한 문제이다.

총 4번의 dfs를 통해 두번째 트리의 지름을 알 수 있다.

첫번째 dfs를 통해 아무지점에서 가장 먼 지점을 구한다.

이 지점은 지름을 구성하는 한 점이 될것이다.

두번째 dfs를 통해 첫번째 dfs에서 구한 점에서 가장 먼 점을 구한다.

그러면 이 점은 트리의 지름을 구성하는 가장 먼 점이 될것이다.

이렇게 2번의 dfs를 통해 우리는 가장 먼 점 2개를 구했다.

그러면 이 2점을 각각 dfs를 돌려, 가장 먼 점에서 2번째인 것을 찾아낸다.

그리고 이렇게 두 거리를 구한 뒤 그 중에 더 큰 점을 선택하면 되는 문제이다.

import sys

input = sys.stdin.readline
def dfs(node):
    distance_list = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    visited[node] = True
    stack = [(node,0)]
    while stack:
        node,distance = stack.pop()
        distance_list[node] = distance
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append((next_node,graph[node][next_node]+distance))
    return distance_list

N = int(input())
graph = [{} for _ in range(N+1)]

for _ in range(N-1):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay


distance1 = dfs(1)
far_point1 = distance1.index(max(distance1))
distance2 = dfs(far_point1)
far_point2 = distance2.index(max(distance2))
distance3 = dfs(far_point2)
result = sorted(distance2+distance3)[-3]
print(result)

단 3번의 dfs를 통해 구하는 방법도 있다.

이 방법은 지름을 구성하는 2점의 전체길이를 한 리스트로 정하고 뒤에서 3번째를 출력해주는 것이다.

왜냐하면 한 리스트당 한 지점에서 가장 먼 지점은 서로 자신들이기 때문에, 그 2점을 제외하고 그 다음번으로 큰 것이

두번째 트리의 지름의 답이된다.

from collections import deque
def bfs(red,blue):
    stack = deque()

    stack.append((*red,*blue,0,''))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    direction = ['U','D','L','R']
    while stack:
        rx,ry,bx,by,dis,route = stack.popleft()

        if dis >= 10:
            return (-1,'-')

        for i in range(4):
            nrx,nry = rx,ry
            r_p = 0
            while 0<=nrx<N and 0<=nry<M and arr[nrx][nry] != '#' and arr[nrx][nry] != 'O':
                nrx += dx[i]
                nry += dy[i]
                r_p += 1
            nbx,nby = bx,by
            b_p = 0
            while 0<=nbx<N and 0<=nby<M and arr[nbx][nby] != '#' and arr[nbx][nby] != 'O':
                nbx += dx[i]
                nby += dy[i]
                b_p += 1

            if (nbx,nby) == (nrx,nry):
                if arr[nbx][nby] == 'O':
                    continue
                if r_p > b_p:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            elif arr[nbx][nby] == 'O':
                continue
            elif arr[nrx][nry] == 'O':
                return (dis+1,route + direction[i])
            nrx -= dx[i]
            nry -= dy[i]
            nbx -= dx[i]
            nby -= dy[i]
            if not visited[nrx][nry][nbx][nby]:continue
            visited[nrx][nry][nbx][nby] = False
            stack.append((nrx,nry,nbx,nby,dis+1,route+direction[i]))
    return (-1,'-')

N,M = map(int,input().split())


arr = []
blue = []
red = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'B':
            blue = (x,y)
        elif temp[y] == 'R':
            red = (x,y)
    arr.append(temp)


visited = [[[[True for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]


result = bfs(red,blue)
if result[0] != -1:
    print(result[0])
    print(result[1])
else:
    print(result[0])

 이 문제는 사실상 구슬탈출 2와 동일한 문제이다.

구슬 탈출2와 달라진점은 이동방향을 저장시키는 것외에는 없다.

문제를 푸는 방식은 다음과 같다.

먼저 방문배열을 4차원 배열로 만들어준다.

그 이유는, 빨간색공이 안 움직이지만, 파란공만 움직이는 경우도 있고,

파란공만 움직이고, 빨간공이 움직이지 않을때가 있으므로, 구분을 하기위해 4차원 배열을 선언을 해주었다.

그리고 BFS를 하는 과정은 다음과 같다. 한 방향으로 정하고 각가 red ball과 blue ball을

구멍 혹은 벽을 만나기전까지 계속 굴려준다.

그러면 최종적으로 위치하곳은 벽 혹은 구멍일 것이다. 이 과정에서 각각의 움직이는 횟수도 세어주었다.

먼저 구멍에 빠졌는지 확인을 해주자.

파란공과 빨간공이 전부 빠졌다면, 이것은 패배한것이므로, 제외를 해주자.

그리고 파란공만 들어간거면 그것 또한 패배한 것이므로, 제외를 하자.

그리고 빨간공만 들어갔을때에는 그때는 이긴것이므로, 지금까지 누적된 이동경로를 반환을 해주면 된다.

그리고 두 공의 위치가 최종적으로 같다면, 둘중 먼저 해당지점에 먼저와있는지가 중요하다.

우리는 위에서 반복횟수를 세어주었다.

반복 횟수가 적다는것은 더 빨리 도착한 것이므로, 반복횟수가 많은 볼을 한칸 뒤로 빼준다.

이러한 작업을 다 마치고 나면 위에서 우리는 벽이나 구멍외에는 멈추지 않았다.

그러면 현재 볼들이 있는 위치는 벽일테니, 뒤로 한칸씩 동일하게 이동해준다.

이렇게 한뒤에, 우리가 방문하지 않은 곳이면 방문표시를하고 stack에 넣어주면 된다.

이 문제는 방문을 어떻게 할것인가, 그리고 공을 굴릴때 어떻게 한번에 끝까지 굴릴것인가. 그리고 같은 위치에

중첩됬을때 어떻게 해결하는지 중요한 문제였다.