[2025 1학기 알고리즘 스터디] 이서영 #1주차

 

* 파이썬으로 풀었습니다.

1. 10989번: 수 정렬하기3
2. 11652번: 카드
3. 18870번: 좌표압축

 

1. 10989번: 수 정렬하기3

문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

정답률(23.935%)을 보자마자 든 생각은

나는 무조건 틀리겠다.

바로 sort를 생각한 저를 의심한 후 정렬 알고리즘에 대해 공부해줍니다.

 

 

 

 

정렬 알고리즘

: n개의 숫자가 입력으로 주어졌을 때, 기준에 맞게 정렬하는 알고리즘

 

 

1. 선택 정렬

: 현재 위치에 들어갈 값을 찾아 정렬 ( 시간복잡도 : O(n^2) )

 

배열 전체에서 최소값 탐색 후 최소값을 배열 현재 위치와 교체해서 남은 배열에 대해 다시 최소값을 탐색합니다.

 

2. 삽입 정렬

: 현재 위치에서 그 이하 배열들을 비교하여 자신이 들어갈 위치를 찾아 그 위치에 삽입 ( 시간복잡도 : O(n^2) )

k번째 원소를 1부터 k-1까지 비교해 적절한 위치에 끼워넣고 뒤의 자료는 뒤로 밀어냅니다.

3. 버블정렬

: 매번 연속된 2개 인덱스를 비교한 후, 값을 뒤로 넘김 ( 시간복잡도 : O(n^2) )

 

4. 병합정렬

: 하나의 배열을 입력받고, 배열의 길이가 1이 될 때까지 두 개의 배열로 분할한 뒤, 합치면서 정렬

( 시간복잡도 : O(nlogn) )

5. 퀵정렬

: 병합정렬과 비슷하지만, pivot point를 기준으로 수가 더 작으면 왼쪽으로, 크다면 오른쪽으로 정렬(오름차순)

( 시간복잡도 : Best: O(nlogn) / Worst: O(n^2) )

 

배운 정렬을 바탕으로 시간복잡도가 제일 괜찮아보이는 퀵정렬로 해봤습니다.

import sys
input = sys.stdin.readline

def quick(array):
    if len(array) <= 1:
        return array
    
    pivot_index = len(array)//2 
    pivot_value = array[pivot_index]
    #피벗을 최대/최소로 잘못 잡으면 최악의 결과를 초래하니 방지목적으로 배열의 중간으로
    
    front_arr, pivot_arr, back_arr = [],[],[]

    for value in array:
        if value < pivot_value:
            front_arr.append(value)
        elif value > pivot_value:
            back_arr.append(value)
        else:
            pivot_arr.append(value)
    
    return quick(front_arr) + pivot_arr + quick(back_arr)

N=int(input())
numlist = []

for i in range(N):
    num = int(input())
    numlist.append(num)

numlist = quick(numlist)

for i in numlist:
    print(i)

안돼!

 

메모리 초과가 안 뜰만한 정렬을 찾던 중 계수 정렬에 대해 알게되었습니다.

 

 

6. 계수정렬

: 숫자의 개수를 세어 정렬하는 알고리즘

시간복잡도: O(n+k) k:최댓값

 

퀵 정렬보다 빠르게 동작할 수 있지만

정수형 데이터만 가능, 데이터의 최댓값이 너무 크면 비효율

 

문제는 정수입력이고 최댓값은 10000이니 계수정렬로 짜면 효율적

 

 

각 숫자의 등장 횟수를 기록할 배열 count[] 생성 후 각 숫자가 몇 번 등장했는지 저장

→ 개수만큼 출력하면 정렬

import sys
input = sys.stdin.readline

def counting(array):
    max_value = max(array)
    count = [0] * (max_value + 1)

    for i in array:
        count[i] += 1 #숫자 개수 세기

    sorted_array = []
    for i in range(len(count)):
        sorted_array.extend([i]*count[i]) #등장 횟수만큼 숫자 추가

    return sorted_array

N=int(input())
numlist = []

for i in range(N):
    num = int(input())
    numlist.append(num)

numlist = counting(numlist)

for i in numlist:
    print(i)

또모리초과

 

해결책

• 입력 배열 numlist를 아예 저장하지 않아서 메모리를 절약
• count[] 배열 크기는 k의 최대가 10000이니 10001로 고정

import sys
input = sys.stdin.readline

N = int(input())

count = [0] * 10001

for _ in range(N):
    num = int(input())
    count[num]+=1

for i in range(1,10001):
    if count[i] != 0:
        for _ in range(count[i]):
            print(i)

