본문 바로가기

C++

 (113)
[백준 1535번] 안녕 link : https://www.acmicpc.net/problem/1535 안녕 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB122361241050.617%문제세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면,..
[백준 1837번] 암호제작 link : https://www.acmicpc.net/problem/1837 암호제작 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB138624118625.514%문제원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 주면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 ..
[백준 1644번] 소수의 연속합 link : https://www.acmicpc.net/problem/1644 소수의 연속합 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB44861824133341.787%문제하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+13+17 = 53 (두 가지)하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5..
[백준 11653번] 소인수분해 link : https://www.acmicpc.net/problem/11653 소인수분해 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB58593209258155.458%문제정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.입력첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.출력N의 인수를 한 줄에 하나씩 증가하는 순서대로 출력한다.예제 입력 1 복사72 예제 출력 1 복사2 2 2 3 3 예제 입력 2 복사3 예제 출력 2 복사3 예제 입력 3 복사6 예제 출력 3 복사2 3 예제 입력 4 복사2 예제 출력 4 복사2 예제 입력 5 복사9991 예제 출력 5 복사97 103 소인수분해 문제이다. 그냥 풀었다. 123456789101112131415161..
[백준 2960번] 에라토스테네스의 체 link : https://www.acmicpc.net/problem/2960 에라토스테네스의 체 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB51302590227252.027%문제에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.이 알고리즘은 다음과 같다.2부터 N까지 모든 정수를 적는다.아직 지우지 않은 숫자 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.아직 모든 숫자를 지우지 않았다면, 다시 2번 단계로 간다.N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) ..
최소 공통 조상(Lowest Common Ancestor / LCA) 1. 개념 트리 그래프 G에서 임의의 정점 A와 B의 최소 공통 조상은 A와 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점이다. 트리 그래프 G에서 임의의 정점 A와 B의 최소 공통 조상은 A 혹은 A의 조상이면서 B 혹은 B의 조상인 정점들 중 가장 깊은 정점이다. 2. 구현 보통 parent[i] 처럼 일차원 배열로 표현하던 부모 배열을 parent[u][k] 2차원 배열로 만든다. 이것이 뜻하는 바는 정점 u의 2^k 번째 부모라는 뜻이다. 이것을 풀어쓰면 2^(k+1) = 2^k + 2^k 이므로 , parent[u][k+1] = parent[parent[u][k]][k] 의 점화식을 구할 수 있다. 이 점화식에서 수 있듯이 k=i 일 때의 정보로 k=i..
벨만 포드 알고리즘 (Bellman-Ford-Moore Algorithm) 1. 개념 V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘. 다익스트라 알고리즘과는 다르게 음의 가중치를 가지는 간선이 있어도 가능하다. 또한, 그래프에 음의 가중치를 가진 사이클의 존재 여부를 확인할 수 있다. 2. 구현 V개의 정점과 E개의 간선을 가진 가중 그래프에서 어떤 정점 A에서 B까지의 최단거리는 최대 V-1개의 간선을 사용한다는 아이디어로 시작한다. 1) Distance[i] : 출발점(S)에서부터 i 정점까지의 최단거리를 저장하는 배열. Distance[S] = 0 으로 초기화하고, 나머지는 모두 무한대로 초기화 2) V-1 번 모든 간선을 확인해 아래의 조건을 만족할 때마다 최단거리배열을 갱신한다. - ..
[백준 1735번] 분수 합 link : https://www.acmicpc.net/problem/1735 분수 합 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB72653012255543.298%문제분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.입력첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.출력첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출..

티스토리툴바