문제 설명

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

제한사항

• 5 ≤ players의 길이 ≤ 50,000
  • players[i]는 i번째 선수의 이름을 의미합니다.
  • players의 원소들은 알파벳 소문자로만 이루어져 있습니다.
  • players에는 중복된 값이 들어가 있지 않습니다.
  • 3 ≤ players[i]의 길이 ≤ 10
• 2 ≤ callings의 길이 ≤ 1,000,000
  • callings는 players의 원소들로만 이루어져 있습니다.
  • 경주 진행중 1등인 선수의 이름은 불리지 않습니다.

아이디어

리스트의 문자열과 해당 인덱스를 딕셔너리로 선언해서 이름과 그 순위를 나타낸다. 

이때 enumerate()를 사용하면 편리하다.

이후 calling에서 이름을 부르면 앞순위 사람과 스왑을 진행해주면 된다.

딕셔너리는 in의 기능이 O(1)이기에 시간복잡도도 좋게 구현할 수 있다.

코드

def solution(players, callings):
    dic={player: idx for idx, player in enumerate(players)}
    
    for name in callings:
        index=dic[name]
        players[index], players[index-1]=players[index-1], players[index]
        dic[players[index]], dic[players[index-1]]=index,index-1
    
    return players

시간복잡도 O(N)

문제 설명

사진들을 보며 추억에 젖어 있던 루는 사진별로 추억 점수를 매길려고 합니다. 사진 속에 나오는 인물의 그리움 점수를 모두 합산한 값이 해당 사진의 추억 점수가 됩니다. 예를 들어 사진 속 인물의 이름이 ["may", "kein", "kain"]이고 각 인물의 그리움 점수가 [5점, 10점, 1점]일 때 해당 사진의 추억 점수는 16(5 + 10 + 1)점이 됩니다. 다른 사진 속 인물의 이름이 ["kali", "mari", "don", "tony"]이고 ["kali", "mari", "don"]의 그리움 점수가 각각 [11점, 1점, 55점]]이고, "tony"는 그리움 점수가 없을 때, 이 사진의 추억 점수는 3명의 그리움 점수를 합한 67(11 + 1 + 55)점입니다.

그리워하는 사람의 이름을 담은 문자열 배열 name, 각 사람별 그리움 점수를 담은 정수 배열 yearning, 각 사진에 찍힌 인물의 이름을 담은 이차원 문자열 배열 photo가 매개변수로 주어질 때, 사진들의 추억 점수를 photo에 주어진 순서대로 배열에 담아 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ name의 길이 = yearning의 길이≤ 100
  • 3 ≤ name의 원소의 길이 ≤ 7
  • name의 원소들은 알파벳 소문자로만 이루어져 있습니다.
  • name에는 중복된 값이 들어가지 않습니다.
  • 1 ≤ yearning[i] ≤ 100
  • yearning[i]는 i번째 사람의 그리움 점수입니다.
• 3 ≤ photo의 길이 ≤ 100
  • 1 ≤ photo[i]의 길이 ≤ 100
  • 3 ≤ photo[i]의 원소(문자열)의 길이 ≤ 7
  • photo[i]의 원소들은 알파벳 소문자로만 이루어져 있습니다.
  • photo[i]의 원소들은 중복된 값이 들어가지 않습니다.

아이디어

name과 yearning을 딕셔너리로 묶어주고 photo에 해당하는 점수들을 return 하는 간단한 구현 문제

코드

def solution(name, yearning, photo):
    dic = {name[i]: yearning[i] for i in range(len(name))}
    answer = []
    for case in photo:
        score = 0
        for person in case:
            if person in dic:
                score += dic[person]
        answer.append(score)
    return answer

시간복잡도 O(N^2)

문제 설명

지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다.

• ["방향 거리", "방향 거리" … ]

예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다.

• 주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다.
• 주어진 방향으로 이동 중 장애물을 만나는지 확인합니다.

위 두 가지중 어느 하나라도 해당된다면, 로봇 강아지는 해당 명령을 무시하고 다음 명령을 수행합니다.
공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단의 좌표는 (0, 0), 우측 하단의 좌표는 (H - 1, W - 1) 입니다.

