eyebrow93

최단경로를 풀 때 가장 먼저 등장하는것이 Dijkstra와 Floyd라고 생각된다.
다익스트라의경우 일반적으로 O(n^2)이지만, Heap구조를 사용하는 순간 O(NlogN)의 시간복잡도로 줄일 수 있으며,
플로이드의 경우 아주간단하게 빼박 O(n^3)이다.

먼저 다익스트라부터 본다면
graph를 만들어 놓고 시작하자.

나는 주로 파이썬의 딕셔너리를 활용해서 graph를 만들고 시작한다.

def mkgraph(ss):
    from collections import defaultdict
    dic=defaultdict(list)
    for fr,to,cost in ss:
        dic[fr].append([to,cost])
        dic[to]
    return dic
costs=[
    [1,2,2],[1,4,1],[1,3,5],[2,3,3],[2,4,2],[3,2,3],[3,6,5],[4,3,3],[4,5,1],[5,3,1],[5,6,2]
]
# dijkstra(mkgraph(costs),1)
mkgraph(costs)

이렇게 하는것이 한눈에 가독성도 좋다고 생각되기에.. 이렇게 한다..
양방향 그래프가 아닌경우 dic[to] 만을 통해서 node가 비어있지 않도록 한다. (순회 시 참조에서 Key가 없는 오류발생을 막기위함)
양방향이라면 dic[to].append([fr,cost]) 를 통해서 양방향으로 만들어준다.

일단 이렇게 그래프만드는것이 끝났으니, 이제 다익스트라를 구현해보자.

from heapq import *
def dijkstra(graph,start):
    INF = int(1e9)
    distances={i : INF for i in graph}
    frt={i:0 for i in graph}
    distances[start]=0
    frt[start]=start
    q = [[0,start]]
    while q:
        dist,now = heappop(q)
        if dist> distances[now]: continue
        for node,n_dist in graph[now]:
            new_dist = dist+n_dist
            if new_dist<distances[node]:
                distances[node] = new_dist
                frt[node] = now
                heappush(q, [new_dist,node])
    return distances, frt

def getRoute(frtable,st,fr):
    tmp=[]
    while st!=fr:
        tmp.append(fr)
        fr=frtable[fr]
    ans=[st,]
    while tmp:
        ans.append(tmp.pop())
    return ans

graph = mkgraph(costs)
dist, frtable = dijkstra(graph,1)
getRoute(frtable,1,5) # 1,4,5 

난 다익스트라를 쓸 때 이후 경로까지 확인할 수 있도록 frt (from table) 을 사용한다.
이를 통해 각각의 노드가 어디에서 온것인지 알 수 있으며, 그것을 역으로 따라올라간다면, start까지 찾아감으로써 경로를 찾을 수 있다.

여담으로 floyd또한 다익스트라보다 쉽게 구현할 수 있는데. , . .
여기서는 graph보다 matrix를 활용하는것이 더욱 좋다..
links의 입력 방식에 따라 매트릭스를 구성하는 것은 쉬우니..

def solution(links,start,mid,end):
    def mkmat(links):
        nodecnt=set()
        for fr,t in links:
            nodecnt.add(fr)
            nodecnt.add(t)
        mat=[[int(1e9)]*len(nodecnt) for _ in range(len(nodecnt))]
        for fr,to in links:
            mat[fr-1][to-1]=1
            mat[to-1][fr-1]=1
        for i in range(len(nodecnt)):
            mat[i][i]=0
        return mat
    def floyd(mat):
        for mid in range(len(mat)):
            for fr in range(len(mat)):
                for to in range(len(mat)):
                    mat[fr][to] = min(mat[fr][to], mat[fr][mid]+mat[mid][to])
        return mat

    mat=mkmat(links)
    mat = floyd(mat)
    print(mat)

    dist= mat[start-1][mid-1] + mat[mid-1][end-1]
    return dist if dist<int(1e9) else -1

링크만 주어진 상황으로 생각하고, 링크에 등장하지 않는 노드는 없다고 가정한다면, mkmat을 통해 링크테이블을 만들고,
플로이드를 통해 각 링크를 순회하며 연산을 진행
fr, mid, to를 사용하여 보기좋게 사용할 수 있다!

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) , 코딩테스트 연습 - 소수 만들기 | 프로그래머스 (programmers.co.kr)

주어진 배열 속에서 숫자 3개를 뽑아서 만들 수 있는 소수의 개수를 찾는 문제. 

크게 2파트로 나뉜다. 

