[코테] 코딩 테스트 합격자 되기 2주차 - 배열

배열은 인덱스와 값을 일대일 대응에 관리하는 자료구조입니다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있습니다. 데이터에 한 번에 접근할 수 있으니 어디에 있는지만 알면 빠르게 탐색할 수 있는 것이죠. 이런 접근 방식을 임의 접근(random access)라고 합니다.

📖 배열 선언

    배열을 선언하는 방법은 다음과 같습니다. 이름이 arr 이고 길이가 8인 정수형 배열을 리스트를 활용해서 선언하는 3가지 방법을 예제를 통해서 알아보겠습니다.

 

    1) 일반적인 방법

arr = [0,0,0,0,0,0,0,0]
arr = [0] * 8

# 결과는 둘 다 동일합니다.

   

    2) 리스트 생성자를 사용하는 방법

arr = list(range(8))    # [0,1,2,3,4,5,6,7]

 

    2) 리스트 컴프리헨션을 활용하는 방법

arr = [0 for _ in range(8)]

 

배열은 인덱스가 0부터 시작합니다. 즉 3번 째 데이터에 접근하려면 arr[2] 와 같이 접근하면 됩니다. 다만 파이썬의 경우, 배열을 지원하는 문법은 없고 대신에 리스트라는 문법을 지원합니다. 엄밀히 말해 배열과 리스트는 다른 개념이지만, 여기서는 코드와 함께 배열을 설명해야 할 때는 파이썬의 리스트를 사용하겠습니다.

 

※ 파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현되어 있습니다. 그래서 파이썬의 리스트는 다른 언어의 배열 기능을 그대로 사용할 수 있으면서 배열 크기도 가변적이므로 코딩 테스트에서 고려할 사항을 조금 더 줄여줍니다. 슬라이싱, 삽입, 삭제, 연결 등의 연산을 제공하므로 더 편리하다고 할 수 있죠.

---

📖 배열과 차원

    배열은 2차원 배열, 3차원 배열과 같이 다차원 배열을 사용할 때도 많습니다. 하지만, 컴퓨터 메모리의 구조는 1차원이므로 2차원, 3차원 배열도 실제로는 1차원 공간에 저장합니다. 다시 말해 배열은 차원과는 무관하게 메모리에 연속 할당됩니다.

 

    1) 1차원 배열

 

        ■ 1차원 배열은 가장 간단한 배열 형태를 가집니다. '간단하다' 라고 말한 이유는 1차원 배열의 모습이 메모리에 할당된 실제 배열의 모습과 같다는 것입니다. 다음 그림을 보면 쉽게 이해할 수 있습니다.

1차원 배열 메모리 할당 모습

 

    2) 2차원 배열

 

        ■ 2차원 배열은 1차원 배열을 확장한 것입니다. 2차원 배열은 파이썬에서 리스트를 사용해 다음과 같이 선언할 수 있습니다.

# 2차원 배열을 리스트로 표현
arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

# arr[2][3] 에 저장된 값을 출력
print(arr[2][3])    # 12

# arr[2][3] 에 저장된 값을 15로 변경
arr[2][3] = 15

# 변경된 값을 출력
print(arr[2][3])  # 15

        

        ■ 리스트 컴프리헨션을 활용하면 다음과 같이 선언할 수도 있습니다.

# 크기가 3 * 4 인 리스트를 선언하는 예
arr = [[i] * 4 for i in range(3)]    # [[0,0,0,0],[1,1,1,1],[2,2,2,2]]

        

        ■ 2차원 배열 데이터에 접근하는 방법은 1차원 배열과 비슷합니다. 행과 열을 명시해 [대괄호] 연산자를 2개 연이어 사용한다는 점만 다릅니다.

2차원 배열 메모리 할당 모습

 

        ■ 왼쪽은 2차원 배열을 사람이 이해하기 쉽도록 2차원으로 표현한 것이고, 오른쪽은 실제 메모리에 2차원 배열이 저장된 상태를 표현한 것입니다. 

        ■ 사람이 이해하기에는 왼쪽의 형태로 이해하는 것이 편리하므로 2차원 배열을 왼쪽의 행과 열 공간처럼 표현하는 경우가 많지만, 실제로는 오른쪽처럼 0행, 1행 순서로 데이터를 할당해 1차원 공간에 저장합니다.

 

---

 

📖 배열 연산의 시간 복잡도

배열 데이터에 접근할 때의 시간 복잡도를 알아봅시다. 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있습니다. 따라서, 데이터에 접근하기 위한 시간 복잡도는 O(1) 입니다.

