재밌는 코딩 공부

https://www.acmicpc.net/problem/10825

나의 풀이 by python

n = int(input())
data = []

for i in range(n):
    name, a, b, c = input().split()
    a, b, c = int(a), int(b), int(c)
    data.append([a, b, c, name])

data = sorted(data, key = lambda x : (-x[0], x[1], -x[2], x[3]))

for i in range(n):
    print(data[i][3])

해당 문제는 여러가지 값을 정렬로 이용해야 할 때 유용하게 사용할 수 있는 예제이다. 

이것이 코딩 테스트이다 답안

n = int(input())
students = [] # 학생 정보를 담을 리스트

# 모든 학생 정보를 입력받기
for _ in range(n):
    students.append(input().split())


students.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

# 정렬된 학생 정보에서 이름만 출력
for student in students:
    print(student[0])

누적합

합들의 값을 미리 더해두는 것을 누적 합이라고 한다.

누적합의 예

A = [i for i in range(10)]
print(A)
for i in range(1, 10):
	A[i] = A[i-1] + A[i]
print(A)

DP[i] = i까지 합

i부터 j까지의 합은 DP[i] - DP[j-1]

<구현으로 인한 풀이>

n, m = map(int, input().split())
lst = [[0 for _ in range(m+1)] for _ in range(n+1)]

for i in range(1, n+1):
    tmp = list(map(int, input().split()))
    for j in range(1, m+1):
        lst[i][j] = tmp[j-1]

k = int(input())
k_lst = [list(map(int, input().split())) for _ in range(k)]
result = []

for u in range(k):
    a,b,x,y = k_lst[u][0], k_lst[u][1], k_lst[u][2], k_lst[u][3]
    sum = 0
    for i in range(a,x+1):
        for j in range(b, y+1):
            sum += lst[i][j]
    result.append(sum)

for i in range(len(result)):
    print(result[i])

