분류 전체보기

[python] 백준 - 2133. 타일 채우기

🤔문제 해결 S2 | DP 이런문제는 역시 단골 DP문제 일단 손으로 구해봤다. i == 0, 2, 4, 6 ( 홀수 일 경우는 제외함 ) 경우의수 == 1, 3, 11, 41 점화식 dp[i] = dp[i-2] * 3 + (dp[2] ~ dp[i-2]) * 2 + 2 i경우의수 = 이전의 경우의 수 * 3 + 이전의 경우의 수 들 * 2 + i만 만드는 경우 💻소스 코드 N = int(input()) if N % 2: print(0) else: dp = [0] * (N + 1) dp[0], dp[2] = 1, 3 for i in range(4, N + 1, 2): dp[i] = dp[i - 2] * 3 + 2 for j in range(2, i - 2, 2): dp[i] += dp[j] * 2 prin..

힙 정렬(heap sort)

📔 힙 정렬(heap sort) 이란 힙트리구조를 이용하여 정렬하는 알고리즘 힙트리: 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 힙정렬을 하기 위해서는 먼저 힙 구조를 가지도록 만들어야 한다. 히피파이 알고리즘을 통해 힙구조로 만든다. 모든 정점에 대해서 히피파이를 수행하므로 n x logn 의 시간복잡도를 가진다. 사실상 모든 정점이 아니라 절반의 정점만 해도 가능하다 n/2 x logn => (n/2이 logn 보다 크다고 가정할 때) => 결국 O(n) 의 시간복잡도를 가진다. 📔 힙 정렬(heap sort) 구현 # (최대)힙 구조 만들기 def heapify(): for i in range(1, N): c = i while c > 0: root = (c - 1..

[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) 📕문제 확인 출..

위상 정렬(topology sort)

📔 위상 정렬(topology sort) 이란 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 어떤 일을 하는 순서를 찾는 알고리즘 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 선행 조건이 반드시 수행되어야 다음을 진행할 수 있다! 위의 그림을 보면 아비터트리뷰널을 짓기 위해서는 템플러아카이브와 스타게이트가 둘다 있어야 한다. 시간복잡도: O(V+E) | V-노드의 수, E-간선의 수 📔 위상 정렬(topology sort) 구현 큐와 스택을 사용할 수 있다. 일반적으로 큐를 사용 진입 차수( 현재 노드에 들어올 수 있는 노드의 수 ) 가 0인 정점을 큐에 삽입 (그림의 사이버네틱스코어) 큐에서 원소를 꺼내 연결..

[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) 이다. 하지만 코드는 매우 간단하다. 📔 플..