데이터를 추가하거나 삭제할 때는 어디에 저장하고 삭제하느냐에 따라 추가 연산에 대한 시간복잡도가 달라집니다.

 

 1) 맨 뒤에 삽입할 경우

 

        ■ 다음과 같은 배열이 있을 때, 2를 추가한다고 생각해본다면, 맨 뒤에 삽입할 때는 arr[3] 에 임의 접근을 바로 할 수 있으며, 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않습니다. 따라서, 시간복잡도는 O(1) 입니다.

맨 뒤에 삽입할 경우

 

 2) 맨 앞에 삽입할 경우

 

        ■ 데이터를 맨 앞에 삽입한다면, 기존 데이터들을 뒤로 한 칸씩 밀어야 합니다. 즉, 미는 연산이 필요한 것이죠. 데이터 개수를 N개를 일반화하면, 시간복잡도는 O(N) 이 되겠습니다.

맨 앞에 삽입할 경우

 

3) 중간에 삽입할 경우

 

        ■ 중간에 삽입할 경우, 만약 5 앞에 데이터를 삽입한다면, 5 이후의 데이터를 뒤로 한 칸씩 밀어야 합니다. 즉, 현재 삽입할 데이터 뒤에 있는 데이터 개수만큼 미는 연산을 해야 하는 것이죠. 이 역시 데이터 개수가 N개라면, 시간복잡도는 O(N) 이 됩니다.

중간에 삽입할 경우

---

 

📖 배열을 선택할 때 고려할 점

데이터에 자주 접근하거나 읽어야 하는 경우, 배열을 사용하면 좋은 성능을 낼 수 있습니다. 예를 들어, 그래프를 표현할 때 배열을 활용하면 임의접근을 할 수 있으므로 간선 여부도 시간복잡도 O(1) 로 판단할 수 있습니다.

 

하지만, 배열은 메모리 공간을 충분히 확보해야 하는 단점도 있습니다. 임의 접근이라는 특징이 있어 바로바로 데이터에 접근할 수 있는 장점이 있지만, 메모리 낭비가 발생할 수도 있다는 말이죠.

 

따라서, 코딩테스트에서는 다음 사항을 고려해 배열을 선택해야 합니다.

 

1) 할당할 수 있는 메모리 크기를 확인해야 합니다 → 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있습니다. 운영체제마다 배열을 할당할 수 있는 메모리의 한계치는 다르지만, 보통은 정수형 1차원 배열은 1000만 개(10^7), 2차원 배열은 3000 * 3000 크기를 최대로 생각합니다.

 

2) 중간에 데이터 삽입이 많은지 확인해야 합니다. → 배열은 선형 자료구조이기 때문에, 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있습니다.

 

---

 

📖 자주 활용하는 리스트 기법

 

■ 리스트에 데이터 추가

 

append() 메서드

# 리스트 맨 끝에 데이터 추가
my_list = [1,2,3]
my_list.append(4)  # [1,2,3,4]

 

+ 연산자

my_list = [1,2,3]
my_list = my_list + [4,5]  # [1,2,3,4,5]

 

insert() 메서드

# 특정 위치에 데이터를 삽입할 수 있음.
# 첫 번째 인수에 데이터를 삽입할 위치, 두 번째 인수에 삽입할 데이터 

my_list = [1,2,3,4,5]
my_list.insert(2,9999) # [1,2,9999,3,4,5]

---

 

■ 리스트에 데이터 삭제

 

pop() 메서드

# pop 할 데이터의 인덱스를 인수로 받아 삭제하고 삭제한 데이터의 값을 반환
my_list = [1,2,3,4,5]
x = my_list.pop(2) # x = 3
print(my_list)     # [1,2,4,5]

 

remove() 메서드

# pop() 과는 다르게, 특정 위치가 아닌 특정 "데이터"자체를 삭제하는 함수
# remove() 메서드는 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제

my_list = [1,2,2,3,4,5]
my_list.remove(2)  # [1,2,3,4,5] - 1번 위치에 있는 2 삭제
my_list.remove(2)  # [1,3,4,5] - 1번 위치에 있는 2 삭제
my_list.remove(5)  # [1,3,4] - 3번 위치에 있는 5 삭제

---

 

■ 리스트 컴프리헨션으로 데이터에 특정 연산 적용

 

→ 리스트 컴프리헨션은 기존 리스트를 기반해 새 리스트를 만들거나, 반복문, 조건문을 이용해 복잡한 리스트를 생성하는 등 다양한 상황에서 사용할 수 있는 문법

 

리스트에 제곱 연산 적용 예

numbers = [1,2,3,4,5]
squares = [num ** 2 for num in numbers] # [1,4,9,16,25]

 

