[2025 1학기 알고리즘 스터디] 김규현 #1주차

1. 수 정렬하기

수 정렬하기

 

처음에 문제를 접했을 때 되게 쉽다고 느꼈다.

N번 만큼 수를 리스트에 집어넣고 sort를 활용해 리스트를 정렬했다.

 

#첫번째 시도
n = int(input())
num_list = []
for _ in range(n):
    num = int(input())
    num_list.append(num)
num_list.sort()
for i in num_list[:]:
    print(i)

 

하지만 결과는 메모리 초과ㅠㅠ

 

메모리 초과를 해결하기 위해 전지전능한 chat GPT의 도움을 받아 "카운팅 정렬" 이라는 알고리즘을 공부했다.

 

 

카운팅 정렬(Counting sort)

 

숫자의 개수를 세서 정렬하는 알고리즘이다.

숫자의 등장횟수를 기록하는 배열을 만든뒤 그 배열을 돌면서 개수를 반복출력하는 방법이다.

시간복잡도는 O(n)으로 매우빠르고 정렬하는 가장 큰 수의 크기만큼 개수 배열을 만들어야되기 때문에 숫자의 범위가 작을 때 적합하다.(ex, (2, 1,000,000)두 수를 카운팅 정렬을 사용하여 정렬하면 1,000,000개의 배열이 만들어지기 때문에 부적합함)

 

import sys
input = sys.stdin.readline
#최대 천만개의 수가 입력되므로 입력 속도 최적화를 위해 sys이용

t = int(input())
count = [0] * 10001
#10000개보다 같거나 작은 수가 입력되므로 10001개의 count배열 만든후 값을 0으로 초기화
#배열 값의 최대값 + 1 만큼 만들어줌

for _ in range(t):
    num = int(input())
    count[num] += 1
#입력되는 num에 해당하는 index에다가 + 1을 해줌

for i in range(10001):
    for _ in range(count[i]):
        print(i)
 #count 배열을 돌면서 등장횟수 만큼 반복해서 출력

 

정렬하고자 하는 숫자의 범위가 작을때 정말 유용할 것 같다.

 

 

2.카드

 

다음 카드 문제는 앞선 수정렬하기 문제와 조금 달랐다.

n의 값은 작아졌지만 들어오는 수의 범위가 엄청 넓어졌고 심지어 음수도 들어온다.

 

#첫번째 시도
import sys
input = sys.stdin.readline

num_list = []

time = int(input())
for _ in range(time):
    num = int(input())
    num_list.append(num)

num_list.sort()#리스트 정렬

current_num = num_list[0]
current_count = 1
max_num = current_num
max_count = 1


for i in range(1, len(num_list)):
    if num_list[i] == num_list[i - 1]:
        current_count += 1

    else:
        if current_count > max_count:
#개수가 같으면 작은 수를 출력하기 때문에 리스트는 작은 수 부터 비교하므로 current와 max같을때 생각할 필요 없음
            max_count = current_count
            max_num = num_list[i - 1]

        current_num = num_list[i]
        current_count = 1

if current_count > max_count:
    max_num = current_num

print(max_num)

 

정답이 되긴 했지만 조금 코드가 길기도 하고 sort를 하는 과정에 시간 복잡도가 O(N log N)이기 때문에 좀 더 효율적인 방법을 공부했다.

 

해시맵(딕셔너리)

딕셔너리는 **해시 테이블(Hash Table)**을 기반으로 동작한다.

해시 함수는 키를 특정 인덱스로 변환하여 그 인덱스에 해당하는 위치에 값을 저장하기 때문에 key에 대한 접근 시간이 평균적으로 O(1)으로 빠르다는 특징이 있다.

 

카드라는 문제는 카드의 값과 개수가 주어지기 떄문에 key, value 값으로 바꾸어 딕셔너리로 사용하기 적합했다.

import sys
input = sys.stdin.readline

time = int(input())
counter = {}#딕셔너리 생성

for _ in range(time):
    num = int(input())
    if num in counter:
        counter[num] += 1
    
    else:
        counter[num] = 1

max_count = max(counter.values())
result = min(key for key, value in counter.items() if value == max_count)

print(result)

 

시간 복잡도도 엄청 빨라지고 코드도 엄청 단순해졌다. (시간복잡도 O(n))

key, value 값을 사용하는 문제에서 애용해야겠다.

 

 

3.좌표 압축

 

 

#첫번째 시도
import sys
input = sys.stdin.readline

time = int(input())
n_list = list(map(int, input().split()))
s_list = set(n_list)
r_list = []

for num in n_list:
    count = 0
    for i in s_list:
        if num > i:
            count += 1
        else:
            pass
    
    r_list.append(count)
    count = 0

print(" ".join(map(str, r_list)))

 

최대 N이 1,000,000개가 들어오는데 2중 for 문을 도는 과정에서 시간초과가 난것 같았다.

이 문제는 입력된 수가 몇번째로 큰 수인지로 생각해서 그에 해당하는 index값을 반환하기로 했다.

 

import sys
input = sys.stdin.readline

time = int(input())
arr = list(map(int, input().split()))

sorted_arr = sorted(set(arr))

rank_map = {value: idx for idx, value in enumerate(sorted_arr)

result = [rank_map[x] for x in arr]
print(" ".join(map(str, result)))

 

앞선 문제와 비슷하게 딕셔너리를 활용하여 작성했는데 enumerate()라는 것을 사용했다.

 

enumerate()는 파이썬에서 내장함수로서 순서가 있는 자료형을 입력값으로 받았을 때 인덱스와 값을 포함하여 리턴한다.

 

enumerate(순서가 있는 객체, start=0)
fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi', 'apple', 'banana']

따라서 문제의 코드에서 set과 sorted로 정렬되어있는 sorted_arr에 enumerate를 사용하면 (0, '가장 작은 값') .... 으로 나타난다.

 

 

마치며 ...

평소에 정려하는 문제를 잘 풀어보지 못했는데 이런 기회에 풀어보고 공부하면서 성장해가는 즐거움을 느꼈다. ^0^