[항해99 취업 리부트 코스 학습일지] 제 집중력 훔친 사람 나와주세요

내 집중력 돌려내~

너무 피곤했던 하루

왜 이렇게 피곤하고 집중도 안 됐는지 모르겠다....

피곤하긴 해도 문제 풀 때, 집중 엄청 많이 했는데 오늘은 뭔가 기운도 없고 배도 아프고 그래서 그런가 너무 힘들었다

그래도 TIL은 써야지..

내일은 잠이나 자야겠다...

---

0. TIL (2024.06.08)

📚오늘 진행한 문제 리스트

1. 백준 11561 징검다리 (실버 3) ✔️

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

풀이⬇️

# 백준 11561 징검다리 - 실버 3

# 징검다리의 개수 -> 점프할 칸의 개수
# 이분탐색 진행하면서 점프할 칸의 개수를 세고 N보다 작거나 같은지 체크
# -> N보다 작거나 같아야 다음 점프가 이전에 뛰었던 점프보다 더 클 수가 있다. (N을 무조건 밟아야 하므로)
import sys
input = sys.stdin.readline


def cross_the_bridge(N):
    res, left, right = 0, 1, N
    while left <= right:
        mid = (left + right) // 2
        sum_mid = mid * (mid + 1) // 2

        if sum_mid <= N:
            left = mid + 1
            res = mid
        else:
            right = mid - 1
    return res


def main():
    T = int(input())
    answer = []
    for _ in range(T):
        N = int(input())
        answer.append(cross_the_bridge(N))
    return '\n'.join(map(str, answer))


print(main())

징검다리의 개수 = 점프할 칸의 개수라고 생각하면 이해하기 그나마 쉬운 문제

최대한 많은 징검다리를 밟기 위해서는 점프를 공차가 1인 등차수열로 밟아야 한다.(문제 조건에 있음)

ex) 1, 2, 3, ... , k 이런 식

그런데 문제의 조건에 N번 징검다리는 무조건 밟아야 한다는 게 있기 때문에 k -> N 까지 밟기 위해서 1~k까지의 합 <= N이 되어야 한다.

ex) 1+2+3 < 9 에서 합이 9보다 작지만 다르게 생각하면 마지막에 3칸 점프가 아닌 6칸 점프를 하면 1+2+6 = 9가 되므로 N까지 밟는 징검다리의 개수를 구할 수 있다.

등차수열의 합 공식을 사용하여 문제를 해결해 주면 쉽게 해결할 수 있다.

 

2. 백준 1417 국회의원 선거 (실버 5) ✔️

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

풀이⬇️

# 백준 1417 국회의원 선거 - 실버 5

# 다솜이보다 크거나 같은 수가 존재하면 해당 득표 수를 가져온다.
# 후보자가 없으면 0 리턴
# 다른 후보의 득표수를 최대 힙으로 만들어서 맨 앞자리랑 다솜이의 득표수를 비교하고 조건에 맞으면 다솜이 득표수를 늘려준다.

# 33188/48
import sys
from heapq import heapify, heappop, heappush
input = sys.stdin.readline


def rig_election(dasom, people):
    cnt = 0
    if not people:
        return cnt

    while -people[0] >= dasom:
        max_val = -heappop(people)
        if max_val >= dasom:
            dasom += 1
            cnt += 1
            heappush(people, -max_val + 1)
    return cnt


def main():
    N = int(input())
    dasom = int(input())
    people = [-int(input()) for _ in range(N-1)]
    heapify(people)
    return rig_election(dasom, people)


print(main())

 

3. 백준 1072 게임 (실버 3) ✔️

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

풀이⬇️

# 백준 1072 게임 - 실버 3

