본문 바로가기
반응형

acmicpc43

백준 #1032 명령 프롬프트 이번 문제는 문자열 처리하는 프로그램을 작성하는 것입니다. 문자열 처리는 성격상 배열, 포인터, C 문자열의 특성 등을 잘 알지 못하면 어려울 수 있습니다. 백준 사이트의 문제는 아래의 링크에 있습니다. https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 알파벳과 "." 그리고 "?"로만 이루어져 있다. www.acmicpc.net 문제는 주어진 여러개의 문자열을 보고 공통된 문자들은 그대로 두고 공통되지 않은, 즉, 그 위치에 올 수 있는 문자들이 여러가지인 경우 ?을.. 2019. 12. 25.
백준 #1026 보물 이번 문제는 문제가 의도하는 뜻만 잘 이해하면 풀 수 있는 문제입니다. 그래서인지 정답자가 상당히 높습니다. 오늘 날짜의 정답자가 8,888명, 정답률 61.5%입니다. 숫자가 8이 연속 4개라서 캡처를 해두었습니다. 문제는 두개의 수열 A[*], B[*]이 주어졌을 때, 적절하게 A[*] 수열을 재배치 해서 다음의 식을 최소화하도록 하는 것입니다. \[ \sum_{k} A[k] \cdot B[k] \] 문제에서는 B[*] 배열은 재배열하면 안된다고 합니다. (함정입니다.) 문제는 아래 링크에 있습니다. https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로.. 2019. 12. 25.
#1017 소수쌍(네트워크 플로우) 처음 이 문제를 접했을 때에는 '혹시 쌍둥이 소수' 문제일까 하고 봤었네요. 소수쌍이 아니라 합이 소수가 되는 숫자들의 합 이야기입니다. 짝수인 N개가 주어지면, 합이 소수가 되는 쌍으로 모두 묶을 수 있다면, 첫번째 수와 묶일 수 있는 수들의 리스트를 내는 문제입니다. 난이도는 Platinum III이지만, 난이도보다는 쉬운 문제입니다. 물론 네트워크 플로우 알고리즘을 알고 있을 때에 한합니다. DFS 알고리즘으로도 풀 수 있지만, 그렇게 하면 시간초과가 납니다. 아래는 해당 문제의 링크입니다. https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10.. 2019. 12. 24.
백준 #1011 Fly me to the Alpha Centauri 이번 문제는 알파 센타우리까지 우주선을 타고 갈 때, 워프기계는 최소 몇번 작동으로 갈 수 있는지 구하는 문제입니다. 우주적인 문제이지만, 사실상 거리의 절반까지 가는데, 1+2+3+...+k 의 값이 거리의 절반보다 작으면서 가장 큰 수가 되는 것을 구하는 문제입니다. 알파 센타우리는 지구로부터 4.37 광년정도 떨어져 있습니다. 우주선이 빛의 속도로 가도 4.37년이 걸리는 곳입니다. 태양과는 주계열성으로는 가장 가까운 별이라서 지구에서 관측할 때 아주 밝게 빛나는 별입니다만, 아쉽게도 우리나라가 있는 위도상에서는 관측이 힘듭니다. 영화에서도 새로운 지구로 자주 쓰이는 별입니다. 영화 패신저스에서도 알파 센타우리가 쓰였죠. 가는데 백여년이 걸려서 사람을 동면시켜서 갑니다. (사실상 그곳까지 가는 기술.. 2019. 12. 22.
백준 #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.
728x90

티스토리툴바