정글 TIL 6(01.17) "RE-zero부터 시작하는 알고리즘"

김동준·2024년 1월 17일

알고리즘

목록 보기

10/11

현 상황에 대한 소고

현재 알고리즘 학습 과정에서 문제가 생겼다. 고등학교 때 수학을 공부하던 식으로 알고리즘 문제를 중심으로 과정을 이해하고 그 코드를 외우는 식으로 공부를 해왔는데, 마음만 급하고 현재 남는 게 없다. 나의 생각을 컴퓨터 언어(파이썬)으로 구현하는 것이 힘들다. 예를 들어 배열 방식으로 숫자를 받아야 할 때 어떻게 코드를 작성해야 할지 모르겠으며, int(input(""))과 같은 기초적인 코드밖에 할 줄 모르겠다. 이를 배열로 전환하려면 또 한 줄의 코드가 필요하고, 코드가 점점 늘지 않겠는가. 또한 응용도 안되고 결과값에 대한 예측이 안된다. (참고로 arr = [int(x) for x in input().split()])

정글에서의 1주차는 "컴퓨팅 사고로의 전환"인데, 완전히 실패한 것이다. 이에 방식을 달리하려 한다. 일단 문법 다시 공부해야겠다. 2주차부터는 더 심화된 알고리즘 문제를 풀어야하지만, 남들보다 늦더라도 뒤쳐지더라도 현 문제점을 정확히 짚고 이를 해결하는 것이 중요하니까. 쓰이는 코드에 담긴 문법에 관한한 반드시 이해하고 정리하겠다.

현재 계획은 기초 문법 숙달을 할 것인데, 코드의 출력문을 쉬운 것부터 예측하며 데이터가 어떻게 변환하는지를 놓치지 않으려 한다.
이후 알고리즘 쉬운 문제들로 반복, "쓰이는 문법" 정리, 의사 코드 작성 연습이 최우선 과제이다. 이것들을 '확실히'하는 것이 목표다.

EOFError 처리 방법

a = input()과 같은 코드를 작성했을 때, 백준에서 런타임 에러(EOFError)의 에러 코드를 자주 만나게 될 것이다. 이 문제는 백준 채점 프로그램에서 여러 줄을 입력받는 유형의 문제에서는 입력의 마지막에 파일의 끝을 알리는 입력이 들어옵니다. 그런데 이때 except EOFError:로 예외 처리를 하지 않으면 더 이상 입력 받을 것이 없는데도 계속 루프가 돌기 때문에 런타임 에러가 발생하는 것이다. 한마디로 채점프로그램이 입력되는 값의 끝을 모른다면 무한 루프에 빠지게 되는 것입니다.
이를 해결하기 위해 try: execpt문을 활용하여 끝을 알려주어야 한다.

while True:
    try:
        # 문자열 입력
        # 결과 출력
    except EOFError:
        break

출처 : https://www.acmicpc.net/board/view/39199

input() 함수

input() 함수는 사용자가 키보드로 입력한 모든 것을 문자열로 저장한다. 입력되는 모든 것을 문자열로 취급하기 때문에 출력물이 문자열이다.
한 줄에 결과값을 계속 이어서 출력하려면, 매개변수 end를 이용해 끝 문자를 지정해야 한다. 큰 따옴표 대신 작은 따옴표(''), 작은 따옴표 세 개('''...'''), 큰 따옴표 세 개("""...""")를 사용해도 된다.

숫자를 입력하세요:3
print(number)
3
type(number)
<class 'str'>

for i in range(10):
	print(i end=' ')

split() 함수

split()는 문자열.split(), 문자열.split('구분자', '분할 횟수')로 사용 가능하다. 문자열을 maxsplit 횟수 만큼 구분자를 기준으로 문자열을 구분하여 잘라 리스트텍스트로 만들어준다.

s = "a b c d e"
print(f'string : {s}')
> string : a b c d e
r = s.split()
print(r)
> ['a', 'b', 'c', 'd', 'e']

파라미터를 아무것도 사용하지 않으면 띄어쓰기, 엔터를 구분하여 문자열을 나누게 된다. 또한 maxsplit 파라미터를 정해주지 않았기 때문에 나눌 수 있을 때까지 나눈다.

map() 함수

