Programming456 #1456 거의 소수 이번 문제는 소수를 구하는 문제입니다. 난이도는 Silver I 정도로 평가됩니다. 소수를 구하는 방법은 여러가지가 있는데, 일단은 2부터 n까지 숫자중 소수를 구하는 것이라면 \(O(n \sqrt {n} )\) 정도의 알고리즘으로 구할 수 있습니다. 에라토스테네스의 체를 이용하면, 메모리 공간이 좀 들겠지만, 가장 준수한 효율로 소수를 구할 수 있습니다. 거의 소수는 소수 \(p\)에 대해서 \(p^N\) 형태로 표현되는 수를 말합니다. 소수 자체는 거의 소수가 아니므로 실제로 주어진 범위안에서 구할 소수는 \( \sqrt {n} \) 범위입니다. 주어진 범위가 a ~ b 까지이므로 2 ~ b 까지의 거의 소수 개수를 구한 후 2 ~ a-1 까지의 거의 소수 개수를 빼주면 됩니다. 숫자의 범위가 \(1.. 2022. 8. 11. #1445 일요일 아침의 데이트 일요일 아침의 데이트는 다익스트라 알고리즘을 이용하는 문제로 Gold II 문제로 잡혀 있습니다. 아침에 산책을 하면서 야외에서 커피를 같이 마시면 즐겁겠죠? 다익스트라 알고리즘을 알고 있는 분들은 어렵지 않게 풀 수 있습니다. 일단 맵을 읽으면, 이 맵을 적절하게 변환을 해주었습니다. 예제와 같이 입력이 주어진다면, 6 6 ...... g..F.. ...... ..g... ...... ...S.g 저는 이 입력을 다음과 같은 형태로 변환을 했습니다. 쓰레기가 있는 주변을 1로 만들고, 쓰레기는 10,000의 값으로 채웠습니다. S, F는 세지 않는다고 했으니, 추후에 그 부분은 다시 0의 값으로 만들고요. 1 0 0 0 0 0 10K 1 0 0 0 0 1 0 1 0 0 0 0 1 10K 1 0 0 0 .. 2022. 8. 9. #1442 멋진 수 숫자를 2진수로 표현했을 때, 1이 연속으로 3번이상 나오던지 0이 연속으로 3번 이상 나오면 멋진 수라고 정의합니다. 주어진 숫자의 범위 안에서 멋진 수가 몇개나 되는지를 알아보는 문제입니다. 숫자의 범위가 21억정도가 되기때문에 이 문제를 풀기 위해서는 범위 안의 숫자를 모두 탐색하는 것은 시간초과가 생길것입니다. 이 문제의 정답자가 적은 이유도 아마 범위안의 숫자를 다 탐색하기 힘들어서일겁니다. 이 문제를 풀기 위해서는 첫번째로 멋진 수가 되기 위한 조건이 필요합니다. 예를 들어서 10자리의 이진수 숫자가 멋진 수가 얼마나 되는지 알아봐야겠죠. 총 갯수는 792개입니다. 전 이것을 계산하기 위해서 멋지지 않은 수가 몇개나 될 것인가를 따졌습니다. 1로 시작하는 10자리의 이진수를 생각한다면, 100.. 2022. 8. 8. #1411 비슷한 단어(String Process) 문자 대치법으로 단어를 변경할 수 있으면 비슷한 단어라고 할 때, 주어진 문자열 중에 몇쌍이 비슷한 단어가 되는지가 문제입니다. 예를 들어서 aab 와 bbc 는 비슷한 단어가 됩니다. a를 b로 바꾸고, b를 c로 바꾸면 되니까요. 그 역으로도 성립해야 하는데, b를 a로 바꾸고, c를 b로 바꾸면 됩니다. 이를 위해서 두개의 배열을 선언했습니다. 첫번째 배열은 첫번째 문자열에서 두번째 문자열로 변경될 변환테이블이고, 두번째 배열은 중복된 문자가 변환테이블에 있는지 검사하는 용도입니다. 중복된 문자가 변환테이블에 발생하면, 역이 성립하지 않으니까요. 수학 함수로 따지면 일대일 대응이 되어야 역함수가 존재하는 것과 같은 이치입니다. 문제 난이도는 Silver II로 꽤 쉽습니다. 제가 구현한 소스입니다... 2020. 3. 3. #1407 2로 몇 번 나누어질까(Mathematics) 이번 문제는 주어진 수 n를 나눌 수 있는 최대 2의 거듭제곱수를 구하고, 일정 범위의 수에 대하여 그 거듭제곱수의 합을 구해야 하는 문제입니다. 난이도는 Gold IV로 높지는 않습니다. n이란 수가 12라면 12를 나눌 수 있는 최대 2의 거듭제곱수는 4이므로 f(12) = 4가 됩니다. 또는 다음과 같이 해도 됩니다. n이란 수를 나눌 수 있는 최대 2의 거듭제곱수는 n을 2진수로 표현했을 때, 가장 오른쪽 1의 위치이다와 동일합니다. 12는 2진수로 1100이므로, 가장 오른쪽 1을 찾게되면 2진수로 100이 되고, 이 값은 4가 됩니다. 그리고 이것을 C 언어에서는 비트연산자를 이용해서 간단하게 계산할 수 있습니다. x & (-x) 를 계산하면 가장 오른쪽 비트를 얻게 됩니다. 하지만 이 문제는.. 2020. 2. 26. #1405 미친 로봇(Full Search, Back Tracking) 이번 문제는 경로를 다니면서, 지나온 길을 거치지 않을 확률을 계산하는 것입니다. 난이도 Gold V로 어렵지는 않은 문제이고요. 복잡한 알고리즘이 아니라, 단순한 백트랙킹을 구현하면 됩니다. 동서남북으로 움직일 수 있는 확률이 주어지고, 동서남북으로 확률적으로 N칸 움직였을 때, 지나온 경로를 다시 방문하지 않는 경로로 움직일 확률이 얼마일까를 계산하는 문제입니다. 예를 들어서 로봇이 NESW로 순차적으로 움직였다면, 원위치로 돌아왔으니, 지나온 경로를 지나게 됩니다. NNES 라던지, SWWS 와 같은 경로는 4칸을 움직이면서 지나온 경로를 지나지 않는 움직임이 됩니다. 문제를 풀기 위해서는 BFS, DFS 들 중 어떤 것을 사용하든 상관이 없습니다. 전 편한 DFS를 사용했습니다. 최대 움직임은 1.. 2020. 2. 23. 이전 1 ··· 38 39 40 41 42 43 44 ··· 76 다음 728x90
