본문 바로가기

Programming456

[C/C++] 프로젝트 오일러 #72 분수 세기(수학) 이번 문제는 분수를 세는 문제입니다. 해당 문제는 아래 링크입니다. https://projecteuler.net/problem=72 Problem 72 - Project Euler Consider the fraction, n/d, where n and d are positive integers. If n projecteuler.net 이 문제는 분모의 범위가 정해졌을 때, 기약분수로 표현할 수 있는 분수는 총 몇개인가에 대한 문제입니다. 모든 경우를 다 따져서 기약분수로 만들어서 겹치는 것 제외하면 되겠다고 생각할 수 있지만, 이것이 생각처럼 쉽지 않습니다. \(d \leq 8\)인 분모 d를 갖는 기약분수는 다음과 같습니다. 1/8 3/8 5/8 7/8 1/7 2/7 3/7 4/7 5/7 6/7 1/6.. 2019. 12. 20.
프로젝트 오일러 간만에 들어가 본 프로젝트 오일러 사이트입니다. 영문 사이트이기 때문인지, 한국 사람들은 많이 하지를 않네요. 옛날에는 백준 아이디도 많이 보였는데, 활동을 안 하는지, 한국인 순위 리스트에서 사라진 것 같습니다. 한때 10위권 안에 들어가 있었는데, 15위로 순위가 전 하락했네요. 시간이 날 때, 가끔씩 풀어봐야겠네요. 박재현님은 1위를 굳건하게 지키시고 계시네요. 아무래도 외국에 계시는 분이시니, 영문 사이트가 편하실 수 있겠다는 생각은 했습니다. 2019. 12. 20.
[C/C++] 백준 #1009 분산처리 분산처리 문제는 무식하게 풀려면 얼마든지 풀 수 있지만, 효율적인 동작을 위해서는 정수론이 필요합니다. 문제 자체는 이해 자체가 어렵지는 않습니다.데이터가 N개 있는데, 10대의 컴퓨터로 순차적으로 데이터 1개씩을 처리할 경우, 마지막 데이터를 처리하는 컴퓨터는 어떤 것이 될 것인가가 문제입니다. 아래는 이 문제의 링크입니다.https://www.acmicpc.net/problem/1009 그런데 여기서 주어진 N이란 숫자가 두개의 숫자 a, b 가 주어졌을 때, \(a^b\)이란 것입니다.더구나 a 의 범위는 100까지이고, b란 범위는 1,000,000 까지입니다. 나머지 연산을 할 경우, 밑수를 나머지 연산을 할 수 있지만, 지수를 나머지 연산하는 것은 중학 수학 범위에서는 벗어납니다. 그래도 .. 2019. 12. 20.
[C/C++] 백준 #1007 벡터 매칭(Mathematics) 이 문제는 Gold II 문제입니다. 처음에는 동적 프로그래밍을 이용한 TSP프로그램인 줄 알고 열심히 짰다가, 예제 결과가 틀렸길래 뭐지 하고 봤었네요. 제가 문제를 풀 때만 해도 Gold I 문제였는데, 그동안 난이도가 떨어졌네요. 어쩐지 벡터 매칭이 문제 이름인데, TSP 문제일리가 없었죠. 그리고 TSP 문제였다면 조금 더 난이도 값이 주어졌을 것 같네요. TSP 문제였다면, 비트매스킹을 써서 동적 프로그래밍으로 답을 해야하죠. 그 귀찮은 프로그래밍을 다 했었는데. 최대 점들의 갯수가 20개이므로, TSP 문제였다고 해도 시간안에 대충 풀었을 듯 합니다. 문제는 2차원 공간상에 점들이 주어지면, 이 점들중 두개씩 짝을 이루어 벡터를 만들었을 때, 그 벡터들의 합이 최소가 되도록 하는 .. 2019. 12. 20.
[C/C++] 백준 #1005 ACM Craft(위상 정렬) 그래프 이론과 관련된 알고리즘은 종류도 여러가지이고, 하나의 문제에 해법도 여러가지가 존재합니다. 프림, 다익스트라, A* 로 이루어지는 알고리즘은 같은 형태이지만, 인접 노드들을 찾아서 업데이트하는 것만 다른 알고리즘이죠. 플로이드 워샬, 크르스칼 등등 사실 다 기억하고 다닐 수도 없습니다. 이번 위상정렬 알고리즘은 간단해서 그나마 외우고 다닐만한 알고리즘이라고 생각됩니다. 문제 자체는 스타크래프트와 같은 전략시뮬레이션 게임의 테크트리와 비슷합니다. 내용이야 그렇지만, 결국 위상정렬을 통하여 최종 테크트리가 이루어지는 최단 시간을 찾는 문제입니다. 문제는 아래와 같습니다. https://www.acmicpc.net/problem/1005 위상정렬도 그래프이다보니, 인접 노드들을 인접행렬을 쓸 것인지, .. 2019. 12. 19.
[C/C++] 백준 #1004 어린왕자 어린왕자 문제는 원의 중심과 반지름을 가지고, 어떤 점을 포함하고 있는지 아닌지를 판별하는 문제입니다. 처음에 이 문제를 보았을 때에는 그림만 보면, 어린왕자의 우주선이 어떤 부피를 가지고 행성사이를 빠져나가는 모습을 상상했었는데, 전혀 그런것과 무관한 문제였습니다. 그림만 보고 어렵지 않을까 생각하고 나중에서야 푼 문제네요. 백준 문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/1004 1004번: 어린 왕자입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점.. 2019. 12. 19.
728x90

티스토리툴바