map() 함수는 map(function, iterable)의 형식으로 첫번째 매개변수로는 함수가 오고, 두 번째 매개변수로는 반복 가능한 자료형(리스트, 튜플 등)이 온다. map 함수의 반환 값은 map 객체이기 때문에 해당 자료형은 list 혹은 tuple로 형을 변환시켜주어야 한다.
함수의 동작은 두번째 인자로 들어온 반복 가능한 자료형(리스트나 튜플)을 첫번째 인자로 들어온 함수에 하나씩 집어넣어서 함수를 수행하는 함수이다.

슬라이스식으로 원소에 접근하기

s[i:j]는 s[i]부터 s[j-1]까지 나열한다.
s[i:j:k]는 s[i]부터 s[j-1]까지 k씩 건너뛰며 나열한다.
s[::-1]는 리스트의 s의 원소 중 맨 끝부터 전부 출력한다.

s = [11, 22, 33, 44, 55, 66, 77]
s[0:6]
> [11, 22, 33, 44, 55, 66]
s[0:7]
> [11, 22, 33, 44, 55, 66, 77]
s[0:7:2]
> [11, 33, 55, 77]
s[-4:-2]
> [44, 55]
s[3:1]
> []

result = [1, 2, 3, 4, 5]
def add_one(n):
    return n + 1
result2 = list(map(add_one, result))
print(result2)
print(type(result2))
> [2, 3, 4, 5, 6]
> <class 'list'>

import math
result1 = list(map(int, [1.1, 2.2, 3.3]))
print(f'map(int, 리스트) : {result1}')
map(int, 리스트) : [1, 2, 3]

sum() 함수

sum(iterable, start = 0) 함수는 반복 가능한 자료형을 받으며 numeric해야 한다. 리스트나 튜플처럼 인덱스가 순환 접근이 가능한 자료형이어야 하고, 내부에는 숫자로만 이루어져 있어야 한다.
인자로 들어온 iterable 내부 모든 요소의 합을 반환한다. 두 번째 인자는 default = 0이고, 첫 번째 인자로 들어온 iterable에 두번째 인자까지 더해준다.

> result1 = sum([1,2,3,4,5])
> print(result1)
15
> a = [1, 2, 'python', 4, 5]
> result2 = sum(a)
TypeError: unsupported operand type(s) for +: 'int' and 'str'
> b = (1,2,3,4,5)
> result3 = sum(b)
> result3
15
> c = []
> d = ()
> result4 = sum(c)
> result5 = sum(d)
> print(result4)
0
> print(result5)
0
> result3 = sum([1,2,3,4,5], 11)
> result4 = sum([], 11)
> print(result3)
26
> print(result4)
11

for 문

for 문의 기본 구조는 for 변수 in 리스트(또는 튜플, 문자열): 수행할문장1 ... 이다. 리스트나 튜플, 문자열의 첫 번째 요소부터 마지막 요소까지 차례로 변수에 대입되어 '수행할문장1'... 등이 수행된다.

> for i in test:
>     print(i)
one
two
three

> a = [(1,2), (3,4), (5,6)]
> for (first, last) in a:
>     print(first, last)          
1 2
3 4
5 6

알고리즘 문제 풀이

2588번 곱셈

두 세자리 자연수가 주어질 때 덧셈의 과정을 출력하는 문제이다.
1. 두 세자리 자연수를 문자열로 입력받아 리스트에 자연수를 자릿수 내림차순으로 저장한다.
2. 두번째 자연수 리스트 요소를 맨뒤의 숫자부터 첫번째 자연수 리스트 요소에 반복하여 곱하고 더한 값을 출력한다.
3. 마지막 줄에는 그 모든 값을 더한 값을 출력한다.

풀이

a = int(input()) # 문자열 -> 정수형
b = input() # 문자열
# print(b[-1])
# 문자열도 인덱싱이 가능하다. 맨 뒤는 -0이 아닌 -1이다.


for i in range(3):
    print(a * int(b[-(i+1)])) # 인덱싱한 b의 요소는 아직 문자열이다. 형변환하자

print(a*int(b))

문자열도 배열처럼 인덱싱이 가능하다. 다만 맨뒤의 요소의 인덱스는 -1부터 시작이다.(-0아님), 문자열은 연산하려면 int형으로 반드시 형변환해주자.

각 데이터의 입력 형태, 출력 형태에 조심하자.

1085 직사각형 탈출

정수 x, y, w, h가 주어진다. 직사각형은 각 변이 좌표축에 평행하다. 직사각형의 경계선까지의 최소 거리를 구하는 문제

