삼성 SW역량테스트 기출 / 2024 상반기 오전 1번 문제 고대 문명 유적 탐사 - 얕은복사, 깊은 복사 / Python 파이썬

 

*문제 출처는 코드트리에 있습니다.

 

삼멘

문제 제목: 고대 문명 유적 탐사

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/ancient-ruin-exploration/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

---

나의 풀이

sudo

"""# 선택 격자 항상 회전
# 유물의 1차 흭득 가치 최대화
# 그 방법이 여러가지라면 각도 작은것
# 그 방법이 여러가지라면 열 작음 > 행 작음

while True
    rotate()
    # 인접한 유물 조각(3개이상) 확인 -> 사라짐
    check_legacy() # bfs
    input_numbers() # 열 작은순 > 열이 같다면 행 번호 큰순으로 숫자 입력
    # 썼던 숫자는 못씀

"""

from collections import deque
K, M = map(int,input().split())
init_maps = [list(map(int,input().split())) for _ in range(5)]
legacy_num = list(map(int,input().split()))

def rotate(sr, sc, maps):
    # 3x3 영역을 시계 방향으로 회전
    new_maps = [row[:] for row in maps]  # 얕은 복사를 여기서만 사용
    for i in range(3):
        for j in range(3):
            new_maps[sr - 1 + j][sc + 1 - i] = maps[sr - 1 + i][sc - 1 + j]
    return new_maps

def bfs(sr,sc,maps,visited):
    num = maps[sr][sc]
    queue = deque([[sr,sc]])
    direct = ((-1,0),(1,0),(0,-1),(0,1))
    near_nums = [[sr,sc]]
    visited[sr][sc] = True
    while queue:
        q = queue.popleft()
        qx, qy = q[0], q[1]
        for i in range(4):
            xx = qx+direct[i][0]
            yy = qy+direct[i][1]
            if 0 <= xx < 5 and 0 <= yy < 5 and visited[xx][yy] == False and maps[xx][yy] == num:
                visited[xx][yy] = True
                queue.append([xx,yy])
                near_nums.append([xx,yy])
    return near_nums, visited

def check_size(maps):
    visited = [[False]*5 for _ in range(5)]
    score = 0 # 유물 가치
    remove_nums = []
    for i in range(5):
        for j in range(5):
            if visited[i][j]== False:
                near_nums,new_visited = bfs(i,j,maps,visited)
                if len(near_nums) >= 3:
                    score += len(near_nums)
                    remove_nums += near_nums
                visited = new_visited
    return score, remove_nums

def max_score_search():
    # 각각의 좌표에 대해 가장 높은 score 찾기
    MAX = float('-inf')
    max_score = [9, 9, 9]  # i, j 좌표, 회전횟수
    final_remove_num = []
    maps = []
    for i in range(1, 4):
        for j in range(1, 4):
            k_maps = init_maps  # 깊은 복사 대신 얕은 복사로 변경
            for k in range(1, 4):  # 3회 회전
                k_maps = rotate(i, j, k_maps)
                score, remove_nums = check_size(k_maps)
                if score > MAX:
                    MAX = score
                    max_score = [i, j, k]
                    final_remove_num = remove_nums
                    maps = k_maps  # 얕은 복사로 유지
                if score == MAX:
                    if k < max_score[2]:  # 각도가 작은 것 우선순위
                        max_score[0], max_score[1], max_score[2] = i, j, k
                        final_remove_num = remove_nums
                        maps = k_maps
                    elif k == max_score[2] and j < max_score[1]:  # 각도가 같다면 열이 작은 것 우선순위
                        max_score[0], max_score[1], max_score[2] = i, j, k
                        final_remove_num = remove_nums
                        maps = k_maps
                    elif k == max_score[2] and j == max_score[1] and i < max_score[0]:  # 각도, 열이 같다면 행이 작은 것 우선
                        max_score[0], max_score[1], max_score[2] = i, j, k
                        final_remove_num = remove_nums
                        maps = k_maps
    answer = 0
    answer += MAX
    return final_remove_num, maps, answer

def input_numbers(maps,remove_nums):
    global legacy_num
    answer = 0
    new_maps = [i[:] for i in maps]
    legacy_num = deque(legacy_num)
    while remove_nums:
        remove_nums.sort(key=lambda x: (x[1], -x[0]))
        # print(remove_nums)
        for i in range(len(remove_nums)):
            # print(legacy_num)
            if legacy_num:
                new_maps[remove_nums[i][0]][remove_nums[i][1]] = legacy_num.popleft()
                # print(q)
                # for j in range(5):
                #     print(new_maps[j])
        score, remove = check_size(new_maps)
        if score >= 3:
            remove_nums = remove
            answer += score
        else:
            break

    return new_maps, answer
