문제
민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.
단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.
예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.
N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.
N = int(input())
words = [input().strip() for _ in range(N)]
weight = {}
for word in words:
length = len(word)
for i, ch in enumerate(word):
value = 10 ** (length - i - 1)
if ch in weight:
weight[ch] += value
else:
weight[ch] = value
sorted_weights = sorted(weight.values(), reverse=True)
num = 9
answer = 0
for w in sorted_weights:
answer += w * num
num -= 1
print(answer)
1. 단어개수를 입력받는다.
2. N개의 단어를 입력받아 리스트 word에 저장한다. ( strip()은 앞뒤 공백을 제거하는 것, for뒤에 _은 보통 사용하던 i처럼 생각하면 됨)
3. 각 알파벳의 가중치 합을 저장할 딕셔너리 weight를 생성한다.
4. 입력된 단어를 하나씩 순회한다. 단어의 글자수를 세서 변수 length에 저장한다.
5. i는 인덱스(0부터 시작), ch는 현재문자이다. enumerate()는 파이썬 내장 함수로 반복 가능한 객체(리스트, 문자열 등)을 순회하면서 (인덱스, 요소) 형태로 값을 반환한다. 단어의 왼쪽부터 한글자씩 순회한다.
6. 현재 문자가 있는 자릿수의 값을 계산하여 value에 저장한다.
7. 현재 문자가 딕셔너리 weight에 이미 저장되어 있는지 확인하고, 이미 있으면 이번 자릿수 가중치를 더한다.
8. 그렇지 않으면 가중치를 계산하여 딕셔너리에 추가한다.
9. .values()는 딕셔너리의 값들만 꺼내는 함수이다. sorted()는 정렬함수이고 기본은 오름차순으로 정렬한다.
reverse = True를 추가하여 내림차순으로 정렬되게 한다. 따라서 문자별 가중치 값들만 꺼내서 내림차순으로 정렬한다.
10. 가장 큰 숫자는 9이므로 num의 초기값을 9로, 구하는 최대 합을 저장할 변수 answer의 초기값을 0으로 한다.
11. 큰 가중치부터 순회하면서 합을 구하고 최종 값 answer를 반환한다.
문제
KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.
예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.
3 7 5 2 6 1 4
아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.
3 7 4 5 2 6 1
이제, 7번 아이를 맨 뒤로 옮긴다.
3 4 5 2 6 1 7
다음 1번 아이를 맨 앞으로 옮긴다.
1 3 4 5 2 6 7
마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.
1 2 3 4 5 6 7
위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.
N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.
N = int(input())
arr = [int(input()) for _ in range(N)]
dp = [1] * N
for i in range(N):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
lis_length = max(dp)
print(N - lis_length)
0. 문제의 핵심은 이미 순서대로인 아이들은 움직이지 않아도 된다는 것이다. 가장 긴 증가하는 부분 수열을 찾고, 나머지 아이들만
움직이면 된다. 증가하는 부분 수열은 순서를 유지한 채로 고른 오름차순을 의미하며 예를 들면 3 5 6, 1 4, 2 6 등이 있다.
1. 아이들 수를 입력 받아 정수형태로 N에 저장한다.
2. N줄 입력을 받아 아이들의 번호를 하나씩 읽어서 리스트 arr에 저장하는 것을 0부터 N-1번까지 반복한다.
3. 길이 N인 리스트 dp를 만들고, 모든 값을 1로 초기화한다. dp[i]는 arr[i]를 마지막 원소로 하는 증가하는 부분 수열의 최대길이를
의미한다. ( 처음에 1로 초기화하는 이유는 어던 원소 arr[i]도 자기자신 하나만으로 증가하는 부분 수열 만들 수 있기 때문)
4. i번째 아이를 마지막 원소로 하는 가장 긴 증가하는 부분 수열을 찾는다. 내부 반복 j는 0부터 i-1까지 모든 이전 아이를 확인한다.
5. arr[j] < arr[i] 라면, j번째까지의 LIS에 i번째 아이를 이어 붙일 수 있다. dp[i]는 dp[i]와 dp[j] + 1 중에서 큰 값을 선택한다.
6. dp리스트에서 가장 큰 값을 찾아서 lis_length에 저장한다. 이 값이 가장 긴 증가하는 부분 수열의 길이이다.
7. 최소 이동 횟수 = N - lis_length 이므로 이 결과 값을 출력한다.
문제
N-퍼즐은 많은 다양한 형태와 이름이 있다. 이번 문제에서 우리가 살펴볼 것은 15-퍼즐이다.
15-퍼즐은 4*4보드에서 움직일 수 있는 정사각형으로 이루어져 있고, 한 정사각형은 빠져있다. 정사각형은 A부터 O까지 이름이 붙여져 있다. 이 퍼즐을 풀면 다음과 같은 그림이 된다.
| A | B | C | D |
| E | F | G | H |
| I | J | K | L |
| M | N | O | . |
우리는 이러한 15-퍼즐에서 흩어짐 정도를 계산할 수 있다. 흩어짐 정도는 각 정사각형의 현재 위치와 퍼즐을 풀었을 때의 위치와의 거리의 합이다.
두 정사각형의 거리는 그 두 정사각형 사이의 맨해튼 거리이다.
15-퍼즐이 주어졌을 때, 흩어짐 정도를 계산하는 프로그램을 작성하시오.
입력
4줄에 걸쳐 현재 퍼즐의 상태가 주어진다.
def solve():
letters = "ABCDEFGHIJKLMNO"
total = 0
for r in range(4):
line = input().strip() # 줄 전체 읽기
row = list(line) # 한 글자씩 분리해서 리스트로 만들기
for c, tile in enumerate(row):
if tile == ".":
continue
idx = letters.index(tile)
gr, gc = divmod(idx, 4)
total += abs(r - gr) + abs(c - gc)
print(total)
if __name__ == "__main__":
solve()
1. letters는 정답 퍼즐에서 각 타일의 순서를 나타내며, 흩어짐 정도를 나타내는 변수 total의 초기값을 0으로 한다.
2. 퍼즐이 4줄이므로 range(4)이고 다음을 4번 반복한다. (r은 현재 위치의 행 번호이다)
3. 입력 퍼즐의 각 줄을 한줄씩 읽는다. 그 후 list()로 각 줄을 쪼개서 문자 4개의 리스트로 만든다.
4. c는 현재 위치의 열 번호이다. tile은 현재 타일을 나타낸다. 현재 줄의 각 칸을 왼쪽에서 오른쪽으로 확인한다.
enumerate()를 사용하면 인덱스와 값을 동시에 얻을 수 있다.
5. 만약 타일이 " . "이면 넘어간다.
6. index()로 현재 타일이 "ABCDEFGHIJKLMNO"에서 몇번째인지 찾는다.
7. gr, gc는 각각 목표 행 번호(goal r), 목표 열 번호(goal c)을 나타낸다. idx는 타일이 정답 퍼즐에서 몇번째 위치에
있어야 하는지(0부터 시작)를 나타낸다.
8. divmod(idx, 4)는 (idx // 4, idx % 4)와 같은 뜻이다. 몫은 목표 행 번호(row)이고, 나머지는 목표 열 번호(col)이다.
9. 맨해튼 거리를 구하는 방법은 | 현재 행 - 목표 행 | + | 현재 열 - 목표 열| 이다. abs()가 절댓값(abbsolute value)을 구하는 함수이다.
이렇게 구한 값을 total에 누적시켜서 전체 흩어짐 정도를 구한다.
10. 최종 total을 출력한다.
+) if __name__ == "__main__":
위의 조건문은 이 파일이 직접 실행될 때만 안쪽 코드를 실행하라는 뜻이다. (파이썬의 관용적 패턴)
보통 다음과 같이 사용한다.
def solve():
# 문제 풀이 코드
if __name__ == "__main__":
solve()- 직접 python myfile.py 실행하면 solve()가 실행되고, 다른 파일에서 import myfile 하면 solve()가 자동 실행되지 않는다.
필요한 이유
- 재사용성: 나중에 다른 코드에서 이 파일을 import 해서 solve()만 호출 할 수 있다.
- 불필요한 실행 방지: import 할 때는 solve()가 실행되면 안되니까 조건으로 막는 것이다.
'SWLUG(2025) > Algorithm' 카테고리의 다른 글
| [2학기 1주차] 새싹, 공 넣기 (0) | 2025.09.15 |
|---|---|
| [SV 8주차] 문자 인식, 전화번호 목록, 시간 관리하기 (4) | 2025.08.27 |
| [SV 6주차] 새, 초콜릿 자르기, 직사각형에서 탈출 (2) | 2025.08.12 |
| [SV 5주차] 숫자 문자열과 영단어, 소수 찾기, n진수 게임 (4) | 2025.08.12 |
| [SV 4주차] 약수의 개수와 덧셈, 콜라츠 추측, 멀리 뛰기 (2) | 2025.08.12 |