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://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인 경우에만 개수를 센다. 재귀로도 풀 수 있지만 시간이 훨씬 오래 걸린다. 코드는 두개 모두 ..
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 스택에 차례대로 인덱스와 그 높이를 넣고, 스택의 가장 끝에 있는 값의 높이가 i번째 탑의 높이보다 높은 경우에 결과 배열에 인덱스+1을 저장한다. 높이가 낮은 경우 pop을 해준다. 스택에 아무것도 남지 않을 때까지 반복한 후 다음 인덱스와 높이를 넣는다. 현재 탑을 기준으로 왼쪽, 그러니까 이전의 탑들 중 자신보다 큰 높이의 탑의 인덱스를 저장해야하기 때..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 전깃줄이 겹치지 않기 위해서 A의 전깃줄 순 으로 정렬한 후 A와 연결된 B의 전깃줄 중 가장 긴 증가하는 부분 수열을 구하면 된다. i번째와 i번째 이전까지의 j번째 값을 비교하며 dp 배열을 채운다. i번째 dp 값과 j번째 dp 값에 개수를 하나 더한 값 중 큰 값으로 i번째 dp를 갱신한다. dp의 최댓값은 겹치지 않고 연결된 전깃줄의 개수이므로, 결과..
https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 어떻게 풀어야할지 감을 못 잡았는데 알고리즘 분류를 보고서야 이분 탐색임을 알았다. 이분 탐색의 왼쪽 값(l)은 배열의 최댓값, 오른쪽 값(r)은 배열 원소들의 총합을 기준으로 시작한다. 가운데 값(m)은 (l+r)//2로 정한다. 블루레이의 크기에 몇 개의 강의가 들어가는지 세어주는 함수를 만들어서 개수를 반환한다. 이 때 블루레이의 크기는 m을 기준으로 판단..
https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 상하좌우로 연결된 부분을 하나의 그림으로 보고, 그림의 크기와 개수를 구해야 한다. 그림의 크기는 BFS를 수행하면서 연결된 곳이 있을 때 마다 개수를 세어주고, 그림의 개수는 BFS가 정상적으로 끝난 후 개수를 세어주면 된다. BFS 과정에서 별도의 방문 배열 없이 기존 입력받은 배열을 갱신해가며 그림이 있을 때(1) BFS를 수행하여 그림이 없다고(0) 변경한..
https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 💡IDEA 그리디를 사용하는 문제이다. A행렬의 3×3 부분 행렬을 뒤집어서 B행렬을 만들어야 한다. 뒤집는 과정을 함수로 만들어서 3×3 부분 행렬의 각 값이 1이면 0으로, 0이면 1로 바꾸어 준다. A행렬과 B행렬의 같은 위치를 비교하여 다른 경우 뒤집는 함수를 실행하고, 횟수를 세어 출력한다. 모든 경우에 뒤집고도 두 행렬이 다른 부분이 있다면 -1을 출력한다. 📌CODE import sys input ..
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 💡IDEA 정렬을 사용하는 문제이다. 좌표 압축의 조건은 현재 값보다 작은 값의 개수를 구하면 되기 떄문에 정렬이 필요하다. 정렬한 배열에서 자신이 몇 번째인지 딕셔너리로 기록해둔 후 원래 배열의 순서에 맞게 출력한다. 이 때 중복된 값이 있을 수 있으므로 set() 함수를 사용해야한다는 점을 주의한다. 📌CODE import sys input =..
https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 💡IDEA 조합을 사용하는 문제이다. 받아온 k개 길이의 배열 중 6개만큼 선택하는 kC6 경우를 출력하면 된다. itertools의 combinations 함수를 사용하면 쉽게 6개를 조합한 배열을 돌려주기 때문에 그대로 출력한다. 📌CODE import sys input = sys.stdin.readline from itertools import combinations while T..
