joohee.log

그리디 : 볼링공 고르기

Thu, 06 Mar 2025 09:25:46 GMT

문제

서로 무게가 다른 볼링공을 골라야 함
볼링공 N개 , 무게는 1~M
두 사람이 볼링공을 고르는 경우의 수

내 풀이

N,M 을 입력받기 / list_N 입력받기
list_N 을 정렬
2중 for문을 돌면서

-- list_N[i]와 list_N[j]이 같으면 패스 -- 없으면 total += 1

N,M = map(int,input().split())
list_N = list(map(int,input().split()))
total = 0

for i in range(len(list_N)):
  for j in range(i, len(list_N)):
    if list_N[i] != list_N[j]:
      total += 1

print(total)

25/03/06

고민

똑같이 2중 for문으로 풀었다,,,

챗지피티에게 물어보니 아래와 같은 코드를 추천해줌ㅠ

# 입력 받기
N, M = map(int, input().split())  # 볼링공 개수, 무게의 범위
balls = list(map(int, input().split()))  # 볼링공의 무게 리스트

1️⃣ 무게별 볼링공 개수 세기

count_by_weight = [0] * (M + 1) # 무게별 개수 저장할 리스트

for ball in balls: count_by_weight[ball] += 1

2️⃣ 전체 조합 계산 (O(N))

total_pairs = (N * (N - 1)) // 2 # 전체 가능한 조합 개수 (nC2) same_weight_pairs = 0 # 같은 무게의 볼링공을 선택하는 경우의 수

for weight in range(1, M + 1): if count_by_weight[weight] > 1: # 같은 무게가 2개 이상이면 same_weight_pairs += (count_by_weight[weight] * (count_by_weight[weight] - 1)) // 2 # 같은 무게끼리 선택하는 경우

3️⃣ 다른 무게의 공을 선택하는 경우의 수 = 전체 조합 - 같은 무게 조합

result = total_pairs - same_weight_pairs

print(result) ~

그리디 : 만들 수 없는 금액

Thu, 06 Mar 2025 09:03:45 GMT

25/03/06

문제

Q) 만들 수 없는 금액 동전 여러 개가 주어질 때, 이 동전들로 만들 수 없는 가장 작은 금액을 구하는 문제.

입력 예) 동전 : [3, 2, 1, 1, 9] 출력 예) 8

내 풀이

data 가장 작은 동전부터 오름차순 정렬
data list 에서 젤 작은애부터 + 해주면서 target (최대값) < 동전 이면 target이 정답 다 돌때까지 target >= 동전 이면 target이 정답임

코드

data = list(map(int,input().split()))
target = 1

data.sort()
print(data)

for i in data:
  if i > target :
    print('answer', target)
    break
  target += i
  print(target)

Fail 인 이유

target += i 가 이해 안감,, 왜 저렇게 하면 더할 수 있는 모든 숫자가 나오는지,,?

그리디 : 체육복

Tue, 09 Jan 2024 14:03:11 GMT

아직 푸는 중이다,, ! ! !

문제

내풀이

lost 와 reserve를 정렬 > 같은 수가 있다면 remove 해주기

-- 같은 수가 있다면 걔네를 delete_list 에 append -- lost, reserve 에서 delete_list 값들을 remove 2. total = len(lost) -- reserve[i]의 값 -+1 = lost에 있을 때 --> lost에서 해당 값 remove 해주기

def solution(n, lost, reserve):
    answer = 0

    delete_list = []
    lost.sort()
    reserve.sort()

    for i in lost:
        if i in reserve:
            delete_list.append(i)

    for i in delete_list:
        lost.remove(i)
        reserve.remove(i)

    for i in reserve:
        if i+1 in lost:
            lost.remove(i+1)
        elif i-1 in lost:
            lost.remove(i-1)

    total = len(lost)
    answer= n - total


    return answer

그리디 : 볼링공 고르기

Tue, 09 Jan 2024 13:20:35 GMT

문제

서로 무게가 다른 볼링공을 골라야 함
볼링공 N개 , 무게는 1~M
두 사람이 볼링공을 고르는 경우의 수

내 풀이

N,M 을 입력받기 / list_N 입력받기
list_N 을 정렬
2중 for문을 돌면서

