killog

1. 신장 트리란? Spanning Tree, 또는 신장 트리라고 부른다. 원래의 그래프의 모든 노드가 연결되어있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야함. 모든 노드가 서로 연결 트리의 속성을 만족시킨다. ( 사이클이 존재하지 않는다. ) 5. Union - Find 알고리즘 Disjoint Set 를 표현할때 사용하는 알고리즘으로 트리구조를 활용하는 알고리즘 간단하게, 노드들중에 연결된 노드를 찾거나, 노드들을 서로 연결할때 사용 Disjoint Set 란? 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대해 정보를 저장하고 조작하는 자료구조 공통원소가 없는 상호 배타적인 부분집합들로 나눠진 원소들에 대한 자료구조를 의미한다. Disjoint S..

얼탱구가 없는 문제였다. dijkstra 함수 나와서 나머지 식의 전개를 유도하게 했더니 2일동안 끙끙댄게 스르륵 풀렸다. 아니 그럼 왜 틀렸었는데!!!!!!! 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다..

1. 최단경로 문제란? * 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제이다. * 가중치그래프( Weight Graph ) 에서 간선(Edge)의 가중치 합이 최소가 되도록하는 경로를 찾는것이 목적이다. 최단 경로 문제 종류 단일 출발 및 단일 도착 최단 경로 문제 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 최단 경로 문제 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 따지고 보면 굉장히 헷깔릴 수 있으므로 명확히 하자면, 예를 들어 A,B,C,D 라는 노드를 가진 그래프에서 특정 노드를 A 라고 한다면, A외 모든 노드인 B,C,D 각 노드와 A 간에 (즉, A-B, A-..

이진수에서 십진수로 변환은 int(이진수,2) 이런식으로 하면된다. 십진수에서 다른 진수로 변환 >>>bin(42)'0b101010' // 이진수 >>>oct(42)'0o52' // 8진수 >>>hex(42)'0x2a' //16진수 T =int(input()) for _ in range(T): N,A = input().split() N=int(N) B = '0b'+'1'*N B = int(B, 2) #A='0?1?' A1 =int('0b'+ A.replace("?","1"),2) A2 =int('0b'+ A.replace("?","0"),2) AB1 = len(str(bin(A1*B))) -2 AB2 = len(str(bin(A2*B))) -2 print(AB1, AB2)

dp가 너무 안돼서 dp 조지기를 하는 중 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. N = int(input()) dp=[100000000]*(N+5) dp[0]=0 dp[1]=0 dp[2] =1 dp[3]=1 dp[4] =2 i = 4 while i

유명한거랑 내가 풀수 있는거랑은 다르지. 내눈엔 dp로 안풀린다. 손코딩하다가 몰라! 하고 답보는 중.. 내일이 코테라면 어떡하냐 그런데 확실히 뭔가 좀 알겠는게 dp 를 배열로 만들고 항상 반복문을 통해 dp 배열을 채워나가는 형식인 것 같다. 요소들을 배열에 넣어 놓는다는 것을 이제 깨우쳤다. 동적 프로그래밍을 이용해서 시간복잡도 O(nk)로 문제를 해결할 수 있다. 🎈 문제 풀이의 핵심 아이디어 => 이진 행렬로 문제를 품 핵심아이디어: 모든 무게에 대하여 최대가치 저장하기 D[i][j] = 배낭에 넣은 물품의 무게 합이 j 일때 얻을 수 있는 최대 가치 각 물품 번호 i 에 따라서 최대 가치 테이블 D[i][j]를 갱신하여 문제를 해결할 수 있다. (이 식은 외워야합니다. 암기암기암기 이 친구때문..

동적 프로그래밍 특징: 한번 구한 값은 다시 구하지 않는다. 점화식을 잘 짜야 풀 수 있는 문제 문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되..

문제를 푸는건지..답을 보는건지.. 머리가 안돌아간다. 위상정렬을 공부해보자. 문제유형: 힙, 위상정렬 문제 난이도 : 중 문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드..