[Algorithm] 백준 2566

---

문제

<그림 1>과 같이 9×9 격자판에 쓰여진 81개의 자연수 또는 0이 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오.

풀이

내가 생각한 알고리즘

1. 입력 받은 값을 하나씩 잘라서 배열에 넣는다.
2. 열과 행을 구분하기 위해 한 행을 먼저 저장한다.
3. 입력을 받으면서 최대값과 그 위치를 저장한다.
4. 이때 갱신이 되는 것에 조심 한다.

코드

table = []
for i in range(0, 9):
    table.append(input().split(' '))

max_num = 0
max_num_in = []

for i in range(0, 9):
    for j in range(0, 9):
        temp = int(table[i][j])
        if temp >= max_num:
            max_num = temp
            max_num_in = [i + 1, j + 1]

print(max_num)
print(max_num_in)

개선할 점

주어진 코드는 주어진 9x9 테이블에서 가장 큰 숫자를 찾고, 그 숫자가 위치한 행과 열을 출력합니다. 이 코드를 개선하기 위해 몇 가지 접근 방법이 있습니다.

1. 입력 유효성 검사: 사용자가 숫자가 아닌 다른 값을 입력하거나, 숫자의 개수가 9x9가 아닌 경우를 처리할 필요가 있습니다. 이를 위해 유효성 검사를 추가하는 것이 좋습니다.

2. 최댓값 탐색 알고리즘 개선: 현재 코드에서는 중첩된 반복문을 사용하여 모든 요소를 확인하고 최댓값을 찾습니다. 이를 개선하여 더 효율적인 알고리즘을 사용할 수 있습니다.

3. 최댓값의 위치 저장 방식 개선: 최댓값의 위치를 찾는 방법을 개선하여 코드의 가독성을 향상시킬 수 있습니다.

다음은 개선된 코드의 예시입니다:

# 행과 열의 개수
ROWS = 9
COLS = 9

# 9x9 테이블 입력 받기
table = []
for _ in range(ROWS):
    row = list(map(int, input().split()))
    if len(row) != COLS:
        print("잘못된 입력입니다. 각 행은 9개의 숫자를 가져야 합니다.")
        exit()
    table.append(row)

# 최댓값 및 최댓값의 위치 찾기
max_num = float('-inf')
max_row, max_col = -1, -1

for i in range(ROWS):
    for j in range(COLS):
        if table[i][j] > max_num:
            max_num = table[i][j]
            max_row, max_col = i + 1, j + 1

# 결과 출력
print("최댓값:", max_num)
print("최댓값의 위치:", (max_row, max_col))

이 코드는 사용자로부터 9x9 테이블을 입력 받고, 유효성을 검사한 후 최댓값과 해당 위치를 찾습니다. 이 코드는 최댓값을 찾기 위해 모든 요소를 확인하지만, 최댓값의 위치를 기록하는 방법이 더 간결하고 가독성이 높습니다.

두번째 생각한 알고리즘

1. 입력 받은 값과 위치를 맵핑한다.
2. 최대값 순으로 정렬한 다음
3. 최대값들을 출력한다.

다음은 이러한 방법을 사용하여 코드를 개선한 예시입니다.

# 행과 열의 개수
ROWS = 9
COLS = 9

# 9x9 테이블 입력 받기
table = []
for _ in range(ROWS):
    row = list(map(int, input().split()))
    if len(row) != COLS:
        print("잘못된 입력입니다. 각 행은 9개의 숫자를 가져야 합니다.")
        exit()
    table.append(row)

# 최댓값과 해당 위치를 매핑
max_values = [(table[i][j], (i + 1, j + 1)) for i in range(ROWS) for j in range(COLS)]

# 최댓값 기준으로 정렬
max_values.sort(reverse=True)

# 최댓값 출력
print("최댓값들:")
for value, position in max_values:
    print(f"최댓값: {value}, 위치: {position}")

이 방법은 최댓값들을 미리 매핑하고, 내림차순으로 정렬하여 최댓값을 출력합니다. 이 방법은 원하는 결과를 더 효과적으로 얻을 수 있으며, 코드도 간결해집니다.

Lesson Learn

부끄럽게도 나는 입력 받아서 숫자로 2차원배열에 저장하는 것에서 헤매었다.