-- list_N[i]와 list_N[j]이 같으면 패스 -- 없으면 total += 1

N,M = map(int,input().split())
list_N = list(map(int,input().split()))
total = 0

for i in range(len(list_N)):
  for j in range(i, len(list_N)):
    if list_N[i] != list_N[j]:
      total += 1

print(total)

그리디 : 만들 수 없는 금액

Tue, 09 Jan 2024 13:07:50 GMT

문제

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값 구하기
입력 예시 5 3 2 1 1 9
출력 예시 8

내 풀이

N, list_N 입력받기
list_N의 원소들의 합을 sum_list 에 append

-- 2중 for문으로 3. sum_list를 정렬 -> for문으로 돌면서 -- result = 1 == sum_list[i] --> result+=1 해주기

N = int,input().split()
list_N = list(map(int,input().split()))
sum_list = []
result = 1

for i in range(len(list_N)):
  current_sum = 0 
  for j in range(i, len(list_N)):
    current_sum += list_N[j]
    sum_list.append(current_sum)

sum_list.sort()
for i in sum_list:
  if result == i:
    result +=1

print(result)

그리드 : 문자열 뒤집기

Mon, 08 Jan 2024 13:41:19 GMT

문제

문자열 S 의 모든 숫자를 같게 하는 것이 목적
연속된 하나 이상의 숫자를 잡고 모두 뒤집기
최소 횟수를 구하여라

내 풀이

문자열 -> 1개씩 잘라서 리스트로 변환
리스트를 for문으로 돌면서 0->1 또는 1->0 으로 바뀌는 구간의 개수 구하기 = count
** count가 짝수 -> total = count//2 count가 홀수 -> total = count//2 +1 **

S = input()
list_S = []
count = 0
total = 0

for i in range(len(S)):
  a = S[i:i+1]
  list_S.append(a)

for i in range(len(list_S)-1):
  if list_S[i] != list_S[i+1] :
    count+=1

if count%2==0:
  total = count//2
else:
  total = count//2 +1

print(total)

그리드 : 곱하기 혹은 더하기

Mon, 08 Jan 2024 13:17:18 GMT

문제

문자열 S
왼쪽 > 오른쪽 순서
'x' 혹은 '+' 연산으로 만들 수 있는 가장 큰 수를 구하기
입력 예시 02984
출력 예시 0+298*4 = 567

내 풀이

문자열 S를 1글자씩 잘라서 int로 바꿔줌
입력된 리스트 를 for문 돌면서

리스트의 i가 0이면 ** 혹은 total 값이 0이면 ** +
0이 아니면 x를 해줌

S = input()
list_S = []
total = 0

for i in range(len(S)):
  a = int(S[i:i+1])
  list_S.append(a)

for i in list_S:
  if i==0 or total==0:
    total += i
  else:
    total *= i

print(total)

그리디 : 모험가길드

Mon, 08 Jan 2024 12:58:41 GMT

문제

모험가 N명
공포도 X
반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있음
여행을 떠날 수 있는 그룹의 최댓값 구하기
입력 예시 5 2 3 1 2 2
출력 예시 2

내 풀이

N, X 입력받기
X 크기 순으로 정렬

outX = X리스트 내 중복값 제거한 리스트 만들기
outX를 돌면서 X리스트 내의 개수 // i 를 + 해주기

N = int,input().split()
X = list(map(int,input().split()))
total = 0

X.sort() # X 정렬
outX = list(set(X)) # X에서 중복 제거

for i in outX:
  total += X.count(i) // i

print(total)

25/03/05

내 풀이

list를 내림차순으로 정렬
listSize = len(list) i = 0 while True: 만약에 i가 list길이보다 작으면
- count+=1
- i += list[i]
  크면 반복문 중지

3 2 2 2 1 0 1 2 3 4 len 5

코드

n = int(input())
data = list(map(int,input().split()))

data.sort(reverse=True)
i = 0
count = 0

while True:
  if i < len(data):
    i += data[i]
    count += 1
  else:
    break

print(count)

k-겹 교차검증 이 먼대?!

Mon, 10 Apr 2023 06:33:47 GMT

원래는 ...