이예엥 ^0^

 

 

2. 11652번: 카드

문제 :

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -2^62보다 크거나 같고, 2^62보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

 

수정렬3으로 경험을 했습니다. 30퍼센트의 정답률과 2^62라는 어마어마한 숫자로 어떻게든 틀리겠구나를 예상해줍니다.

???

 

 

문제를 보고 처음에 든 생각은 입력된 값들을 특정 리스트에 정리하고, 제일 많은 값을 출력하자 였습니다.

그렇다고 리스트로 접근하는 순간

arr = [0] * (2**63) #양수,음수 포함

 

메모리 초과

 

 

 

리스트와 달리 입력된 숫자만 저장 가능한 딕셔너리를 이용해줍니다.

count_dict = {}
count_dict[숫자] = 개수

 

import sys
input = sys.stdin.readline

N = int(input())
count_dict = {}

for _ in range(N):
    card = int(input())
    if card in count_dict:
        count_dict[card] += 1
    else:
        count_dict[card] = 1

max_count = max(count_dict.values()) 
max_dict={}

for k,v in count_dict.items():
    if v == max_count:
        max_dict[k] = v

result = sorted(max_dict)
print(result[0])

 

count_dict key : 입력받은 수

count_dict value : 해당 수의 개수

 

max_count = count_dict의 value 중 제일 큰 수

max_dict = count_dict의 value가 젤 큰 것끼리 모아둔 것

 

max_dict를 정렬해서 여러 개일 때 젤 작은 것을 출력했습니다.

이예엥 ^0^

 

 

3. 18870번: 좌표 압축

문제 :

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

..?

문제가 이해 안 될 땐 예제를 잠깐 봐줍니다.

 

 

예제 입력 1

5
2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

 

X1일 때는 2보다 작은 수가 -10, -9 로 두 개 있으니 2를 출력 ..

본인 보다 작은 수의 개수를 출력하라는 뜻은 숫자의 순위를 출력하라는 뜻과 같으므로 정렬을 이용합니다!

 

첫 번째 시도

import sys
input = sys.stdin.readline

N = int(input())
xSet = list(map(int,input().split()))

xSetSort = sorted(xSet)

for i in xSet:
    print(xSetSort.index(i), end=' ')

 

두 번째 예제가 이상

index 때문.

xSetSort = [999, 999, 999, 1000, 1000, 1000]으로 되어서 중복을 제거해주어야합니다!

 

두 번째 시도

import sys
input = sys.stdin.readline

N = int(input())
xSet = list(map(int,input().split()))

xSetSort = sorted(set(xSet))

for i in xSet:
    print(xSetSort.index(i), end=' ')

 

집합을 이용하여 중복을 제거해주고 정렬하였습니다.

하지만 제일 중요한 건 코딩실력 찌끄래기인 저를 항상 의심하는 자세.

 

index의 무서움을 알게되었습니다.

 

 

index

• 리스트에서 특정 값의 위치를 찾는 함수로 O(n)의 시간이 걸립니다.
• 최악의 경우 O(n^2)가 되어 시간 초과

 

해결책:

enumerate

→ 파이썬에서 순서가 있는 자료형을 입력 받았을 때 인덱스와 값을 포함하여 리턴

 

enumerate를 이용해 딕셔너리를 생성합니다

근데 왜? 

 

 

 

해시 테이블

• 키(Key)에 데이터(Value)를 저장하는 데이터 구조
• Key를 통해 데이터를 바로 받아올 수 있음 → 속도가 엄청 빨라짐
• 파이썬의 딕셔너리가 해쉬테이블의 예

인덱스는 리스트에서 값을 처음부터 하나씩 찾아야합니다. 하지만 이걸 n번 반복하면 시간복잡도는 O(n^2)이 됩니다.

개망함!

 

하지만 딕셔너리는 해시테이블을 사용하여 바로바로 접근합니다. 그러니 딕셔너리를 만들어주도록 합니당

import sys
input = sys.stdin.readline

N = int(input())
xSet = list(map(int,input().split()))

xSetSort = sorted(set(xSet))
xDict = {}

for index,value in enumerate(xSetSort):
    xDict[value] = index

for i in xSet:
    print(xDict[i], end=' ')

이예엥^0^

 

문제를 풀며 알게 된 것은 그동안 문제를 풀며 시간복잡도의 중요성을 몰랐다는 것입니다 (알고리즘문제 풀면서..)

• 시간복잡도의 중요성
• 정렬 알고리즘
• 딕셔너리
• 해시테이블
• 나를 의심하기