1. 숫자 3개 뽑아 더하기

2. 소수 판별

소수를 판별하는데는, 가장 효율적인 방법인 에라토스테네스의 체를 활용했다. 

숫자 3개를 뽑아 더하는것에 있어서는, 배열 속 중복된 수가 없다는점과, 비복원추출의 방법을 사용해야하므로, 
combinations 를 사용했다.

from itertools import combinations
def solution(nums):
    def mknum(n):
        arr=[i for i in range(n+1)]
        
        for i in range(2,(n//2)+1):
            # print(arr)
            if arr[i]<2: continue
            else:
                cnt=2
                while i*cnt < len(arr):
                    # print(i*cnt)
                    arr[i*cnt]=0
                    cnt+=1
        return [i for i in arr[2:] if i!=0]
    
    arr=mknum(max(nums)*3)
    numlist=list(map(lambda x : sum(x), list(combinations(nums,3))))
    answer=0
    for n in numlist:
        if n in arr:
            answer+=1

    return answer
solution([1,2,7,6,4])

코딩테스트 연습 - 행렬 테두리 회전하기 | 프로그래머스 (programmers.co.kr)

문제는 위 링크에서 확인하면된다.

총 두가지의 연산을 진행해야하는데, 
1. 실제 회전
2. 회전하는동안 스치는 숫자들의 최솟값

최대한 단순하게 풀기위해 시계방향으로 돌린다고 생각하고 풀었다.

#2021 Dev-matching웹백 행렬테두리 회전하기
# rows,columns,queries	result
# rows,columns,queries=6,6,[[2,2,5,4],[3,3,6,6],[5,1,6,3]]#	[8, 10, 25]
rows,columns,queries=3,3,[[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]]#	[1, 1, 5, 3]
# rows,columns,queries=100,97,[[1,1,100,97]]#	[1]
def mprint(mat):
    for m in mat:
        print(m)

def solution(rows,columns,queries):
    mat=[[1+j+(columns*i) for j in range(columns)] for i in range(rows)]
    # mprint(mat);print()
    answer=[]
    for query in queries:
        mat,miner=rot(mat,query)
        answer.append(miner)
        mprint(mat)
        print(miner)
    return answer

def rot(mat,q):
    x1,y1=q[0]-1,q[1]-1
    x2,y2=q[2]-1,q[3]-1
    print(x1,y1,x2,y2)
    tmp=mat[x1][y1]
    rt=0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    x,y=x1,y1
    miner=mat[x1][y1]
    while True:
        nx,ny=x+dx[rt], y+dy[rt]
        if rt==0 and nx==x2 and ny<y2:
            rt=1
        elif rt==1 and nx==x2 and ny==y2:
            rt=2
        elif rt==2 and nx==x1:
            rt=3
        elif rt==3 and ny==y1:
            mat[x][y] = tmp
            break
        miner = min(miner,mat[nx][ny])
        mat[x][y]=mat[nx][ny]
        x=nx
        y=ny
    return mat, miner
solution(rows,columns,queries)

dx,dy를 통해 4방향의 회전을 구했으며, 각각 반시계방향 앞녀석의 것을 가져온다. 
rt를 통해 회전의 방향을 확인하며, 각 회전방향 중 tern이 필요한 순간을 if의 조건을 통해 나눠줬다.

참조 : python-for-coding-test/8.cpp at master · jun1116/python-for-coding-test (github.com) , 이것이 코딩테스트다

이진탐색으로 바꿔서 푸는문제이다. 

원하는 조건에 맞게 탐색을 진행해야한다는 점에서 연습을 반복해놓을 필요가 있다.

n=6
m=[19,15,10,17]
def solution(n,m):
    st=0
    end=max(m)
    ans=0
    while st<=end:
        tmp=0
        mid = (st+end)//2
        for i in m:
            tmp+=max(0,i-mid)
        if tmp<n:
            end=mid-1
        else:
            ans=mid
            st=mid+1
    return ans
solution(n,m)

#include <bits/stdc++.h>
using namespace std;
int n,m, answer;
vector<int> arr;
n=4;m=6;
answer=0;
arr={19,15,10,17};
int st=0;
int end=1e9;
while (st<=end){
    int mid = (st+end)/2;
    long long int total=0;
    
    for (int i=0; i<n; i++){
        if (arr[i]>mid){ 
            total += arr[i]-mid;
        }
    }
    if (total<m){
        end = mid-1;
    }
    else{
        answer=mid;
        st=mid+1;
    }
}
cout<<answer<<endl;