코린이 첫 알고리즘 문제 도전
코딩도장이란 사이트에서 가져온 문제입니다.
내 생애 처음으로 푼 알고리즘 문제입니다.~
문제.
n개의 정수를 가진 배열이 있다. 이 배열은 양의정수, 음의 정수를 모두 가지고 있다.
이제 당신은 이 배열을 좀 특별한 방법으로 정렬해야 한다.
정렬이 되고 난 후, 음의 정수는 앞쪽에 양의정수는 뒷쪽에 있어야 한다.
또한 양의정수와 음의정수의 순서에는 변함이 없어야 한다.
예시 -1 1 5 -8 3 → -1 -8 1 5 3
파이썬 기준
챗 GPT한테 물어보니 이렇게 푸네요
챗GPT 풀이
def special_sort(arr):
negative = [x for x in arr if x < 0]
positive = [x for x in arr if x >= 0]
return negative + positive
저는 파이썬의 문법에 대해서는 1도 모르지만 대충 뭔 말인지는 알겠습니다.
수학에서 집합의 조건 제시법이란 굉장히 비슷하네요.
저는 수학문제 풀듯이 해결했습니다.
방법1
def move_positives_right(arr):
length = len(arr)
i = 0
count = 0
while count < length:
if arr[i] >= 0:
arr.append(arr.pop(i))
else:
i += 1
count += 1
return arr
간단하게 저런 문법 모르겠고라는 마음가짐으로 푼 건데 아이디어는 제가 제시했고
문법은 기특한 챗GPT님께서 제시해줬습니다.
저의 지시사항은
양수를 볼 때마다 맨 오른쪽으로 보내라였습니다.
그런데, 한가지 문제점이 생기죠. 처음 풀때는 사실 너무 쉽다 생각했는데 간과한 점이 있었습니다.
바로 양수를 맨 오른쪽으로 보내면 오른쪽에 양수에 쌓여있기에 계속해서 무한히 이 과정을 반복합니다.
아하~
그래서 조금 궁리하다 제 아이디어를 어떻게든 관철시키고자 한 가지 조건을 덧붙입니다.
흠,,
그냥 정수의 갯수만큼만 탐색하면 되지 않나?
조금 생각해보니 될 것 같아서
만든 소스코드가 저것입니다.
방법2
def rearrange_negatives_method1(arr):
last_negative_index = -1
for i in range(len(arr)):
if arr[i] < 0:
last_negative_index += 1
arr.insert(last_negative_index, arr.pop(i))
return arr
다음 방법은 방법1과 발상은 비슷합니다.
초기에 문제를 보고 여러가지 아이디어를 냈는데
심플하게 양수를 오른쪽으로 제끼는 게 방법 1이고
음수를 왼쪽으로 제끼는 게 방법 2입니다.
처음에는 음수를 보이면 왼쪽으로 보내면 된다고 생각했는데 역시 예기치 못한 문제가 발생합니다.
초기에 GPT가 준 해답에서 '음수가 발견되면 가장 왼쪽에 있는 양수와 위치를 교환한다'라는 논지의 코드를 짰는데
그러면 음수는 왼쪽으로 순서가 그대로 정렬되지만
양수는 위치가 바뀌죠
예를 들어,
-1 1 5 -3 같은 경우 -3을 탐지하고 1과 위치를 교환할 겁니다.
그러면 이는
-1 -3 5 1이 되버립니다.
그래서, GPT한테 왜 그따구로 코드를 짰는지 고민해봤는데 찾아보니 교환하는 것이
알고리즘에서는 가장 적은 노동, 가장 적은 에너지를 사용하는(이런 표현을 해도 되는지 모르겠지만) 행위이기 때문임을 깨닫습니다.
그래서 또 돌파구를 찾았는데
교환하려니 순서가 바뀌고
다른 조건을 넣자니 코드가 길어지고 탐색의 과정이 길어집니다.
그래서, 어떻게든 음수를 왼쪽으로 보내버린다라는 아이디어를 살린 게 음수를 추출하고 삽입하는 형식의 위 방법인데
제가 생각해도 별롭니다.
알고리즘 문제를 처음 풀어봤는데 수학이랑은 쫌 다르다고 느꼈습니다. 확실히
그렇지만 또 이것만의 매력이 있어서 푸는 재미를 쫌 느꼈는데
처음 아이디어를 관철시키려고 이것저것 궁리하는 재미랑
효율적인 풀이가 뭐가 있을까 아이디어를 내는 재미가 있어서 이 점은 수학 문제 풀이랑은 쫌 비슷하기 했습니다.
코딩이란 것이 결국 컴퓨터의 언어로 표현해야 하기 때문에 '내가 이러면 되는 거 아니야?'라고 생각한 것이
컴퓨터한테는 어려운 문제일수도 있고 나한테 어려운 행위가 컴퓨터한테는 쉬울 수도 있단 것을 깨달았습니다.
앞으로 알고리즘 문제를 푸는 것도 꽤 재밌을 것 같네요.