# 게임 횟수를 늘려가면서 승률의 변화를 찾는 문제
# 게임 횟수 = 10억 -> 이분 탐색
# 게임 횟수에 대해 이분 탐색 진행
# 내 이전 승률과 mid 만큼 게임을 한 뒤의 승률을 비교해서 다르다면 최소의 값을 찾기 위해 right = mid - 1
# 동일하다면 판수의 변화를 줘야하므로 left = mid + 1
# 승률 계산할 때, 연산 순서 고려해서 100 곱하고 진행 -> 나눗셈 연산에서 소수점 오차가 생길 수 있다.

# 31120/44
import sys
input = sys.stdin.readline


def play_the_game(X, Y):
    res, left, right = 0, 1, X
    z = (Y * 100) // X
    if z >= 99:
        return -1
    while left <= right:
        mid = (left + right) // 2
        new_z = (100 * (Y + mid)) // (X + mid)
        if new_z > z:
            right = mid - 1
            res = mid
        else:
            left = mid + 1
    return res


def main():
    X, Y = map(int, input().split())
    return play_the_game(X, Y)


print(main())

반례를 다 체크해도 틀렸다고 나오길래 뭔가 싶었는데

z를 구하는 과정에서 나눗셈 연산 다음에 곱셈 연산을 진행했는데 거기서 발생하는 소수점 오차로 인해 발생하는 문제였다.

그래서 곱셈을 먼저 진행하고 나눗셈을 진행했더니 문제를 해결했다.

 

4. 백준 2304 창고 다각형 (실버 2) ✔️

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

풀이⬇️

# 백준 2304 창고 다각형 - 실버 2

# 주어진 기둥의 l 값에 따라 오름차순 정리
# 최고 높이를 가진 기둥 양 옆으로 넓이 구해준다.

# 31120/44
import sys
input = sys.stdin.readline


def make_polygon(materials):
    idx, area = 0, 0
    # 최고 기둥 높이 + 인덱스 찾기
    for i in range(len(materials)):
        if materials[i][1] > area:
            area = materials[i][1]
            idx = i

    # 최고 기둥 기준 왼쪽
    max_h = materials[0][1]
    for i in range(idx):
        if max_h < materials[i+1][1]:
            area += max_h * (materials[i+1][0] - materials[i][0])
            max_h = materials[i+1][1]
        else:
            area += max_h * (materials[i + 1][0] - materials[i][0])

    # 최고 기둥 기준 오른쪽
    max_h = materials[-1][1]
    for i in range(len(materials) - 1, idx, -1):
        if max_h < materials[i - 1][1]:
            area += max_h * (materials[i][0] - materials[i-1][0])
            max_h = materials[i - 1][1]
        else:
            area += max_h * (materials[i][0] - materials[i - 1][0])
    return area


def main():
    N = int(input())
    pillars = sorted([tuple(map(int, input().split())) for _ in range(N)])
    return make_polygon(pillars)


print(main())

 

5. 백준 19638 센티와 마법의 뿅망치 (실버 1) ✔️

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

풀이⬇️

# 백준 19638 센티와 마법의 뿅망치 - 실버 1

# 우선순위 큐 사용해서 제일 키가 큰 거인의 키를 반으로 줄여나간다.
# T만큼 진행하고 종료 -> T가 엄청 큰데 target = 1 이라면 바로 종료

# 37044/140
import sys
from heapq import heapify, heapreplace
input = sys.stdin.readline