3 23 85 34 17 74 25 52 65
10 7 39 42 88 52 14 72 63
87 42 18 78 53 45 18 84 53
34 28 64 85 12 16 75 36 55
21 77 45 35 28 75 90 76 1
25 87 65 15 28 11 37 28 74
65 27 75 41 7 89 78 64 39
47 47 70 45 23 65 3 41 44
87 13 82 38 31 12 29 29 80

이 값을 입력 받는 것인데, 각 숫자들은 ' '로 구분되고, 한 줄이 끝나면 '\n'으로 구분된다.

1. 테이블 저장 방법
   한 줄씩, 9줄이 입력되고 2차원 배열로 저장하는 방법인데, 문자열을 한번에 int로 저장하는 것이다.

2. 무엇이 효율적인 코드일까?
   주어진 두 코드를 비교할 때, 각각의 공간복잡도와 시간복잡도를 살펴보겠습니다.

첫 번째 코드

table = []
for i in range(0, 9):
    table.append(input().split(' '))

max_num = 0
max_num_in = []

for i in range(0, 9):
    for j in range(0, 9):
        temp = int(table[i][j])
        if temp >= max_num:
            max_num = temp
            max_num_in = [i + 1, j + 1]

print(max_num)
print(max_num_in)

• 공간 복잡도:

  • 테이블을 저장하기 위한 2차원 배열이 필요합니다. 이 배열은 9x9 크기이므로 공간 복잡도는 O(81)입니다.
  • 추가적으로 최대값을 저장하기 위한 변수 max_num과 그 위치를 저장하기 위한 리스트 max_num_in이 필요합니다. 이 변수들은 공간 복잡도에 O(1)을 추가합니다.

• 시간 복잡도:

  • 테이블을 입력하고 최댓값을 찾는 과정에서 2중 반복문을 사용합니다. 이는 각 요소에 대해 한 번씩만 반복하기 때문에 시간 복잡도는 O(81)입니다.

두 번째 코드

# 행과 열의 개수
ROWS = 9
COLS = 9

# 9x9 테이블 입력 받기
table = []
for _ in range(ROWS):
    row = list(map(int, input().split()))
    if len(row) != COLS:
        print("잘못된 입력입니다. 각 행은 9개의 숫자를 가져야 합니다.")
        exit()
    table.append(row)

# 최댓값과 해당 위치를 매핑
max_values = [(table[i][j], (i + 1, j + 1)) for i in range(ROWS) for j in range(COLS)]

# 최댓값 기준으로 정렬
max_values.sort(reverse=True)

# 최댓값 출력
print("최댓값들:")
for value, position in max_values:
    print(f"최댓값: {value}, 위치: {position}")

• 공간 복잡도:

  • 입력을 받은 후 최대값과 해당 위치를 저장하기 위해 리스트 max_values를 사용합니다. 이 리스트의 크기는 9x9 즉 81개의 요소가 있습니다. 따라서 공간 복잡도는 O(81)입니다.

• 시간 복잡도:

  • 최댓값과 해당 위치를 매핑하는 과정에서 2중 반복문을 사용합니다. 이는 각 요소에 대해 한 번씩만 반복하기 때문에 시간 복잡도는 O(81)입니다.
  • 이후 최댓값을 정렬하기 위해 sort() 함수를 사용합니다. 일반적으로 퀵소트와 같은 정렬 알고리즘을 사용하며, 평균적으로 O(n log n)의 시간 복잡도를 갖습니다. 따라서 이 부분의 시간 복잡도는 O(81 log 81)입니다.

두 코드 모두 공간 복잡도와 시간 복잡도에서 큰 차이가 없습니다.

두 경우 모두 2차원 배열에 대한 탐색을 수행하며, 최댓값을 찾는 과정에서 81개의 요소를 모두 확인합니다.

다만 두 번째 코드는 추가적으로 정렬을 수행하는데, 이는 시간적인 소요를 약간 더 가져올 수 있습니다. 하지만 데이터의 크기가 작은 경우, 이러한 차이는 미미할 것입니다.

결론

두 번째 코드가 뭔가 효율적으로 보이지만 공간복잡도와 시간복잡도 면에서는 별 차이가 없다.
그러면 간결한게 최고다 !