공부, 기록

문제링크 : www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net N, M = map(int,input().split()) trueman = list(map(int,input().split())) trueman.pop(0) truemanlist = set(trueman) party=list() for i in range(M): line = list(map(int,input().split()))[1:] if not truemanlist.isdisjoint(set(line)):..

문제링크 : www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net def solution(N, lines): if N == 1 : return 1 else: dp=[0]*N updp=[1]*N downdp=[1]*N for i in range(N): for j in range(i): if lines[i] > lines[j]: if updp[i] < updp[j] + 1: updp[i] = updp[j]+1 for i in range(N-1,0,-1): for j in range(N-..

문제링크 : 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..