def use_the_magic(centi_H, T, giants):
    cnt = 0
    for i in range(T):
        if -giants[0] == 1 or -giants[0] < centi_H:
            break
        else:
            heapreplace(giants, -(-giants[0] // 2))
            cnt += 1

    return check_max_val(cnt, centi_H, giants)


def check_max_val(cnt, centi_H, giants):
    if -giants[0] >= centi_H:
        return 'NO', -giants[0]
    return 'YES', cnt


def main():
    N, centi_H, T = map(int, input().split())
    giants = [-int(input()) for _ in range(N)]
    heapify(giants)
    return use_the_magic(centi_H, T, giants)


print('\n'.join(map(str, main())))

 

6. 백준 3649 로봇 프로젝트 (골드 5) ✔️

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

풀이⬇️

# 백준 3649 로봇 프로젝트 - 골드 5

# 조각들을 양 옆에서부터 투 포인터로 순회하면서 조각의 합이 x에 적합한지 확인하기
# 정렬시켜서 양 옆에서 찾으면 정답이 여러 개인 경우의 최댓값을 구할 수 있음
import sys
input = sys.stdin.readline


def block_the_hall(x, pieces):
    left, right = 0, len(pieces) - 1
    while left < right:
        sum = pieces[left] + pieces[right]
        if sum == x:
            return pieces[left], pieces[right]
        elif sum > x:
            right -= 1
        else:
            left += 1
    return None


def main():
    while True:
        try:
            x = int(input()) * 10000000
            n = int(input())
            pieces = sorted([int(input()) for _ in range(n)])
            ans = block_the_hall(x, pieces)
            print(f'yes {ans[0]} {ans[1]}') if ans else print('danger')
        except:
            break


main()

 

7. 백준 16120 PPAP (골드 4) ❌✔️

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

풀이⬇️

# 백준 16120 PPAP - 골드 4

# 문자열 S를 순회하면서 arr 에 넣고 맨 끝 4자리가 PPAP면 P만 남기고 다음 반복 진행
# 최종적으로 P만 남는다면 PPAP 문자열이다.

import sys
input = sys.stdin.readline


def find_string(S):
    arr = []
    PPAP = ['P', 'P', 'A', 'P']
    for i in range(len(S)):
        arr.append(S[i])
        if arr[-4:] == PPAP:
            for _ in range(3):
                arr.pop()
    if arr == ['P']:
        return 'PPAP'
    return 'NP'



def main():
    S = input().strip()
    return find_string(S)


print(main())

 

8. 백준 11834 홀짝 (골드 2) ❌✔️

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

풀이⬇️

# 백준 11834 홀짝 - 골드 2

# 각 층 별로 홀수와 짝수가 반복
# layer 1: 1 (1개) -> 1번째까지
# layer 2: 2, 4 (2개) -> 1+2 = 3번째까지
# layer 3: 5, 7, 9 (3개) -> 1+2+3 = 6번째까지
# layer 4: 10, 12, 14, 16 (4개) -> 1+2+3+4 = 10번째까지
# 내가 찾는 N번째 숫자가 일단 어떤 layer에 속해 있는지 찾고 해당 레이어에서 몇 번째 숫자인지 찾으면 된다.
# 이분탐색을 통해 layer 찾기 -> 원소의 개수가 N 이상이라면 일단 N번째 숫자보다 큰 숫자들이 존재한다는 것
# 그렇게 layer의 위치를 찾고 그 후에는 해당 레이어의 마지막 index - N을 해주어 차이가 얼마나 있는지 본다.
# 각 레이어의 수열은 공차가 2인 등차수열이므로 반복횟수 * 2(공차) 만큼 끝번째 숫자에서 빼줘서 정답 도출함
import sys
input = sys.stdin.readline


def find_layer(N):
    layer, left, right = 0, 0, N
    while left <= right:
        mid = (left + right) // 2
        num_of_elements = (mid ** 2 + mid) // 2
        if num_of_elements >= N:
            layer = mid
            right = mid - 1
        else:
            left = mid + 1
    return layer


def find_val(N, layer):
    repeat = (layer ** 2 + layer) // 2 - N
    val = layer ** 2 - 2 * repeat
    return val


def main():
    N = int(input())
    return find_val(N, find_layer(N))


print(main())

---

📝오늘자 질문

1. 오늘 진행된 강의에서 학습한 내용은 무엇인가요

• 이분 탐색, 정렬, 그래프

 

2. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

• 소수점 오차 발생 문제로 인해 나눗셈 연산 전에 곱셈 연산 먼저 진행하기
• Decimal

---

* 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지