turn_score = []
while K > 0:
    remove_nums, maps, answer = max_score_search()
    if answer == 0:
        break
    new_maps, answer2 = input_numbers(maps,remove_nums)
    turn_score.append(answer + answer2)
    if new_maps == init_maps:
        break
    else:
        init_maps = [i[:] for i in new_maps]
    K -= 1

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

처음에 깊은 복사로 계속 갈기다가 시간 초과 났다..

얕은 복사로 해줄건 계속 복사해주고 수정해야한다.

 

나름 쉬운 문제였지만, 시험장에서 이런거 때문에 시간초과나서 다풀었다고 오만하지말고

얕은 복사 할 부분은 잘 복사해서 사용하도록 하자

얕은 복사와 깊은 복사의 차이 및 시간 초과 원인 분석

1. 얕은 복사와 깊은 복사

얕은 복사는 객체의 참조만 복사하여 원본과 복사본이 같은 데이터를 공유하는 방식이다. 리스트를 얕은 복사하면 리스트 자체만 복사되고 내부 요소들은 원본을 참조하게 된다.

 

shallow_copy = original_list[:]

 

깊은 복사는 객체의 모든 데이터를 새롭게 복사하는 방식이다. 복사된 객체는 원본과 독립적으로 동작하며, 변경해도 원본에 영향을 미치지 않는다.

 

import copy

deep_copy = copy.deepcopy(original_list)

또는

maps = [[maps[i][j] for j in range(5)] for i in range(5)]

 

2. 시간 초과의 원인

1. 반복되는 깊은 복사: 기존 코드에서는 rotate 함수에서 매번 5x5 배열을 깊은 복사하여 작업을 진행했다. 이 과정이 반복되면서 불필요하게 메모리와 연산 시간이 증가했다.
2. 회전과 탐색의 반복: max_score_search 함수에서 좌표마다 3번 회전하며, 매번 복사와 BFS 탐색을 진행했다. 이로 인해 중복된 깊은 복사와 탐색이 반복되어 시간이 많이 소모됐다.
3. 불필요한 연산: 깊은 복사를 할 때마다 새 배열을 만들어서 메모리와 CPU를 소모했으며, 이로 인해 성능이 떨어졌다.

3. 수정 전 코드와 수정 후 코드

수정 전 코드 (깊은 복사 사용)

def max_score_search():
    MAX = float('-inf')
    max_score = [9, 9, 9]
    final_remove_num = []
    maps = []
    for i in range(1, 4):
        for j in range(1, 4):
            k_maps = [i[:] for i in init_maps]  # 깊은 복사
            for k in range(1, 4):
                k_maps = rotate(i, j, k_maps)
                score, remove_nums = check_size(k_maps)
                if score > MAX:
                    MAX = score
                    max_score = [i, j, k]
                    final_remove_num = remove_nums
                    maps = [i[:] for i in k_maps]  # 깊은 복사
    return final_remove_num, maps, MAX

 

수정 후 코드 (얕은 복사 사용)

def max_score_search():
    MAX = float('-inf')
    max_score = [9, 9, 9]
    final_remove_num = []
    maps = []
    for i in range(1, 4):
        for j in range(1, 4):
            k_maps = init_maps  # 얕은 복사
            for k in range(1, 4):
                k_maps = rotate(i, j, k_maps)
                score, remove_nums = check_size(k_maps)
                if score > MAX:
                    MAX = score
                    max_score = [i, j, k]
                    final_remove_num = remove_nums
                    maps = k_maps  # 얕은 복사로 변경
    return final_remove_num, maps, MAX

4. 해결 방법

얕은 복사를 사용하여 불필요한 깊은 복사를 줄였다. 필요한 부분만 얕은 복사를 하고, 나머지는 기존 배열을 참조하도록 변경했다. 이렇게 하면 배열 전체를 새로 만들지 않으면서 성능을 최적화할 수 있다.

5. 결론

시간 초과 문제는 반복적인 깊은 복사로 인해 발생했다. 얕은 복사를 사용하여 불필요한 복사를 줄이고, 배열 참조를 통해 성능을 개선하여 문제를 해결했다.

 

 

---

※ 알아야 할 것

 

- 깊은 복사는 모든 데이터를 새로 복사해 메모리와 시간이 많이 소요되며, 얕은 복사는 참조만 복사해 더 효율적이다.

- 기존 코드는 불필요한 깊은 복사로 인해 배열을 계속 복사하며 연산을 반복해 시간 초과가 발생했다.

- 얕은 복사로 수정해 불필요한 복사를 줄이고 성능을 최적화하여 시간 초과 문제를 해결했다.