알루 코딩

이 문제는 비교적 간단하지만, 간단하게 풀면 시간초과에 걸리기 때문에 조금은 생각을 해야 하는 문제입니다. 문제에서는 정렬된 정수 배열 nums가 주어집니다. 배열의 각 요소 'i' 에 대해, 해당 요소와 배열 내 다른 모든 요소 'j' 들과의 절대 차이인 |nums[i] - nums[j]| 의 합을 구하는 것이 목표입니다. 이 문제에서 각 원소를 순회하면서 절댓값 계산을 하면 nums의 길이가 10**5 까지 있기 때문에 시간초과가 날 수 밖에 없습니다. 이 문제를 효율적으로 해결하기 위해서는 누적합(prefix)와 역누적합(suffix)를 사용해야 합니다. 누적합(prefix sum)과 역누적합(suffix sum)의 사용은 꼭 알아야 하는 알고리즘 중에 하나입니다. prefix sum에 대해 잠시 ..

리트코드에서의 1번문제입니다. 문제를 설명해보자면, 입력값으로 nums 라는 숫자배열이 주어집니다. 그리고 target값도 입력값으로 주어지는데요, nums배열에서 두 숫자를 더해 target을 만들 수 있다면, 해당 두 숫자의 인덱스 값을 배열 형태로 출력하는 문제입니다. 문제 자체는 비교적 간단한 문제입니다만, 이 문제를 어떻게 효율적으로 풀어야 할지는 고민해봐야 할 부분입니다. 해당 문제를 직관적으로 풀자면 for문을 두 번 돌면 됩니다. 대략적인 코드는 아래와 같겠죠. for i in range(len(nums)): for j in range(i+1,len(nums)): if (nums[i] + nums[j]) == target: return [i,j] 하지만, 위와 같이 푼다면, 이미 시간복잡도..

정렬(Sorting)이란 ? : 데이터를 측정한 기준에 따라서 순서대로 나열하는 것으로, 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘은 굉장히 다양한데, 이 중에서 많이 사용하는 정렬은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등이 있다. 정렬 알고리즘을 잘 공부하면, 알고리즘의 효율을 높일 수 있다. 또한, 코딩 테스트에서의 정렬 알고리즘 문제는 어느 정도 정해진 답이 있어서, 외워서 잘 풀어낼 수 있는 문제라고도 할 수 있다. 오름차순을 기준으로 각 정렬을 살펴보자. 선택 정렬(Selection Sort) : 데이터가 무작위로 있을 때, 그 중 가장 작은 값을 선택해 맨 앞에 있는 값과 바꾸고, 그 다음 작은 값을 선택해 앞에서 두 번째 값과 바꾸는 과정을 계속 ..

그리디(Greedy) 알고리즘 : 욕심쟁이 알고리즘이라고도 하는 탐욕 알고리즘은 단순하지만 강력한 문제 해결법이다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 가장 좋은 것을 선택하는 알고리즘으로, 문제에서 '가장 큰 순서대로' 혹은 '가장 작은 순서대로' 와 같은 기준을 문제에서 알게 모르게 제공해준다. 정렬 알고리즘을 사용했을 때, 효과적으로 풀 수 있어, 보통 정렬 알고리즘과 짝을 이루어 출제되곤 한다. 대표적인 그리디 알고리즘 예제 - 1) 동전 거스름돈 문제 import sys input = sys.s..

코딩 테스트 문제를 풀 때, 시간과 메모리를 측정하는 방법을 알아보자! 파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다. 문제를 풀면서, 자신이 제대로 알고리즘을 작성하고 있는지 알아야 하기 때문이다. 몇몇 기업은 코딩 테스트를 볼 때, 제출 횟수를 제한 하기 때문에 시간과 메모리를 중간에 체크하는 법을 알면 문제를 옳은 알고리즘으로 풀었는지 미리 알 수 있을 것이다. 아래는 특정한 프로그램의 수행 시간을 측정하는 소스코이다. import time start_time = time.time() # 측정 시작 # 프로그램 소스코드 ~~~~ end_time = time.time() # 측정 종료 print("time : ", end_time - start_time) # 수행시간 출력 예를 들..

정답률이 낮은 이유는 아마 제출 수가 적은 것도 그렇지만, 예외처리 때문일 것이다. 나도 한 2번 틀리고 반례를 발견했으니 말이다. 우선, 시간제한도 2초로 넉넉한 편이어서 for문이나 while문 사용에 거부감이 없었다. 이번 코드리뷰는 내가 제출했었던 코드들을 순차적으로 살펴보자. 맨 처음 제출해서 틀렸던 코드는 아래와 같다. import sys input = sys.stdin.readline n = int(input()) vote_list = [] count = 0 for i in range(n): vote_list.append(int(input())) dasom = vote_list[0] not_dasom = sorted(vote_list[1:], reverse=True) print(not_das..

맨 처음에, 솔직히 문제가 잘 이해가 가지 않았다. 일단 예제 입력을 그대로 문제에 적용해보면, 입력으로 주어진 배열 A의 원소 2 3 1 은 아래와 같이 표현할 수 있다. B[P[0]] = A[0]->B[1] = 2 B[P[1]] = A[1]->B[2] = 3 B[P[2]] = A[2]->B[0] = 1 다시한번, 문제를 잘 읽어보면, 여기서 B배열은 A배열의 비내림차순 배열이라는 것을 알 수 있었다. 우리는 A배열로부터 B배열을 만들었는데, 그럼 자연스럽게 P배열은 A배열의 원소 크기 순이라는 것을 알 수 있다. 여기서 만약, 동일한 크기의 원소라면, 앞서 있는 것을 먼저 출력하면 된다. 예를 들어 A 배열이 1 3 2 2 라고 하면 P배열은 0 3 1 2 순으로 출력 될 것이다. 작성한 코드는 아래..