알고리즘 테스트 벼락치기 (기본문제)

백준 17269, 이름 궁합 테스트

N, M = map(int, input().split())
A, B = input().split()

num_alphabet = [3,2,1,2,4,3,1,3,1,1,3,1,3,2,1,2,2,2,1,2,1,1,1,2,2,1]

new_name = ''  # 알파벳 궁합 이름
min_len = min(N, M)

for i in range(min_len):
    new_name += A[i] + B[i]
new_name += A[min_len:] + B[min_len:]

# ord() 아스키 코드를 활용한 것이 관건
ascii_name = [num_alphabet[ord(i)-ord('A')] for i in new_name]  # 획수 궁합 이름

# 풀이1 또는 풀이2 선택
# 풀이1 ########################
for i in range(N + M - 2):
    for j in range(N + M - 1 - i):
        ascii_name[j] += ascii_name[j + 1]
        ascii_name[j] %= 10
# 풀이2 ########################
while len(ascii_name) > 2:
    for i in range(len(ascii_name) - 1):
        ascii_name[i] = (ascii_name[i] + ascii_name[i + 1]) % 10
    ascii_name.pop()
################################

print(f'{10 * ascii_name[0] + ascii_name[1]}%')

• 획수는 직접 리스트를 만들어서 기입하는 것이 빠름
• 풀이 방법 : 알파벳으로 된 이름 궁합을 먼저 만들고(new_name), 아스키 코드(ord())를 통해 알파벳과 획수를 대응 시켜서 획수로 바꿈. 그 후 문제에 주어진 대로 계산. 

---

백준 17389, 보너스 점수

N, S = input(), input()

score, bonus = 0, 0

for i, ox in enumerate(S):
    if ox == 'O':
        score += i + 1 + bonus
        bonus += 1
    else:
        bonus = 0

print(score)

• 풀이 방법 : 문제의 점수가 문제의 번호와 같기 때문에 enumerate() 함수를 생각할 수 있음. 실제 점수(score)와 보너스 점수(bonus)를 각각 생각해서 계산 가능

---

백준 1920, 수 찾기

N = int(input())
A = {i : 1 for i in map(int, input().split())}
M = int(input())
A_ = list(map(int, input().split()))

for num in A_:
    # 풀이1 or 풀이2
    # 풀이1 ################
    print(A.get(num, 0))
    # 풀이2 ################
    print(1 if num in A else 0)

• 딕셔너리.get(x, y) >> Key 값(=x)에 대응하는  Value를 반환하고, 수가 존재하지 않으면 y를 반환함
• 풀이 방법 : A_는 마지막 줄 입력 값임. A를 모든 value가 1인 딕셔너리로 정의해주고, get() 함수를 사용해서 A_ 리스트에 있는 값이 A에 존재하면 value인 1을 반환하게 하고 없으면 0을 반환하게 함.

---

백준 16165, 걸그룹 마스터 준석이

N, M = map(int, input().split())

team2member = {}
member2team = {}

for i in range(N):
    team = input()
    num_member = int(input())

    team2member[team] = []
    for j in range(num_member):
        member = input()
        
        team2member[team].append(member)
        member2team[member] = team

for i in range(M):
    quiz = input()
    team_or_member = int(input())

    if team_or_member:
        print(member2team[quiz])
    else:
        for mem in sorted(team2member[quiz]):
            print(mem)

• 풀이 방법 : 퀴즈 종류가 2개, 즉 팀명을 주면 멤버들 이름을(team2member), 멤버 이름을 주면 팀 이름을(member2team) 맞춰야 하기 때문에 2개의 딕셔너리를 우선 만들었다. 예를 들면, team2member = {twice : [sana, jihyo, ... ], ... }, member2team = {sana : twice, jihyo : twice, ... }로 만듬. 두 번째 for문에서는 퀴즈 조건에 맞게 딕셔너리에서 value 값을 불러오게 했다.

---

백준 17224, APC는 왜 서브태스크 대회가 되었을까?

N, L, K = map(int, input().split())

easy, hard = 0, 0

for i in range(N):
    sub1, sub2 = map(int, input().split())

    if sub2 <= L:
        hard += 1
    elif sub1 <= L:
        easy += 1

# hard
score = min(hard, K) * 140
# easy
if hard < K:
    score += min(easy, K-hard) * 100

print(score)

• 풀이 방법 : 현정이가 푼 쉬운 문제에 100 곱하고 어려운 문제에 140을 곱하는게 관건. for문을 통해서 쉬운 문제와 어려운 문제 개수를 구함. 그리고 마지막에 점수를 곱해서 더함. L과 K의 조건을 min함수와 if문의 대소 관계로 해결하는 것이 중요. (어려운 문제가 풀 수 있는 문제면 먼저 풀기 때문에, K개 중 어려운 문제를 먼저 계산하고 나머지는 쉬운 문제로 취급해서 점수를 계산했음)