공원을 나타내는 문자열 배열 park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때, 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 3 ≤ park의 길이 ≤ 50
  • 3 ≤ park[i]의 길이 ≤ 50
    • park[i]는 다음 문자들로 이루어져 있으며 시작지점은 하나만 주어집니다.
      • S : 시작 지점
      • O : 이동 가능한 통로
      • X : 장애물
  • park는 직사각형 모양입니다.
• 1 ≤ routes의 길이 ≤ 50
  • routes의 각 원소는 로봇 강아지가 수행할 명령어를 나타냅니다.
  • 로봇 강아지는 routes의 첫 번째 원소부터 순서대로 명령을 수행합니다.
  • routes의 원소는 "op n"과 같은 구조로 이루어져 있으며, op는 이동할 방향, n은 이동할 칸의 수를 의미합니다.
    • op는 다음 네 가지중 하나로 이루어져 있습니다.
      • N : 북쪽으로 주어진 칸만큼 이동합니다.
      • S : 남쪽으로 주어진 칸만큼 이동합니다.
      • W : 서쪽으로 주어진 칸만큼 이동합니다.
      • E : 동쪽으로 주어진 칸만큼 이동합니다.
    • 1 ≤ n ≤ 9

아이디어

쉬운 그래프 탐색 구현 문제, 시작점 찾은 이후 routes의 방향과 이동칸수 만큼 이동, 경로에 X가 있다면 이동하지 않는다.

코드

시간복잡도 O(N^2)

def solution(park, routes):
    answer=[]
    #시작점 찾기
    for i in range(len(park)):
        for j in range(len(park[0])):
            if park[i][j]=='S':
                sx,sy=i,j
                break
               
    op=[[-1,0],[0,1],[0,-1],[1,0]] #NEWS
  
    for route in routes:
        news,n=route.split(' ')
        n=int(n)
        nx,ny=sx,sy
        
        if news=='N': idx=0
        elif news=='E': idx=1
        elif news=='W':idx=2
        else: idx=3
        
        print(nx,ny)
        for i in range(n):
            dx,dy=op[idx][0],op[idx][1]
            if 0<=sx+dx<len(park) and 0<=sy+dy<len(park[0]) and park[sx+dx][sy+dy]!='X':
                sx,sy=sx+dx,sy+dy
            else:
                sx,sy=nx,ny
                break
                
    answer.append([sx,sy])

딕셔너리를 활용해 {N:[-1,0], E:[0,1], W:[0,-1], S:[1,0]}으로 작성했다면 코드가 더 간결했을 것으로 생각된다.

문제 설명

코딩테스트를 준비하는 머쓱이는 프로그래머스에서 문제를 풀고 나중에 다시 코드를 보면서 공부하려고 작성한 코드를 컴퓨터 바탕화면에 아무 위치에나 저장해 둡니다. 저장한 코드가 많아지면서 머쓱이는 본인의 컴퓨터 바탕화면이 너무 지저분하다고 생각했습니다. 프로그래머스에서 작성했던 코드는 그 문제에 가서 다시 볼 수 있기 때문에 저장해 둔 파일들을 전부 삭제하기로 했습니다.

컴퓨터 바탕화면은 각 칸이 정사각형인 격자판입니다. 이때 컴퓨터 바탕화면의 상태를 나타낸 문자열 배열 wallpaper가 주어집니다. 파일들은 바탕화면의 격자칸에 위치하고 바탕화면의 격자점들은 바탕화면의 가장 왼쪽 위를 (0, 0)으로 시작해 (세로 좌표, 가로 좌표)로 표현합니다. 빈칸은 ".", 파일이 있는 칸은 "#"의 값을 가집니다. 드래그를 하면 파일들을 선택할 수 있고, 선택된 파일들을 삭제할 수 있습니다. 머쓱이는 최소한의 이동거리를 갖는 한 번의 드래그로 모든 파일을 선택해서 한 번에 지우려고 하며 드래그로 파일들을 선택하는 방법은 다음과 같습니다.