<DP를 활용한 풀이>

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
# DP[i][j] = 1, 1부터 (i, j)까지의 부분합
DP = [[0 for i in range(M+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1]
        
for _ in range(int(input())):
    i, j, x, y = map(int, input().split())
    print(DP[x][y] - DP[i-1][y] - DP[x][j-1] + DP[i-1][j-1])

https://www.acmicpc.net/problem/17224

<해당 문제의 나의 풀이>

N, L, K = map(int, input().split())
subtask = []
score = 0
count = 0

for i in range(N):
    sub1, sub2 = map(int, input().split())
    subtask.append([sub1, sub2])
    
subtask.sort(key=lambda x:x[1])

for lst in subtask:
    if count >= K:
        break
    sub1, sub2 = lst[0], lst[1]
    if L >= sub1:
        score += 100
        count += 1
    if L >= sub2:
        score += 40
    
print(score)

<해설>

위 문제의 핵심은 2차원 배열을 정렬하여야 한다는 것입니다. 왜냐하면, 해당 문제의 최대 풀 수 있는 문제 수가 정해져 있습니다. 그런데, 역량이 부족하여 2번째 어려운 보너스 부분 점수를 못 받는 문제를 먼저 풀어버리면 문제 풀이 수가 증가하여 최대한 받을 수 있는 점수가 줄어들게 됩니다. 따라서 최대한 많은 점수를 얻기 위해서는 어려운 문제 기준으로 정렬을 수행하여야 합니다.

<람다식을 통해 2차원 배열의 2번째 요소로 정렬하는 방법>

subtask.sort(key=lambda x:x[1])

https://www.acmicpc.net/problem/1920

백준 문제를 풀면서 위 문제를 풀 수 있는 흥미로운 방법을 찾아내어 기록합니다.

위 문제를 처음 봤을 때 저의 풀이입니다.

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

for ele in lstM:
    if ele in A: 
        print(1)
    else:
        print(0)

해당 문제를 해결하기 위해서 in 을 활용하였습니다.

위 방식은 심플하고 좋아보이지만 python3으로 해결하려고 하면 시간초과가 발생합니다. (하지만 pypy3은 괜찮아요)

이번에는 패스트캠퍼스 강의를 통해서 알게된 풀이 방식입니다.

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

for i in range(M):
	print(A.get(B[i],0))

위 문제의 핵심은 딕셔너리를 활용하는 것입니다. 입력 받을 때 {} 안에 for 문을 활용하여 입력값들을 딕셔너리로 받습니다. 그리고, get함수를 통해서 첫번째 인자 값이 존재하지 않는다면 2번째 인자 값을 반환하도록 합니다.

위와 같은 방식으로 딕셔너리를 활용하여 코딩할 수 있습니다.

이번에 이것이 코딩 테스트에서 문자열 압축 문제를 풀었고 해당 문제는 프로그래머스의 문제였다.

https://programmers.co.kr/learn/courses/30/lessons/60057 

해당 문제를 거의다 풀어갈 때, 나머지를 어떻게 더할 것인가에 대한 고민이 생겼다.

고민을 하던중 알게된 것이 아래의 코드이다.

s = 'abcdefg'
print(s[4:100])

결과

efg

해당 결과를 보기전까진 [:] 에서 오른쪽 숫자는 문자열 길이를 초과해서는 안될 것이라는 생각이 있었는데 넘어가도 최대 값 이상 안넘어가며 오류또한 나타나지 않는 결과를 얻었다. 

다시말해, 값이 초과하여도 상관이 없기 때문에 for문을 끝까지 돌려도 된다는 것이다.

아래 코드는 이코테 답안이다.

def solution(s):
	answer = len(s)
    # 1개 단위(step)부터 압축 단위를 늘려가며 확인
    for step in range(1, len(s) // 2 + 1):
    	compressed = ""
        prev = s[0:step] # 앞에서부터 step만큼의 문자열 추출
        count = 1
        # 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
        for j in range(step, len(s), step):
        	# 이전 상태와 동일하다면 압축 횟수(count) 증가
            if prev == s[j:j + step]:
            	count += 1
            # 다른 문자열이 나왔다면(더 이상 압축하지 못하는 경우라면)
            else:
            	compressed += str(count) + prev if count >= 2 else prev
                prev = s[j:j + step] # 다시 상태 초기화
                count = 1
         # 남아 있는 문자열에 대해서 처리
         compressed += str(count) + prev if count >= 2 else prev
         # 만들어지는 압축 문자열이 가장 짧은 것이 정답
         answer = min(answer, len(compressed))
	return answer

알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다. 

<나의 풀이>

s = input()

charList = []
numList = []

for i in range(len(s)):
    if ord(s[i]) >= 65:
        charList.append(s[i])
    else:
        numList.append(s[i])

charList.sort()
numList.sort()

for i in range(len(charList)):
    print(charList[i], end='')
for i in range(len(numList)):
    print(numList[i], end='')

해당 문제는 문자의 크기를 비교하고 해당 문자가 숫자인지 알파벳인지 구별해야한다.

- 문자의 크기를 비교하여 정렬하는 것은 sort()함수를 호출하면된다.

- 해당 문자가 숫자인지 알파벳 인지는 ord(s[i]) >= 65를 이용하여 구할수 있다.

65이상 값이 알파벳으로 분류되는 것은 A의 아스키 코드 값이 65이기 때문이다.

앞으로도 종종 알파벳인지 숫자인지 구별할 필요가 있을 것으로 생각되므로 ord(s[i]) >= 65 조건을 기억해두자

볼링공 고르기

A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고 공의 번호는 1번부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다.

입력조건 

  - 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다.

(1 <= N <= 1000, I <= M <= 10)

  - 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.

<나의 답안>  

# 볼링공 고르기 p.315
from itertools import combinations

if __name__ == '__main__':
    n, m = map(int, input().split())
    arr = list(map(int,input().split()))
    numArr = [0]*n
    for i in range(n):
        numArr[i] = i+1

    comArr = list(combinations(arr,2))
    result = 0
    for i in comArr:
        if i[0] != i[1]:
            result +=1
    print(result)

<나의 답안 해설>

위의 문제는 2사람이 볼링공을 고르는 경우의 수를 출력하면된다. 하지만, 한 가지 조건이 있다. 

2명의 사람은 서로 무게가 다른 볼링공을 골라야 한다. 

따라서 2명(2개의 수의조합)을 토대로 combination으로 순서 변경없는 조합의 수를 찾아냈다. 

그다음에 2개의 값이 같으면 for문에서 값을 더하지 않는 식으로 해결하였다. 

<정답>

# 볼링공 고르기 p.315
if __name__ == '__main__':
    n, m = map(int, input().split())
    data = list(map(int, input().split()))
    
    # 1부터 10까지의 무게를 담을 수 있는 리스트
    array = [0] * 11
    
    for x in data:
        # 각 무게에 해당하는 볼링공의 개수 카운트
        array[x] += 1
        
    result = 0
    # 1부터 m까지의 각 무게에 대하여 처리
    for i in range(1, m+1):
        n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
        result += array[i] * n # B가 선택하는 경우의 수와 곱하기
    
    print(result)

정답의 경우 정답을 보면 명쾌해 질 줄 알았는데 쉽지 않다고 느끼게 되는 것 같다. 

모험가 길드 문제는 공포도가 x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있습니다.

첫째줄에 n이 주어지고 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어집니다.

모든 모험가를 특정한 그룹에 넣을 필요는 없습니다.

여행을 떠날 수 있는 그룹 수의 최대값을 구하는 프로그램을 작성하세요.

<나의 풀이>

from collections import deque

if __name__ == '__main__':
    n = int(input())
    list1 = list(map(int, input().split()))
    list1.sort(reverse=True)
    arr = deque(list1)
    result = 0

    while arr:
        x = arr[0]

        if x <= len(arr):
            for i in range(x):
                arr.popleft()
        else:
            break
        result += 1

    print(result)

나의 풀이는 잘못 되었습니다. 해당 알고리즘은 그리디가 적용되어야 됩니다. 하지만 저는 가장 공포도가 높은 모험가를

먼저 파티에 넣는 식으로 하였기 때문에 그룹의 수는 가작 적은 그룹의 수가 리턴 될 것입니다. 그것을 알고도 위와같은 알고리즘을 사용한 것은 가장 큰 값을 기준으로 해야 나중에 뒤에서 더 큰 공포를 가진 모험가가 나타나서 위 조건을 이탈하는 케이스를 생각했기 때문입니다.

아래는 정답입니다.

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수

for i in data: # 공포도를 낮은 것부터 하나씩 확인하며
	count += 1
    if count >= i:
    	result += 1
        count = 0

정답을 보면 if count >= i:

라는 조건이 있습니다. 해당 조건 덕분에 뒤에서 갑자기 공포도가 큰 모험가가 포함 되어도 공포도가 x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날수 있는 조건을 만족할 수 있습니다.

https://www.acmicpc.net/problem/10870

n = int(input())
d = [0]*(n+1)
if n > 0:
    d[1] = 1

if n >= 2:
    for i in range(2, n+1):
        d[i] = d[i-1] + d[i-2]
print(d[n])

n이 0일 경우 dp[1]은 index out of bound 에러가 발생하기 때문에 조건문을 활용해야 한다.

https://www.acmicpc.net/problem/2839

설탕 배달은 DP와 그리드 방식으로 해결 가능합니다. 사실 시간이 적다면 그리드 방식이 좋을 수 있지만

해당 문제는 DP 문제로 분류되어있으니 DP 방식으로 풀도록 하겠습니다.

해당 문제의 점화식입니다.

min(dp[j], dp[j-arr[i]] +1)

해당 문제의 풀이입니다.

n = int(input())
arr = [3, 5]
dp = [5001]*(n+1)
dp[0] = 0

for i in range(len(arr)):
    for j in range(arr[i], n+1):
        if dp[j - arr[i]] != 5001:
            dp[j] = min(dp[j], dp[j-arr[i]] +1)
if dp[n] == 5001:
    print(-1)
else:
    print(dp[n])

동적 계획법 방식중에서도 다운 - 탑 방식을 선택했습니다.

DP의 크기는 N+1의 크기로 생성합니다.

DP의 0번째 인덱스의 값은 0으로 생성하고 나머지는 5001의 값을 넣습니다.

5001의 값을 넣은 이유는 5001 값이 가장 최고 값이 될 것이기 때문입니다.

설탕 봉투의 키로 수는 3KG, 5KG 가 있습니다.

따라서 작은 설탕 봉투 3KG를 먼저 DP에값을 채워 넣습니다.

그다음에 5KG 봉투를 채워 넣습니다.

5키로 봉투를 채워 넣을 때 만약 현재 인덱스가 8이면 

8에는 5001의 값이 들어가 있을 것입니다.

8일 때 DP [8-5]의 값을 확인할 것이고 확인된 값은 DP [3] = 1 일 것입니다.

값을 비교하게되면 min(5001, 2)가 될 것이고 2의 값이 들어가게 될 것입니다.

위와 같은 방식으로 해당 인덱스의 가장 작은 수가 값으로 들어올 것입니다.