무니화니

오늘의 문제는 well-known 알고리즘 중 하나인 TSP (Traveling Salesman Problem)을 이용한 문제인 외판원 순회 문제이다. 친구가 이 문제를 풀다가 어렵다고 해서 풀어봤었는데, 정말 이해하는데 오래 걸렸다. 사실 이 문제의 중요한 부분은 바로 비트마스킹인데, 아직까지 비트 연산을 이용해서 알고리즘을 풀어본 적이 많지 않아서 더욱 낯설었다. 우선, TSP라는 문제 자체가 아직도 최선의 해결책이 발견되지 않은 연구 중인 알고리즘이지만, 이 근간은 dynamic programming에 있다. 나도 이를 이용하여 해결했다. import sys input=sys.stdin.readline n=int(input()) w=[list(map(int,input().split())) for _..

오늘의 문제는 ACM Craft이다. from collections import deque import sys input=sys.stdin.readline t=int(input()) for _ in range(t): n,k=map(int,input().split()) time=[0]+list(map(int,input().split())) adj=[[] for _ in range(n+1)] degree=[0]*(n+1) answer=[0]*(n+1) for _ in range(k): a,b=map(int,input().split()) adj[a].append(b) degree[b]+=1 w=int(input()) q=deque() for i in range(1,n+1): if degree[i]==0: q...

개강 기념으로 블로그를 업데이트 해보려고 한다. 시간 제한이 까다로운 문제이고, DP를 통해서 해결했다. import sys input=sys.stdin.readline n=int(input()) ndata=list(map(int,input().split())) m=int(input()) mdata=list(list(map(int,input().split())) for _ in range(m)) dp=[[0 for _ in range(n)] for _ in range(n)] for index in range(n): for start in range(n): end=start+index if end>=n: break if start==end: dp[start][end]=1 continue if end==st..

최근 장염에 걸려서 포스팅을 하지 못했다. 모두 건강 유의하고 아프지 않았으면 좋겠다. 오랜만에 올려보는 기하 관련 문제이다. '신발끈 공식,' 즉 CCW를 통해서 구했다. 한 점을 정한다. 이후 두 점들을 쌍으로 정하여 신발끈 공식을 통해 삼각형의 넓이를 구한다. answer=0 data.append(data[0]) for i in range(n): area=0 area+=(data[i][0]-data[0][0])*(data[i+1][1]-data[0][1]) area-=(data[i+1][0]-data[0][0])*(data[i][1]-data[0][1]) area/=2 answer+=area print(round(abs(answer),1)) P.S. CCW는 두가지로 가능하다.

오늘의 문제는 Dynamic Programming으로 풀 수 있는 문제이다. 은근 잘 보일만 하면서도 각이 잘 안 보이는게 Dynamic Programming인 것 같다. 문제 자체는 이해하기 쉽다. 기지국들이 정사각형 모양으로 통신 범위를 만드는데, 모든 빌딩들이 이 통신폭 안에 있어야한다. 모든 기지국들은 x축 위에 있다. n=int(input()) coord=[list(map(int,input().split())) for _ in range(n)] for i in range(n): if coord[i][1]

문제 타이틀, 문제 스토리도 귀엽지만, 문제 풀이의 알고리즘을 찾기 쉽지 않다. 문제를 보고 바로 다이내믹 프로그래밍 알고리즘으로 문제를 풀어야 함을 떠올려야 하는 것이 중요한 포인트였다. lcs와 비슷한 방법으로 풀었는데, n=int(input()) left=[0]+[int(input()) for _ in range(n)] right=[0]+[int(input()) for _ in range(n)] dp=[[0]*(n+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,n+1): dp[i][j]=max(dp[i-1][j],dp[i][j-1]) if abs(left[i]-right[j])

멘토님께서 추천해주신 골드 난이도를 자랑하는 '전기가 부족해'라는 문제이다. 이 문제의 특징은, 기존의 문제는 각 지점까지의 거리가 '1' 이나 특정 숫자로 정해져 있어서, 단순히 지점까지의 거리를 일괄적으로 계산하기 유리했는데, 이번 각 지점사이의 비용이 모두 상이하기에, 기존의 문제 해결 방법으로 풀 수 없었다. 그래서 이번에 사용한 알고리즘은 Kruskal Algorithm이다. (크루스칼 알고리즘) 크루스칼 알고리즘은 그래프 내에 있는 모든 점들을 제일 적은 비용으로 연결할 수 있는 방법이다. '신장 트리' 중 제일 비용의 합이 적은 '최소 신장 트리' (Minimum Spanning Tree) 를 구하는 과정이다. (신장 트리란 '사이클'을 형성 하지 않는 선에서, 모든 노드가 적어도 하나의 간..

DP를 이용한 문제이다. 이 문제를 풀 때, 제일 중요한 점은 처음에 벌통, 벌 두 마리 중 두 가지는 양 끝에 둬야한다. 이를 '귀류법'을 통해서 증명했는데, 귀류법이란 간단하게 말해서 증명하고자 하는 것을 반대되는 것을 옳다고 가정하고, 이가 모순됨을 증명하여 기존의 증명이 옳다는 것을 증명하는 방법이다. 이 문제에서는, 벌통이나 벌 두마리가 제일 양 끝에 있는 예시가 최적이 해가 아니라고 했을 때, 이들이 가운데에 몰려있는 경우의 합이 양 끝에서 더한 합보다 작기에 모순되고, 그래서 이들이 양 끝에 있어야한다, 라는 결론이 나온다. 이 문제는 '스페셜 저지' 문제로, 구현해낸 n의 범위에 따라서 점수를 매긴다. 최대한 시간 적합하도록 문제를 구현해야 100점이라는 완벽한 점수를 매길 수 있다. n=..

요즘 Sogang ICPC 팀에 들어가서 그룹으로 알고리즘을 공부하고 있는데, 멘토님께서 추천해주신 첫번째 문제이다. well-known한 문제라고 하셨는데, 생각보다 어렵고, 처음부터 떠올리기 힘들어서 애를 먹었다. 알고리즘은 정말 간단하다. import heapq n=int(input()) data=[list(map(int,input().split())) for _ in range(n)] data.sort() q=[] for i in data: if q: if q[0]

오늘의 문제는 웰-노운 문제 중 하나인 트리의 지름이다. 생각보다 방법만 알면 구현하기 쉬웠는데, 그 아이디어를 떠올리는게 너무 힘들었다. deque를 이용해서 문제를 푼다, 먼저, 트리의 시작 노드부터 해서 BFS 탐색을 하는데, 모든 노드에 대해서 이동하면서, 값을 더해가면서 제일 말단의 branch node들 중 합이 제일 큰 node를 발견한다. 이 때, 그 해당 node에서부터 BFS탐색을 하는데, 거기서 최댓값이 정답이 된다. 이 문제의 해답을 알게 되고, 머리를 맞은 것 처럼 놀라웠다. from collections import deque import sys input=sys.stdin.readline def bfs(start): visited=[-1 for _ in range(n+1)] v..