파이썬

[python] 백준 - 11729. 하노이 탑 이동 순서

🤔문제 해결 S2 | 재귀 하노이탑 - 1번에 위치한 원반을 고대로 3번으로 옮기는 것!! 재귀를 배울 때 단골 문제 💻소스 코드 def hanoi(n, start, end, sub): if n == 1: # print(f'{start}=>{end}') answer.append([start, end]) return hanoi(n - 1, start, sub, end) # print(f'{start}=>{end}') answer.append([start, end]) hanoi(n - 1, sub, end, start) N = int(input()) answer = [] hanoi(N, 1, 3, 2) # 출력 print(len(answer)) for i in answer: print(*i) 📕문제 확인 출..

[python] 백준 - 1182. 부분수열의 합

🤔문제 해결 S2 | 완전탐색(백트래킹) 문제를 잘 이해하지 못해서 많이 헷갈렸다. 그냥 쉽게 설명해서 주어진 숫자들 중 n개를 뽑아서 더한 값이 S와 같은 조합이 몇개인지 구하라는 말 파이썬에서는 쉽게 콤비네이션을 쓰면 된다. 문제 유형에 백트래킹이 있으므로 백트래킹을 연습하고 싶으면 백트래킹을 써도 좋다. 💻소스 코드 from itertools import combinations N, S = map(int, input().split()) numbers = list(map(int, input().split())) answer = 0 for i in range(1, N + 1): for combi in combinations(numbers, i): # print(combi) if sum(combi) ==..

플로이드 와샬(Floyd Warshall)

📔 플로이드 와샬(Floyd Warshall) 란 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. ( 출처: 위키백과 ) 모든 정점에서 모든 정점으로의 최단 경로를 구하는 것! 거쳐가는 정점을 기준으로 구한다. 다이나믹 프로그래밍 기법을 이용 다익스트라의 경우 한 정점에서 모든 정점까지 의 최단 경로 반복문이 3개이므로 시간복잡도는 O(N^3) 이다. 하지만 코드는 매우 간단하다. 📔 플..

[python] 백준 - 11055. 가장 큰 증가 부분 수열

🤔문제 해결 S2 | 다이나믹프로그래밍 역시 이런 문제는 DP문제이다. dp 리스트를 만든다.(1차원, 인풋값으로 받은 수열과 똑같은 값으로 만든다.) 수열에서 자신보다 앞 쪽에 있는 값 중에서 자신보다 작은 값의 인덱스를 찾는다. 해당 인덱스의 dp값중 가장 큰 값과 자신의 값을 더해 dp를 다시 채운다. dp에서 max값을 출력 💻소스 코드 N = int(input()) numbers = list(map(int, input().split())) dp = numbers[:] dp[0] = numbers[0] # print(f'최초DP: {dp}') for i in range(1, N): for j in range(i): if numbers[j] < numbers[i]: dp[i] = max(dp[i],..

에라토스테네스의 체(Sieve Of Eratosthenes)

📔 에라토스테네스의 체(Sieve Of Eratosthenes) 란 대표적인 소수 판별 알고리즘 ( 소수: Prime Number ) 한꺼번에 많은 숫자의 소수를 판별할 때 사용 숫자 한개의 소수를 판별하는 기본 소수 판별 알고리즘의 시간복잡도는 O(N) 하지만 수학적으로 접근해서 시간복잡도를 O(N^(1/2)) 까지 줄일 수 있다. 에라토스테네스의 체를 사용하면 시간복잡도는 O(n log log n) 📔 에라토스테네스의 체(Sieve Of Eratosthenes) 구현 자연수 50까지의 숫자 중에서 소수를 구한다고 생각해보자. 기본 알고리즘을 사용할 경우 O(N*N^(1/2)) 의 시간복잡도가 생긴다. 에라토스테네스의 체를 이용하여 구해보자. 먼저 51개의 값이 1(True)인 리스트를 만든다. for..

[python] 백준 - 11722. 가장 긴 감소하는 부분 수열

🤔문제 해결 S2 | DP 참고(비슷한 유형) : deok2kim.tistory.com/173 [python] 백준 - 11055. 가장 큰 증가 부분 수열 🤔문제 해결 S2 | 다이나믹프로그래밍 역시 이런 문제는 DP문제이다. dp 리스트를 만든다.(1차원, 인풋값으로 받은 수열과 똑같은 값으로 만든다.) 수열에서 자신보다 앞 쪽에 있는 값 중에서 자신 deok2kim.tistory.com numbers에는 수열이 들어있다. dp라는 1차원 리스트를 만든다. (1초 초기화, 감소하는 부분 수열의 길이가 들어갈 것이다.) 1로 초기화한 이유는 혼자만 가능할 때는 길이가 1이므로 numbers를 하나씩 돌면서 자신보다 앞쪽의 숫자와 비교한다. 자신보다 앞쪽의 숫자가 클 경우 - 나와 그 숫자는 감소하는 부..