분류 전체보기
[백준/1058/파이썬] 친구
https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net Problem 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오. 조건 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해..
[알고리즘/DP/개념] 팰린드롬
Panlindrom 똑바로 읽으나 , 거꾸로 읽으나 똑같은 글자를 Panlindrom 우리나라 말로는 회문이라고 한다. 예를들어 , 주황색 방향으로 읽든(정방향) ,파랑색 방향(역방향)으로 읽든 "기러기"로 읽힌다. 팰린드롬이 현실생활에?! 1. 지폐수집 지폐 수집계에서는 RADAR라고 부르는데, 일반 화폐보다 조금 더 가치가 있다고 한다. 참고로, 1가지 숫자로만 되어있으면 "솔리드"라고 부르는데, "9999999"로 되어있는 지폐가 있다면 보존을 잘 해놓자. 약 100만원의 이상의 가치를 가지고 있다고 한다. 2. 염기서열 생명과학에서 DNA가 이루는 염기서열을 분석할 때, 특정 염기배열을 나타내는 개념으로 쓰인다고 합니다.( 팰린드롬 확인하기 팰린드롬을 확인하는 제일 직관적인 방법은, 문자열을 뒤집..
[백준/1173/파이썬] 운동
https://www.acmicpc.net/problem/1173 1173번: 운동 첫째 줄에 다섯 정수 N, m, M, T, R이 주어진다. www.acmicpc.net Problem 영식이가 운동을 하는 과정은 1분 단위로 나누어져 있다. 매 분마다 영식이는 운동과 휴식 중 하나를 선택해야 한다. 조건 운동을 선택한 경우, 영식이의 맥박이 T만큼 증가한다. 즉, 영식이의 맥박이 X였다면, 1분 동안 운동을 한 후 맥박이 X+T가 되는 것이다. 단, 영식이는 맥박이 M을 넘는 것을 원하지 않기 때문에, X+T가 M보다 작거나 같을 때만 운동을 할 수 있다. 휴식을 선택하는 경우 맥박이 R만큼 감소한다. 즉, 영식이의 맥박이 X였다면, 1분 동안 휴식을 한 후 맥박은 X-R이 된다. 단,맥박은 절대로 m..
[백준/1541/파이썬] 잃어버린 괄호
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net Problem 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 조건 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자..
[백준/1922/파이썬] 네트워크 연결
https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net Problem 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결..
[백준/1197/파이썬] 최소 스패닝 트리
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net Problem 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 조건 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개..
[알고리즘/개념/그래프] 크루스칼 알고리즘(KrusKal Algorithm)
개념 MST(Minnimal Spanning Tree)를 알아내는 알고리즘 중 하나로, Graph를 탐사하는 방법 중 하나이기도 합니다. Graph를 탐사하는 과정을 보면, 모든 정점들을 가장 적은 비용으로 연결하기 위해서 사용되는 알고리즘입니다. MST(Minimal Spanning Tree) Minimal Spanning Tree는 최소 신장 트리라고도 합니다. Spanning Tree가 뭔지 수학적 정의도 있고, 말로 정의하는 것도 좋지만, 그림으로써 먼저 이해하는게 좋습니다. 아래와 같은 그래프가 있다고 합시다. 위 그래프의 Spanning Tree 위의 그림들을 먼저 보고, 하나씩 특징들을 생각해봅시다. Spanning Tree 모든 노드를 사이클 없이 방문하는 Tree Tree 이기 때문에, ..
[백준/1076/파이썬] 저항
https://www.acmicpc.net/problem/1076 1076번: 저항 첫째 줄에 첫 번째 색, 둘째 줄에 두 번째 색, 셋째 줄에 세 번째 색이 주어진다. 위의 표에 있는 색만 입력으로 주어진다. www.acmicpc.net Problem 전자 제품에는 저항이 들어간다. 저항은 색 3개를 이용해서 그 저항이 몇 옴인지 나타낸다. 처음 색 2개는 저항의 값이고, 마지막 색은 곱해야 하는 값이다. 저항의 값은 다음 표를 이용해서 구한다. 조건 첫째 줄에 첫 번째 색, 둘째 줄에 두 번째 색, 셋째 줄에 세 번째 색이 주어진다. 위의 표에 있는 색만 입력으로 주어진다. SOL 마지막 입력은 10의 거듭제곱으로 계산 해준다. 저항을 계산할 때, red red white면, 22*10^9 옴이 된다..