생각 생각

https://acmicpc.net/problem/13334  13334번: 철로입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0www.acmicpc.net매번 새로운 알고리즘이 나오는 것이 신기하다. 스위핑 알고리즘이라는 것을 알게 되었다. n차원 평면에서 순서대로 방향에 맞춰 탐색해나가는 방법인데, 응용도 어렵고 대부분의 경우 한 차원을 정렬하고 시작하기에 힙이나 (레이지 프로파게이션을 곁들인)세그먼트 트리를 같이 써야 해서 어렵다고 한다.이 경우에는 우선순위 큐만 이용해도 된다. 방법은 다음과 같다.끝점..

https://acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 재미있는 문제였다. 말 그대로 브루트포스의 정석. 시키는 대로 하나하나 층을 살펴보면 된다. import sys from collections import deque from itertools import permutations input=sys.stdin.readline def rotate(floor): base_floor=floor[0] new_list=[[0]*5 for _ i..

https://acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 이제 무지성 구현이 가능해진 LIS(nlogn). import sys, bisect input=sys.stdin.readline while True: try: n=int(input()) prices=list(map(int,input().split())) temp=[prices[0]] for i in range(n): if temp[-1]

https://acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 플로이드가 제일 쉬웠어요. 1트클할 수 있었는데, ‘불가능’을 잘못 해석했다.. 불가능하다는 건 곧 최단 경로가 최단경로가 아니라는 것을 의미한다. 간선/정점 개수 적을 때는 visited 이용하자. 자꾸 set 이용해서 창조손해보지말고. import sys input=sys.stdin.readline INF=sys.maxsize N=int(input()) graph=[list(map..

https://acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 수업듣다 심심해서 구현한 플로이드 문제. 경로를 찾는 더 좋은 방법이 있을 듯하다. 인접 행렬을 이용해서 푸는 방법도 있다고 한다. import sys input=sys.stdin.readline INF=sys.maxsize n=int(input()) m=int(input()) dp=[[INF]*n for _ in range(n)] ways=[[[]]*(n+1) for _ in range(n+1)] ..

https://acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 트리에서의 dp는 두 번째인데, 전에 풀었던 문제보다 난해했다. 설마 dp 테이블을 두 개로 나눠서 방문하는 경우와 방문하지 않는 경우를 나눠야 하나 했는데 맞았다. dfs, dp 다 알고도 막상 트리에 적용이 안 되니 좀 답답하다…. 별론으로 비트마스킹으로 처음에 풀었는데 visited보다 훨씬 느렸다. N이 10000으로 상대적으로 작아서 그런 것 같다. import sys input=sys..

https://acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 일반 다익스트라에 더해 내가 해당 지점에 방문했었는지 여부를 검사한다. 단순하게 일반적인 다익스트라에 도착 여부를 더해주면 된다. import sys from heapq import heappop, heappush input=sys.stdin.readline INF=sys.maxsize T=int(input()) for _ in range(T): answers=[] n,m,t=map(int,inpu..

https://acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 알고리즘 수업 시간에 배웠던 잘 알려진 그리디 문제. 그때는 unit task scheduling problem이라고 배웠던 것 같다. 그리디 알고리즘임을 알기만 한다면 문제 풀이는 크게 어렵지 않다. from heapq import heappop,heappush import sys input=sys.stdin.readline INF=sys.maxsize N=int(input()) noodles=[] for _ ..