본문 바로가기
반응형

Programming/BOJ252

백준 #1009 분산처리 분산처리 문제는 무식하게 풀려면 얼마든지 풀 수 있지만, 효율적인 동작을 위해서는 정수론이 필요합니다. 문제 자체는 이해 자체가 어렵지는 않습니다. 데이터가 N개 있는데, 10대의 컴퓨터로 순차적으로 데이터 1개씩을 처리할 경우, 마지막 데이터를 처리하는 컴퓨터는 어떤 것이 될 것인가가 문제입니다. 아래는 이 문제의 링크입니다. https://www.acmicpc.net/problem/1009 그런데 여기서 주어진 N이란 숫자가 두개의 숫자 a, b 가 주어졌을 때, \(a^b\)이란 것입니다. 더구나 a 의 범위는 100까지이고, b란 범위는 1,000,000 까지입니다. 나머지 연산을 할 경우, 밑수를 나머지 연산을 할 수 있지만, 지수를 나머지 연산하는 것은 중학 수학 범위에서는 벗어납니다. 그래도.. 2019. 12. 20.
#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.
백준 #1004 어린왕자 어린왕자 문제는 원의 중심과 반지름을 가지고, 어떤 점을 포함하고 있는지 아닌지를 판별하는 문제입니다. 처음에 이 문제를 보았을 때에는 그림만 보면, 어린왕자의 우주선이 어떤 부피를 가지고 행성사이를 빠져나가는 모습을 상상했었는데, 전혀 그런것과 무관한 문제였습니다. 그림만 보고 어렵지 않을까 생각하고 나중에서야 푼 문제네요. 백준 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중.. 2019. 12. 19.
백준 #1003 피보나치 함수 이 문제는 6개월전에 백준 문제들을 본격적으로 풀면서 풀었던 문제입니다. 난이도는 Silver III 문제입니다. 피보나치 함수는 아주 간단한 구조를 가지고 있는데, 다양한 성질 등이 발견되면서 자주 거론되는 수열입니다. C/C++ 언어를 배울 때에는 재귀함수(자기호출함수)의 개념을 익히는 데에 하노이 타워와 자주 거론됩니다. 이 문제는 정답률이 높은 편은 아닙니다. 아마 초기문제여서 그럴 수도 있겠네요. https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 피보나치 수열은 초기화 값에 따라서 수열이 조금씩 틀려지는데요. fib(0) = 0, f.. 2019. 12. 16.
[C/C++] 백준 #1002 터렛(수학) 이 문제는 백준 사이트에 가입하고 처음 풀었던 것 같습니다. 지식인에서 백준 알고리즘 문제를 물어보았는데, 답변을 달기 위해서 백준 알고리즘에 가입했고, 그 후 몇문제를 풀었던 기억이 납니다. 당시에는 연세대를 다닐때였으니까, 연세대로 등록을 했었는데, 벌써 몇년 전 일이네요. 꽤 오래전부터 프로젝트 오일러 사이트에 익숙했었던 탓에, 백준과 같이 실제 채점서버가 있는 사이트는 거의 안 했었는데, 최근에 다시 시작했습니다. 이 문제의 정답 비율은 19%로 상당히 낮은데, 사실 문제의 난이도보다는 문제의 설명이 알아듣기 힘들어서인 듯 하다. 문제를 푼 사람들이 설정한 문제의 난이도는 Silver IV입니다. . 문제의 링크입니다. https://www.acmicpc.net/problem/1002 1002번.. 2019. 12. 16.
728x90

티스토리툴바