안녕하세요 지난주부터 참여하고 있는 구름레벨의 알고리즘 먼데이 챌린지 1주차 해설을 해보려고 합니다. 1주차 해설이 올라왔고 복습문제가 올라왔으므로.. 풀이를 진행해보겠습니다.
해당 게시물의 모든 출처는 구름 레벨의 알고리즘 먼데이 챌린지에 있습니다.
1번 문제
문제설명:
1번부터 n개의 섬이 존재한다. 또한 i번 섬과 i+1번 섬은 단방향의 다리로 연결되어있다(i는 1부터 n). 최종적으로 n번섬은 1번섬으로 다시 돌아오게 연결되어있다.
이때 각 섬사이에 연결된 다리의개수가 주어지고, 섬사이를 이동할때 다른 다리를 이용했다면 다른 경로로 본다면, 총 가능한 경로의 수는 몇개인가?
해설:
보통 섬과 섬사이 다리가 있는 문제들을 풀때는 항상 복잡한 알고리즘을 사용했기에 긴장했으나... 1주차 문제답게 알고보니 쉬운 문제였다.
다른 다리를 사용하면 다른 경로로 치므로... 모든 경우를 독립시행으로 각 다리의 개수를 곱해주기만 하면 될것이다.
n = int(input())
l1 = list(map(int,input().split()))
total = 1
for k in l1:
total = total*k
print(total)인풋을 받고 다 곱해줘서 출력해주면 정답!
2번 문제
문제설명:
주인공의 이름과 어떤 수업에 있는 수강생들의 이름이 주어질때, 자신과 비슷한 이름을 가진 사람이 몇명있는지를 알아내면 된다. 이때, 비슷한 이름이라는 것은 어떤 사람의 이름에 자신의 이름이 포함되어있는지로 한다.
해설:
파이썬의 문자열처리는 신이다... 그냥 하면 된다. in으로 선형 탐색으로 해결해버리면 된다.
n, a = input().split()
n = int(n)
total = 0
for _ in range(n):
b = input()
if a in b:
total = total + 1
print(total)3번 문제
맨해튼 거리 문제가 나왔다. 일전에 SUAPC대회에서 현대오토에버 측에서 냈던 문제랑 비슷한거같은데..
문제설명:
4개의 수직선상 좌표가 주어지고 맨해튼 거리 공식에 따른 최대값이 얼마일지를 찾아라. 맨해튼 거리는 |x1-x2|+ |x3-x4|와 같은꼴로 표현한다.
해설:
이론상 수학적으로 어떤 경우가 최대의 맨해튼거리일지를 찾아내야한다. 모든 경우의 수를 구할수도 있지만 사실은 최적의 해는 이미 구해져있다.
4개의 좌표를 sort시킨후, 맨앞과 맨뒤의 값의 차이, 그리고 그다음쌍의 차이가 바로 최적의 해가 된다.
l1 = list(map(int,input().split()))
l1.sort()
total = 0
total = total + abs(l1[0]-l1[-1]) + abs(l1[1]-l1[2])
print(total)수학적으로 증명이 가능!
4번문제
매우 유명하고 전형적인 소수판별 문제이다. 문제가 약간 어렵게쓰여있어서 이해하는데 시간이 걸렸다.
문제설명:
간단히 말하자면 주어진 숫자 배열의 index값이 소수일때 해당 숫자들의 총합을 구하면된다.(1<=n<=100,000)
해설:
소수판단의 경우에는 너무나도 유명하고 관련 알고리즘들이 이미 개발이 되어있습니다. 그렇다면 문제의 데이터의 개수와 시간복잡도를 따져서 가장 간단하면서도 기준을 통과할만한 알고리즘을 선정하는게 중요하겠죠.
구름기준 레벨 1문제이기도하고 앞의 세문제가 너무 쉽게나와서 4번문제를 풀면서도 뇌를빼고(?) 풀려고 시도를 했습니다. 즉 시간복잡도는 무슨 그냥 소수의 정의에 입각하여 약수의 개수를 구하는방식으로 완전탐색을 돌렸죠.
결과는! 틀렸습니다였습니다. 문제는 구름레벨 ide에서는 시간초과로 틀린건지 뭔지 알려주질 않는다는거였습니다(제가 잘못알고있는걸까요)? 아무튼 디버깅을 제가 해야했기에 문제를 다시 읽어보니 그제서야 읽히는 n의 범위.... 데이터의 개수가 10만개... 당연히 O(n^2)의 완전 탐색으로는 풀릴일이 없겠죠.
그렇다면 저희가 사용할수 있는 무기는 두개가 있습니다.
- 제곱근까지의 판단
이 판별법은 약수의 성질에서 기초합니다. 모든 약수는 좌우 대칭을 이룹니다. 따라서 좌우의 중간인 가운데까지 판단을 한다는거죠(이 가운데는 나누기2가 아닌 제곱근이 되야합니다). 이렇게 된다면 제곱근까지만 판별을 하면 되므로 하나의 소수판별에 O(n^1/2)이 소모됩니다. 따라서 최종적으로는 O(n^3/2)가 되겠네요. 해당문제에서는 이정도의 시간복잡도로만 제출해도 correct를 받을수있습니다.
- 에라토스테네스의 채
너무나도 유명한 알고리즘.. 수들을 나열하고 채에 걸러내듯이 지워나가는 방법이다.
1. 모든 수를 나열하고 소수 = true라고 flag값을 부여한다
2. 숫자 2부터 쭉 순회를 하면서 소수를 만나면 해당 수의 배수들을 모두 지운다(flag값을 false로 부여하는것으로 해결)
3. 더이상 반복할수없을때까지 위의 과정을 반복한다.위의 방법은 무려 시간복잡도가 O(NloglogN).... 굉장한 속도를 자랑한다. 따라서 정말로 큰 범위의 수의 소수를 판단하려면 에라토스테네스의 채를 무조건 사용해야한다.
나는 완전 기본 소수판단 코드에서 범위만 제곱근으로 제한하여 풀었다.
n = int(input())
l1 = list(map(int,input().split()))
def prime_number(x):
for i in range(2, int(pow(x,0.5))+1):
if x%i==0:
return False
return True
total = 0
for k in range(1,n):
if prime_number(k+1):
total = total+l1[k]
print(total)후기
난이도는 1주차답게 굉장히쉬웠다(소수에서 일격을 맞았지만). 그러나 ide가 너무나도 불친절하고(특히 파이썬은 if else범위를 지멋대로 지정해버려서 미쳐버리겠다) 심지어 스탬프 미지급 이슈도 있어서 구름레벨에 아쉬움을 표한다. 언능 개선을 시켜서 이번기회에 좋은 플랫폼으로 거듭났으면 좋겠다.
