killog

최소 스패닝 트리는 결국 다익스트라에서 will_visit 을 우선순위큐에 넣는 방식으로 푼다고 생각하면 된다. 다시한번 풀어볼것 문제 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 ..

이걸 보고 어떻게 이분 탐색이라는 생각을 해내고 이분 탐색이라는 것을 여기에 어떻게 적용하지?? 에 대한 생각이 많았던 문제. 결국 참고 문헌을 봤다. 내가 보기에 이분 탐색이라는 것은 결국 전체에 주어지는 제한 조건수 제한 조건 이라는 키워드와 범위가 있음을 생각을 해야하는 것 같은데, 거기까지의 발상이 안된다. 구간 나누기 문제들을 좀 더 풀어야겠다. 문제 N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다. 배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다. 구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다. ..

HashMap은 Java Collections Framework에 속한 구현체 클래스입니다. Java Collections Framework는 1998년 12월에 발표한 Java 2에서 정식으로 선보였습니다. Map 인터페이스 자체는 Java 5에서 Generic이 적용된 것 외에 처음 선보인 이후 변화가 없지만, HashMap 구현체는 성능을 향상시키기 위해 지속적으로 변화해 왔습니다. 개요 HashMap과 Hashtable은 Map인터페이스를 상속받아 구현되어 데이터를 키와 값으로 관리하는 자료구조이다. 큰 특징으로는 키(Key)가 데이터를 추출할 때 구분자로 활용하는 방식을 취하는데 이는 리스트 인터페이스와 같은 자료구조보다 탐색에 있어 더 높은 효율을 기대할 수 있다. 공통 정의 키에 대한 해시 ..

나는 아직 그리디에 약하다. 이 문제의 경우 시간 초과를 1시간 동안 받다가 포기했다. 오답노트를 해야한다고 생각해서 작성한다. 필수 핵심 아이디어는 문자를 ord 를 통한 수로 만들고, 그것을 index 로 접근하는 것이 주 방법인거 같은데 정확한 파악이 안된다. 이전 내 풀이는 왜 시간 초과지?? import collections import sys sys.setrecursionlimit(10 ** 4) input = sys.stdin.readline print = sys.stdout.write def iinput(): return int(input()) def lisinput(): return list(map(int, input().split())) def dq(a): return collectio..

이번 시간에는 자바의 단점에 대해 알아보겠습니다. 자바는 대표적인 객체지향 언어인데요, 그로 인해 개발 설계가 복잡해지고, 런타임 속도가 비교적 느려진단 단점이 있습니다. 객체 지향의 단점 ( https://java119.tistory.com/19 , 참고 문헌입니다. ) 개발 설계의 복잡함 느려지는 런타임 속도 따라서 처리 속도가 중요한 애플리케이션에는 적합하지 않습니다. 또한, GUI 요소가 많은 MS 윈도 응용 프로그램 개발에는 적합하지 않습니다. 뿐만 아니라, jvm 이라는 가상머신을 사용하기 때문에, 하드웨어에 연결하여 제어할 수 없습니다. 따라서, 직접 하드웨어를 정밀하게 조정해야 하는 프로그램 개발에는 적합하지 않습니다. 보일러 플레이트란? 컴퓨터 프로그래밍에서 상용구 코드 또는 단순한 상용..

n^2 가 안되게 하기 위해 remain 을 만들어서 풀어야하는 문제. 이전에 풀어본 유형임에도 오래걸렸다. 문제 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모..

이 문제에서 제일 중요한 포인트는 문제 푸는 핵심 전략이 아닌 제한 범위이다. 수빈이가 갈 수 있는 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000) 이 100000 를 방어 변두리로 잡는 것이 이 문제의 핵심 포인트 였다. 앞으로 제한 조건을 좀 더 잘 활용해야함을 잊지 말자. 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위..

1시간 10분 걸림. 문제 제대로 구현 안해서 한번 틀리고, 인덱스 에러를 안잡아 줘서 한번 틀렸고, 가짓수를 다 해봤는데 안될 경우를 생각하지 못해 여러번 틀렸다. 안될 경우를 대비해 answer 에 불가능이란 값을 default 로 줬어야하는 문제. transpose 함수를 알게 되었다. def transpose(graph): return list(map(list, zip(*graph))) 문제 크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 = len(curA[0]): return commandR(cur..