2024. 12. 9. 15:52ㆍAlgorithms/백준알고리즘 연습
1208-1209 이틀에 걸쳐 공부
2798번 블랙잭
로직
1. n, m을 받는다
2. n 으로 루프를 돌려 해당하는 수들을 모두 리스트에 넣는다
3. 리스트안의 3자리숫자를 돌려가며 더한다.
4. 리스트안의 3의 더하기가 21을 넘으면 break, 아니면 while로 돌려 합을 리스트에 넣는다.
5. 리스트의 max 값을 출력한다.
여기서 내가 지금 구현하기 어려운 루프 - 3 번
- for 문을 세번 돌려서 구현해야 하는 것으로 생각됨
초기 코드
a_list = []
plus_list = []
import sys
n,m = map(int, sys.stdin.readline().split())
for i in range (n):
c = int(sys.stdin.readline())
a_list.append(c)
for x in len(a_list):
for y in (a_list[a_list[x]+1],a_list[-1]):
for z in (a_list[a_list[y]+1],a_list[-1]):
plus_list.append(x+y+z)
while True :
for i in plus_list :
if i >= 21 :
break
else :
print(max(plus_list))value error 남
잘못된점
Yes, there are several issues with this code. Let's go through them:
- In the line for x in len(a_list):, you're trying to iterate over an integer (the length of a_list), which is not iterable. You should use range(len(a_list)) instead.
- The nested loops for y and z are incorrect. You're only considering the second and last elements of a_list, not all possible combinations.
- The variable a is being redefined in each iteration, overwriting previous values.
- The while True loop will run indefinitely because there's no condition to exit the loop.
- The break statement inside the for loop will only exit that loop, not the while loop.
- The logic for finding the closest sum to M (which I assume is what you're trying to do) is incorret
code rewriting
intertools.combinations = generate all possible combinations of 3 cards
import sys
from itertools import combinations
N, M = map(int, sys.stdin.readline().split())
cards = list(map(int, sys.stdin.readline().split()))
max_sum = 0
for combo in combinations(cards, 3):
current_sum = sum(combo)
if current_sum <= M and current_sum > max_sum:
max_sum = current_sum
print(max_sum)
넘을 경우에는 지금 더한 값이 max라는 조건을 덧붙여주면, 합이 21을 넘는 값을 제외시킬 수 있음 - > 복잡한 while 을 안써도 됨
만약 내 초기 코드를 쓸거였으면
import sys
N, M = map(int, sys.stdin.readline().split())
cards = list(map(int, sys.stdin.readline().split())) # Read all cards in one line
max_sum = 0
for i in range(N - 2):
for j in range(i + 1, N - 1):
for k in range(j + 1, N):
current_sum = cards[i] + cards[j] + cards[k]
if current_sum <= M and current_sum > max_sum:
max_sum = current_sum
print(max_sum)이렇게 바꾸어주어야 함 i를 돌릴때는 j와 k에 배정될 두 수를 빼고, j를 돌릴때는 k에 배절될 수 하나를 빼줘야 함 (범위에서)
2231번
분해합
재밌다...
분해합 다국어
| 2 초 | 192 MB | 174368 | 80867 | 63641 | 45.441% |
문제
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.
예제 입력 1 복사
216
예제 출력 1 복사
198
216 = 1+9+8+198
조건 : 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 생성자가 없는 경우에는 0을 출력한다.
1. 문자열로 변환 후, 분리하는 방법
변수 number = 123에 대하여, list 변수에 원소를 넣어본 결과
a = []
for i in str(number):
a.append(i)
분해하고 다시 더해서 맞는지 볼 필요가 있음
초기 코드
import sys
n = int(sys.stdin.realine().split())
alist = []
for i in str(n):
alist.append(i)
a = n - sum(alist)
if a == ''.join(map(str, a_list)):
print(a)
else :
print(0)이게 틀린 이유가, 복수의 값이 있을 경우에 가장 작은 생성자를 어떻게 구할지 모르겠음
복수의 값이 있을 수 있으니 list로 받아야하는건가..?
이 코드는 순서가 잘못됨
정답 코드
n = int(input())
result = 0
for i in range(1, n+1):
nums = list(map(int, str(i))) #한글자씩리스트에저장
result = sum(nums) + i #한글자씩리스트에저장한거랑1에서부터n까지숫자더한거랑 더해
if result == n:
print(i)
break
if i == n:
print(0)
19532번
초기코드
what's wrong for this code to pull out x =2, y = -1?
a = 1
b= 3
c= -1
d= 4
e= 1
f = 7
a1=0
b1=0
c1=0
d1=0
e1=0
f1=0
while True:
for i in range (-999, 999) :
if a*i == d:
a*i == a1
i*b == b1
i*c == c1
d1= d - a1
e1 = e-b1
f1 = f- c1
y= f1/e1
x = (c- b*y)/a
print(x,y)루프가 끝나지 않는 코드를 씀
determinant = a*e - b*d
if determinant != 0:
x = (c*e - b*f) / determinant
y = (a*f - c*d) / determinant
print(x,y )
else:
print("No unique solution exists.")
이렇게 간단하게 짤 수 있음
방정식을 쓸 수 있다는 사실을 생각을 못했다니.. 너무 컴퓨터를 얕잡아 봤다
1018번 체스판 다시 칠하기
파이썬에서 리스트 안의 연속된 글자 개수를 찾는 방법은 다음과 같습니다:
- itertools의 groupby 함수 사용:
8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW이걸 보면 연속된 글자 3개 있을때 가운데 를 바꾸어주어야 함 -> 이 로직이 맞나? 아닌것같음
이건 또 이렇게 나와야 함
예제 입력 5 복사
10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB
예제 출력 5 복사
0
일단 이런 문제가 나오면
1. 보드를 생성
2,
#part1
def count_repaint(board, x,y)
count1, count2 = 0,0
for i in range(8) :
for j in range(8):
if (i+j)) %2 == 0:
if board[x+i][y+j] != 'W': count1 += 1
if board[x+i][y+j] != 'B': count2 += 1
else:
if board[x+i][y+j] != 'B': count1 += 1
if board[x+i][y+j] != 'W': count2 += 1
return min(count1,count2)
#part2
N,M = map(int, input().split())
board = [input() for _ range(N)]
min_repaint = 64
for i in range(N-7):
for j in range(M-7): #시작점 설정
min_repaint = min(min_repaint, count_repaint(board, i , j)
print(min_repaint)part1 :
- count1과 count2는 각각 두 가지 체스판 패턴에 대해 다시 칠해야 하는 칸의 수를 세는 변수입니다.
- 두 개의 중첩된 for 루프 (i와 j)는 8x8 크기의 영역을 순회합니다.
- (i + j) % 2 == 0 조건은 체스판의 패턴을 확인합니다:
- 이 조건이 참이면 (i+j가 짝수), 해당 칸은 첫 번째 패턴에서 흰색이어야 합니다.
- 이 조건이 거짓이면 (i+j가 홀수), 해당 칸은 첫 번째 패턴에서 검은색이어야 합니다.
- 첫 번째 패턴 (count1):
- (i+j)가 짝수일 때 'W'가 아니면 count1 증가
- (i+j)가 홀수일 때 'B'가 아니면 count1 증가
- 두 번째 패턴 (count2):
- (i+j)가 짝수일 때 'B'가 아니면 count2 증가
- (i+j)가 홀수일 때 'W'가 아니면 count2 증가
- 모든 칸을 확인한 후, 두 패턴 중 더 적은 수의 칸을 다시 칠하는 경우를 선택합니다 (min(count1, count2)).
이 로직은 주어진 8x8 영역에서 체스판 패턴을 만들기 위해 최소한으로 다시 칠해야 하는 칸의 수를 계산합니다.
1436번 영화감독 숌
문제
666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.
종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다.
숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.
입력
첫째 줄에 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.
예제 입력 1 복사
2
예제 출력 1 복사
1666
예제 입력 2 복사
3
예제 출력 2 복사
2666
예제 입력 3 복사
6
예제 출력 3 복사
5666
예제 입력 4 복사
187
예제 출력 4 복사
66666
예제 입력 5 복사
500
예제 출력 5 복사
166699로직 펼치기
1. 1카운트 될때마다 뒷자리수 666을 제외한 앞의 자릿수가 올라감
초기 코드 - 잘못됨(1의자리까지밖에 먹히지 않음)
N= 3
count= []
for i in range(N):
count.append(i)
print(str(max(count))+"666")
187이 들어가면 66,666이 나와야 함
def find_doom_number(n):
count = 0
num = 666
while True:
if '666' in str(num):
count += 1
if count == n:
return num
num += 1
N = int(input())
result = find_doom_number(N)
print(result)
주어진 N번째 "종말의 수"를 찾기 위해 666부터 시작하여 순차적으로 숫자를 증가시키며 "666"이 포함된 수를 찾아나가는 방식을 사용
- 무한 루프:
- 현재 num을 문자열로 변환하여 '666'이 포함되어 있는지 확인합니다.
- '666'이 포함되어 있다면 count를 1 증가시킵니다.
- count가 입력받은 n과 같아지면, 해당 num을 반환합니다.
- 조건을 만족하지 않으면 num을 1 증가시키고 계속 진행합니다
2839번
설탕 배달 다국어
| 1 초 | 128 MB | 354461 | 136504 | 101276 | 37.882% |
문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
예제 입력 1 복사
18
예제 출력 1 복사
4
예제 입력 2 복사
4
예제 출력 2 복사
-1
예제 입력 3 복사
6
예제 출력 3 복사
2
예제 입력 4 복사
9
예제 출력 4 복사
3
정확하게 나누어지는 몫을 구하는게 첫번째이다.
n = int(input())
c = 0
while True:
a,b = divmod(n, 5)
if b%3 == 0:
c = (b//3)
print(a+c)
else:
c= (b//3)+1
print(a+c)
break내가 짠 코드는 봉지의 최소갯수는 맞출 수 있으나, 안나눠지는 경우 -1 을 하는 것이 어려움
어떻게 바꿔야 할까?
1. 3x+5y = n이라는 방정식에 해가 없는 경우 = -1, 있는경우 루프를 돌린다.
AI의 도움을 받아 수정한 코드
n = int(input())
def has_solution(n):
for x in range(n // 3 + 1):
if (n - 3 * x) % 5 == 0:
return True
return False
if has_solution(n):
while True:
a, b = divmod(n, 5)
if b % 3 == 0:
c = b // 3
print(a + c)
else:
c = (b // 3) + 1
print(a + c)
break
else:
print(-1)
함수를 써서 해결할 수 있음
그러나 백준에서는 틀렸다고 함
그리디 알고리즘이 필요함
" 그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미"
앞선 코드가 정답이 아닌 이유
앞서 제안한 코드가 이 문제를 정확하게 풀 수 없는 이유는 다음과 같습니다:
- 최적해를 보장하지 않음:
이전 코드는 5로 나눈 후 남은 값을 3으로 처리하는 방식을 사용했습니다. 이 방법은 항상 최소 개수의 봉지를 찾아주지 않습니다. 예를 들어, N=12의 경우 이전 코드는 5kg 2개와 3kg 1개(총 3개)로 계산하지만, 실제 최적해는 3kg 4개입니다. - 일부 케이스 누락:
이전 방식은 5로 나눈 나머지를 처리할 때, 3으로 나누어 떨어지지 않는 경우 올림을 사용했습니다. 이로 인해 실제로는 해가 존재하는 경우에도 해를 찾지 못할 수 있습니다. - 그리디 접근의 한계:
설탕 배달 문제는 단순히 큰 단위(5kg)부터 채우는 그리디 방식으로는 최적해를 항상 찾을 수 없습니다. 때로는 작은 단위(3kg)를 더 많이 사용하는 것이 최적일 수 있습니다.
perplexity는 지속적으로 함수를 사용하는데, 함수 사용에는
- 코드 재사용: 반복되는 로직을 함수로 만들어 여러 번 호출하면 코드 중복을 줄일 수 있습니다.
- 가독성 향상: 복잡한 로직을 함수로 분리하면 코드를 이해하고 최적화하기 쉬워집니다.
- 최적화 용이성: 특정 기능을 함수로 분리하면 해당 부분만 집중적으로 최적화할 수 있습니다.
- 캐싱 활용: 함수의 결과를 캐싱하여 반복적인 계산을 줄일 수 있습니다.
이런 장점이 있다고 함
함수 쓴 정답 코드
def sugar_delivery(N):
for i in range(N // 5, -1, -1):
remainder = N - (5 * i)
if remainder % 3 == 0:
return i + (remainder // 3)
return -1
N = int(input())
result = sugar_delivery(N)
print(result)
함수 안쓴 코드
N = int(input())
result = -1
for i in range(N // 5, -1, -1):
remainder = N - (5 * i)
if remainder % 3 == 0:
result = i + (remainder // 3)
break
print(result)for i in range(N // 5, -1, -1):
1. 5 : 시작값을 5로 나눈 몫 - 5kg 봉지를 최대로 나눌 수 있는 값
2. -1 : 종료값으로 로프가 0까지 포함되어 실행됨.
3. -1 : 반복마다 i값이 1씩 감소
점점 5kg 봉지를 최대한 많이 사용하는 경우부터 시작하여, 점점 5kg봉지 개수를 줄여가며 가능한 조합을 확인
함수 쓰고 안쓰고 차이
두 버전의 코드는 알고리즘적으로 동일하며, 따라서 시간 복잡도도 같습니다. 둘 다 O(N/5)의 시간 복잡도를 가집니다.
- 함수를 사용한 버전:
- 장점: 코드의 모듈화와 재사용성이 높습니다.
- 단점: 함수 호출에 따른 아주 작은 오버헤드가 있을 수 있습니다.
- 함수를 사용하지 않은 버전:
- 장점: 함수 호출 오버헤드가 없어 미세하게 더 빠를 수 있습니다.
- 단점: 코드 재사용성이 낮고, 복잡한 로직의 경우 가독성이 떨어질 수 있습니다.