머신러닝을 학습시킬 때, 훈련 데이터 / 테스트 데이터로 나눈다 ( 보통 70 : 30 으로 나눔 )
70% 데이터를 모델 테스트 과정에서도 사용할 방법이 있다면 좋겠지?

k겹 교차검증

= 집합을 체계적으로 바꿔가면서 모든 데이터에 대해 모형의 성과를 측정하는 검증 방식

k겹 → 전체 데이터셋을 K개의 부분집합으로 나눈다 ( fold = k 개로 나눈 부분집합 데이터 )
교차 → fold 들을 차례대로 교차해 테스트 데이터로 사용 ( 아래 그림을 보자 ! )

k-겹 교차검증의 흐름

만약 우리가 모델의 정확도(accuracy)를 측정해보고 싶다면, 1번 fold가 테스트 데이터일 때 모델을 학습시켜 정확도를 산출, 2번 fold가 테스트 데이터일 때 모델을 학습시켜 정확도를 산출, 3번 fold가 테스트 데이터일 때 모델을 학습시켜 정확도를 산출... 이 과정을 k번 fold까지 반복 → 모델 검증 결과가 k개 나온다 → 이 k개의 결과물들의 평균값 = K겹 교차 검증 방식을 활용한 모델의 성능

참고사이트

https://bbdata.tistory.com/10

프로그래머스 : 등수 매기기

Tue, 07 Feb 2023 08:48:15 GMT

문제

풀이

def solution(score):
    answer = []
    avgList=[]

    for i in score:
        avgList.append(sum(i)/len(i))

    sort_avgList= sorted(avgList, reverse=True)

    for i in avgList:
        answer.append(sort_avgList.index(i)+1)

    return answer

주의사항

1) 원래 점수를 list에 기록한다
2) list를 점수 순위대로 sort한 new_list를 만든다
3) new_list에서 list의 값을 찾고 인덱스 값을 넣는다

프로그래머스 : 영어가싫어요

Thu, 02 Feb 2023 02:00:52 GMT

문제

코드

def solution(numbers):
    answer = 0
    eng = {'zero' : 0, 'one':1, 'two':2, 'three' : 3, 'four':4, 'five':5,'six' : 6, 'seven' : 7, 'eight':8,'nine':9}

    for k, v in eng.items():
        numbers = numbers.replace(k, str(v))

    answer = int(numbers)
    return answer

주의

dict 형태로 0부터 9까지 key,value를 맞춰준다
dict.items() : Key, Value 쌍 얻는 함수 (k,v 모두 출력)
for문을 돌면서 k,v 를 가져온 뒤 numbers에 있는 k를 v(str형태로 변형) 로 바꿔준다

코드업2001 최소대금

Tue, 27 Dec 2022 01:16:57 GMT

문제

입력예시

출력예시

987.8

코드

'''
로직
1. 입력 5행 → 파스타 3개 / 쥬스 2개 로 저장
2. 파스타 및 쥬스 정렬 (sort)
3. 파스타[0] + 쥬스[0] + 10%의 가격
'''

pasta=[]
juice=[]

for i in range(3):
    a = int(input())
    pasta.append(a)

for i in range(2):
    a = int(input())
    juice.append(a)

pasta.sort()
juice.sort()

pretotal = pasta[0]+juice[0]
total = pretotal + 0.1*pretotal

print(total)

코드업6098 성실한개미

Tue, 27 Dec 2022 01:15:41 GMT

문제

입력예시

1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 0 0 1
1 0 0 1 1 1 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 1 0 1 0 1
1 0 0 0 0 1 2 1 0 1
1 0 0 0 0 1 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

출력예시

1 1 1 1 1 1 1 1 1 1
1 9 9 1 0 0 0 0 0 1
1 0 9 1 1 1 0 0 0 1
1 0 9 9 9 9 9 1 0 1
1 0 0 0 0 0 9 1 0 1
1 0 0 0 0 1 9 1 0 1
1 0 0 0 0 1 9 1 0 1
1 0 0 0 0 1 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

코드

graph=[]
for i in range(10):
    a = list(map(int,input().split()))
    graph.append(a)

x=1
y=1