여기서, numbers 리스트는 그대로입니다. 리스트 컴프리헨션은 연산이 끝난 리스트를 반환할 뿐이지 연산 대상 리스트를 바꾸진 않습니다.

---

 

■ 그 외에도 유용한 메서드

 

len() 메서드

→ 리스트의 전체 데이터 개수(길이)를 반환하는 함수

 

index() 메서드

→ 특정 데이터가 처음 등장한 인덱스를 반환하는 함수, 없으면 -1 을 반환

 

sort() 메서드

→ 사용자가 정한 기준에 따라 리스트 데이터를 정렬하는 함수

 

count() 메서드

→ 특정 데이터 개수를 반환하는 함수

 

fruits = ["apple","banana","cherry","durian","elderberry","fig","grape","apple"]

len(fruits) # 7

fruits.index("cherry") # 2

fruits.sort()
# ["apple","apple","banana","cherry","durian","elderberry","fig","grape"]

fruits.sort(reverse=True) 
# ["grape","fig","elderberry","durian","cherry","banana","apple","apple"]

fruits.count("apple") # 2

---

 

📖 몸풀기 문제

 

01. 배열 정렬하기

 

[문제]

정수 배열을 정렬해서 반환하는 solution 함수를 완성하세요.

 

[제약조건]

• 정수 배열의 길이는 2이상 10^5 이하입니다.
• 정수 배열의 각 데이터 값은 -100000 이상 100000 이하입니다.

[최종코드]

import sys
input = sys.stdin.readline

def solution(arr):
    arr.sort()
    return arr


print(solution([1,-5,2,4,3])) # 반환값 : [-5, 1, 2, 3, 4]
print(solution([2,1,1,3,2,5,4])) # 반환값 : [1, 1, 2, 2, 3, 4, 5]
print(solution([1,6,7])) # 반환값 : [1, 6, 7]

 

문제만 놓고 보면 간단해 보이지만, 제약 조건을 주의 깊게 봐야 합니다. 제약 조건을 보면 데이터 개수는 최대 10^5개입니다.

즉 제한 시간이 3초라면 O(N^2) 알고리즘은 사용할 수 없는 것이죠. 

너무 문제가 쉽다고 생각해서 제약조건을 고려하지 않으면 안된다는 점을 보여주기 위한 몸풀기 문제입니다.

정답코드는 아주 짧지만, 항상 제약조건을 보는 습관을 들입시다.

 

※ sort() 메소드를 사용하지 않고 O(N^2) 정렬 알고리즘을 사용한다면?

import time
import random
def bubble_sort(arr): # 버블 정렬 - O(N^2)

    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[i] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

def do_sort_func(arr): # 정렬 함수 사용 - O(nlogn)

    arr.sort()
    return arr

def measure_time(func,arr): # 시간을 측정하고 정렬된 배열을 반환

    start_time = time.time()
    result = func(arr)
    end_time = time.time()
    return end_time - start_time, result

arr = random.choices(range(1,10001), k=10000) # 1부터 10000까지 10000개 중복해서 리스트만들기
# O(n^2) 정렬
bubble_time, bubble_result = measure_time(bubble_sort,arr)
print("버블 정렬 실행 시간:",format(bubble_time,".10f"))

# O(nlogn) 정렬
sort_func_time, sort_func_result = measure_time(do_sort_func,arr)
print("정렬 sort 함수 실행 시간:",format(sort_func_time,".10f"))

# 구 개의 코드의 결과가 동일한지 확인
print("두 정렬 결과가 동일하나요?",bubble_result == sort_func_result)

 

결과

 

---

02. 배열 제어하기

 

[문제]

정수 배열을 하나 받습니다. 배열의 중복값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 solution 함수를 구현하세요.

 

[제약조건]

• 정수 배열의 길이는 2이상 1000 이하입니다.
• 정수 배열의 각 데이터 값은 -100000 이상 100000 이하입니다.

[입출력 예]

입력	출력
[4,2,2,1,3,4]	[4,3,2,1]
[2,1,1,3,2,5,4]	[5,4,3,2,1]

 

[최종코드]

import sys
input = sys.stdin.readline

def solution(arr):

    return sorted(list(set(arr)),reverse=True)


# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution([4, 2, 2, 1, 3, 4])) # 반환값 : [4, 3, 2, 1]
# print(solution([2, 1, 1, 3, 2, 5, 4])) # 반환값 : [5, 4, 3, 2, 1]

 

