문제링크 : www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net #PYPY3로 실행 import sys def solution(nums,N): dp = [1] * N for i in range(1,N): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j]+1) return max(dp) def main(): N = int(input()) nums = list(map(int,sy..

문제링크 : www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net def solution(MAPS, N): visitied = [[0 for _ in range(N)]for i in range(N)] landnum=2 answer = list() mins = 9999 dx=[1,-1,0,0]; dy =[0,0,1,-1] #섬 구분 for i in range(N): for j in range(N): if MAPS[i][j] == 1: MAPS[i][j] = landnum..

문제링크 : www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net import sys from collections import deque input = sys.stdin.readline """def solution(graph,questions): answer = list() notanswer = list() answers=[0]*len(questions) for idx, question in enumerate(questions): a, b = questi..

문제링크 : www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net def solution(lists): answer = [0]*len(lists) # 먼저 짓는게 없는 경우 for i in range (len(lists)): if len(lists[i]) == 2: answer[i] = lists[i][0] while 0 in answer: for i in range(len(lists)): buildtime = lists[i][0] buildtimes=..

문제링크 : www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import math import heapq as hq import copy def solution(graph, start, end): godist = list() answer = [0]*start for i in range(start): queue= list() dist = [math.inf]*start dist[i] = 0 hq.heappush(queue,[dist..

문제링크 : www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net import sys input=sys.stdin.readline def solution(graph,V): stack = list() visitied = set() stack.append((0,0)) visitied.add(0) maxlen = 0 maxnode=0 while stack: node, dist = stack.pop() if dist > maxlen: maxlen = dist ..

문제링크 : programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr def isPalindrome(s, start, end): diff = int((end - start + 1) / 2 - 1) for i in range(diff + 1): c1 = s[start + i] c2 = s[end - i]; if c1 != c2: return False return True def ..

문제링크 : programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr def solution(n, results): win = {x:set() for x in range(1, n+1)} lose = {x:set() for x in range(1, n+1)} for winner, loser in results: win[winner].add(loser) lose[loser].add(winner) for i in range(1, n+1): for winner in lose[i]: win[winner].update(win[i]) for loser..

문제링크 : programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr def solution(m, n, puddles): dp = [[0]*m for i in range(n)] for i in range(len(dp)): for j in range(len(dp[i])): if i == 0 and j == 0 : dp[i][j]=1 elif [j+1,i+1] in puddles: dp[i][j] = 0 else: dp[i]..

문제링크 : programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr def solution(genres, plays): answer = [] songs = dict() for i,x in enumerate(zip(genres, plays)): if x[0] not in songs: songs[x[0]]=[[i,x[1]]] else: songs[x[0]].append([i,x[1]]) suchgenre=getManyGenre(ge..