목록알고리즘 (20)

개발 기록

[알고리즘|파이썬] 백준 2529 부등호

문제 링크: https://www.acmicpc.net/problem/2529📌 문제 탐색하기시간 제한: 1초메모리 제한: 256 MB ✏️ 구해야 하는 정답두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족할 때, 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다.제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다조건:- 2 ≤ k ≤ 9- 부등호 관계를 만족한다- 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }- 선택된 숫자는 모두 달라..
알고리즘 2025. 2. 5. 23:31
[알고리즘|파이썬] 백준 2210 숫자판 점프

문제 링크: https://www.acmicpc.net/problem/2210📌 문제 탐색하기시간 제한: 2초메모리 제한: 128 MB 구해야 하는 정답0~9 숫자가 채워져 있는 5*5 숫자판에 임의의 위치에서 시작하여 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙여 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구해야 한다.조건:- 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 됨.- 0으로 시작하는 수 만들 수 있음. 예) 000123 예시:1 1 1 1 11 1 1 1 11 1 1 1 11 1 1 2 11 1 1 1 1111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 12..
알고리즘 2025. 2. 4. 23:08
[알고리즘|파이썬] 백준 1182 부분수열의 합

문제 링크: https://www.acmicpc.net/problem/1182📌 문제 탐색하기시간 제한: 2초메모리 제한: 256 MB구해야 하는 정답N개의 정수가 주어지고, 이 N개로 만들 수 있는 부분수열 중 합이 S인 개수를 구하는 문제이다.예를 들어, {1, 2, 3} 의 부분수열은 총 7개이고, 이들의 합은 다음과 같다:{1} -> 1{2} -> 2{3} -> 3{1, 2} -> 3{1, 3} -> 4{2, 3} -> 5{1, 2, 3} -> 6 이때 모든 부분수열을 구하여 합을 계산해보는 방식으로, 즉 완전 탐색으로 문제를 접근해도 되는지 고려해봐야 한다.N개의 정수로 만들 수 있는 부분수열은 2^N - 1 개이다. nCn+nCn-1+…+nC1 = 2^n - 1 문제에서 N의 범위를 1 ≤ ..
알고리즘 2025. 2. 4. 00:14
[알고리즘|파이썬] 백준 16937 두 스티커

문제 링크: https://www.acmicpc.net/problem/16937📌 문제 탐색하기시간 제한: 2초메모리 제한: 512 MB알고리즘 선택N개의 스티커 중 2개를 골라야하므로 조합으로 푸는 방식으로 접근했을때,nCr = n!/r!(n-r)!nC2 = n!/2!(n-2)! = n(n-2)/2그러므로 O(n^2)이라는 시간 복잡도를 갖게 된다.문제에서 N의 범위를 1 주었기 때문에,1 , 주어진 시간 2초 안에 사용할 수 있다. 주어진 N개의 스티커 중 2개의 조합을 구하고, 조합들 중 H*W 모눈종이에 들어 가는 조합들의 합 중 최댓값을 구하도록 한다.📌 코드 설계하기1. 주어진 N개의 사이즈 중 H*W 사이즈보다 크지 않은 스티커를 리스트로 받음2. 받은 리스트로 nC2 조합을 만듦3. ..
알고리즘 2025. 2. 3. 00:02
이전 Prev 1 2 3 Next 다음