killog

2020.10.20 2021.03.09 틀림 맞은줄 알고 있었지만 틀림 뭐지?????? 이때 풀이도 틀린거임 (원리 잘못 이해 다시 풀자) 알고리즘 자체에 익숙하지 않다고 많이 반성하게 된 문제.. 아직 난 잘 모르나보다,다이나믹 프로그래밍 수식만 알았으면 쉽게 맞출수 있는 문제였는데.. 아직 모자르다. 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주..

Union Find( 유니온 파인드) 는 대표적인 알고리즘입니다. 바로 합집합 찾기라는 의미를 가진 알고리즘인데, 서로소 집합(Disjoint-set) 알고리즘이라고 부릅니다. 구체적으로 여러 개의 노드가 존재할때, 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 위와 같이 여러 개의 노드가 서로 자유분방하게 존재한다고 생각해보자. 이와 같이 모두 연결되지 않고 가가 자기 자신만을 집합의 원소를 가지고 있을때를 다음과 같이 표현할 수 있다. 모든 값이 자기 자신을 가르키도록 만드는 것이다. 아래 표에서 첫번째 행은 '노드 번호'를 의미하고, 두번째 행은 '부모 노드 번호'를 의미합니다. 즉, 자신이 어떠한 부모에 포함되어있는지를 의미합니다. 이 떄 위와 ..

Union Find( 유니온 파인드) 는 대표적인 알고리즘입니다. 바로 합집합 찾기라는 의미를 가진 알고리즘인데, 서로소 집합(Disjoint-set) 알고리즘이라고 부릅니다. 구체적으로 여러 개의 노드가 존재할때, 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 위와 같이 여러 개의 노드가 서로 자유분방하게 존재한다고 생각해보자. 이와 같이 모두 연결되지 않고 가가 자기 자신만을 집합의 원소를 가지고 있을때를 다음과 같이 표현할 수 있다. 모든 값이 자기 자신을 가르키도록 만드는 것이다. 아래 표에서 첫번째 행은 '노드 번호'를 의미하고, 두번째 행은 '부모 노드 번호'를 의미합니다. 즉, 자신이 어떠한 부모에 포함되어있는지를 의미합니다. 이 떄 위와 ..

기분이 좋아 종이에 예쁘게 싸서 오래 기억하고 싶은 기분이다.

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)