💻 Problem문제 보러 가기 상훈이는 N개의 선물 상자를 가지고 있다. 선물 상자에는 현재 담겨있는 선물의 개수가 적혀있다.선물을 받을 아이들이 M명 있다. 아이들은 각자 1에서 M까지의 서로 다른 번호를 하나씩 부여받았다. 1번 아이부터 M번 아이까지 한 번에 한 명씩, 현재 선물이 가장 많이 담겨있는 상자에서 각자 원하는 만큼 선물을 가져간다. 이때, 앞서 누군가 선물을 가져갔던 선물 상자에서 또다시 가져가도 상관없다.하지만 상자에 자신이 원하는 것보다 적은 개수의 선물이 들어있다면, 선물을 가져가지 못해 실망한다.상훈이는 한 명이라도 실망하지 않고 모두가 선물을 가져갈 수 있는지 궁금하다. 💡 Approachheapq 모듈을 활용하여 최대 힙을 구현했다.최대 힙의 경우 최소 힙과 동일하게 구..

💻 Problem문제 보러 가기 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다. 💡 Approachheapq 모듈 활용하여 최소 힙을 구현했다. ✏️ Solutionimport sysimport heapqinput = sys.stdin.readlinen = int(input())heap = []for _ in range(n): x = int(input()) if x == 0: print(heapq.heappop(heap) if heap else 0) else: ..

💻 Problem문제 보러 가기 화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.자주 나오는 단어일수록 앞에 배치한다.해당 단어의 길이가 길수록 앞에 배치한다.알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자. 💡 Approach먼저 딕셔너리에 단어와 그 단어의 빈도수를 저장했다.그 후 sorted 함수..

💻 Problem문제 보러 가기  가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.  💡 Approach아래는 백준 예제 입력을 기반으로 그린 그래프의 모습이다.그림으로 보면 각 노드가 어떻게 이어져있는지 더 쉽게 이해할 수 있다. 플로이드 워셜 알고리즘으로 풀었다.플로이드 워셜의 키워드는 경출도!!3중 for문을 경유지-출발지-도착지 순으로 적어야 한다. 처음 입력받은 인접 행렬에는 직접적으로 이어지는 간선이 존재하는지 저장되어 있다.이 인접 행렬에서 간접적으로 이어지는지(경유지를 통해)를 업데이트하면 그게 정답이다. 출발지와 경유지가 이어져있고 경유지와 도착지가 이어져있으면 출발지에서 ..

💻 Problem문제 보러 가기  방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.  💡 Approach간선 정보(간선의 양 끝점)를 입력받고 있기 때문에 간선 정보를 가지고 graph를 만들어야 한다.만든 그래프를 바탕으로 정점 1부터 그래프 탐색을 시작한다. 만약 연결 요소가 하나인 그래프라면 첫 탐색에서 모든 정점에 방문 처리가 됐을 것이다.하지만 연결 요소가 2 이상인 그래프라면 첫 탐색 이후에 방문 처리가 되지 않은 정점이 있을 것이다.그렇게 방문 처리 되지 않은 정점을 찾아서 해당 정점을 기준으로 그래프 탐색을 하는 것을 반복하여 그래프 탐색을 몇 번했는지 세면 된다. 아래는 연결 요소에 대한 이해를 돕기 위한 필기이..

💻 Problem문제 보러 가기 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 💡 Approach처음에 생각이 잘 안 났다..그리디인 줄도 몰랐는데 모든 경우의 수를 따지는 게 아니라 괄호가 들어가야 하는 최선의 선택만을 따져야 해서 그리디인 것 같다. 문제의 목표는 식의 값을 최소로 만드는 것이다.식의 값을 가장 작게 만들기 위해서는 최대한 큰 수를 빼야 한다.즉, '-' 뒤에는 항상 괄호를 치는 것이 좋다. 예를 들어, 5+4-5-10+20 라는 식이 주어졌다고 치자.가장 작은 수를 만들기 위..

💻 Problem문제 보러 가기  해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야 한다. 해빈이가 가진 의상들이 주어졌을 때 과연 해빈이는 알몸이 아닌 상태로 며칠 동안 밖에 돌아다닐 수 있을까?  💡 Approach의상을 입을 수 있는 경우의 수를 구하면 된다.만약 headgear에 해당하는 의상이 hat, turban이 있다면 해빈이가 의상을 입을 수 있는 경우의 수는 3이다.hat을 쓰거나turban을 쓰거나아무것도 쓰지 않거나즉, 한 의상의 종류에 대해 입을 수 있는 경우의 수는 해당 종류의 의상 개수 + 1이다.각 의상 종류에 대해 ..

💻 Problem문제 보러 가기  N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.  💡 Approach이 문제의 시간 제한은 0.25초이다.1초가 약 1억이니 0.25초면 약 25,000,000이다.피보나치의 기본 재귀 코드는 시간복잡도가 2^n이기에 재귀로 풀면 안 된다. 피보나치 수열은 n이 2 이상일 때, f(n) = f(n-1) + f(n-2) 이다.재귀로 풀면 f(n)을 구할 때, f(n-1)을 구하기 위해 f(n-2)를 계산했음에도 f(n-2)를 다시 구해서 f(n-1)과 더해야 한다. 사진으로 보면 이해하기 더 쉽다.위 사진에서 f(5)를 구하려고 할 때, 중복 계산이 여러 번 발생하는 것을 확인할 수 있다. DP..