---

백준 9037, The candy war

N = int(input())

for _ in range(N):
    num_child = int(input())
    candy = list(map(int, input().split()))

    cnt = 0
    while True:
        candy = [c + 1 if c % 2 else c for c in candy]
        if len(set(candy)) == 1:
            print(cnt)
            break
        candy = [candy[i] // 2 + candy[(i + 1) % num_child] // 2 for i in range(num_child)]
        cnt += 1

• 풀이 방법 : 아이들이 가지고 있는 사탕의 개수가 서로 같으면, 반 씩 주고 받는 사탕의 개수도 같음. 따라서 i번 째 사탕 반 개랑 i + 1번 째 사탕 반 개를 더 한 것이 같은 지를 보면 됨. 

---

백준 16956, 늑대와 양

R, C = map(int, input().split())
M = [list(input()) for i in range(R)]

dx, dy = [0, -1, 0 ,1], [1, 0 ,-1, 0]
check = False

for i in range(R):
    for j in range(C):
        if M[i][j] == 'W':
            for w in range(4):
                i_, j_ = i + dx[w], j + dy[w]
                if i_ < 0 or i_ == R or j_ < 0 or j_ == C:
                    continue
                if M[i_][j_] == 'S':
                    check = True

if check:
    print(0)
else:
    print(1)
    for i in range(R):
        for j in range(C):
            if M[i][j] not in 'SW':
                M[i][j] = 'D'

for i in M:
    print(''.join(i))

• 풀이 방법 : 늑대 기준으로 동서남북에 양이 없으면 울타리 쳐버리기 ( 울타리 최소 개수를 구하는게 아니므로 가능)
• dx, dy는 방향 벡터를 나타내기 위함. 동북서남(ENWS) 순으로 벡터를 만들었음. 

---

백준 14620, 꽃길

N = int(input())
G = [list(map(int, input().split())) for i in range(N)]

dx, dy = [0, 0, -1, 0, 1], [0, 1, 0, -1, 0]
cost = 10000

def func(case):
    cost = 0
    flower = []
    for f in case:
        x = f // N
        y = f % N
        if x == 0 or x == N - 1 or y == 0 or y == N - 1:
            return 10000
        for way in range(5):
            flower.append((x + dx[way], y + dy[way]))
            cost += G[x + dx[way]][y + dy[way]]

    if len(set(flower)) != 15:
        return 10000
    return cost

for i in range(N * N):
    for j in range(i + 1, N * N):
        for k in range(j + 1, N * N):
            cost = min(cost, func([i, j ,k]))

print(cost)

• 문제 풀이 : i, j, k는 꽃 3개의 경우의 수를 볼 것임. (0, 0) ~ (N, N)의 배열을 0 ~ (N * N - 1)로 볼 것임. 즉, (0, 0), (0, 1), (0, 2) 순으로 생각하지 않고 0, 1, 2 순으로 생각할 것. 최대 비용은 200 * 5 = 10000 이므로 10000을 기준으로 min함수를 이용해 대소관계를 비교해서 최솟값을 구할 것임. func()함수에서는 flower 리스트에 꽃이 차지한 좌표를 넣어서 5 * 3 = 15개의 좌표를 차지하는지 확인할 것이고, cost 값으로 최솟값을 구함.

---

백준 1012 , 유기농 배추 (Flood fill)

import sys
sys.setrecursionlimit(10000)

T = int(input())
A, ck = [], []


dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]


def dfs(x, y):
    global A, ck
    
    if ck[x][y] == 1:
        return 

    ck[x][y] = 1
    for i in range(4):
        xx, yy = x + dx[i], y + dy[i]
        if A[xx][yy] == 0 or ck[xx][yy] == 1:
            continue
        dfs(xx, yy)


def process():
    global A, ck

    M, N, K = map(int, input().split())
    A = [[0 for _ in range(M + 2)] for _ in range(N + 2)]
    ck = [[0 for _ in range(M + 2)] for _ in range(N + 2)]

    for _ in range(K):
        X, Y = map(int, input().split())
        A[Y + 1][X + 1] = 1

    ans = 0
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            if A[i][j] == 0 or ck[i][j] == 1:
                continue
            dfs(i, j)
            ans += 1
            
    print(ans)


for _ in range(T):
    process()

 

 

• (M,N)의 배열에 0으로 패딩을 줌 >> (M + 2, N + 2) => 모서리 부분에 인접한 배추 계산 방법을 고려함
•