• 드래그는 바탕화면의 격자점 S(lux, luy)를 마우스 왼쪽 버튼으로 클릭한 상태로 격자점 E(rdx, rdy)로 이동한 뒤 마우스 왼쪽 버튼을 떼는 행동입니다. 이때, "점 S에서 점 E로 드래그한다"고 표현하고 점 S와 점 E를 각각 드래그의 시작점, 끝점이라고 표현합니다.
• 점 S(lux, luy)에서 점 E(rdx, rdy)로 드래그를 할 때, "드래그 한 거리"는 |rdx - lux| + |rdy - luy|로 정의합니다.
• 점 S에서 점 E로 드래그를 하면 바탕화면에서 두 격자점을 각각 왼쪽 위, 오른쪽 아래로 하는 직사각형 내부에 있는 모든 파일이 선택됩니다.

예를 들어 wallpaper = [".#...", "..#..", "...#."]인 바탕화면을 그림으로 나타내면 다음과 같습니다.

이러한 바탕화면에서 다음 그림과 같이 S(0, 1)에서 E(3, 4)로 드래그하면 세 개의 파일이 모두 선택되므로 드래그 한 거리 (3 - 0) + (4 - 1) = 6을 최솟값으로 모든 파일을 선택 가능합니다.

(0, 0)에서 (3, 5)로 드래그해도 모든 파일을 선택할 수 있지만 이때 드래그 한 거리는 (3 - 0) + (5 - 0) = 8이고 이전의 방법보다 거리가 늘어납니다.

머쓱이의 컴퓨터 바탕화면의 상태를 나타내는 문자열 배열 wallpaper가 매개변수로 주어질 때 바탕화면의 파일들을 한 번에 삭제하기 위해 최소한의 이동거리를 갖는 드래그의 시작점과 끝점을 담은 정수 배열을 return하는 solution 함수를 작성해 주세요. 드래그의 시작점이 (lux, luy), 끝점이 (rdx, rdy)라면 정수 배열 [lux, luy, rdx, rdy]를 return하면 됩니다.

제한사항

• 1 ≤ wallpaper의 길이 ≤ 50
• 1 ≤ wallpaper[i]의 길이 ≤ 50
  • wallpaper의 모든 원소의 길이는 동일합니다.
• wallpaper[i][j]는 바탕화면에서 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
• wallpaper[i][j]는 "#" 또는 "."의 값만 가집니다.
• 바탕화면에는 적어도 하나의 파일이 있습니다.
• 드래그 시작점 (lux, luy)와 끝점 (rdx, rdy)는 lux < rdx, luy < rdy를 만족해야 합니다.

아이디어

# 위치들의 (x,y)좌표의 최소에 해당하는 x,y값과 (x+1,y+1)의 좌표의 최대에 해당하는 x,y값을 찾아서 return 하는 구현문제

코드

def solution(wallpaper):
    n=len(wallpaper)
    m=len(wallpaper[0])
    #print(n,m)
    check1=[]
    check2=[]
    for i in range(n):
        for j in range(m):
            if wallpaper[i][j]=='#':
                check1.append(i)
                check1.append(i+1)
                check2.append(j)
                check2.append(j+1)
                

    answer = []
    answer.append(min(check1))
    answer.append(min(check2))
    answer.append(max(check1))
    answer.append(max(check2))
    return answer

문제 설명

어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다. 벽에 동아리 · 학회 홍보나 회사 채용 공고 포스터 등을 게시하기 위해 테이프로 붙였다가 철거할 때 떼는 일이 많고 그 과정에서 페인트가 벗겨지곤 합니다. 페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다.

넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다. 이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.

벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.

• 롤러가 벽에서 벗어나면 안 됩니다.
• 구역의 일부분만 포함되도록 칠하면 안 됩니다.

즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다. 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.

한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다. 예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.

정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.

• 1 ≤ m ≤ n ≤ 100,000
• 1 ≤ section의 길이 ≤ n
  • 1 ≤ section의 원소 ≤ n
  • section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
  • section에서 같은 원소가 두 번 이상 나타나지 않습니다.
  • section의 원소는 오름차순으로 정렬되어 있습니다.

입출력 예

아이디어

페인트를 section 구간 시작부터 m칸 만큼 채우는 구현 문제

코드 - 시간복잡도 : O(N^2)

def solution(n, m, section):
    answer = 0
    while section:
        if len(section) > 0:
            next_pos = section[0] + m
            while section and section[0] < next_pos:
                section.pop(0) # O(N)
            answer += 1
    return answer

