제레미 베러미의 타임라인

최소 스패닝 트리란? 최소 스패닝 트리(Minimum spanning tree) 는 그래프 이론에서 자주 사용하는 개념이다. 최소 신장트리, MST라고도 부르는데 다 같은 말이다. 스패닝 트리 / 최소 스패닝 트리 '최소 스패닝 트리'를 살펴보기에 앞서, 먼저 '스패닝 트리'를 이해해보자. 스패닝 트리는 어떤 그래프에서 모든 정점을 포함하지만, 사이클이 발생하지 않는 트리다. 다음 그래프를 보면서 이해해보자. 위 그래프는 사이클이 있다. 1번, 2번, 3번 노드가 서로 사이클을 발생시킨다. 사이클을 없애면서 모든 노드를 포함하는 그래프는 다음과 같은 모양이 될 것이다. 위에 보이는 그래프들 모두 '스패닝 트리' 다. 사이클이 없고 모든 노드를 포함하기 때문이다. 이때 스패닝 트리의 '가중치'를 물어본다면..

my_dict = dict() my_dict[(0,0)] = 1 딕셔너리인데 키 값이 튜플이다. 이 경우 문제 없이 실행될까? 결론부터 말하면, 된다! 키(key) 값(value) 10 "민수" 20 "상호" 30 "수현" 딕셔너리는 키-값 쌍으로 이루어진 자료형이다. 파이썬에 내장된 딕셔너리는 '해시 테이블' (Hash table) 구조로 구현되어 있다. 해시 테이블을 논리적으로 표현하면 다음과 같은 모양이다. # Logical model of Python Hash table -+-----------------+ 0| | -+-----------------+ 1| ... | -+-----------------+ .| ... | -+-----------------+ i| ... | -+----------..

문제음이 아닌 정수가 N개 들어있는 리스트가 주어졌을 때, 리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.해설처음에는 "?? 뭐지 이런게 플래5라고?" 싶을 정도로 단순히 풀릴 것 같은 문제였다.각 숫자들을 '가장 큰 자릿수'에 맞춘 다음, 정렬시킨 후 원본 값을 불러오면 되는거 아닌가 했던 것이다.예를 들어,3 30 34 5 9 의 경우3 30 34 5 9(자릿수 맞추기)30 30 34 50 90(정렬)90 50 34 30 30(원본값 불러오기)9 5 34 3 30 로 풀 수 있지 않을까 했던 것이다.  실제로 이렇게 생각을 하고 제출하니 83%까지는 올라가는 듯 했다. 그러나 여지없는 실패.위 방식으로 코드를 짜면 다음과 같은 반례가 생긴다.21211 121A..

문제정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) ..

문제수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.문자열의 뒤에 A를 추가한다.문자열을 뒤집고 뒤에 B를 추가한다.주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 해설문제 설명이 단순한 것에 비해 발상이 조금 까다롭게 느껴진 문제다.S를 T로 바꿀 때, 두 가지 연산이 가능하다.문자열의 뒤에 A를 추가한다.문자열을 뒤집고 뒤에 B..

문제 1932번: 정수 삼각형첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.www.acmicpc.net 위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.해설다이나믹 프로그래밍(DP)를 이용해 풀 수 있는 문제다. 위에서부터 아래로, 하향식으로..

문제 13549번: 숨바꼭질 3수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때www.acmicpc.net수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른..

문제세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다.전광판에는 같은 내용의 문구가 무한히 반복되어 나온다. 또, 전광판의 크기는 전광판에서 한번에 보이는 최대 문자수를 나타낸다. 만약 전광판의 크기가 L이라면, 한번에 L개의 문자를 표시할 수 있는 것이다.광고업자는 최대한의 광고효과를 내기 위해서 길이가 N인 광고를 무한히 붙여서 광고한다.예를 들어, 광고 업자 백은진이 광고하고 싶은 내용이 aaba 이고, 전광판의 크기가 6이라면 맨 처음에 보이는 내용은 aabaaa 이다. 시간이 1초가 지날 때마다, 문자는 한 칸씩 옆으로 이동한다. 따라서 처음에 aabaaa가 보였으면 그 ..

문제우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.해설DP를 활용해 푸는 냅색 유형의 문제다.우선, 우리는 이게 왜 DP 문제인지 생각해보아야 한다.  예를 들어, 1원짜리 동전과 2원짜리 동전이 있다.이 동전으로 각각 1원, 2원, 3원을 만드는 상황을 생각해보자. 그러면 다음과 같을 것이다. (1원) 동전을 사용하는 경우, (1원/2원) 동전을 사용하는 경우로 나누어 두 줄..

npm i -g firebase-tools npm WARN config global `--global`, `--local` are deprecated. Use `--location=global` instead. npm WARN deprecated har-validator@5.1.5: this library is no longer supported npm ERR! command failed npm ERR! command sh -c node scripts/postinstall npm ERR! internal/modules/cjs/loader.js:638 npm ERR! throw err; npm ERR! ^ npm ERR! npm ERR! Error: Cannot find module '/root/.nvm/..