김머성 블로그

[BAE/<JOON> 문제풀이] 1463. 1로 만들기 (DP.001)

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 난 DP를 잘 못한다. 알고리즘 톡방의 어떤 분의 블로그에서 본 내용인데 DP를 못할 때 특효약은 DP 200문제를 풀어보는거라고 한다. 맞는말 같다. 다른 알고리즘들은 난이도가 어려워져도 해당 알고리즘의 틀에서 크게 벗어나지 않는 반면에 DP는 문제 자체가 다양하고 다른 알고리즘들과도 비교적 쉽게 연결이 가능해서 더 어려운것 같다. 오늘부터 DP문제만 풀어봐야겠다. 더보기 #include #include #include using namespace std; int main() { int n; cin >> n;..

[BAE/<JOON> 문제풀이] 2960. 에라스토네스의 체

https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 www.acmicpc.net 에라스토네스의 체 문제이다. 지워진 수인지 아닌지만 판단해서 지워지지 않은 수일 경우를 세면 된다. 더보기 #include #..

[BAE/<JOON> 문제풀이] 10989. 수 정렬하기3

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 오늘 일어나서 너무 기운이 없어서 쉬운 문제 풀고 좀 쉴라했는데... 그럴라고 쉬워보이는 문제 집었는데.. 어이없게 계속 못풀었다. 문제를 보면 주어지는 숫자의 범위를 10000까지의 자연수로 한정하고 있다. 즉, 10000까지의 숫자가 각각 몇번씩 나오는지만 세서 순차 출력하면 되는 문제다. 그런데 자꾸 시간 초과가 뜨는 것이다... 거진 4시간 가량을 고민하며 혹시 분할정복문제인가 하며 퀵정렬 분할 임계점이나 ..

[BAE/<JOON> 문제풀이] 1922. 네트워크 연결

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 스패닝 트리 문제이다. 이런 간선 비용을 구하는 문제는 대부분 간선 위주 연결로 해결할 수 있는 문제이다. 간선 비용을 정렬해두고 하나하나 연결하며 최종 값을 찾는 방식이다. 더보기 #include #include #include using namespace std; struct eg { int s, e, p; }; vector parent; bool operator (eg e1, eg..

[BAE/<JOON> 문제풀이] 2798. 블랙잭

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net 문제가 단순해서 딱히 쓸건없다. 주말이라 간단한 구현문제만 풀었다. 더보기 #include #include using namespace s..

시작

비트코인 회사 댕기는 친구가 회사에서 은행 전문만들면서 전문 통신이 되게 어렵다길래 나도 해보려고 시작했다. 최근에 boost라이브러리에 관한 관심도 생겼고 c++공부에도 좋은 경험이 될 것 같다. 처음 만든지는 대략 1달 정도 지난 것 같은데 쓰레드, 동시성에 대해서도 공부할 거리가 많은 것 같다. 꾸준히 맨들어야겠다.