지식을 나누는 공간

문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 코드 import heapq import sys INF=sys.maxsize def dijk(start): dis = [INF] * (n+1) q=[] heapq.heappush(q,(0,start)) dis[start]=0 while q: cost,node=heapq.heappop(q) if cost>dis[node]: continue for i in graph[node]: new_c..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 코드 n=list(input().rstrip()) m=list(input().rstrip()) dp=[[0]*(len(n)+1) for _ in range(len(m)+1)] for i in range(1,len(m)+1): for j in range(1,len(n)+1): if n[j-1]==m[i-1]: dp[i][j]=dp[i-1][j-1]+..

문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 n=int(input()) row=[0]*n result=0 def check(x): for i in range(x): if row[i]==row[x] or abs(row[i]-row[x])==abs(i-x): return False return True def dfs(x): global result if x==n: result+=1 return for i in range(n): row[x]=i if ..

문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 코드 from collections import deque r,c=map(int, input().split()) INF=int(1e10) dx=[-1,1,0,0] dy=[0,0,-1,1] visited=[[0]*c for _ in range(r)] array=[list(input().rstrip()) for _ in range(r)] dr,dc=0,0 queue=deque() for i in range(..

문제 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 코드 import sys input=sys.stdin.readline INF=sys.maxsize n,m,r=map(int, input().split()) item=list(map(int, input().split())) graph=[[INF]*(n+1) for _ in range(n+1)] for i in range(n+1): for j in range(n+1): if i==j: graph[i]..

문제 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 코드 import sys INF=sys.maxsize t=int(input()) while(t): t-=1 k=int(input()) arr=list(map(int, input().split())) dp=[[0]*k for _ in range(k)] subsum={-1:0} for i,v in enumerate(arr): subsum[i]=subsum[i-1]+v for i in r..

문제 https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 코드 import sys import heapq input=sys.stdin.readline def sol(li): small=[] big=[] middle=li[0] result=[middle] for idx,val in enumerate(li[1:],1): if val > middle: heapq.heappush(big,val) else: heapq.heapp..

문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 코드 n,m=map(int, input().split()) lst=[] def dfs(start): if len(lst)==m: print(' '.join(map(str,lst))) return for i in range(start, n+1): if i not in lst: lst.append(i) dfs(i+1) lst.pop() dfs(1) 생각 정리

문제 https://www.acmicpc.net/problem/15926 15926번: 현욱은 괄호왕이야!! 첫 번째 입출력에서, 맨 처음 위치부터 4개를 잘라낸 (())가 가장 긴 올바른 괄호 문자열이다. 두 번째 입출력에서, 6번째 위치부터 8개를 잘라낸 ()((()))가 가장 긴 올바른 괄호 문자열이다. www.acmicpc.net 코드 n=int(input()) array=list(input()) dp=[0]*n stack=[] for i in range(len(array)): if array[i]=="(": stack.append(i) else: if stack: if array[stack[-1]]=="(": n=int(stack.pop()) dp[i] = dp[n] = 1 count=0 res..

문제 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 코드 array=list(input()) stack=[] temp=1 result=0 for i in range(len(array)): if array[i]=="(": stack.append("(") temp*=2 elif array[i]=="[": stack.append("[") temp*=3 elif array[i]==")": if not stack or stack[-1]=="[": r..