while(True):

    if graph[x][y+1]==2 :
        #print('x0',x,'y',y)
        graph[x][y]=9
        graph[x][y+1]=9
        break
    elif graph[x][y+1]==1 and graph[x+1][y]==2:
        graph[x][y]=9
        graph[x+1][y]=9
        break
    elif graph[x][y+1]==1 and graph[x+1][y]==0:
        #print('x2',x,'y',y)
        graph[x][y]=9
        x +=1
    elif graph[x][y+1]==0:
        #print('x1',x,'y',y)
        graph[x][y]=9
        y += 1
    else:
        #print('x3',x,'y',y)
        graph[x][y]=9
        break

for i in range(10):
    for j in range(10):
        print(graph[i][j], end=' ')
    print()

주의

if문의 향연,,,
while(True)를 사용할 때는 break를 잘 걸어주어야 한다 안그러면 시간초과 어쩌고가 나더라고?

코드업6097 설탕과자뽑기

Tue, 27 Dec 2022 01:12:30 GMT

문제

입력예시

출력예시

코드

#h세로 w가로
h,w = map(int,input().split())
#count막대개수
count = int(input())

graph=[ [0]* w for _ in range(h) ]
#print(graph)

for i in range(count):
    l,d,x,y = map(int,input().split())
    for j in range(l):
        if d==0:
            #print('j',j,'y',y+j-1,'x',x-1)
            graph[x-1][y+j-1]=1
        else:
            #print('j',j,'y',y-1,'x',x-j-1)
            graph[x+j-1][y-1]=1

for i in range(h):
    for j in range(w):
        print(graph[i][j] , end=' ')
    print()

주의

x가 가로 y가 세로 이다
어디서 j를 넣어줘야하는지 자리를 잘 확인해야한다

코드업6096 바둑알 십자 뒤집기

Tue, 27 Dec 2022 01:06:52 GMT

문제

입력예시

0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
2
10 10
12 12

출력예시

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

코드

graph= []
for i in range(19):
    graph.append(list(map(int,input().split())))

count = int(input())

where=[]    
for i in range(count):
  a = list(map(int,input().split()))
  where.append(a)

for i in range(count):
    n,m = where[i]
    for j in range(19):
        if graph[j][m-1] == 1: 
            graph[j][m-1] = 0 
        else:
            graph[j][m-1] = 1

        if graph[n-1][j] == 1:
            graph[n-1][j]=0
        else:
            graph[n-1][j]=1

for i in range(19):
    for j in range(19):
        print(graph[i][j], end=' ')
    print()

주의

x가 세로 y가 가로 이다
어디서 -1 해줘야하는지 자리수를 잘 체크해줘야한다

코드업6095 바둑판에 흰돌놓기

Tue, 27 Dec 2022 01:03:03 GMT

문제

입력예시

출력예시

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

코드

count = int(input())
where=[]
graph=[[0] * 19 for _ in range(19)]
# print(graph)

for i in range(count):
    a,b = map(int,input().split())
    where.append((a,b))
# print(where)

for i in range(count):
    n,m=where[i]
    graph[n-1][m-1] = 1

for i in range (19):
    for j in range(19):
        print(graph[i][j], end=' ')
    print()

주의사항

팀결성 : 그래프

Mon, 19 Dec 2022 23:57:44 GMT

로직

같은 팀 여부 확인

find 로직으로 각 학생의 루트노드 찾기
- 루트노드가 아니라면 , 재귀적호출 ㄱㄱ
루트노드가 같으면 YES , 아니면 NO 출력

팀합치기 = union로직

a,b를 각 a,b의 루트노드로 변수 할당 (find로직)
if a

학생의 부모리스트 (→루트노드가 될) parent=[]

부모리스트를 1...N(i) 으로 초기화

N,M 입력받기 : N학생의수(=팀번호) , M연산횟수

M (for문) 번 돌면서

k,a,b 입력받기

if k 값이 0이면 → 팀합치기

1이면 → 같은 팀 여부 확인

# 팀찾기 (루트노드 찾기) def team_find(x,parent): if parent[x] != x: parent[x] = team_find(parent[x],parent) return parent[x] # 팀합치기 def team_union(a,b,parent): a = team_find(a,parent) b = team_find(b,parent) if a
주의사항 find 로직 진행 시 → 재귀함수 호출 할 때 매개변수로 parent[x]를 줘야함 → x를 그냥 주면 무한 재귀함수에 빠져벌임,, 부모 리스트를 자기자신으로 초기화 하기전 (i) → [0]*(n+1)로 초기화 해주는 과정이 꼭 필요하다 부모 리스트를 자기자신으로 초기화 할 때 0~(n+1) 까지 해주어야한다 → 문제에 제시되어있음

