https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 2022.07.14 - [Algorithm/BOJ] - [BOJ][python] 11052. 카드 구매하기 문제에서 최대 금액으로 카드를 구매하는 것을 풀었는데, 이번엔 최소 금액으로 구매 해야한다. 풀이 방법은 거의 비슷한데, 최소 금액을 구하기 위해 min_tmp로 최솟값을 갱신하여 카드 i개를 구매하는 비용을 계산한다.초기 min_tmp값은 적당히 큰..
https://school.programmers.co.kr/learn/courses/30/lessons/12899 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡IDEA 재귀를 사용하여 풀었다. 문제를 보면 1, 2, 4 세 가지 숫자로 10진수를 나타내야 하므로 3진법이라고 볼 수 있다. 일반적으로 3진법이면 3으로 나누었을 때의 나머지를 가지고 판단하면 되는데, 이 문제에서는 0을 취급하지 않기 때문에 조금 주의해야 한다. 처음에는 이전에 나온 값을 재사용할 수 있는 동적 계획법이 좋지 않을까 생각해서 그렇게 풀었지만 정확성 테스트는 모두 통과했지만..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 처음에는 커서를 움직이며 한 배열에서 pop과 insert 연산을 사용했는데, 시간 초과가 발생했다. 쉽게 커서를 구현하려면 스택을 사용하면 된다. 기존 입력받은 배열(arr)과, 커서 뒤의 배열을 위해 스택용(arr_tmp)을 만든다. 커서의 왼쪽은 arr, 오른쪽은 arr_tmp라고 생각하면 편하다. 연산의 종류에 따라 두 배열에 append 및 pop을 통..
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 💡IDEA 집합을 사용하는 문제이다. 쉽고 빠르게 집합을 구현하기 위해 크루스칼 알고리즘을 사용했다. 집합의 부모를 찾는 함수와 합집합 연산을 하는 함수를 만들었다. 연산이 0인 경우에 합집합을, 1인 경우에는 a의 부모와 b의 부모가 같은지 판단하여 출력한다. 📌CODE import sys input = sys.stdin.readline sys.setre..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 가로 세로가 50 이하이므로 브루트 포스를 더불어 사용했다. 육지(L)인 곳 중 상하좌우로 이어진 곳 중 최단 거리로 이동할 수 있어야 한다. 거리를 재기 위해 큐에서 카운트를 세어준다. 반환 값은 계산한 거리 중 가장 큰 값을 반환한다. 모든 행렬을 순환하면서 모든 육지(L)를 확인하며 최단 거리로 이동하는 시간을 갱신하여 출력한다. 📌CODE import s..
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 시작 층(S)에서 시작하여 도착 층(G)까지 U씩 올라가거나 D씩 내려가며 몇 번만에 다다를 수 있는지 판단해야 한다. 버튼을 누르는 횟수는 방문 배열을 사용하여 구하도록 했다. F층 이내에 있는 층 중 방문하지 않은 층을 방문하며 횟수를 세어준다. 도착 층(G)에 다다르면 방문 배열로 센 횟수에서 -1을 해서 출력한다. 첫 시작을 1로 했기 때문에 -1을 해줘야 함을 ..
https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 시작 볼륨에서부터 시작해서 조절할 수 있는 크기만큼 더하고 뺀 값을 바탕으로 dp 배열을 채운다. 예제 입력 1번의 경우는 다음과 같다. S=5에서부터 시작해서 볼륨리스트 첫번째 값인 5를 더하고 뺀 값인 0과 10을 체크해준다. 볼륨리스트 두번째 값은 3인데, 0에서는 3으로, 10에서는 7로 체크할 수 있다. 범..
https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 💡IDEA 수학을 사용하는 문제이다. 1로만 이루어져 있는 수라는 점에서 속을 뻔 했지만, 그냥 상관 없이 두 수의 최대공약수를 구하면 된다. 최대공약수 만큼 1을 연속하여 출력한다. 📌CODE import math A, B = map(int, input().split()) print('1'*math.gcd(A, B))
https://school.programmers.co.kr/learn/courses/30/lessons/62048 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡IDEA 수학 문제다. 규칙을 찾는 게 중요한데, 처음엔 일차함수처럼 기울기를 사용해서 풀려고 했지만 12번 테스트 케이스가 시간초과가 발생했다. 다시 고민해서 최대공약수를 사용해서 푸는 방법을 생각했다. 최대공약수만큼 중복되는 점을 사용해서 가로+세로-최대공약수 만큼의 사각형을 사용할 수 없게 된다. 예시에서 가로 8 세로 12인 경우, 가로 2 세로 3인 사각형이 최대공약수인 4번 반복된다...
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 💡IDEA 브루트포스를 사용하는 문제이다. N이 20 이하인 자연수이므로 충분히 브루트포스로 해결할 수 있지 않을까 했다. itertools의 combinations 함수를 사용하여 부분 수열을 구하는데, 조합을 구성하는 개수는 1개부터 N개까지이다. 조합 중 합이 S인 경우에만 개수를 센다. 재귀로도 풀 수 있지만 시간이 훨씬 오래 걸린다. 코드는 두개 모두 ..