처음에 코드를 작성할 때 시간복잡도를 고려하지 않고 section.pop(0)를 사용하였다.

section을 만약에 deque()로 선언해주고 section.popleft()를 해주었다면 O(1)의 시간복잡도가 형성되었을 것이다.

다만, section은 리스트로 선언되어있어 section.pop(0)는 O(N)의 시간복잡도를 가지게 되었다.

N=1,000,000이라 통과하지 않을 것으로 예상하였으나 통과를 하게 되서 코드를 제출하고 다시볼때 의문이 들었다.

시간복잡도를 고려해서 코드를 짜도록 하자.

(이후 정리할 겸 아래의 글을 작성하였다.)

코드 - 시간복잡도 : O(N)

from collections import deque

def solution(n, m, section):
	section=deque(section)
    answer = 0
    while section:
        if len(section) > 0:
            next_pos = section[0] + m
            while section and section[0] < next_pos:
                section.popleft() # O(1)
            answer += 1
    return answer

문제 설명

휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.

예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.

같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.

이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.

1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.

단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

• 1 ≤ keymap의 길이 ≤ 100
  • 1 ≤ keymap의 원소의 길이 ≤ 100
  • keymap[i]는 i + 1번 키를 눌렀을 때 순서대로 바뀌는 문자를 의미합니다.
    • 예를 들어 keymap[0] = "ABACD" 인 경우 1번 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 A 가 됩니다.
  • keymap의 원소의 길이는 서로 다를 수 있습니다.
  • keymap의 원소는 알파벳 대문자로만 이루어져 있습니다.
• 1 ≤ targets의 길이 ≤ 100
  • 1 ≤ targets의 원소의 길이 ≤ 100
  • targets의 원소는 알파벳 대문자로만 이루어져 있습니다.

아이디어

keymap에서의 알파벳과 해당 최소 인덱스를 각각 dic에 키, 값으로 넣어주기

targets에서 해당하는 점수 answer에 넣어주기

파이썬 딕셔너리를 이용한 구현 문제

시간복잡도는 O(N^2)이다.

코드

def solution(keymap, targets):
    dic={}
    for i in range(len(keymap)):
        for j in range(len(keymap[i])):
            alphabet=keymap[i][j]
            if alphabet in dic.keys():
                dic[alphabet]=min(dic[alphabet], j+1)
            else:
                dic[alphabet]=j+1
         
    answer = []
    for i in range(len(targets)):
        total=0
        for j in range(len(targets[i])):
            if targets[i][j] in dic.keys():
                total+=dic[targets[i][j]]
            else:
                total=-1
                break
        answer.append(total)
    
    return answer

문제 설명

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

• 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
• 한 번 사용한 카드는 다시 사용할 수 없습니다.
• 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
• 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.

문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들 있다면 "Yes"를, 만들 수 없다면 "No"를 return하는 solution 함수를 완성해주세요.

• 1 ≤ cards1의 길이, cards2의 길이 ≤ 10
  • 1 ≤ cards1[i]의 길이, cards2[i]의 길이 ≤ 10
  • cards1과 cards2에는 서로 다른 단어만 존재합니다.
• 2 ≤ goal의 길이 ≤ cards1의 길이 + cards2의 길이
  • 1 ≤ goal[i]의 길이 ≤ 10
  • goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있습니다.
• cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.

아이디어 설명

덱 구조를 활용하여 card1, card2 자료구조 변경 -> 시간복잡도 낮은 popleft쓰기 위해

goal의 첫 원소부터 card1[0], cards2[0]가 있는지 확인

있다면 해당 cards의 첫 원소 popleft()

없다면 answer=NO 이후 탈출시켜준다.

시간복잡도 O(N)

코드

from collections import deque

def solution(cards1, cards2, goal):
    answer="Yes"
    cards1=deque(cards1)
    cards2=deque(cards2)

    for i in range(len(goal)):
        if cards1 and cards1[0]==goal[i]:
            cards1.popleft()
        elif cards2 and cards2[0]==goal[i]:
            cards2.popleft()
        else:
            answer="No"
            break
    
    return answer

1. 분할 정복(Divide and Conquer)

큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘

문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다.