풀이
직사각형 가로, 세로의 길이에서 x와 y를 빼서 가장 가까운 x와 y좌표를 구한다. 그 뒤 x,y의 크기를 비교해서 가장 가까운 x나 y로 이동한다. 그 차이가 같을시 x로 이동한다.
사실 그럴 필요도 없이 점과 가장 가까운 변의 위치를 찾기만 하면 되기 때문에 min() 함수를 이용하여 가장 가까운 x 혹은 y 좌표를 얻는다.

x, y, w, h = map
print(min(x, y, w-x, h-y))

10950 A+B-3

두 정수 A와B를 입력받은 다음, A+B를 출력하는 문제

풀이
반복할 횟수 N번을 입력받아 for문으로 N번 두 숫자 a,b를 입력받고 그 합을 출력하면 된다.

T = int(input(""))

for i in range(T):
    a, b = map(int, input().split(" "))
    print(a+b)

4344 평균은 넘겠지

C개의 테스트 개수에서 각 테스트 마다 N명의 시험 결과가 주어진다. 이들의 평균을 구하여 시험 결과가 평균을 넘는 비율을 구하는 문제

풀이
주어진 문자열을 리스트로 저장하고, 리스트의 0번째 인덱스를 N명의 시험 결과 갯수로 사용한다. 1번째 인덱스부터 끝까지의 리스트 요소의 합을 구하고 0번째 인덱스로 나눈 평균 점수와 각 요소를 비교하여 평균 이상인 비율을 출력한다.

n = int(input())

for _ in range(n):
    nums = list(map(int, input().split()))
    avg = sum(nums[1:])/nums[0]
    cnt = 0
    for score in nums[1:]:
        if score > avg:
            cnt += 1
    rate = cnt/nums[0] * 100
    print(f'{rate:.3f}%')

내 코드

c = int(input())

for _ in range(c):
    idx = sum = 0
    n = list(map(int, input().split()))
    num = n[0]
    for i in range(num-1):
        sum += int(n[i+1])
    avg = sum / n[0]
    for j in range(num-1):
        if n[j+1] > avg:
            idx += 1
    print(f"{avg}%")

아이디어는 근사하나, sum() 함수를 이용하지 못했다. 슬라이싱도 [1:]로 편하게 할 수 있었을 것을.. 마지막으로 우습게도 / 연산자를 떠올리지 못했다. //이랑 %만 있는줄..
2869번 달팽이는 올라가고 싶다
달팽이는 높이 V미터인 나무 막대를 낮에 A미터 올라갔다가 밤에는 B미터 미끄러진다. 달팽이가 나무 막대를 모두 올라가려면 며칠이 걸리는지 구하는 문제
풀이
올라가는 A미터와 B미터를 한 묶음으로, 그 차인 A-B를 반복하여 더한다. 최초로 V미터를 넘는 인덱스를 구한다. 그 합이 0보다 작다면 정상에 등반한 것으로 판단한다.

A, B, V = map(int, input().split())

x = (V - B) / (A - B) # 여기가 핵심, V - B를 해야 정상에 올랐을 때 끝난다
if x == int(x): # x 가 정수형이라면 나누어 떨어지기 때문에.
    print(int(x))
else: 
    print(int(x) + 1)

N = input().split()
a = int(N[0])
b = int(N[1])
c = int(N[2])
idx = sum = 0

while True:
    sum += (a - b)
    idx += 1
    if c - sum < 0:
        print(idx)
        break

2750 수 정렬하기

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램 작성하기

풀이
퀵 정렬으로 풀이

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

for _ in range(n):
    num = int(input())
    arr.append(num)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    low_arr, equal_arr, high_arr = [], [], []

    for num in arr:
        if num < pivot:
            low_arr.append(num)
        elif num == pivot:
            equal_arr.append(num)
        else:
            high_arr.append(num)

    result = quick_sort(low_arr) + equal_arr + quick_sort(high_arr)

    return result

merged_arr = quick_sort(arr)

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

# for n in merged_arr:
#    print(n)

또 기초 문법에서 막혔다. 마지막 for문으로 merged_arr의 배열의 요소를 출력해야 하는데, 처음엔 for i in merged_arr: print(merged_arr[i])로 작성했는데 계속 인덱스 범위를 벗어났다고 나왔다. 룸메이트에게 물어본 결과 for 문의 작동 원리를 숙지하지 못해서 생긴 결과였다.
내가 작성한 for 문은 merged_arr에서 요소를 하나씩 꺼내서 i로 쓰는데, 배열의 인덱스는 0부터 시작하기 때문에 merged_arr는 1부터 5까지의 숫자기때문에 에러가 발생했다. 이 문제는