[항해99 취업 리부트 코스 학습일지] 점점 늘어가는 건 나의 몸무게

좀 빠져봐.

알고리즘 7일차!

전반적으로 문제가 쉬워서 빨리 풀 수 있었다.

근데 요즘 항해를 하다 보니 운동할 시간이 없다...

아침에 하자니 매일 2시 반에 자서 아침에 일어날 자신이 없는데

그렇다고 끝나면 아파트 헬스장이 문을 닫는단 말이지..

공부도 체력 싸움이라 했거늘

이대로 앉아만 있으면 조만간 허리디스크 또 터질게 분명하니까 틈틈히 스트레칭도 해줘야겠다~!

---

0. TIL (2024.06.06)

📚오늘 진행한 문제 리스트

1. 백준 15829 Hashing (브론즈 2) ✔️

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

풀이⬇️

# 백준 15829 Hashing - 브론즈 2

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


L = int(input())
S = str(input().strip())
r = 31
M = 1234567891
ans = 0
for i in range(len(S)):
    ans += (ord(S[i]) - ord('a') + 1) * r ** i
print(ans % M)

 

2. 백준 1920 수 찾기 (실버 4) ✔️

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

풀이⬇️

# 백준 1920 수 찾기 - 실버 4

import sys
input = sys.stdin.readline


N = int(input())
A = set(input().strip().split())
M = int(input())
print('\n'.join('1' if num in A else '0' for num in input().strip().split()))

 

3. 백준 9375 패션왕 신해빈 (실버 3) ✔️

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

풀이⬇️

# 백준 9375 패션왕 신해빈 - 실버 3

# 34016/72
import sys
from collections import Counter
from functools import reduce

input = sys.stdin.readline


TC = int(input())
for _ in range(TC):
    n = int(input())
    clothes = Counter([input().strip().split()[1] for _ in range(n)])
    answer = reduce(lambda x, y: x * (y + 1), clothes.values(), 1) - 1
    print(answer)

 

4. 백준 11286 절댓값 힙 (실버 1) ✔️

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

풀이⬇️

# 백준 11286 절댓값 힙 - 실버 1

# 39824/144
import sys
import heapq
input = sys.stdin.readline


N = int(input())
abs_heap = []
for _ in range(N):
    num = int(input())
    if num:
        heapq.heappush(abs_heap, (abs(num), num))
    else:
        print(heapq.heappop(abs_heap)[1]) if abs_heap else print(0)

 

5. 백준 2075 N번째 큰 수 (실버 2) ✔️

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

풀이⬇️

# 백준 2075 N번째 큰 수 - 실버 2

import sys
import heapq
input = sys.stdin.readline


N = int(input())
nums = []
for _ in range(N):
    row = list(map(int, input().split()))
    for e in row:
        heapq.heappush(nums, e)
        if len(nums) > N:
            heapq.heappop(nums)
print(nums[0])

 

6. 백준 15903 카드 합체 놀이 (실버 1) ✔️

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

풀이⬇️

# 백준 15903 카드 합체 놀이 - 실버 1

# 33188/60
import sys
import heapq
input = sys.stdin.readline


n, m = map(int, input().strip().split())
cards = list(map(int, input().strip().split()))
heapq.heapify(cards)
while m > 0:
    x_y = heapq.heappop(cards) + heapq.heappop(cards)
    for _ in range(2):
        heapq.heappush(cards, x_y)
    m -= 1
print(sum(cards))

 

7. 백준 1715 카드 정렬하기 (골드 4) ✔️

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

풀이⬇️

# 백준 1715 카드 정렬하기 - 골드 4

import sys
import heapq
input = sys.stdin.readline


N = int(input())
cards = list(int(input()) for _ in range(N))
cards.sort()
ans = 0
while len(cards) > 1:
    x_y = heapq.heappop(cards) + heapq.heappop(cards)
    ans += x_y
    heapq.heappush(cards, x_y)
print(ans)

 

8. 백준 21939 문제 추천 시스템 Version 1 (골드 4) ✔️

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

풀이⬇️

# 백준 21939 문제 추천 시스템 Version 1 - 골드 4

# heap 사용해서 난이도 -> 번호 순으로 pop (쉬운 문제 = 난이도 -> 번호 작은 순 / 어려운 문제 = 난이도 -> 번호 큰 순)
# solved 하게 되면 heap에서 인덱스로 찾을 수 없을 것 -> dict 만들어서 heap에서 제거했다는 여부 판별
import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline


def main():
    N = int(input())
    min_heap, max_heap = [], []
    check = defaultdict(bool)
    for _ in range(N):
        num, level = map(int, input().strip().split())
        heapq.heappush(min_heap, (level, num))
        heapq.heappush(max_heap, (-level, -num))
        check[num] = True
    M = int(input())
    for _ in range(M):
        command = input().strip().split()
        res = run_recommend_system(command, min_heap, max_heap, check)
        print(res) if res else 0


def run_recommend_system(command, min_heap, max_heap, check):
    # 추천 시스템이 작동하면서 이전 작업에 의해 변경된 점을 계속 업데이트 해준다.
    # ex) 문제가 이미 풀렸지만 heap에 남아있는 경우
    update_max_val(check, max_heap)
    update_min_val(check, min_heap)

    if 'add' in command:
        heapq.heappush(min_heap, (int(command[2]), int(command[1])))
        heapq.heappush(max_heap, (-int(command[2]), -int(command[1])))
        check[int(command[1])] = True
    elif 'recommend' in command:
        if command[1] == '1':
            return -max_heap[0][1]
        else:
            return min_heap[0][1]
    else:
        check[int(command[1])] = False

    return None


def update_max_val(check, max_heap):
    while not check[-max_heap[0][1]]:
        heapq.heappop(max_heap)


def update_min_val(check, min_heap):
    while not check[min_heap[0][1]]:
        heapq.heappop(min_heap)


main()

 

주어진 조건에 따라 구현하면 되는 문제

여기서 해결해야 할 부분은 이미 해결한 문제를 어떻게 Heap에서 뺄 것인가에 중점을 둬야 한다.

solved 명령어로 삭제가 됐을 때, 이걸 바로 삭제하는 것이 아니라 Soft Delete 느낌처럼 우선 삭제되었다는 표시를 해두고 작업을 계속 진행하면서 업데이트 메서드를 계속 돌려주는 방식으로 구현했다.

add 명령어가 들어왔을 때, 최대 힙이나 최소 힙에 이미 풀고 사라진 문제가 남아 있으면서 최대 혹은 최소 값으로 존재하고 있을 경우가 있으니까 그걸 제거하고 업데이트를 해줘야 하고

recommend 명령어의 경우 무조건 최대 혹은 최소 난이도를 추천해줘야 하므로 상태 업데이트 함수를 실행 후에 추천을 해주면 된다.

---

📝오늘자 질문

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

• Heap, Hash Table

 

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

• heapfiy() 메서드의 시간복잡도는 O(N) -> 원본이 필요하다면 복사해서 사용하자.
• 보통 최대와 최소를 같이 물어보는 문제에서 heap을 사용해야 한다면 최대 힙과 최소 힙을 구분해서 구현하자

---

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

https://hanghae99.spartacodingclub.kr/reboot

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