전보 : 최단경로 Tue, 13 Dec 2022 11:41:30 GMT 로직 (플로이드워셜 이용 ) n,m,c 입력받기 : 도시개수 , 통로개수 , 도시 graph=[] 무한으로 초기화 a,b가 같으면 0으로 초기화 x,y,z 입력받고 -> garph에 넣어주기 알고리즘 수행 if graph[c][i] < INF and graph[c][i]!=0 : count += 1 count : 도시 c 와 연결된 도시의 수 distance : 도시 c 와 연결된 도시 중 가장 긴 거리 결과 출력 코드 # 1 n,m,c = map(int,input().split()) # 2 INF = int(1e9) graph=[] graph = [[INF] * (n+1) for _ in range(n+1)] for a in range(n+1): for b in range(n+1): if a==b : graph[a][b]=0 graph[b][a]=0 for i in range(m): x,y,z= map(int,input().split()) graph[x][y] = z # 3 count = 0 distance =0 for b in range(n+1): if graph[c][b] < INF and graph[c][b]!= 0 : # count : 연결된 도시의 수 (+1) count+=1 # distance : 가장 먼 거리 출력하기 distance = max(distance, graph[c][b]) print(count,distance) 주의사항 플로이드 워셜 알고리즘을 이용했다 N이 1000을 넘어가기에 시간복잡도에서 걸릴 수도 있다ㅜ count , distance 변수의 의미를 잘 보고 로직을 이용한다 미래도시 : 최단경로 Tue, 13 Dec 2022 10:24:57 GMT 로직 (플로이드 워셜) N,M : 회사수 , 경로수 입력받기 graph=[] 2차원리스트 초기화 자기자신 -> 자기자신 0으로 초기화 a,b 입력받으면 1로 초기화 x,k : 거쳐갈노드 , 최종목적지노드 입력받기 플로이드워셜 알고리즘 수행 결과 출력 코드 import sys #input = sys.stdin.readline() # 1 n,m = map(int,input().split()) # 2 INF = int(1e9) graph=[[INF]* (n+1) for _ in range(n+1)] for a in range(1,n+1): for b in range(1,n+1): if a==b : graph[a][b]=0 for i in range (m): a,b = map(int,(input().split())) graph[a][b]=1 graph[b][a]=1 # 3 잊지않고 입력받아주기 x,k = map(int,input().split()) # 4 for k in range(1,n+1): for a in range(1,n+1): for b in range(1,n+1): graph[a][b]= min(graph[a][b], graph[a][k]+graph[k][b]) # 거리에 대한 변수를 따로 만들어줘야 한다! distance = graph[1][k] + graph[k][x] # 5 if distance >= INF: print(-1) else: print(distance) 주의사항 플로이드 워셜 알고리즘을 이용 INF는int(1e9) 를 이용하여 무한으로 정의해주어야함 distance 거리에 대한 변수를 따로 만들어줘야한다! 바닥공사 : 다이나믹 프로그래밍 Sun, 11 Dec 2022 09:36:32 GMT << 점화식 >> d[i] = d[i-1] + d[i-2]*2 i-1 : 2x1 하나의 경우만 있음 i-2 : 2x2 / 1x2(2) -> 2개의 경우가 있음 로직 N 입력받기 크기가 1001 인 d를 0으로 초기화 d[1] = 1 d[2] = 3 for i in range(3,N+1): 점화식사용 코드 N = int(input()) d = [0] * 1001 d[1]=1 d[2]=3 for i in range(3,N+1): d[i] = (d[i-1] + d[i-2]*2)%796796 print(d[N]) 주의할점 점화식을 떠올리는 것이 쉽지 않다,,, 그림을 그리면서 해볼 것 ! for문 시작점이 3인 것을 주의하자 ! 1과 2는 이미 정의해주었기 때문 d[0]은 0으로 초기화해둔 그대로 둔다