생각 생각

https://acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 꽤나 빨리 푼 문제였다. 이래저래 고민할 것이 많았던 종합세트같은 느낌. import sys input=sys.stdin.readline n,m=map(int,input().split()) graph=[[0] for _ in range(n)] # 하나하나 녹이는 건 너무 오래 걸린다. 다음에 녹을 양을 저장하는 배열을 만든다. # -1이라는 건 얼음이 아니라 물이라는 것. 초기값은 물로 둔다. to..

https://acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 위상정렬의 정석 문제. 한 번에 풀렸다. N,M=map(int,input().split()) singers=[[] for _ in range(N+1)] in_order=[0]*(N+1) q=[] ans=[] for _ in range(M): temp=list(map(int,input().split())) for i in range(1,len(temp)-1): singers[temp[i..

https://acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 소마 코딩테스트를 준비중인데, bfs는 적응 됐고 dp는 사실상 그리 어렵게 안 나올 것 같아서 그리디를 연습한다. 간단한 문제였다. import heapq import sys # 표준입력으로 받는지 여부에 따라 차이가 굉장히 컸다. input=sys.stdin.readline N=int(input()) answer=0 cards=[] for i in range(N): heapq.heapp..

https://acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트마스킹을 쓸 수도, 그냥 이진수로 풀 수도 있는데 사실 속도 차이는 거의 없었다. 방법 1. 이진수로 푸는 경우 # deque를 사용할 필요가 없다. popleft나 pop이나 상관없는 문제. n,m=map(int,input().split()) # visited에는 처음에는 방문 여부를, 나중에는 어떤 몇번 방인지를 저장한다. visited=[[False]*n for _ in range(m)] ..

https://acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net deepcopy 안해서 한참을 헤맨 문제. 아이디어는 찾는데 얼마 걸리지 않았다. 이 경우 출발점에 따라 결과가 달라지니 플로이드-워셜 알고리즘도 생각해 보았다. 그러나 모든 점을 다 고려하더라도 다익스트라가 더 빠를 것 같았다. 출발점마다 다익스트라를 실행하고, 거리가 수색 범위 이상인 것을 배제하는 방법으로 풀었다. import heapq,sys input=sys.stdin.readline INF=sys...

https://acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 아직 언제 다익스트라를 써야 하고 언제 플로이드-워셜을 써야 하는지가 헷갈려서 시간이 걸린 문제. 처음에는 플로이드 워셜이라 생각해서 코드를 짰다가 실패했다. 코드는 다음과 같았다. import sys input=sys.stdin.readline INF=sys.maxsize n=int(input()) m=int(input()) dp=[[[INF,[]] for i in ra..

https://acmicpc.net/problem/25330 25330번: SHOW ME THE DUNGEON 올 여름 출시된 RPG 게임 "SHOW ME THE DUNGEON"은 주인공 시루가 몬스터에게 침략당한 마을을 구하는 내용의 게임이다. 배경이 되는 나라는 $0, 1, 2, \cdots, N$번의 번호가 붙어있는 $N+1$개의 마을로 이루 www.acmicpc.net 간단한 백트래킹 문제였다. 정해진 체력을 최대한 활용하여 가장 많은 수의 주민을 해방시키면 된다. 이때 특이했던 점은 cost가 누적으로 점점 커졌다는 점이다. import sys input=sys.stdin.readline n,hp=map(int,input().split()) c=list(map(int,input().split()..

https://acmicpc.net/problem/20947 20947번: 습격받은 도시 $N$개의 줄에 도시의 정보를 출력한다. 각 줄은 $N$개의 문자를 포함하며 $i$번째 줄 $j$번째 문자는 도시의 세로 $i$번째 가로 $j$번째 칸에 대한 정보이다. 빈칸일 경우 ., 건물일 경우 O, 건물 잔해 www.acmicpc.net 크리스마스 이벤트로 떴던 간단한 bfs 문제였다. 기본 아이디어는, 폭발이 일어났을 수 있는 곳은 상하좌우가 모두 잔해이거나 모두 잔해가 아니어야 한다는 점이다. n=int(input()) graph=[list(input()) for _ in range(n)] def bomb(): def column(col): #column을 기준으로 폭탄이 못 들어가는 위치를 찾는다. de..