Algorithm/Baekjoon

🗂️ 문제 링크: https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 💡 접근법 접두사X 집합이란 집합의 어떤 한 단어가 다른 단어의 접두어가 되지 않는 집합을 말한다. 즉 전체 집합에서 다른 단어의 접두어가 되는 단어들 제외한 단어들의 개수를 구하는 문제이다. 리스트를 정렬하고 각각의 요소를 순회하면서 현재 문자열이 다음 문자열에 접두어가 되는지 확인한다. 여기서 문자열을 정렬했기 때문에..

🗂️ 문제 링크: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 💡 접근법 가운데를 말해요 문제와 비슷한 문제이다. 즉, 최대 힙과 최소 힙을 생성하여 중앙값을 구하면 된다. leftHeap에는 중간값보다 같거나 작은 값들이 저장되고, rightHeap에는 중간값보다 큰 값들이 저장된다. leftHeap의 루트를 중간값으로 꺼낼 것이다. 이때 만약 수의 개수가 짝수 개라면 중간에 있는 두 수 중 작은 수를 말해야 ..

🗂️ 문제 링크: https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 💡 접근법 중간값을 뽑아내기 위해서 최대 힙(leftHeap)과 최소 힙(rightHeap), 총 2개의 힙을 사용한다. leftHeap에는 중간값보다 같거나 작은 값들이 저장되고, rightHeap에는 중간값보다 큰 값들이 저장된다. leftHeap의 루트를 중간값으로 꺼낼 것이다. 이때 만약 수의 개수가 짝수 개라면 중간에 있는 두 수 중 작은 수를 말해야 한..

🗂️ 문제 링크: https://www.acmicpc.net/problem/14235 14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net 💡 접근법 heapq 라이브러리를 사용하여 a가 0이 아니라면 선물의 가치를 heap에 저장하고, a가 0이라면 선물의 가치가 큰 순서대로 힙에서 요소를 꺼내 출력한다. 이때 힙에 남아있는 요소의 개수가 0이라면 -1을 출력한다. 또한 최대힙을 구성하기 위해 push할때 -부호를 붙여서 힙에 요소를 넣어주고, pop할 때는 -부호를 붙여서 출력한다. 😎 내 코드 import sys..

🗂️ 문제 링크: ttps://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 💡 접근법 heapq 라이브러리를 사용하면 간단하게 풀 수 있다. 입력으로 들어오는 값들을 1차원 리스트로 만든다. 이때 메모리 초과를 고려하여 heap의 크기를 N으로 고정해야 한다. 따라서 heapq.nlargest(N, arr)를 사용하여 arr에 N번째까지 큰 수들만 남기면서 새로운 입력 값들을 arr에 업데이트한다. 😎 내 코드 import heapq import sys N = ..

🗂️ 문제 링크: https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 💡 접근법 N의 범위가 1,000,000이므로 시간복잡도 O(NLogN)을 갖는 정렬 알고리즘을 사용해야 한다. 파이썬 내장 정렬함수, 퀵정렬, 병합정렬, 힙정렬이 제한 시간 내에 해결할 수 있는 알고리즘이다. 이 중 힙정렬을 사용하여 구현한다. 파이썬의 heapq 라이브러리는 최소 힙으로 구현되어 있기 때문에 heap 배열을 생성하여 입력값을 push하고 하나씩 po..

🗂️ 문제 링크: https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 💡 접근법 그리디 알고리즘을 사용한다. 최소값을 구하기 위해서는 작은 수에서 큰 수를 빼야 한다. 따라서 덧셈으로 연속된 부분에 괄호를 쳐서 이를 계산한 후 빼는 방식으로 문제를 해결하면 된다. 이때 예외처리로 주의해야 할 부분이 있다. -로 입력값을 split하고 문제에서 주어진 테케를 시도할 경우 A = ['100', '40+50+74', '30+29', '45+43+1..

🗂️ 문제 링크: https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 💡 접근법 그리디 알고리즘을 이용하여 문제에 접근한다. 즉 현재 시점에서 최선의 선택을 하고 이 선택이 전체 문제를 해결할 수 있는지 확인한다. 문제에서 제시한 대로 최소 동전 개수를 구하기 위해서는 가장 가격이 큰 동전부터 차례대로 순회하면 된다. 😎 내 코드 import sys N, K = map(int, sys..