대표적인 예로, 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있다.

2. 동작 방식

1. 문제를 작은 부분 문제들로 분할한다.
2. 분할된 부분 문제들을 각각 재귀적으로 해결한다.
3. 부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다.

3.  시간 복잡도

시간 복잡도는 일반적으로 부분 문제의 개수, 분할된 문제의 크기, 분할과정의 복잡도에 따라 결정된다.

대부분의 경우, 분할 정복 알고리즘은 재귀적인 방법으로 문제를 해결하므로, 재귀 호출의 깊이에 따라 시간 복잡도가 결정된다.

분할된 문제들의 크기가 일정하다면, 재귀 호출의 깊이는 로그 시간 복잡도에 비례한다.

분할된 문제의 개수가 N이라면, 시간 복잡도는 O(N*logN)

그러나 분할된 문제의 개수가 지수적으로 증가하거나 분할된 문제들이 크기가 일정하지 않은 경우, 시간 복잡도가 지수적으로 증가할 수 있다.

이 경우에는 다른 알고리즘을 고려해야 한다.

4. 병합 정렬(Merge Sort)

분할과 정복을 모두 사용하여 리스트를 반으로 나누어 각각을 재귀적으로 정렬하고, 정렬된 두 개의 부분 리스트를 합쳐 전체 리스트를 정렬하는 방식

1. 동작 과정

1. 분할: 입력 리스트를 반으로 나눕니다.
2. 정복: 각각의 부분 리스트를 재귀적으로 병합 정렬합니다.
3. 결합: 정렬된 부분 리스트를 합쳐 전체 리스트를 정렬합니다.

2. 파이썬 구현 코드

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # Divide
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # Conquer
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    
    # Combine
    return merge(left_sorted, right_sorted)
    
    
def merge(left, right):
    result = []
    i, j = 0, 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result += left[i:]
    result += right[j:]
    
    return result

• merge_sort 함수 :
  • 입력 리스트를 반으로 나누고 재귀적으로 호출하여 각각을 정렬
  • 마지막으로 merge 함수를 사용하여 두 정렬된 리스트를 합병하여 전체 리스트를 정렬
• merge 함수 :
  • 두 개의 정렬된 리스트를 인수로 받아, 두 리스트를 비교하여 작은 순서대로 result 리스트에 삽입하고, 남은 요소를 추가하여 반환

5. 퀵 정렬(Quick Sort)

분할과 정복을 사용하여 리스트를 분할하고, 각각을 재귀적으로 정렬한 다음, 전체 리스트를 합치지 않고 원래 위치에 놓여있는 것을 기준으로 정렬

특히, 정렬을 위해 별도의 저장 공간을 필요로 하지 않아 메모리 사용량이 적다는 특징이 있다.

1. 동작과정

1. 기준점(pivot) 선택: 리스트에서 하나의 원소를 기준점으로 선택한다.
2. 분할: 기준점을 기준으로 리스트를 두 개로 분할한다. 분할된 두 개의 리스트는 각각 기준점보다 작은 값과 큰 값으로 이루어져 있다.
3. 정복: 각각의 부분 리스트를 재귀적으로 퀵 정렬한다.
4. 결합: 정렬된 부분 리스트를 합쳐 전체 리스트를 정렬한다.

2. 파이썬 구현 코드

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # Divide
    pivot = arr[0]
    left = []
    right = []
    
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    
    # Conquer
    left_sorted = quick_sort(left)
    right_sorted = quick_sort(right)
    
    # Combine
    return left_sorted + [pivot] + right_sorted

• quick_sort 함수 :
  • 입력 리스트의 첫 번째 요소를 기준으로 왼쪽과 오른쪽 부분 리스트를 나눔
  • 재귀적으로 각각을 정렬하여 마지막으로 합쳐서 반환

입력 리스트의 첫 번째 요소를 기준으로 나누기 때문에, 최악의 경우(이미 정렬된 리스트, 피벗이 가장 작거나 큰 수 등)에는 분할이 제대로 이루어지지 않아 시간 복잡도가 O(n^2)에 근접해질 수 있다.

이를 방지하기 위해서는 피벗을 무작위로 선택하거나, 미리 섞어서 평균적인 경우를 대응하는 방법 등이 있다.