집합은 중복값을 허용하지 않으므로, 문제에서 요구하는 중복 문제를 한 번에 해결할 수 있습니다. 가끔 파이썬 함수를 통해 해결할 수 있는 문제를 굳이 직접 코드를 작성해서 해결하려는 경우가 있는데, 그럴 필요 없습니다. 

'파이썬에는 코딩테스트에 유용한 함수가 많다. 굳이 직접 작성하려 하지 마라' 를 강조하는 몸풀기 문제였습니다. 

set() 함수는 해시 알고리즘으로 데이터를 저장하므로 시간 복잡도를 O(N) 을 보장합니다.
sort()나 sorted() 함수는 reverse 매개변수에 넣은 조건이 디폴트가 False(오름차순)이고, True 면 내림차순 정렬을 해줍니다.

 

---

 

03. 두 개 뽑아서 더하기

 

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/68644

프로그래머스

 

[최종코드]

def solution(numbers):
    
    answer = set()
    
    n = len(numbers)
    
    for i in range(n-1):
        for j in range(i+1,n):
            answer.add(numbers[i] + numbers[j])

    return sorted(answer)

---

 

04. 모의고사

 

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42840

프로그래머스

 

[최종코드]

def solution(answers):
    
    score = [0,0,0]
    
    number1 = [1,2,3,4,5]
    number2 = [2,1,2,3,2,4,2,5]
    number3 = [3,3,1,1,2,2,4,4,5,5]
    
    tmp1, tmp2, tmp3 = 0,0,0
    
    for idx,a in enumerate(answers):
        
        if a == (number1[idx % 5]):
            score[0] += 1
        if a == (number2[idx % 8]):
            score[1] += 1
        if a == (number3[idx % 10]):
            score[2] += 1
    
    target = max(score)
    highest = []
    for idx,s in enumerate(score):
        if s == target:
            highest.append(idx+1)
            
    return highest

 

 

---

05. 행렬의 곱셈

 

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/12949

프로그래머스

 

[최종코드]

def solution(arr1, arr2):
    
    n = len(arr1)
    m = len(arr2[0])
    
    answer = [[0] * m for _ in range(n)]
    print(answer)
    
    for i in range(n):
        for j in range(m):
            for k in range(len(arr1[0])):
                answer[i][j] += (arr1[i][k] * arr2[k][j])
    
    # 행렬 곱셈은 3중 for문 메모
    return answer

 

흡사, 플로이드 워셜 알고리즘과 비슷하다고 생각합니다.

 

---

 

06. 실패율

 

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42889

프로그래머스

[최종코드]

def solution(N, stages):
    
    challenging = [0] * (N+2)
    users = len(stages)
    
    for s in stages:
        
        challenging[s] += 1
    
    challenging = challenging[1:-1]
    
    for idx, c in enumerate(challenging):
        
        if c == 0  or users <= 0:
            challenging[idx] = [idx+1,0]
            continue
        
        challenging[idx] = [idx+1,c/users]
        users -= c
        
    challenging = sorted(challenging, key = lambda x:(-x[1],x[0]))

    answer = [idx for (idx,v) in challenging]
    
    return answer

---

07. 방문 길이

 

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

 

[최종코드]

def solution(dirs):
    
    def search(nx,ny):
        global curx,cury,answer

        if -5 <= nx <= 5 and -5 <= ny <= 5:
            if (curx,cury,nx,ny) not in visited and (nx,ny,curx,cury) not in visited:
                answer += 1
                visited.append((curx,cury,nx,ny))
            curx = nx
            cury = ny
    
    visited = []
    global curx, cury, answer
    curx,cury = 0, 0
    answer = 0
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
                
    for d in dirs:

        if d == "U":
            nx = curx + dx[0]
            ny = cury + dy[0]
            
        elif d == "D":
            
            nx = curx + dx[1]
            ny = cury + dy[1]

        elif d == "L":
            
            nx = curx + dx[2]
            ny = cury + dy[2]

        elif d == "R":
            nx = curx + dx[3]
            ny = cury + dy[3]   
        
        search(nx,ny)
        
    return answer

 

 

---

 

※ 추가문제 입니다.

 

1. N개의 데이터가 채워진 리스트를 아래 조건을 기준으로 정렬하는 코드를 구현해주세요.

• 홀수보다 짝수가 앞에 옵니다. 
• 홀수 혹은 짝수 간에는 값이 적을 수록 앞에 옵니다.

[최종코드]

import sys
input = sys.stdin.readline

def solution(arr):

    arr = sorted(arr)	# 기존 배열 먼저 쫙 정렬
    even = []			# 짝수를 담을 배열
    odd = []			# 홀수를 담을 배열

    for x in arr:

        if x % 2 == 0:
            even.append(x)
        else:
            odd.append(x)


    return even + odd


# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution([4, 2, 2, 1, 3, 4])) # 반환값 : [4, 3, 2, 1]
# print(solution([2, 1, 1, 3, 2, 5, 4])) # 반환값 : [5, 4, 3, 2, 1]

---

 

2. 아래의 요구조건에 맞는 함수를 구현해주세요. nums와 k는 인자로 받고 함수이름은 solution 으로 해주세요.

• 프로토타입 : solution(nums, k)
• 길이가 N인 정수 리스트 nums 와 정수 k를 가지고 있습니다. 여기서 k는 회전의 횟수를 나타냅니다.
• 목표는 리스트의 모든 요소를 오른쪽으로 k번 회전시키는 것입니다. 이 때, 회전은 리스트의 마지막 요소가 첫 번째 위치로 이동하고, 나머지 요소들이 오른쪽으로 하나씩 이동하는 것을 의미합니다.

예를 들어, nums = [1,2,3,4,5] 이고 k = 2 인 경우, 리스트는 다음과 같이 변환됩니다.

 

첫 번째 회전 후 : [5,1,2,3,4]

두 번째 회전 후 : [4,5,1,2,3]

 

요구 사항

• 리스트 nums 와 정수 k를 입력으로 받는 파이썬 함수를 작성하세요.
• 함수는 리스트를 k 번 회전시킨 결과르 반환해야 합니다.
• 모듈러 연산을 사용하여 효율적으로 문제를 해결하세요.

 

[최종코드]

import sys
input = sys.stdin.readline

def solution(nums,k):

    n = len(nums)
    answer = nums[:]
    move = k % n

    for i in range(n):
        answer[i] = nums[(n-move+i) % n]

    return answer


# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
print(solution([4, 2, 2, 1, 3, 4],3)) # 반환값 : [1, 3, 4, 4, 2, 2]
print(solution([2, 1, 1, 3, 2, 5, 4],13)) # 반환값 : [1, 1, 3, 2, 5, 4, 2]
print(solution([1,2,3,4,5],2))    #  반환값 :[4, 5, 1, 2, 3]

---

 

3. 아래의 요구조건에 맞는 함수를 구현해주세요. (심화 문제, 선택)

 

• M x N 크기의 2차원 배열 grid 를 가지고 있습니다. 이 배열은 0(지뢰가 없음) -1(지뢰가 있음)의 두 가지 숫자로 구성되어 있습니다. 당신의 목표는 각 0 위치에 대해 인접한 8개의 셀(수평, 수직, 대각선) 중 지뢰(-1) 의 개수를 계산하여 해당 위치에 그 숫자를 기록하는 것입니다.
• 예를 들어, grid 가 [[-1,0,0], [0,0,-1], [0,-1,0]] 처럼 주어질 때, 지뢰찾기 보드의 모양은 아래와 같습니다.

-1 0 0
0 0 -1
0 -1 0

 

결과 값은 [[-1,2,1],[2,3,-1],[1,-1,2]] 가 되야 하고, 그림으로 나타내면 아래와 같습니다.

-1 2 1
2 3 -1
1 -1 2

 

 

 

[최종코드]

import sys
input = sys.stdin.readline
import copy

def solution(grid):

    n = len(grid)
    m = len(grid[0])
    answer = copy.deepcopy(grid)

    dr = [-1, -1, -1, 0, 0, 1, 1, 1]  # 8방향 row
    dc = [-1, 0, 1, -1, 1, -1, 0, 1]  # 8방향 col

    for i in range(n):
        for j in range(m):
            if grid[i][j] == 0:
                cnt = 0
                for d in range(8):
                    ni = i + dr[d]
                    nj = j + dc[d]
                    if 0 <= ni < n and 0 <= nj < m and grid[ni][nj] == -1:
                        cnt += 1

                answer[i][j] = cnt

    return answer


# TEST 코드 입니다. 주석을 풀고 실행시켜보세요

# grid = [[-1,0,0], [0,0,-1], [0,-1,0]]  #  반환값 : [[-1, 2, 1], [2, 3, -1], [1, -1, 2]]
# grid = [[-1,0,-1], [-1,0,-1], [-1,0,0]]  #  반환값 : [[-1, 4, -1], [-1, 5, -1], [-1, 3, 1]]

# print(solution(grid))

---

---

💡기초 추가문제

https://school.programmers.co.kr/learn/courses/30/lessons/120817

프로그래머스

 

https://school.programmers.co.kr/learn/courses/30/lessons/120821

프로그래머스

 

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

💡 [추천문제]

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

---