공부, 기록

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

문제링크 : programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr def solution(tickets): routes = {} for t in tickets: routes[t[0]] = routes.get(t[0], []) + [t[1]] for r in routes: routes[r].sort(reverse=True) stack = ["ICN"] path = [] while len(stack) > 0: top = stack[-1] if top no..

문제링크 : programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr import heapq def solution(operations): operlist = list(operations) hq=[] answer =[] for i in operlist: oper,num = i.split(" ") if oper == "I": heapq.heappush(hq,int(num)) elif oper =="D": if len(hq)!=0: if num == "1": hq.pop(-1) elif num == "-1": heapq.heappop(hq) if len(hq) == 0: answer =[0,0] else: ans..

문제링크 : programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr def solution(routes): answer = 1 routes.sort(key = lambda x : abs(x[0]-x[1])) routes.sort(key=lambda x: -x[0]) camera=list() camera.append(routes[0][0]) X=True for i in routes: check=len(camera) idx=0 while X==True: if i[0]

문제링크 : programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr import heapq as hq def solution(jobs): lens=len(jobs) answer = 0 heap = list() jobs.sort() hq.heappush(heap,jobs.pop(0)) first = hq.heappop(heap) time = first[0]+first[1] answer = first[1] lasttime=fir..

문제링크 : programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr from collections import deque def solution(n, edge): graph = [[] for i in range(n+1)] for i in edge: graph[i[0]].append(i[1]) graph[i[1]].append(i[0]) queue = deque() visited=set() queue.append(1) visited.add(1) distance=[0 for i in range(n+1)]..