06. 온보딩 알고리즘 사전스터디 1일차

코이그·2023년 3월 6일

OT

오후 3시에 30분 가량 OT를 진행했고 팀을 배정받았다. 팀장이 되었다. 5명이서 팀이 되었는데 다들 적극적으로 참여해주셔서 다행이다. 간단한 자기소개 후 온보딩 노션 페이지를 한 번씩 훑어보고 어떤 방식으로 스터디모임을 진행할 지 정하고 바로 페어 프로그래밍에 들어갔다.

페어 프로그래밍

페어 프로그래밍: 동료/쌍/짝 프로그래밍.

네비게이터: 전략 제시
드라이버: 전략을 토대로 코드 작성

매일 번갈아가며 위 두 역할로 나뉘어 코드를 구현하는 방식이다. 팀에 구성원이 한 명 더 있다면 스펙테이터(관전 / 의견 제시)의 역할이 추가된다.
우리 조는 5명이었기 때문에 1팀(2인), 2팀(3인)으로 나눠서 진행했는데 나는 1팀이어서 네비게이터/드라이버 역할을 번갈아가며 1일차 5문제를 풀었다.

문제풀이

백준 문제. 1일차에는 난이도 하 문제2, 난이도 중하 문제3으로 총 5문제로 이루어져있다. 1, 3, 5번 문제들은 네비게이터, 2, 4번 문제들은 드라이버로 진행했다.

1. 설탕 배달

처음에는 단순하게 '목표 킬로그램수를 5로 나눈 나머지가 3이 아니면 -1, 3이면 5로 나눈 몫 + 1' 방식으로 접근했다.
일단 문제에 대한 이해가 조금 부족했던 것 같다. 어떻게든 목표 킬로수를 맞춰야 했다.
다음으로 생각했던 방법은 5로 나눈 나머지를 3 뿐 아니라 1, 2, 4의 경우도 고려했다.

나머지가 2인 경우의 예시: 7, 12, 17, 22 등.
나머지가 4인 경우의 예시: 9, 14, 19, 24 등.

잘 생각해보니 나머지가 2인 경우에는 7을 제외하면 5의 배수와 3의 배수인 12로 구성된다.

예) 12(3의 배수), 17(5+12), 22(10+12)

해결방법: 목표 킬로그램수에서 12(3의 4배수)를 빼고 5로 나눈 몫에 4(12는 3의 4배수)를 더했다.

나머지가 4인 경우도 똑같다. 4와 9를 제외하면 5의 배수와 3의 배수인 9로 구성된다.

예) 14(5+9), 19(10+9), 24(15+9)

해결방법: 목표 킬로그램수에서 9(3의 3배수)를 빼고 5로 나눈 몫에 3(9는 3의 3배수)을 더했다.

total = int(input())

five = total / 5

if total % 5 == 3 or total % 5 == 1:
    print(int(five + 1))
elif total % 5 == 0:
    print(int(five))
elif total % 5 == 2 and total != 7:
    print(int((total - 12) / 5 + 4))
elif total % 5 == 4 and total != 4 and total != 9:
    print(int((total - 9) / 5 + 3))
else:
    if total % 3 == 0:
        print(int(total / 3))
    else:
        print(-1)

2. 베르트랑 공준

입력한 숫자 N과 2N 사이의 소수의 갯수를 구하는 문제다. 사실 구현 자체는 어렵지 않았는데 시간 초과로 통과는 못했다.

1차 시도: 제일 단순한 방법일텐데 N+1부터 2N까지 반복문(1중)을 돌며 각 숫자를 2에서 N/2를 반복(2중)하며 나누었을 때 나머지가 0이라면 소수가 아니기 때문에 2중 반복문을 break; 2중 반복문을 break 없이 끝까지 돌았다면 소수이기 때문에 카운트 증가.

위 방법이 맞는 로직이긴 하지만 요구하는 입력값이 1에서 123,456 사이라 큰 숫자에 한해서 2중 반복문을 돌게 되면 시간이 엄청 오래 걸리기 때문에 시간 초과로 통과 실패.

2차 시도: 어떻게든 2중 반복문을 쓰고 싶지 않아서 생각해낸 방법이다. 1중 반복문은 어쩔 수 없이 돌아야 하지만, 각 숫자에 한해서 2~N/2 반복을 거치지 않을 수 있다. 몇 가지 필터로 걸러내는 작업을 진행했다.

N이 2, 3, 5, 7로 나누어 떨어지는가
N의 루트가 정수인가

root = n ** (1/2)               # 루트 구하는 법
if root - int(root) ==(!=) 0:   # 정수인지 확인하는 법

하지만 위 처럼 했을 때 걸러지지 않는 숫자들이 있었는데 소수가 배수인 숫자들이었다. 예를 들면 143(13*11). 143의 유이한 배수가 모두 소수이기 때문에 위의 어떤 필터에도 걸러지지 않는다.

이 문제는 내일 페어를 만나서 다시 생각해보기로 했다.

3. 달팽이는 올라가고 싶다

1차 시도: 가장 단순한 방법으로,
1. d(이동 거리) 변수가 v(목표치)보다 크거나 같은 지 확인하며 while 반복문을 돌면서
2. 바로 count(일 수) 증가.
3. 그 후 a만큼 더해주고 v와 크거나 같은 지 한번 더 체크
4. 맞다면 break, 아니면 b만큼 빼기.

위 과정대로 반복문을 돌면 원하는 답이 나온다.
매우 단순하지만 2번과 같이 입력값으로 큰 수가 들어오면 역시 시간초과로 통과하지 못한다.

이 문제 역시 내일 다시 생각해보기로 했다.

문제의 길이가 가장 길어서 처음에는 쫄았지만 읽었을 때 딱히 이해되지 않을 정도로 어려운 문제는 아니었다. 개인적으로 드라이버로 코딩을 하면서 한 수 배운 문제였다.
원래 내가 생각한 방식은 2차원 배열을 정의해서 값을 일일히 채워넣는 것이었다. 하지만 페어(네비게이터)가 제시하신 의견대로 진행했는데, 처음에는 사실 이게 맞나 라는 생각이 들었다. 배열이나 반복문 등이 아닌 단순 연산으로 해결하는 방법이었기 때문이다. 디테일한 부분은 내가 수정을 좀 하긴 했지만 전체적인 로직 자체는 백준 기준에 통과했다.

t = int(input())

for i in range(t):
    h, w, n = input().split()
    h = int(h)
    w = int(w)
    n = int(n)

    x = n % h
    y = n / h

    if x == 0:
        x = h
        print(x * 100 + int(y))
    else:
        print(x * 100 + int(y) + 1)